Journal Home > Volume 29 , Issue 2
Tsinghua Science and Technology 2024, 29(2): 305-324 https://doi.org/10.26599/TST.2023.9010048
Open Access | Issue | Published: 22 September 2023

Solving Multi-Objective Vehicle Routing Problems with Time Windows: A Decomposition-Based Multiform Optimization Approach

Show Author's Information Yiqiao Cai1( ),  Zifan Lin1,  Meiqin Cheng1,  Peizhong Liu2( ),  Ying Zhou3
College of Computer Science and Technology, Huaqiao University, and Xiamen Key Laboratory of Data Security and Blockchain Technology, Xiamen 361021, China
College of Engineering, Huaqiao University, Quanzhou 362000, China
School of Computer Sciences, Shenzhen Institute of Information Technology, Shenzhen 518000, China
Keywords:
MOVRPTW, multiform optimization, multiform construction, knowledge transfer, adaptive local search
Cite this article:
Cai Y, Lin Z, Cheng M, et al. Solving Multi-Objective Vehicle Routing Problems with Time Windows: A Decomposition-Based Multiform Optimization Approach. Tsinghua Science and Technology, 2024, 29(2): 305-324. https://doi.org/10.26599/TST.2023.9010048
Download citation
EndNote(RIS)
BibTeX

73

Views

24

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text Electronic supplementary material About this article

In solving multi-objective vehicle routing problems with time windows (MOVRPTW), most existing algorithms focus on the optimization of a single problem formulation. However, little effort has been devoted to exploiting valuable knowledge from the alternate formulations of MOVRPTW for better optimization performance. Aiming at this insufficiency, this study proposes a decomposition-based multi-objective multiform evolutionary algorithm (MMFEA/D), which performs the evolutionary search on multiple alternate formulations of MOVRPTW simultaneously to complement each other. In particular, the main characteristics of MMFEA/D are three folds. First, a multiform construction (MFC) strategy is adopted to construct multiple alternate formulations, each of which is formulated by grouping several adjacent subproblems based on the decomposition of MOVRPTW. Second, a transfer reproduction (TFR) mechanism is designed to generate offspring for each formulation via transferring promising solutions from other formulations, making that the useful traits captured from different formulations can be shared and leveraged to guide the evolutionary search. Third, an adaptive local search (ALS) strategy is developed to invest search effort on different alternate formulations as per their usefulness for MOVRPTW, thus facilitating the efficient allocation of computational resources. Experimental studies have demonstrated the superior performance of MMFEA/D on the classical Solomon instances and the real-world instances.


menu
Abstract
Full text
Outline
Electronic supplementary material
About this article

Solving Multi-Objective Vehicle Routing Problems with Time Windows: A Decomposition-Based Multiform Optimization Approach

Show Author's information Yiqiao Cai1( ), Zifan Lin1, Meiqin Cheng1, Peizhong Liu2( ), Ying Zhou3
College of Computer Science and Technology, Huaqiao University, and Xiamen Key Laboratory of Data Security and Blockchain Technology, Xiamen 361021, China
College of Engineering, Huaqiao University, Quanzhou 362000, China
School of Computer Sciences, Shenzhen Institute of Information Technology, Shenzhen 518000, China

Abstract

In solving multi-objective vehicle routing problems with time windows (MOVRPTW), most existing algorithms focus on the optimization of a single problem formulation. However, little effort has been devoted to exploiting valuable knowledge from the alternate formulations of MOVRPTW for better optimization performance. Aiming at this insufficiency, this study proposes a decomposition-based multi-objective multiform evolutionary algorithm (MMFEA/D), which performs the evolutionary search on multiple alternate formulations of MOVRPTW simultaneously to complement each other. In particular, the main characteristics of MMFEA/D are three folds. First, a multiform construction (MFC) strategy is adopted to construct multiple alternate formulations, each of which is formulated by grouping several adjacent subproblems based on the decomposition of MOVRPTW. Second, a transfer reproduction (TFR) mechanism is designed to generate offspring for each formulation via transferring promising solutions from other formulations, making that the useful traits captured from different formulations can be shared and leveraged to guide the evolutionary search. Third, an adaptive local search (ALS) strategy is developed to invest search effort on different alternate formulations as per their usefulness for MOVRPTW, thus facilitating the efficient allocation of computational resources. Experimental studies have demonstrated the superior performance of MMFEA/D on the classical Solomon instances and the real-world instances.

