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.

Kritik tesislerin korunması son yirmi yılda giderek daha fazla ilgi görmektedir. Kritik tesisler arasında köprüler, demiryolları, enerji santralleri, hastaneler ve ulaşım merkezleri gibi fiziksel varlıklar bulunmaktadır. Bu çalışmada, bir taşıt yönlendirme bağlamında en kritik depoların belirlenmesi için iki seviyeli bir optimizasyon problemi sunuyoruz. Sorun, bir yönlendirme ağında maksimum aksamaya yol açmayı amaçlayan bir rakip ajanın (saldırgan) perspektifinden bir saldırgan savunma oyuncusu oyunu (Stackelberg oyunu) olarak modellenmiştir. Bu soruna r-interdiction seçici çoklu depo araç yönlendirme sorunu (RI-SMDVRP) diyoruz. Saldırgan, üst düzey problemde (ULP), kesin olarak müdahale etmek için r deposunu seçen karar vericidir. Savunucu, saldırı sonrasında araç rotalarını optimize eden alt seviye probleminde (LLP) karar vericidir. Savunucu, kalan depoları kullanarak veya bir üçüncü taraf lojistik hizmet sağlayıcısına dış kaynak kullanarak tüm müşteri taleplerini karşılamalıdır. ULP, kesintilerin kardinalitesi dokuz depodan beşi geçmediğinde geçerli olan kapsamlı numaralandırma ile çözülür. LLP için seçici çoklu depo VRP'ye uyarlanmış bir tabu arama buluşsal yöntemi uygularız. Sonuçlarımız, standart MDVRP test örneklerinden sentetik olarak oluşturulan bir dizi RI-SMDVRP örneği üzerinde elde edilir. ULP, kesintilerin kardinalitesi dokuz depodan beşi geçmediğinde geçerli olan kapsamlı numaralandırma ile çözülür. LLP için seçici çoklu depo VRP'ye uyarlanmış bir tabu arama buluşsal yöntemi uygularız. Sonuçlarımız, standart MDVRP test örneklerinden sentetik olarak oluşturulan bir dizi RI-SMDVRP örneği üzerinde elde edilir. ULP, kesintilerin kardinalitesi dokuz depodan beşi geçmediğinde geçerli olan kapsamlı numaralandırma ile çözülür. LLP için seçici çoklu depo VRP'ye uyarlanmış bir tabu arama buluşsal yöntemi uygularız. Sonuçlarımız, standart MDVRP test örneklerinden sentetik olarak oluşturulan bir dizi RI-SMDVRP örneği üzerinde elde edilir.