TY - GEN
T1 - An Efficient Metaheuristic Algorithm for Solving Soft-clustered Vehicle Routing Problems
AU - Kou, Yawen
AU - Zhou, Yangming
AU - Zhou, Mengchu
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - A soft-clustered vehicle routing problem (SoftClu-VRP) is an important variant of the well-known capacitated vehicle routing problem, where customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. As a highly useful model for parcel delivery in courier companies, SoftCluVRP is NP-hard. In this work, we propose an efficient metaheuristic algorithm for solving it. Starting from an initial population, it iterates by using a solution recombination operator (to generate a promising offspring solution), a hybrid neighborhood search (to find a high-quality local optimum), and a population updating strategy (to manage a healthy population). Experiments on two groups of 378 widely-used benchmark instances show that it achieves highly competitive performance compared to state-of-the-art algorithms. In particular, our algorithm finds the best upper bounds on 320 instances.
AB - A soft-clustered vehicle routing problem (SoftClu-VRP) is an important variant of the well-known capacitated vehicle routing problem, where customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. As a highly useful model for parcel delivery in courier companies, SoftCluVRP is NP-hard. In this work, we propose an efficient metaheuristic algorithm for solving it. Starting from an initial population, it iterates by using a solution recombination operator (to generate a promising offspring solution), a hybrid neighborhood search (to find a high-quality local optimum), and a population updating strategy (to manage a healthy population). Experiments on two groups of 378 widely-used benchmark instances show that it achieves highly competitive performance compared to state-of-the-art algorithms. In particular, our algorithm finds the best upper bounds on 320 instances.
KW - Combinatorial Optimization
KW - Evolutionary Computation
KW - Metaheuristic
KW - Vehicle Routing Problem
UR - http://www.scopus.com/inward/record.url?scp=85146960325&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146960325&partnerID=8YFLogxK
U2 - 10.1109/ICNSC55942.2022.10004081
DO - 10.1109/ICNSC55942.2022.10004081
M3 - Conference contribution
AN - SCOPUS:85146960325
T3 - ICNSC 2022 - Proceedings of 2022 IEEE International Conference on Networking, Sensing and Control: Autonomous Intelligent Systems
BT - ICNSC 2022 - Proceedings of 2022 IEEE International Conference on Networking, Sensing and Control
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 19th IEEE International Conference on Networking, Sensing and Control, ICNSC 2022
Y2 - 15 December 2022 through 18 December 2022
ER -