Journal Home > Volume 3 , Issue 3
Complex System Modeling and Simulation 2023, 3(3): 202-219 https://doi.org/10.23919/CSMS.2023.0008
Open Access | Issue | Published: 02 August 2023

Energy-Efficient Multi-Trip Routing for Municipal Solid Waste Collection by Contribution-Based Adaptive Particle Swarm Optimization

Show Author's Information Xiaoning Shen1( ),  Hongli Pan2,  Zhongpei Ge2,  Wenyan Chen2,  Liyan Song3,  Shuo Wang4
Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, and also with the 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
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, the Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
School of Computer Science, University of Birmingham, Birmingham, B15 2TT, UK
Keywords:
particle swarm optimization, energy conservation, municipal solid waste collection, multi-trip, contribution
Cite this article:
Shen X, Pan H, Ge Z, et al. Energy-Efficient Multi-Trip Routing for Municipal Solid Waste Collection by Contribution-Based Adaptive Particle Swarm Optimization. Complex System Modeling and Simulation, 2023, 3(3): 202-219. https://doi.org/10.23919/CSMS.2023.0008
Download citation
EndNote(RIS)
BibTeX

452

Views

67

Downloads

Citations

6

Crossref

N/A

WoS

2

Scopus

N/A

CSCD

Abstract Full text About this article

Waste collection is an important part of waste management system. Transportation costs and carbon emissions can be greatly reduced by proper vehicle routing. Meanwhile, each vehicle can work again after achieving its capacity limit and unloading the waste. For this, an energy-efficient multi-trip vehicle routing model is established for municipal solid waste collection, which incorporates practical factors like the limited capacity, maximum working hours, and multiple trips of each vehicle. Considering both economy and environment, fixed costs, fuel costs, and carbon emission costs are minimized together. To solve the formulated model effectively, contribution-based adaptive particle swarm optimization is proposed. Four strategies named greedy learning, multi-operator learning, exploring learning, and exploiting learning are specifically designed with their own searching priorities. By assessing the contribution of each learning strategy during the process of evolution, an appropriate one is selected and assigned to each individual adaptively to improve the searching efficiency of the algorithm. Moreover, an improved local search operator is performed on the trips with the largest number of waste sites so that both the exploiting ability and the convergence accuracy of the algorithm are improved. Performance of the proposed algorithm is tested on ten waste collection instances, which include one real-world case derived from the Green Ring Company of Jiangbei New District, Nanjing, China, and nine synthetic instances with increasing scales generated from the commonly-used capacitated vehicle routing problem benchmark datasets. Comparisons with five state-of-the-art algorithms show that the proposed algorithm can obtain a solution with a higher accuracy for the constructed model.


menu
Abstract
Full text
Outline
About this article

Energy-Efficient Multi-Trip Routing for Municipal Solid Waste Collection by Contribution-Based Adaptive Particle Swarm Optimization

Show Author's information Xiaoning Shen1( ), Hongli Pan2, Zhongpei Ge2, Wenyan Chen2, Liyan Song3, Shuo Wang4
Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, and also with the 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
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, the Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
School of Computer Science, University of Birmingham, Birmingham, B15 2TT, UK

Abstract

Waste collection is an important part of waste management system. Transportation costs and carbon emissions can be greatly reduced by proper vehicle routing. Meanwhile, each vehicle can work again after achieving its capacity limit and unloading the waste. For this, an energy-efficient multi-trip vehicle routing model is established for municipal solid waste collection, which incorporates practical factors like the limited capacity, maximum working hours, and multiple trips of each vehicle. Considering both economy and environment, fixed costs, fuel costs, and carbon emission costs are minimized together. To solve the formulated model effectively, contribution-based adaptive particle swarm optimization is proposed. Four strategies named greedy learning, multi-operator learning, exploring learning, and exploiting learning are specifically designed with their own searching priorities. By assessing the contribution of each learning strategy during the process of evolution, an appropriate one is selected and assigned to each individual adaptively to improve the searching efficiency of the algorithm. Moreover, an improved local search operator is performed on the trips with the largest number of waste sites so that both the exploiting ability and the convergence accuracy of the algorithm are improved. Performance of the proposed algorithm is tested on ten waste collection instances, which include one real-world case derived from the Green Ring Company of Jiangbei New District, Nanjing, China, and nine synthetic instances with increasing scales generated from the commonly-used capacitated vehicle routing problem benchmark datasets. Comparisons with five state-of-the-art algorithms show that the proposed algorithm can obtain a solution with a higher accuracy for the constructed model.

Keywords: particle swarm optimization, energy conservation, municipal solid waste collection, multi-trip, contribution

References(39)

[1]
F. R. McDougall, P. R. White, M. Franke, and P. Hindle, Integrated Solid Waste Management: A Life Cycle Inventory. Oxford, UK: Blackwell Science, 2001.
DOI
[2]
E. C. Rada, M. Grigoriu, M. Ragazzi, and P. Fedrizzi, Web oriented technologies and equipments for MSW collection, in Proc. International Conference on Risk Management, Assessment, and Mitigation, Bucharest, Romania, 2010, pp. 150–153.
[3]

