The r-interdiction selective multi-depot vehicle routing problem

Abstract The protection of critical facilities has been attracting increasing attention in the past two decades. Critical facilities involve physical assets such as bridges, railways, power plants, hospitals, 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 context. The problem is modeled as an attacker–defender game (Stackelberg game) from the perspective of an adversary agent (the attacker) who aims to inflict maximum disruption on a routing network. We refer to this problem as the r-interdiction selective multi-depot vehicle routing problem (RI-SMDVRP). 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 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 logistics service provider. The ULP is solved through exhaustive enumeration, which is viable when the cardinality of interdictions does not exceed five among nine depots. For the LLP we implement a tabu search heuristic adapted to the selective multi-depot VRP. Our results are obtained on a set of RI-SMDVRP instances synthetically constructed from standard MDVRP test instances.