Bilevel Memetic Search Approach to the Soft-Clustered Vehicle Routing Problem

Yangming Zhou
Yangming Zhou
[email protected]
https://orcid.org/0000-0002-4254-6517
Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China;Sino-US Global Logistics Institute, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China;Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China;
Search for more papers by this author
,
Yawen Kou
Yawen Kou
[email protected]
https://orcid.org/0000-0003-1670-4750
Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China;
Search for more papers by this author
,
MengChu Zhou
Corresponding Author
MengChu Zhou
[email protected]
https://orcid.org/0000-0002-5408-8752
Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China;Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, New Jersey 07102
Search for more papers by this author

Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China;Sino-US Global Logistics Institute, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China;Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China;

Search for more papers by this author

Yawen Kou

[email protected]

https://orcid.org/0000-0003-1670-4750

Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China;

Search for more papers by this author

MengChu Zhou

Corresponding Author

MengChu Zhou

[email protected]

https://orcid.org/0000-0002-5408-8752

Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China;Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, New Jersey 07102

Search for more papers by this author

Published Online:9 Dec 2022https://doi.org/10.1287/trsc.2022.1186

References

Absi N, Archetti C, Dauzère-Pérès S, Feillet D (2015) A two-phase iterative heuristic approach for the production routing problem. Transportation Sci. 49(4):784–795.Link, Google Scholar
Accorsi L, Vigo D (2021) A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Transportation Sci. 55(4):832–856.Link, Google Scholar
Balas E, Simonetti N (2001) Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. Comput. 13(1):56–75.Link, Google Scholar
Battarra M, Erdoğan G, Vigo D (2014) Exact algorithms for the clustered vehicle routing problem. Oper. Res. 62(1):58–71.Link, Google Scholar
Bektaş T, Erdoğan G, Røpke S (2011) Formulations and branch-and-cut algorithms for the generalized vehicle routing problem. Transportation Sci. 45(3):299–316.Link, Google Scholar
Cordeau J, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J. Comput. 18(4):433–443.Link, Google Scholar
Cosma O, Pop PC, Sitar CP (2022) A two-level based genetic algorithm for solving the soft-clustered vehicle routing problem. Carpathian J. Math. 38(1):117–128.Crossref, Google Scholar
Defryn C, Sörensen K (2017) A fast two-level variable neighborhood search for the clustered vehicle routing problem. Comput. Oper. Res. 83:78–94.Crossref, Google Scholar
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
Flood MM (1956) The traveling-salesman problem. Oper. Res. 4(1):61–75.Link, Google Scholar
Fu ZH, Hao JK (2015) Dynamic programming driven memetic search for the Steiner tree problem with revenues, budget, and hop constraints. INFORMS J. Comput. 27(2):221–237.Link, Google Scholar
Glover FW (1989) Tabu search, Part I. INFORMS J. Comput. 1(3):190–206.Link, Google Scholar
Golden BL, Wasil EA, Kelly JP, Chao IM (1998) The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets, and computational results. Crainic TG, Laporte G, eds. Fleet Management and Logistics (Springer, Boston), 33–56.Crossref, Google Scholar
Gusfield D (2002) Partition-distance: A problem and class of perfect graphs arising in clustering. Inform. Processing Lett. 82(3):159–164.Crossref, Google Scholar
Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1):106–130.Crossref, Google Scholar
Helsgaun K (2017) An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University, Department of Computer Science, Roskilde, Denmark.Google Scholar
Heßler K, Irnich S (2021) A branch-and-cut algorithm for the soft-clustered vehicle-routing problem. Discrete Appl. Math. 288:218–234.Crossref, Google Scholar
Hintsch T (2021) Large multiple neighborhood search for the soft-clustered vehicle-routing problem. Comput. Oper. Res. 129:105132.Crossref, Google Scholar
Hintsch T, Irnich S (2018) Large multiple neighborhood search for the clustered vehicle-routing problem. Eur. J. Oper. Res. 270(1):118–131.Crossref, Google Scholar
Hintsch T, Irnich S (2020) Exact solution of the soft-clustered vehicle-routing problem. Eur. J. Oper. Res. 280(1):164–178.Crossref, Google Scholar
Hintsch T, Irnich S, Kiilerich L (2021) Branch-price-and-cut for the soft-clustered capacitated arc-routing problem. Transportation Sci. 55(3):687–705.Link, Google Scholar
Hoogeboom M, Battarra M, Erdogan G, Vigo D (2016) Erratum: Exact algorithms for the clustered vehicle routing problem. Oper. Res. 64(2):456–457.Link, Google Scholar
Kuhn HW (2005) The Hungarian method for the assignment problem. Naval Res. Logist. 52(1):7–21.Crossref, Google Scholar
Lai X, Hao J, Fu Z, Yue D (2021) Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping. Eur. J. Oper. Res. 289(3):1067–1086.Crossref, Google Scholar
Li F, Golden B, Wasil E (2005) Very large-scale vehicle routing: New test problems, algorithms, and results. Comput. Oper. Res. 32(5):1165–1179.Crossref, Google Scholar
Li B, Wu G, He Y, Fan M, Pedrycz W (2022) An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem. IEEE/CAA J. Automatica Sinica 9(7):1115–1138.Crossref, Google Scholar
Li J, Zhou M, Sun Q, Dai X, Yu X (2015) Colored traveling salesman problem. IEEE Trans. on Cybernetics 45(11):2390–2401.Google Scholar
Lü Z, Hao JK (2010) A memetic algorithm for graph coloring. Eur. J. Oper. Res. 203(1):241–250.Crossref, Google Scholar
Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
Miller DL (1995) A matching based exact algorithm for capacitated vehicle routing problems. INFORMS J. Comput. 7(1):1–9.Link, Google Scholar
Porumbel D, Hao JK, Kuntz P (2010) An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37:1822–1832.Crossref, Google Scholar
Ramos-Figueroa O, Quiroz-Castellanos M, Mezura-Montes E, Schütze O (2020) Metaheuristics to solve grouping problems: A review and a case study. Swarm Evolutionary Comput. 53:100643.Crossref, Google Scholar
Setubal JC (1996) Sequential and parallel experimental results with bipartite matching algorithms. Technical report, University of Campinas, Institute of Computing, Campinas, Brazil.Google Scholar
Sevaux M, Sörensen K (2008) Hamiltonian paths in large clustered routing problems. Proc. EU/Meeting 2008 Workshop Metaheuristics Logist. Vehicle Routing, vol. 8, 411–417.Google Scholar
Su Z, Lü Z, Wang Z, Qi Y, Benlic U (2020) A matheuristic algorithm for the inventory routing problem. Transportation Sci. 54(2):330–354.Link, Google Scholar
Vidal T, Battarra M, Subramanian A, Erdogan G (2015) Hybrid metaheuristics for the clustered vehicle routing problem. Comput. Oper. Res. 58:87–99.Crossref, Google Scholar
Wang J, Sun Y, Zhang Z, Gao S (2020) Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms. IEEE/CAA J. Automatica Sinica 7(4):1134–1153.Crossref, Google Scholar
Whitley D (1994) A genetic algorithm tutorial. Statist. Comput. 4(2):65–85.Crossref, Google Scholar
Zhou Y, Hao JK, Duval B (2017) Opposition-based memetic search for the maximum diversity problem. IEEE Trans. Evolutionary Comput. 21(5):731–745.Crossref, Google Scholar
Zhou Y, Hao JK, Glover F (2019) Memetic search for identifying critical nodes in sparse graphs. IEEE Trans. Cybernetics 49(10):3699–3712.Crossref, Google Scholar
Zhou Y, Xu W, Fu ZH, Zhou M (2022) Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems. IEEE Trans. Intelligent Transportation Systems 23(9):16072–16082.Crossref, Google Scholar
Zhou Y, Hao JK, Fu ZH, Wang Z, Lai X (2021) Variable population memetic search: A case study on the critical node problem. IEEE Trans. Evolutionary Comput. 25(1):187–200.Crossref, Google Scholar

Volume 57, Issue 3

May-June 2023

Pages 573-837, C2

Article Information

Supplemental Material

Metrics

Information

Received:April 01, 2022
Accepted:September 19, 2022
Published Online:December 09, 2022

Cite as

Yangming Zhou, Yawen Kou, MengChu Zhou (2022) Bilevel Memetic Search Approach to the Soft-Clustered Vehicle Routing Problem. Transportation Science 57(3):701-716.

https://doi.org/10.1287/trsc.2022.1186

Keywords

Acknowledgments

The authors thank the anonymous referees for their helpful comments and suggestions. They are also grateful to Stefan Ropke, Thibaut Vidal, and Maria Battarra for kindly sharing the benchmark instances.

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Bilevel Memetic Search Approach to the Soft-Clustered Vehicle Routing Problem

References

Volume 57, Issue 3

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News