T. E. Kanchanabhan, J. A. Mohaideen, S. Srinivasan, and V. L. K. Sundaram, Optimum municipal solid waste collection using geographical information system (GIS) and vehicle tracking for Pallavapuram municipality, Waste Manag. Res., vol. 29, no. 3, pp. 323–339, 2011.
DOI Google Scholar
[4]

B. G. Wilson and B. W. Baetz, Modeling municipal solid waste collection systems using derived probability Distributions. I: Model development, J. Environ. Eng., vol. 127, no. 11, pp. 1031–1038, 2001.
DOI Google Scholar
[5]
V. Wagner and D. Rutherford, Survey of best practices in emission control of in-use heavy-duty diesel vehicles, https://theicct.org/sites/default/files/publications/ICCT_HDV_in-use_20130802.pdf, 2013.
[6]

E. J. Beltrami and L. D. Bodin, Networks and vehicle routing for municipal waste collection, Networks, vol. 4, no. 1, pp. 65–94, 1974.
DOI Google Scholar
[7]

M. A. Hannan, M. S. H. Lipu, M. Akhtar, R. A. Begum, M. A. A. Mamun, A. Hussain, M. S. Mia, and H. Basri, Solid waste collection optimization objectives, constraints, modeling approaches, and their challenges toward achieving sustainable development goals, J. Clean. Prod., vol. 277, p. 123557, 2020.
DOI Google Scholar
[8]

H. Wu, F. Tao, Q. Qiao, and M. Zhang, A chance-constrained vehicle routing problem for wet waste collection and transportation considering carbon emissions, Int. J. Environ. Res. Public Health, vol. 17, no. 2, p. 458, 2020.
DOI Google Scholar
[9]

J. C. Molina, I. Eguia, and J. Racero, Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: A case study, TOP, vol. 27, no. 2, pp. 253–287, 2019.
DOI Google Scholar
[10]

H. Wu, F. Tao, and B. Yang, Optimization of vehicle routing for waste collection and transportation, Int. J. Environ. Res. Public Health, vol. 17, no. 14, p. 4963, 2020.
DOI Google Scholar
[11]

I. Markov, S. Varone, and M. Bierlaire, Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities, Transp. Res. B:Methodological, vol. 84, pp. 256–273, 2016.
DOI Google Scholar
[12]

Y. Shi, L. Lv, F. Hu, and Q. Han, A heuristic solution method for multi-depot vehicle routing-based waste collection problems, Appl. Sci., vol. 10, no. 7, p. 2403, 2020.
DOI Google Scholar
[13]

E. B. Tirkolaee, I. Mahdavi, and M. M. S. Esfahani, A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time, Waste Manag., vol. 76, pp. 138–146, 2018.
DOI Google Scholar
[14]

H. R. Lewis, Computers and intractability: A guide to the theory of NP-completeness, The Journal of Symbolic Logic, vol. 48, no. 2, pp. 498–500, 1983.
DOI Google Scholar
[15]

A. Louati, L. H. Son, and H. Chabchoub, Smart routing for municipal solid waste collection: A heuristic approach, J. Ambient Intell. Humaniz. Comput., vol. 10, no. 5, pp. 1865–1884, 2019.
DOI Google Scholar
[16]

Q. Wei, Z. Guo, H. C. Lau, and Z. He, An artificial bee colony-based hybrid approach for waste collection problem with midway disposal pattern, Appl. Soft Comput., vol. 76, pp. 629–637, 2019.
DOI Google Scholar
[17]

A. Expósito-Márquez, C. Expósito-Izquierdo, J. Brito-Santana, and J. A. Moreno-Pérez, Greedy randomized adaptive search procedure to design waste collection routes in La Palma, Comput. Ind. Eng., vol. 137, p. 106047, 2019.
DOI Google Scholar
[18]

Q. Qiao, F. Tao, H. Wu, X. Yu, and M. Zhang, Optimization of a capacitated vehicle routing problem for sustainable municipal solid waste collection management using the PSO-TS algorithm, Int. J. Environ. Res. Public Health, vol. 17, no. 6, p. 2163, 2020.
DOI Google Scholar
[19]

M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm, Waste Manag., vol. 71, pp. 31–41, 2018.
DOI Google Scholar
[20]

M. A. Islam, Y. Gajpal, and T. Y. ElMekkawy, Hybrid particle swarm optimization algorithm for solving the clustered vehicle routing problem, Appl. Soft Comput., vol. 110, p. 107655, 2021.
DOI Google Scholar
[21]

Y. -J. Zheng, X. Chen, H. -F. Yan, and M. -X. Zhang, Evolutionary algorithm for vehicle routing for shared e-bicycle battery replacement and recycling, Appl. Soft Comput., vol. 135, p. 110023, 2023.
DOI Google Scholar
[22]

