Journal Home > Volume 2 , Issue 2
Complex System Modeling and Simulation 2022, 2(2): 142-155 https://doi.org/10.23919/CSMS.2022.0008
Open Access | Issue | Published: 30 June 2022

A Region Enhanced Discrete Multi-Objective Fireworks Algorithm for Low-Carbon Vehicle Routing Problem

Show Author's Information Xiaoning Shen1,  Jiaqi Lu2,  Xuan You2,  Liyan Song3( ),  Zhongpei Ge2
Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, Jiangsu Key Laboratory of Big Data Analysis Technology, School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China
Research Institute of Trustworthy Autonomous Systems, and also with the Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
Keywords:
multi-objective optimization, vehicle routing problem, carbon emission, fireworks algorithm, region enhanced
Cite this article:
Shen X, Lu J, You X, et al. A Region Enhanced Discrete Multi-Objective Fireworks Algorithm for Low-Carbon Vehicle Routing Problem. Complex System Modeling and Simulation, 2022, 2(2): 142-155. https://doi.org/10.23919/CSMS.2022.0008
Download citation
EndNote(RIS)
BibTeX

548

Views

26

Downloads

Citations

5

Crossref

N/A

WoS

5

Scopus

N/A

CSCD

Abstract Full text About this article

A constrained multi-objective optimization model for the low-carbon vehicle routing problem (VRP) is established. A carbon emission measurement method considering various practical factors is introduced. It minimizes both the total carbon emissions and the longest time consumed by the sub-tours, subject to the limited number of available vehicles. According to the characteristics of the model, a region enhanced discrete multi-objective fireworks algorithm is proposed. A partial mapping explosion operator, a hybrid mutation for adjusting the sub-tours, and an objective-driven extending search are designed, which aim to improve the convergence, diversity, and spread of the non-dominated solutions produced by the algorithm, respectively. Nine low-carbon VRP instances with different scales are used to verify the effectiveness of the new strategies. Furthermore, comparison results with four state-of-the-art algorithms indicate that the proposed algorithm has better performance of convergence and distribution on the low-carbon VRP. It provides a promising scalability to the problem size.


menu
Abstract
Full text
Outline
About this article

A Region Enhanced Discrete Multi-Objective Fireworks Algorithm for Low-Carbon Vehicle Routing Problem

Show Author's information Xiaoning Shen1, Jiaqi Lu2, Xuan You2, Liyan Song3( ), Zhongpei Ge2
Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, Jiangsu Key Laboratory of Big Data Analysis Technology, School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China
School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China
Research Institute of Trustworthy Autonomous Systems, and also with the Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

Abstract

A constrained multi-objective optimization model for the low-carbon vehicle routing problem (VRP) is established. A carbon emission measurement method considering various practical factors is introduced. It minimizes both the total carbon emissions and the longest time consumed by the sub-tours, subject to the limited number of available vehicles. According to the characteristics of the model, a region enhanced discrete multi-objective fireworks algorithm is proposed. A partial mapping explosion operator, a hybrid mutation for adjusting the sub-tours, and an objective-driven extending search are designed, which aim to improve the convergence, diversity, and spread of the non-dominated solutions produced by the algorithm, respectively. Nine low-carbon VRP instances with different scales are used to verify the effectiveness of the new strategies. Furthermore, comparison results with four state-of-the-art algorithms indicate that the proposed algorithm has better performance of convergence and distribution on the low-carbon VRP. It provides a promising scalability to the problem size.

Keywords: multi-objective optimization, vehicle routing problem, carbon emission, fireworks algorithm, region enhanced

References(42)

