AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (12.8 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

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
Show Author Information

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

MOVRPTWmultiform optimizationmultiform constructionknowledge transferadaptive local search

Electronic Supplementary Material

Download File(s)
305-324ESM.pdf (124.7 KB)

References

[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[41]
T. Back, D. B. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation. Boca Raton, FL, USA: CRC Press, 1997.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 2,
April 2024
Pages 305-324
DOI: 10.26599/TST.2023.9010048
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

473

Views

71

Downloads

3

Crossref

0

Web of Science

3

Scopus

0

CSCD

Altmetrics
Received: 31 January 2023
Revised: 08 May 2023
Accepted: 25 May 2023
Published: 22 September 2023
© The author(s) 2024.

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