F. Wang, F. Liao, Y. Li, X. Yan, and X. Chen, An ensemble learning based multi-objective evolutionary algorithm for the dynamic vehicle routing problem with time windows, Comput. Ind. Eng., vol. 154, p. 107131, 2021.
DOI Google Scholar
[23]

X. Shen, J. Lu, X. You, L. Song, and Z. Ge, A region enhanced discrete multi-objective fireworks algorithm for low-carbon vehicle routing problem, Complex System Modeling and Simulation, vol. 2, no. 2, pp. 142–155, 2022.
DOI Google Scholar
[24]

Y. -J. Zheng, X. Chen, Q. Song, J. Yang, and L. Wang, Evolutionary optimization of COVID-19 vaccine distribution with evolutionary demands, IEEE Trans. Evol. Comput., vol. 27, no. 1, pp. 141–154, 2023.
DOI Google Scholar
[25]

Y. Shen, L. Yu, and J. Li, Robust electric vehicle routing problem with time windows under demand uncertainty and weight-related energy consumption, Complex System Modeling and Simulation, vol. 2, no. 1, pp. 18–34, 2022.
DOI Google Scholar
[26]

T. Bektaş and G. Laporte, The pollution-routing problem, Transp. Res. B:Methodological, vol. 45, no. 8, pp. 1232–1250, 2011.
DOI Google Scholar
[27]
J. Kennedy and R. Eberhart, Particle swarm optimization, in Proc. ICNN'95—Int. Conf. Neural Networks, Perth, Australia, 1995, pp. 1942–1948.
[28]

V. Leggieri and M. Haouari, A matheuristic for the asymmetric capacitated vehicle routing problem, Discrete Appl. Math., vol. 234, pp. 139–150, 2018.
DOI Google Scholar
[29]

H. Li, K. Gao, P. -Y. Duan, J. -Q. Li, and L. Zhang, An improved artificial bee colony algorithm with Q-learning for solving permutation flow-shop scheduling problems, IEEE Trans. Syst. Man Cybern., vol. 53, no. 5, pp. 2684–2693, 2023.
DOI Google Scholar
[30]

I. Sbai, S. Krichen, and O. Limam, Two meta-heuristics for solving the capacitated vehicle routing problem: The case of the Tunisian Post Office, Oper. Res., vol. 22, no. 1, pp. 507–549, 2022.
DOI Google Scholar
[31]
V. Singh and S. Choudhary, Genetic algorithm for traveling salesman problem: Using modified partially-mapped crossover operator, in Proc. 2009 Int. Multimedia, Signal Processing and Communication Technologies, Aligarh, India, 2009, pp. 20–23.
DOI
[32]

J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Trans. Evol. Comput., vol. 10, no. 3, pp. 281–295, 2006.
DOI Google Scholar
[33]

S. Hougardy, F. Zaiser, and X. Zhong, The approximation ratio of the 2-opt heuristic for the metric traveling salesman problem, Oper. Res. Lett., vol. 48, no. 4, pp. 401–404, 2020.
DOI Google Scholar
[34]
Y. Pan, K. Gao, Z. Li, and N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved jaya algorithm, IEEE Trans. Cybern., doi: 10.1109/TCYB.2022.3164165.
DOI
[35]

J. Chen, B. Dan, and J. Shi, A variable neighborhood search approach for the multi-compartment vehicle routing problem with time windows considering carbon emission, J. Clean. Prod., vol. 277, p. 123932, 2020.
DOI Google Scholar
[36]

L. Zhen, C. Ma, K. Wang, L. Xiao, and W. Zhang, Multi-depot multi-trip vehicle routing problem with time windows and release dates, Transportation Research Part E:Logistics and Transportation Review, vol. 135, p. 101866, 2020.
DOI Google Scholar
[37]

Y. Sun, D. Wang, M. Lang, and X. Zhou, Solving the time-dependent multi-trip vehicle routing problem with time windows and an improved travel speed model by a hybrid solution algorithm, Clust. Comput., vol. 22, no. 6, pp. 15459–15470, 2019.
DOI Google Scholar
[38]

E. B. Tirkolaee, M. Alinaghian, A. A. R. Hosseinabadi, M. B. Sasi, and A. K. Sangaiah, An improved ant colony optimization for the multi-trip capacitated arc routing problem, Comput. Electr. Eng., vol. 77, pp. 457–470, 2019.
DOI Google Scholar
[39]

E. B. Tirkolaee, A. A. R. Hosseinabadi, M. Soltani, A. K. Sangaiah, and J. Wang, A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services, Sustainability, vol. 10, no. 5, p. 1366, 2018.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 02 February 2023
Revised: 22 March 2023
Accepted: 17 April 2023
Published: 02 August 2023
Issue date: September 2023

Copyright

© The author(s) 2023.

Acknowledgements

Acknowledgment

This work was supported by the Guangdong Provincial Key Laboratory (No. 2020B121201001), National Natural Science Foundation of China (NSFC) (Nos. 61502239 and 62002148), Natural Science Foundation of Jiangsu Province of China (No. BK20150924), and Shenzhen Science and Technology Program (No. KQTD2016112514355531).

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