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

• Published in: Computers & industrial engineering 2024-03, Vol.189, p.109942, Article 109942
• Main Authors: Liu, Wenjie, Qiu, Jing, Deng, Jing, Zheng, Nanxi, Chang, Xiangyun, Liu, Yun
• Format: Article
• Language: English
• Subjects: Multi-depot vehicle routing problem with simultaneous delivery and pickup; Neighbourhood structure; Route-selection strategy; Time limit; Variable neighbourhood search
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2024.109942

•A multi-depot vehicle routing problem with simultaneous delivery & pickup and time limit.•A variable neighborhood search algorithm embedded a novel perturbation mechanism.•High-quality and low- CPU time results produced by our proposed algorithm. 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 well-known MDVRPSDPTL benchmark instances.