A Memetic Algorithm for Large-Scale Real-World Vehicle Routing Problems with Simultaneous Pickup and Delivery with Time Windows
Pages 78 - 92
Abstract
The vehicle routing problem with simultaneous pickup and delivery with time windows (VRPSPDTW) is an important variant of the vehicle routing problem which has received considerable attention among researchers in the last decade. The vast majority of solution methodologies for the VRPSPDTW have been applied to synthetic problem instances that bear little resemblance to routing problems found in the real world. Recently, 20 large-scale VRPSPDTW instances based on real customer data from the transportation company known as JD Logistics became publicly available as a new benchmark VRPSPDTW problem set.
In this paper, a memetic algorithm (MA), referred to as MA-BCRCD, is proposed for use on these real-world instances. The MA prioritizes efficient search and utilizes a crossover method which is shown to be more effective than that of the previous MA approach (known as MATE) applied to this set. MA-BCRCD finds new best known solutions for all 20 instances. It also performs better on average for all instances in comparison to the performance of MATE. The results and analysis provided in this study suggest that further improvements on this problem set are possible both in terms of solution quality and search efficiency.
References
[1]
Alvarenga GB, Mateus GR, and De Tomi G A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows Comput. Oper. Res. 2007 34 6 1561-1584
[2]
Angelelli E and Mansini R Klose A, Speranza MG, and Van Wassenhove LN The vehicle routing problem with time windows and simultaneous pick-up and delivery Quantitative Approaches to Distribution Logistics and Supply Chain Management 2002 Heidelberg Springer 249-267
[3]
Baker BM and Ayechew M A genetic algorithm for the vehicle routing problem Comput. Oper. Res. 2003 30 5 787-800
[4]
Battarra, M., Cordeau, J.F., Iori, M.: Pickup-and-delivery problems for goods transportation, chapter 6. In: Vehicle Routing: Problems, Methods, and Applications, 2nd edn., pp. 161–191. SIAM (2014)
[5]
Braekers K, Ramaekers K, and Van Nieuwenhuyse I The vehicle routing problem: state of the art classification and review Comput. Ind. Eng. 2016 99 300-313
[6]
Desaulniers, G., Madsen, O.B., Ropke, S.: The vehicle routing problem with time windows, chapter 5. In: Vehicle Routing: Problems, Methods, and Applications, 2nd edn., pp. 119–159. SIAM (2014)
[7]
Dethloff J Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up: Fahrzeugeinsatzplanung und redistribution: Tourenplanung mit simultaner auslieferung und rückholung OR-Spektrum 2001 23 79-96
[8]
Hof J and Schneider M An adaptive large neighborhood search with path relinking for a class of vehicle-routing problems with simultaneous pickup and delivery Networks 2019 74 3 207-250
[9]
Kassem S and Chen M Solving reverse logistics vehicle routing problems with time windows Int. J. Adv. Manuf. Technol. 2013 68 1–4 57-68
[10]
Koç Ç, Laporte G, and Tükenmez İ A review of vehicle routing with simultaneous pickup and delivery Comput. Oper. Res. 2020 122
[11]
Liu, F., et al.: A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window. J. Heuristics 1–43 (2023)
[12]
Liu S, Tang K, and Yao X Memetic search for vehicle routing with simultaneous pickup-delivery and time windows Swarm Evol. Comput. 2021 66
[13]
Liu Z et al. A new hybrid algorithm for vehicle routing optimization Sustainability 2023 15 14 10982
[14]
Lu Y, Benlic U, and Wu Q An effective memetic algorithm for the generalized bike-sharing rebalancing problem Eng. Appl. Artif. Intell. 2020 95
[15]
Mingyong L and Erbao C An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows Eng. Appl. Artif. Intell. 2010 23 2 188-195
[16]
Ombuki B, Ross BJ, and Hanshar F Multi-objective genetic algorithms for vehicle routing problem with time windows Appl. Intell. 2006 24 17-30
[17]
Prins C A simple and effective evolutionary algorithm for the vehicle routing problem Comput. Oper. Res. 2004 31 12 1985-2002
[18]
Ropke S and Pisinger D An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows Transp. Sci. 2006 40 4 455-472
[19]
Shi Y, Zhou Y, Boudouh T, and Grunder O A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window Eng. Appl. Artif. Intell. 2020 95
[20]
Solomon MM Algorithms for the vehicle routing and scheduling problems with time window constraints Oper. Res. 1987 35 2 254-265
[21]
Wang C, Mu D, Zhao F, and Sutherland JW A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows Comput. Ind. Eng. 2015 83 111-122
[22]
Wang HF and Chen YY A genetic algorithm for the simultaneous delivery and pickup problems with time window Comput. Ind. Eng. 2012 62 1 84-95
[23]
Wu, H., Gao, Y.: An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup-delivery and time window. Appl. Soft Comput. 110203 (2023)
Recommendations
A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls
AbstractThe electric vehicle routing problem (EVRP) has been studied increasingly because of environmental concerns. However, existing studies on the EVRP mainly focus on time windows and sole linehaul customers, which might not be practical as backhaul ...
Highlights- Propose an electric vehicle routing problem with time windows and mixed backhauls.
- Design a new diversity-enhanced memetic algorithm to solve the problem.
- Conduct experiments with 54 new instances, two classical benchmarks, and a ...
A memetic particle swarm optimization algorithm for multimodal optimization problems
Recently, multimodal optimization problems (MMOPs) have gained a lot of attention from the evolutionary algorithm (EA) community since many real-world applications are MMOPs and may require EAs to present multiple optimal solutions. In this paper, a ...
Region based memetic algorithm for real-parameter optimisation
Memetic algorithms with an appropriate trade-off between the exploration and exploitation can obtain very good results in continuous optimisation. That implies the evolutionary algorithm should be focused in exploring the search space while the local ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jun 2024
403 pages
ISBN:978-3-031-62911-2
DOI:10.1007/978-3-031-62912-9
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 June 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025