1
Y. Wang, S. Peng, X. Zhou, M. Mahmoudi, and L. Zhen, Green logistics location-routing problem with eco-packages, Transportation Research Part E: Logistics and Transportation Review, vol. 143, p. 102118, 2020.https://doi.org/10.1016/j.tre.2020.102118
DOI
2
M. Asghari and S. M. J. M. Al-e-hashem, Green vehicle routing problem: A state-of-the-art review, International Journal of Production Economics, vol. 231, p. 107899, 2021.https://doi.org/10.1016/j.ijpe.2020.107899
DOI
3
F. E. Zulvia, R. J. Kuo, and D. Y. Nugroho, A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products, Journal of Cleaner Production, vol. 242, p. 118428, 2020.https://doi.org/10.1016/j.jclepro.2019.118428
DOI
4
A. Jabbarzadeh, F. Darbaniyan, and M. S. Jabalameli, A multi-objective model for location of transfer stations: Case study in waste management system of Tehran, Systems Engineering, vol. 9, no. 1, pp. 109–125, 2018.
5
T. Long and Q. S. Jia, Matching uncertain renewable supply with electric vehicle charging demand-A Bi-level event-based optimization method, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 33–44, 2021.https://doi.org/10.23919/CSMS.2021.0001
DOI
6
G. B. Dantzig and J. H. Ramser, The truck dispatching problem, Management Science, vol. 6, no. 1, pp. 80–91, 1959.https://doi.org/10.1287/mnsc.6.1.80
DOI
7
J. Jemai, M. Zekri, and K. Mellouli, An NSGA-II algorithm for the green vehicle routing problem, in Proc. 12thEuropean Conference on Evolutionary Computation in Combinatorial Optimization, Málaga, Spain, 2012, pp. 37–48.https://doi.org/10.1007/978-3-642-29124-1_4
DOI
8
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.https://doi.org/10.1109/4235.996017
DOI
9
Z. Xu, A. Elomri, S. Pokharel, and F. Mutlu, A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows, Computers & Industrial Engineering, vol. 137, p. 106011, 2019.https://doi.org/10.1016/j.cie.2019.106011
DOI
10
J. Zhang, Y. Zhao, W. Xue, and J. Li, Vehicle routing problem with fuel consumption and carbon emission, International Journal of Production Economics, vol. 170, pp. 234–242, 2015.https://doi.org/10.1016/j.ijpe.2015.09.031
DOI
11
Y. Xiao, Q. Zhao, I. Kaku, and Y. Xu, Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Computers & Operations Research, vol. 39, no. 7, pp. 1419–1431, 2012.https://doi.org/10.1016/j.cor.2011.08.013
DOI
12
Y. Wang, K. Assogba, J. Fan, M. Xu, Y. Liu, and H. Wang, Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost, Journal of Cleaner Production, vol. 232, pp. 12–29, 2019.https://doi.org/10.1016/j.jclepro.2019.05.344
DOI
13
D. Tayachi and H. Boukadi, A variable neighborhood search to reduce carbon dioxide emissions in the capacitated vehicle routing problem, in Proc. 2019 6thInternational Conference on Control, Decision and Information Technologies (CoDIT), Paris, France, 2019, pp. 297–301.https://doi.org/10.1109/CoDIT.2019.8820702
DOI
14
R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, The green vehicle routing problem: A systematic literature review, Journal of Cleaner Production, vol. 279, p. 123691, 2021.https://doi.org/10.1016/j.jclepro.2020.123691
DOI
15
X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.https://doi.org/10.23919/CSMS.2021.0018
DOI
16
F. Zhao, S. Di, J. Cao, J. Tang, and Jonrinaldi, A novel cooperative multi-stage hyper-heuristic for combination optimization problems, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 91–108, 2021.https://doi.org/10.23919/CSMS.2021.0010
DOI
17
W. Zhang, W. Hou, C. Li, W. Yang, and M. Gen, Multidirection update-based multiobjective particle swarm optimization for mixed no-idle flow-shop scheduling problem, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 176–197, 2021.https://doi.org/10.23919/CSMS.2021.0017
DOI
18
H. Lu, S. Yang, M. Zhao, and S. Cheng, Multi-robot indoor environment map building based on multi-stage optimization method, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 145–161, 2021.https://doi.org/10.23919/CSMS.2021.0011
DOI
19
W. Gong, Z. Liao, X. Mi, L. Wang, and Y. Guo, Nonlinear equations solving with intelligent optimization algorithms: A survey, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 15–32, 2021.https://doi.org/10.23919/CSMS.2021.0002
DOI
20
X. Ge, R. Wu, amd H. Rabitz, Optimization landscape of quantum control systems, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 77–90, 2021.https://doi.org/10.23919/CSMS.2021.0014
DOI
21
P. R. De Oliveira Da Costa, S. Mauceri, P. Carroll, and F. Pallonetto, A genetic algorithm for a green vehicle routing problem, Electronic Notes in Discrete Mathematics, vol. 64, pp. 65–74, 2018.https://doi.org/10.1016/j.endm.2018.01.008
DOI
22
K. Zhang, B. Qiu, and D. Mu, Low-carbon logistics distribution route planning with improved particle swarm optimization algorithm, in Proc. 2016 International Conference on Logistics, Informatics and Service Science (LISS), Sydney, Australia, 2016, pp. 1–4.https://doi.org/10.1109/LISS.2016.7854443
DOI
23
L. B. Pulido-Gaytan, A. Tchernykh, S. Nesmachnow, A. Cristóbal-Salas, A. Avetisyan, H. E. C. Barrera, and C. J. B. Hernandez, Multi-objective optimization of vehicle routing with environmental penalty, in Proc. 10thInternational Conference on Supercomputing, Monterrey, Mexico, 2019, pp. 147–162.https://doi.org/10.1007/978-3-030-38043-4_13
DOI
24
Y. Li, H. Soleimani, and M. Zohal, An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives, Journal of Cleaner Production, vol. 227, pp. 1161–1172, 2019.https://doi.org/10.1016/j.jclepro.2019.03.185
DOI
25
E. Jabir, V. V. Panicker, and R. Sridharan, Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem, Transportation Research Part D: Transport and Environment, vol. 57, pp. 422–457, 2017.https://doi.org/10.1016/j.trd.2017.09.003
DOI
26
Y. Tan and Y. Zhu, Fireworks algorithm for optimization, in Proc. First International Conference on Advances in Swarm intelligence, Beijing, China, 2010, pp. 355–364.https://doi.org/10.1007/978-3-642-13495-1_44
DOI
27
J. Ji, H. Xiao, and C. Yang, HFADE-FMD: A hybrid approach of fireworks algorithm and differential evolution strategies for functional module detection in protein-protein interaction networks, Applied Intelligence, vol. 51, pp. 1118–1132, 2021.https://doi.org/10.1007/s10489-020-01791-4
DOI
28
X. Liu and X. Qin, A neighborhood information utilization fireworks algorithm and its application to traffic flow prediction, Expert Systems with Applications, vol. 183, p. 115189, 2021.https://doi.org/10.1016/j.eswa.2021.115189
DOI
29
M. Zare, M. R. Narimani, M. Malekpour, R. Azizipanah-Abarghooee, and V. Terzija, Reserve constrained dynamic economic dispatch in multi-area power systems: An improved fireworks algorithm, International Journal of Electrical Power & Energy Systems, vol. 126, p. 106579, 2021.https://doi.org/10.1016/j.ijepes.2020.106579
DOI
30
Y. -J. Zheng, Q. Song, and S. -Y. Chen, Multiobjective fireworks optimization for variable-rate fertilization in oil crop production, Applied Soft Computing, vol. 13, no. 11, pp. 4253–4263, 2013.https://doi.org/10.1016/j.asoc.2013.07.004
DOI
31
L. Liu, S. Zheng, and Y. Tan, S-metric based multi-objective fireworks algorithm, in Proc. 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan, 2015, pp. 1257–1264.https://doi.org/10.1109/CEC.2015.7257033
DOI
32
S. I. Bejinariu, H. Costin, F. Rotaru, R. Luca, and C. Niţă, Fireworks algorithm based single and multi-objective optimization,Bulletin of the Polytechnic Institute of IASI, Automatic Control and Computer Science, vol. 62, no. 66, pp. 19–34, 2016.
33
X. Chen, C. Shi, A. Zhou, S. Xu, and B. Wu, A hybrid replacement strategy for MOEA/D, in Proc. 13thInternational Conference on Bio-Inspired Computing: Theories and Applications, Beijing, China, 2018, pp. 246–262.https://doi.org/10.1007/978-981-13-2826-8_22
DOI
34
T. Zhang, G. Liu, Q. Yue, X. Zhao, and M. Hu, Using firework algorithm for multi-objective hardware/software partitioning, IEEE Access, vol. 7, pp. 3712–3721, 2018.https://doi.org/10.1109/ACCESS.2018.2886430
DOI
35
H. L. Tang, H. S. Tang, and X. Zhu, Research on low-carbon vehicle routing problem based on modified ant colony algorithm, Chinese Journal of Management Science, vol. 29, no. 7, pp. 118–127, 2021.
36
K. Deb, M. Mohan, and S. Mishra, Towards a quick computation of well-spread pareto-optimal solutions, in Proc. 2ndInternational Conference on Evolutionary Multi-Criterion Optimization, Faro, Portugal, 2003, pp. 222–236.https://doi.org/10.1007/3-540-36970-8_16
DOI
37
Y. Sun, G. G. Yen, and Z. Yi, IGD indicator-based evolutionary algorithm for many-objective optimization problems, IEEE Transactions on Evolutionary Computation, vol. 23, no. 2, pp. 173–187, 2019.https://doi.org/10.1109/TEVC.2018.2791283
DOI
38
H. K. Singh, Understanding hypervolume behavior theoretically for benchmarking in evolutionary multi/ many-objective optimization, IEEE Transactions on Evolutionary Computation, vol. 24, no. 3, pp. 603–610, 2020.
39
The VRP Web, http://www.bernabe.dorronsoro.es/vrp/, 2022.
40
L. He, W. Li, Y. Zhang, and Y. Cao, A discrete multi-objective fireworks algorithm for flowshop scheduling with sequence-dependent setup times, Swarm and Evolutionary Computation, vol. 51, p. 100575, 2019.https://doi.org/10.1016/j.swevo.2019.100575
DOI
41
N. H. Abdulmajeed and M. Ayob, A firework algorithm for solving capacitated vehicle routing problem, International Journal of Advancements in Computing Technology, vol. 6, no. 1, p. 79, 2014.
42
E. Zitzler, M. Laumanns, and L. Thiele, SPEA2: Improving the strength pareto evolutionary algorithm, TIK-Report, doi: 10.3929/ethz-a-004284029.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 11 January 2022
Revised: 01 May 2022
Accepted: 18 May 2022
Published: 30 June 2022
Issue date: June 2022

Copyright

© The author(s) 2022

Acknowledgements

Acknowledgment

This work was supported by the Guangdong Provincial Key Laboratory (No. 2020B121201001), the National Natural Science Foundation of China (NSFC) (Nos. 61502239 and 62002148), Natural Science Foundation of Jiangsu Province of China (No. BK20150924), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (No.2017ZT07X386), Shenzhen Science and Technology Program (No. KQTD2016112514355531), and Research Institute of Trustworthy Autonomous Systems (RITAS).

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