April 08, 2022, 9:00 AM - 9:20 AM
Weibo Lin, Huawei Cloud
This paper addresses the Split Delivery Vehicle Routing Problem (SDVRP), a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where the same customer can be served by multiple vehicles. Our approach is based on Iterated Local Search (ILS) and employs an improved perturbation mechanism and a new neighborhood structure called SD-Swap∗. By implementing a Lazy Static Move Descriptor (LSMD) mechanism, the proposed algorithm is quite efficient.