ISTANBUL KÜLTÜR UNIVERSITY
DEPARTMENT OF INDUSTRIAL ENGINEERING 

SEMINAR SERIES

A Trilevel r-Interdiction Multi-Depot Vehicle Routing Problem with Customer Selection

by
Mir Ehsan Hesam Sadati

PhD Candidate 
Koç University – Dept. of Industrial Engineering   
E-mail: msadati14@ku.edu.tr

Abstract: 

The protection of critical facilities in supply chain networks attracts increasing attention in the OR literature. Critical facilities involve physical assets such as bridges, railways, terminals, hospitals, power stations, and transportation hubs among others. In this study 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 routing 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 refer to this problem as the trilevel r-interdiction multi-depot vehicle routing problem with customer selection (3LRI-MDVRP). 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 the depot interdictions. All three levels of the problem have an identical objective function which is comprised of three cost components. (i) Operating or acquisition cost of the vehicles. (ii) Traveling cost incurred by the vehicles. (iii) Outsourcing cost due to unsatisfied demand of customers. The defender aspires to minimize this objective function while the attacker tries to maximize it. As a solution approach to this trilevel discrete optimization problem, we resort to smart exhaustive enumeration for the ULP and MLP. For the LLP we implement a hybrid metaheuristic method combining Variable Neighborhood Search and Tabu Search heuristic (VNS-TSH) techniques adapted to the selective multi-depot VRP. Our results are obtained on a set of 3LRI-MDVRP instances that are synthetically constructed from standard MDVRP test instances in the literature.

All interested are cordially invited.

Date    : October 17, 2018
Time   : 11:00 – 12:00
Room    : 3. Kat Çok Amaçlı Seminer Salonu