文献类型：期刊文献

英文题名：Variable neighbourhood search embedded perturbation mechanism for multi-depot vehicle routing problem with simultaneous delivery & pickup, and time limit

作者：Liu, Wenjie[1];Qiu, Jing[1];Deng, Jing[1];Zheng, Nanxi[1];Chang, Xiangyun[2];Liu, Yun[1]

机构：[1]Nanjing Univ Aeronaut & Astronaut, Coll Econ & Management, Nanjing 211106, Peoples R China;[2]East China Univ Sci & Technol, Dept Management Sci & Engn, Shanghai 200237, Peoples R China

年份：2024

卷号：189

外文期刊名：COMPUTERS & INDUSTRIAL ENGINEERING

收录：;EI(收录号：20240715544784);WOS:【SCI-EXPANDED(收录号:WOS:001179351600001)】；

基金：This work is supported by grants from the National Natural Science Fund of China (71871117 and 72074078) and the Royal Society of UK (IEC\NSFC\201348) .

语种：英文

外文关键词：Variable neighbourhood search; Route-selection strategy; Multi-depot vehicle routing problem with; simultaneous delivery and pickup; Time limit; Neighbourhood structure

摘要：Given its complex combinatorial features, the multi-depot vehicle routing problem with simultaneous delivery & pickup, and time limits (MDVRPSDPTL) is a well-known and challenging real-world problem faced by manufacturing enterprises. Vehicles depart from different depots to simultaneously deliver new products and pick up packaging or used products within a prescribed time limit. In this study, we developed a mixed-integer linear programming model to assign customers to depots and determine a group of vehicle routes to minimise total travel cost. A variable neighbourhood search algorithm embedded with a novel perturbation mechanism (including a route-selection strategy and a retention strategy for the current best solution) was proposed to solve the model efficiently. The perturbation mechanism helps the algorithm quickly escape local optima to improve computational precision and reduce computation time. The numerical results indicate that the proposed algorithm outperforms existing state-of-the-art algorithms in terms of solution quality and computation time for wellknown MDVRPSDPTL benchmark instances.