An Improved Benders Decomposition Algorithm for an Arc Interdiction Vehicle Routing Problem

Amirsaman Kheirkhah | Hamidreza Navidi | Masume Messi Bidgoli

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=31829
Date :  2016/04/05
Publish in :    IEEE Transactions on Engineering Management
DOI :  https://doi.org/10.1109/tem.2016.2542849
Link :  http://ieeexplore.ieee.org
Keywords :Benders, Algorithm, Vehicle, Routing

Abstract :

---

The vehicle routing problem is one of the most important and well-known issues that is considered by researchers in recent years. There are some vital or expensive shipments, such as fuel shipments, vehicles carryingmoney, prisoner transfer vehicles, and so on, that are being assassinated by some interdictors. The problem of routing in these kinds of shipments ismore complicated in comparison with the classical routing problems. In this paper, routing of these special kinds of shipments is integrated for the first time into the network interdiction concepts. For this purpose, a bilevel programming model is proposed and a benders decomposition algorithm is developed for small-size problems. Two supervalid inequalities are proposed to improve the efficiency of this algorithm. Also, two bilevel metaheuristics are suggested to solve this Stachelberg interdictor-evader game for large-size problems. To show the applicability and efficiency of the solution methods, some randomly generated and also benchmark instances are used. The computational results show that the two proposed metaheuristic algorithms could be effective for solving these problems.