The r-Depot Interdiction Vehicle Routing Problem with Demand Outsourcing
Deniz Aksen  1, *@  , Mir Ehsan Hesam Sadati  2@  , Necati Aras  3@  
1 : Koç University  (KU)  -  Website
College of Administrative Sciences and Economics Rumelifeneri Sarıyer / İSTANBUL -  Turkey
2 : Koç University  (KU)  -  Website
Graduate School of Sciences and Engineering, Rumelifeneri Yolu 34450 Sarıyer Istanbul Turkey -  Turkey
3 : Department of Industrial Engineering, Bogazici University  -  Website
Boğaziçi University Department of Industrial Engineering 34342, Bebek, Istanbul, Turkey -  Turkey
* : Corresponding author

The protection of critical facilities in supply chain networks increasingly attracts attention in the past 15 years. Critical facilities involve physical assets such as bridges, railways, terminals, power plants, hospitals, police stations, and transportation hubs among others. In this study, we introduce a bilevel optimization problem for the determination of the most critical depots in a vehicle routing network. The problem is first modelled as an attacker-defender game (Stackelberg game) from the perspective of an adversary agent (the attacker) who aims to inflict the maximum disruption on a delivery or collection type routing network. We refer to this problem as the r-depot interdiction vehicle routing problem (RDI-VRP) with demand outsourcing. The attacker is the decision maker in the upper level problem (ULP) who chooses r depots to interdict with certainty. The defender is the decision maker in the lower level problem (LLP) who re-optimizes the vehicle routes in the wake of the attack. The defender has to satisfy all customer demand either using the remaining depots or through outsourcing to a third party service provider. We solve the ULP through exhaustive enumeration which is viable when r, namely the cardinality of interdictions of the attacker, does not exceed five among 10 candidate depots. For the LLP we experiment with a savings-based heuristic and a nearest neighbourhood insertion heuristic adapted to the selective multi-depot VRP by so-called 1-node and 2-node marginal cost analyses. Our results are obtained on a set of RDI-VRP instances synthetically constructed from standard MDVRP test instances.

Online user: 1 RSS Feed