Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups

作者：Li, Jian^*; Pardalos, Panos M.; Sun, Hao; Pei, Jun; Zhang, Yong

来源：Expert Systems with Applications, 2015, 42(7): 3551-3561.

DOI：10.1016/j.eswa.2014.12.004

• Vehicle routing problem
• Simultaneous deliveries and pickups
• Multi-depot
• Iterated local search
• Adaptive neighborhood selection

Although the multi-depot vehicle routing problem with simultaneous deliveries and pickups (MDVRPSDP) is often encountered in real-life scenarios of transportation logistics, it has received little attention so far. Particularly, no papers have ever used metaheuristics to solve it. In this paper a metaheuristic based on iterated local search is developed for MDVRPSDP. In order to strengthen the search, an adaptive neighborhood selection mechanism is embedded into the improvement steps and the perturbation steps of iterated local search, respectively. To diversify the search, new perturbation operators are proposed. Computational results indicate that the proposed approach outperforms the previous methods for MDVRPSDP. Moreover, when applied to VRPSDP benchmarks, the results are better than those obtained by large neighborhood search, particle swarm optimization, and ant colony optimization approach, respectively.

• 出版日期2015-5-1
• 单位南京农业大学; 合肥工业大学; 东南大学; 青岛大学