A variable neighborhood search for the last-mile delivery problem during major infectious disease outbreak

Jiang, Li; Zang, Xiaoning; Dong, Junfeng; Liang, Changyong; Mladenovic, Nenad

During major infectious disease outbreak, such as COVID-19, the goods and parcels supply and distribution for the isolated personnel has become a key issue worthy of attention. In this study, we propose a delivery problem that arises in the last-mile delivery during major infectious disease outbreak. The problem is to construct a Hamiltonian tour over a subset of candidate parking nodes, and each customer is assigned to the nearest parking node on the tour to pick up goods or parcels. The aim is to minimize the total cost, including the routing, allocation, and parking costs. We propose three models to formulate the problem, which are node-based, flow-based and bilevel programing formulations. Moreover, we develop a variable neighborhood search algorithm based on the ideas from the bilevel programing formulations to solve the problem. Finally, the proposed algorithm is tested on a set of randomly generated instances, and the results indicate the effectiveness of the proposed approach.