Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/23888
Title: | Vehicle Routing Problem with Interdiction |
Authors: | Xu, Michael |
Advisor: | Huang, Kai |
Department: | Computational Engineering and Science |
Keywords: | Vehicle Routing;Interdiction;Split Delivery;Mixed Integer Programming |
Publication Date: | 2017 |
Abstract: | In this thesis, 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 arc has a chance to be interdicted. When interdiction happens, the vehicle traveling on this arc is lost or blocked and thus unable to continue the trip. We model the occurrence of interdiction as a given probability and consider the multi-period expected delivery. 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. Most importantly, we examine Dror and Trudeau's property applied to our problem setting. Finally, we present efficient heuristic algorithms to solve these problems and show the effectiveness through numerical studies. |
URI: | http://hdl.handle.net/11375/23888 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Xu_Michael_Z_201704_master.pdf.pdf | 639.63 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.