Title:   Vehicle Routing Problem with Interdiction

We study the role of interdiction in the Vehicle Routing Problem (VRP), which naturally arises in humanitarian logistics and military applications. We assume that in a general network, each edge has a chance to be interdicted. When interdiction happens, the vehicle traveling on this edge is lost, thus unable to continue the trip. Our objective is to minimize the total travel cost or to maximize the demand fulfillment, depending on the supply quantity. This problem is called the Vehicle Routing Problem with Interdiction (VRPI). We first prove that the proposed VRPI problems are NP-hard. Then we show some key analytical properties pertaining to the optimal solutions of these problems. Importantly, the original Dror and Trudeau's property does not hold for these problems. However, a generalization of the Dror and Trudeau's property holds. We also present efficient heuristic algorithms to solve these problems. Finally, our numerical studies demonstrate the effectiveness of the proposed models and algorithms.