A Trilevel r-Interdiction Selective Multi-Depot Vehicle Routing Problem
Deniz Aksen  1, *@  , Mir Ehsan Hesam Sadati  2@  , Necati Aras  3@  
1 : Koç University  (KU)  -  Website
Rumelifeneri Yolu 34450 Sarıyer Istanbul Turkey -  Turkey
2 : Istanbul Kültür University  (İKÜ)  -  Website
İstanbul Kültür Üniversitesi Ataköy Yerleşkesi E5 Karayolu üzeri Bakırköy 34158 İstanbul -  Turkey
3 : Department of Industrial Engineering, Bogazici University  (BOUN)  -  Website
Boğaziçi University Department of Industrial Engineering 34342, Bebek, Istanbul, Turkey -  Turkey
* : Corresponding author

We introduce a trilevel optimization problem for the determination of the most critical depots in a multi-depot vehicle routing network. The problem is modelled as a ‘defender-attacker-defender' game from the perspective of the defender who needs to protect a limited number of depots on an existing network against interdiction by an adversary agent whom we designate as the attacker. The attacker's objective is to inflict the maximum disruption on this network by annihilating a certain number of unprotected depots beyond repair. We call this problem the trilevel r-interdiction selective multi-depot vehicle routing problem (3LRI-SMDVRP). The defender is the decision maker in the upper level problem (ULP) who decides which depots to protect. In the middle level problem (MLP), the attacker chooses r depots to interdict among the unprotected ones. Finally, in the lower level problem (LLP), the decision maker is again the defender who optimizes the vehicle routes and thereby selects which customers are to be served in the wake of depot interdictions. All three levels of the problem have an identical objective function comprised of three cost components. (i) Operating cost of the vehicles. (ii) Traveling cost. (iii) Outsourcing cost due to unsatisfied demand. The defender aspires to minimize this objective function while the attacker tries to maximize it. As a solution approach, we resort to smart exhaustive enumeration for the ULP and MLP. For the LLP we implement a hybrid method combining Variable Neighborhood Descent and Tabu Search heuristic techniques adapted to the SMDVRP.

  • Picture
Online user: 1 RSS Feed