Keywords: MOVRPTW, multiform optimization, multiform construction, knowledge transfer, adaptive local search

References(47)

[1]
B. Kallehauge, J. Larsen, O. B. G. Madsen, and M. M. Solomon, Vehicle routing problem with time windows, in Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds. New York, NY, USA: Springer, 2006. pp. 67–98.
DOI
[2]
K. Braekers, K. Ramaekers, and I. V. Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Comput. Ind. Eng., vol. 99, pp. 300–313, 2016.
DOI Google Scholar
[3]
J. Mańdziuk, New shades of the vehicle routing problem: Emerging problem formulations and computational intelligence solution methods, IEEE Trans. Emerg. Top. Comput. Intell., vol. 3, no. 3, pp. 230–244, 2019.
DOI Google Scholar
[4]
R. Baldacci, A. Mingozzi, and R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, Eur. J. Oper. Res., vol. 218, no. 1, pp. 1–6, 2012.
DOI Google Scholar
[5]
O. Bräysy and M. Gendreau, Vehicle routing problem with time windows, part II: Metaheuristics, Transp. Sci., vol. 39, no. 1, pp. 119–139, 2005.
DOI Google Scholar
[6]
A. Dixit, A. Mishra, and A. Shukla, Vehicle routing problem with time windows using meta-heuristic algorithms: A survey, in Harmony Search and Nature Inspired Optimization Algorithms, N. Yadav, A. Yadav, J. C. Bansal, K. Deep, and J. H. Kim, eds. Singapore: Springer, 2019: 539-546.
DOI
[7]
E. T. Yassen, M. Ayob, M. Z. Ahmad Nazri, and N. R. Sabar, An adaptive hybrid algorithm for vehicle routing problems with time windows, Comput. Ind. Eng., vol. 113, pp. 382–391, 2017.
DOI Google Scholar
[8]
Y. J. Gong, J. Zhang, O. Liu, R. Z. Huang, H. S. H. Chung, and Y. H. Shi, Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach, IEEE Trans. Syst. Man Cybern. Part C Appl. Rev., vol. 42, no. 2, pp. 254–267, 2012.
DOI Google Scholar
[9]
Y. Marinakis, M. Marinaki, and A. Migdalas, A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows, Inf. Sci., vol. 481, pp. 311–329, 2019.
DOI Google Scholar
[10]
Y. Zhang, J. Wang, and Z. Zhang, Edge-based formulation with graph attention network for practical vehicle routing problem with time windows, in Proc. 2022 Int. Joint Conf. Neural Networks (IJCNN), Padua, Italy, 2022, pp. 1–8.
DOI Google Scholar
[11]
Y. Qi, Z. Hou, H. Li, J. Huang, and X. Li, A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows, Comput. Oper. Res., vol. 62, pp. 61–77, 2015.
DOI Google Scholar
[12]
B. Moradi, The new optimization algorithm for the vehicle routing problem with time windows using multi-objective discrete learnable evolution model, Soft Comput., vol. 24, no. 9, pp. 6741–6769, 2020.
DOI Google Scholar
[13]
J. Castro-Gutierrez, D. Landa-Silva, and J. Moreno Pérez, Nature of real-world multi-objective vehicle routing with evolutionary algorithms, in Proc. 2011 IEEE Int. Conf. Systems, Man, and Cybernetics, Anchorage, AK, USA, 2011, pp. 257–264.
DOI Google Scholar
[14]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.
DOI Google Scholar
[15]
Y. Zhou and J. Wang, A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows, IEEE Syst. J., vol. 9, no. 3, pp. 1100–1113, 2015.
DOI Google Scholar
[16]
Y. Cai, M. Cheng, Y. Zhou, P. Liu, and J. M. Guo, A hybrid evolutionary multitask algorithm for the multiobjective vehicle routing problem with time windows, Inf. Sci., vol. 612, pp. 168–187, 2022.
DOI Google Scholar
[17]
B. Li, J. Li, K. Tang, and X. Yao, Many-objective evolutionary algorithms: A survey, ACM Comput. Surv., vol. 48, no. 1, p. 13, 2015.
DOI Google Scholar
[18]
Y. Sun, G. G. Yen, and Z. Yi, IGD indicator-based evolutionary algorithm for many-objective optimization problems, IEEE Trans. Evol. Comput., vol. 23, no. 2, pp. 173–187, 2019.
DOI Google Scholar
[19]
K. C. Tan, L. Feng, and M. Jiang, Evolutionary transfer optimization-A new frontier in evolutionary computation research, IEEE Comput. Intell. Mag., vol. 16, no. 1, pp. 22–33, 2021.
DOI Google Scholar
[20]
A. Gupta, Y. S. Ong, and L. Feng, Insights on transfer optimization: Because experience is the best teacher, IEEE Trans. Emerg. Top. Comput. Intell., vol. 2, no. 1, pp. 51–64, 2018.
DOI Google Scholar
[21]
E. Osaba, J. Del Ser, and P. N. Suganthan, Evolutionary multitask optimization: Fundamental research questions, practices, and directions for the future, Swarm Evol. Comput., vol. 75, p. 101203, 2022.
DOI Google Scholar
[22]
L. Zhang, Y. Xie, J. Chen, L. Feng, C. Chen, and K. Liu, A study on multiform multi-objective evolutionary optimization, Memet. Comput., vol. 13, no. 3, pp. 307–318, 2021.
DOI Google Scholar
[23]
B. Da, A. Gupta, Y. S. Ong, and L. Feng, Evolutionary multitasking across single and multi-objective formulations for improved problem solving, in Proc. 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, Canada, 2016, pp. 1695–1701.
DOI Google Scholar
[24]
Z. Guo, H. Liu, Y.-S. Ong, X. Qu, Y. Zhang, and J. Zheng, Generative multiform Bayesian optimization, IEEE Trans. Cybern., vol. 53, no. 7, pp. 4347–4360, 2023.
DOI Google Scholar
[25]
Y. Wu, H. Ding, M. Gong, A. K. Qin, W. Ma, Q. Miao, and K. C. Tan, Evolutionary multiform optimization with two-stage bidirectional knowledge transfer strategy for point cloud registration, IEEE Trans. Evol. Comput., vol. PP, no. 99, p. 1, 2022.
DOI Google Scholar
[26]
R. Jiao, B. Xue, and M. Zhang, A multiform optimization framework for constrained multiobjective optimization, IEEE Trans. Cybern., vol. 53, no. 8, pp. 5165–5177, 2023.
DOI Google Scholar
[27]
M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., vol. 35, no. 2, pp. 254–265, 1987.
DOI Google Scholar
[28]
N. Saini and S. Saha, Multi-objective optimization techniques: A survey of the state-of-the-art and applications, Eur. Phys. J. Spec. Top., vol. 230, no. 10, pp. 2319–2335, 2021.
DOI Google Scholar
[29]
J. Bader and E. Zitzler, Hype: An algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., vol. 19, no. 1, pp. 45–76, 2011.
DOI Google Scholar
[30]
M. Kim, T. Hiroyasu, M. Miki, and S. Watanabe, SPEA2+: Improving the performance of the strength Pareto evolutionary algorithm 2, in Parallel Problem Solving from Nature-PPSN VIII, X. Yao, E. K. Burke, and J. A. Lozano, eds. Berlin, Germany: Springer, 2004, pp. 742–751.
DOI
[31]
Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, 2007.
DOI Google Scholar
[32]
X. Ma, J. Yin, A. Zhu, X. Li, Y. Yu, L. Wang, Y. Qi, and Z. Zhu, Enhanced multifactorial evolutionary algorithm with meme helper-tasks, IEEE Trans. Cybern., vol. 52, no. 8, pp. 7837–7851, 2022.
DOI Google Scholar
[33]
D. Lim, Y. S. Ong, Y. Jin, and B. Sendhoff, Evolutionary optimization with dynamic fidelity computational models, in Advanced Intelligent Computing Theories and Applications, D. S. Huang, D. C. Wunsch, D. S. Levine, and K. H. Jo, eds. Berlin, Germany: Springer, 2008, pp. 235–242.
DOI
[34]
K. Qiao, K. Yu, B. Qu, J. Liang, H. Song, and C. Yue, An evolutionary multitasking optimization framework for constrained multiobjective optimization problems, IEEE Trans. Evol. Comput., vol. 26, no. 2, pp. 263–277, 2022.
DOI Google Scholar
[35]
I. M. Oliver, D. Smith, and J. R. Holland, Study of permutation crossover operators on the traveling salesman problem, in Proc. Second Int. Conf. on Genetic Algorithms and Their Application, Broadway Hillsdale, NJ, USA, 1987, pp. 224–230.
Google Scholar
[36]
O. Bräysy and M. Gendreau, Vehicle routing problem with time windows, part I: Route construction and local search algorithms, Transp. Sci., vol. 39, no. 1, pp. 104–118, 2005.
DOI Google Scholar
[37]
Z. Zhou, X. Ma, Z. Liang, and Z. Zhu, Multi-objective multi-factorial memetic algorithm based on bone route and large neighborhood local search for VRPTW, in Proc. 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, UK, 2020, pp. 1–8.
DOI Google Scholar
[38]
K. Deb, M. Mohan, and S. Mishra, Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evol. Comput., vol. 13, no. 4, pp. 501–525, 2005.
DOI Google Scholar
[39]
I. Das and J. E. Dennis, Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., vol. 8, no. 3, pp. 631–657, 1998.
DOI Google Scholar
[40]
A. Gupta, Y. S. Ong, and L. Feng, Multifactorial evolution: Toward evolutionary multitasking, IEEE Trans. Evol. Comput., vol. 20, no. 3, pp. 343–357, 2016.
DOI Google Scholar
[41]
T. Back, D. B. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation. Boca Raton, FL, USA: CRC Press, 1997.
DOI
[42]
Y. Zhou, L. Kong, Y. Cai, Z. Wu, S. Liu, J. Hong, and K. Wu, A decomposition-based local search for large-scale many-objective vehicle routing problems with simultaneous delivery and pickup and time windows, IEEE Syst. J., vol. 14, no. 4, pp. 5253–5264, 2020.
DOI Google Scholar
[43]
J. Wang, T. Weng, and Q. Zhang, A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows, IEEE Trans. Cybern., vol. 49, no. 7, pp. 2467–2478, 2019.
DOI Google Scholar
[44]
C. A. C. Coello and M. Reyes Sierra, A study of the parallelization of a co-evolutionary multi-objective evolutionary algorithm, in Proc. Mexican International Conference on Artificial Intelligence, Monterrey, Mexico, 2004, pp. 688-697.
DOI Google Scholar
[45]
E. Zitzler and L. Thiele, Multiobjective optimization using evolutionary algorithms—A comparative case study, IEEE Trans. Evol. Comput., vol. 3, no. 4, pp. 257-271, 1999.
DOI Google Scholar
[46]
S. García, A. Fernández, J. Luengo, and F. Herrera, A study of statistical techniques and performance measures for genetics-based machine learning: Accuracy and interpretability, Soft Comput., vol. 13, no. 10, pp. 959–977, 2009.
DOI Google Scholar
[47]
J. Derrac, S. García, D. Molina, and F. Herrera, A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol. Comput., vol. 1, pp. 3–18, 2011.
DOI Google Scholar
File
305-324ESM.pdf (124.7 KB)
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 31 January 2023
Revised: 08 May 2023
Accepted: 25 May 2023
Published: 22 September 2023
Issue date: April 2024

Copyright

© The author(s) 2024.

Acknowledgements

This work was supported in part by the Natural Science Foundation of Fujian Province of China (No. 2021J01318), the National Natural Science Foundation Youth Fund Project (No. 62202314), the Fujian Provincial Science and Technology Major Project (No. 2020HZ02014), and the Quanzhou Science and Technology Major Project (No. 2021GZ1).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return