A bi-level model and memetic algorithm for arc interdiction location-routing problem

This paper investigates arc interdiction location-routing problem (AI-LRP), a new variant of the classical LRP. There are two decision-makers with dissimilar perceptions of the problem, making efforts to achieve their contradictory yet interconnected targets. While the interdictor develops a plan to disrupt products flow in a distribution network, the distributor strives to mitigate the effects of disruption and to deliver goods to customers at minimal risk and cost in the interdicted network. The impacts they have on one another are formulated as a bi-level programming model, with the interdictor taking decisions at the upper level. This problem has wide applications in reality, including distribution of particular goods such as money, precious metals, hazardous materials, and even prisoners that may need security measures. To solve the problem, an efficient memetic algorithm (EMA) with a dynamic local search is proposed. The efficiency of the developed EMA is demonstrated by comparing its performance with a few LRP algorithms published in the literature as well as with a commercial solver. A cost-benefit analysis, along with a case study in maritime transportation, is conducted to provide managerial insights. The results from numerical experiments show that when more budgets are allocated to interdiction and the distributor estimates the interdictor's parameters with less accuracy, AI-LRP is capable of formulating close-to-real-life cases under information asymmetry more effectively.