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 International Journal of Crowd Science Article
PDF (588 KB)
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

Heterogeneous Electric Vehicle Routing Problem with Multiple Compartments and Multiple Trips for the Collection of Classified Waste

Zhishuo Liu1( ), Lujing Sun1, Xingquan Zuo2, Haoxiang Li3
School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China
School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Department of Biomedical Engineering, Tsinghua University, Beijing 100084, China
Show Author Information

Abstract

This paper studies the collection of classified waste using electric commercial vehicles (ECVs). The fleet of ECVs is heterogeneous, and ECVs have separated compartments, namely, they have different capacities for each type of waste. Each ECV is allowed to deliver multiple times and can be recharged more than once in public recharging stations during its route. A mathematical model is proposed for the heterogeneous electric vehicle routing problem with multiple compartments, multiple trips, and time windows (HEVRP-MCMT). The objective of the problem is to minimize the vehicle fixed cost and variable energy consumption cost. A hybrid ant colony optimization (ACO) with variable neighborhood search (VNS) is developed and applied to a number of problem instances and a real-life instance. Numerical results show that, for small-scale problem instances, our approach finds better or the same optimal solutions in a significantly shorter computational time than CPLEX; for large-scale problem instances, our approach outperforms two meta-heuristics. Experiments on a real-life problem instance show that using a fleet of multicompartment vehicles can save considerable cost compared with using single-compartment vehicles only.

Keywords

ant colony optimizationelectric vehicle routing problemcollection of classified wastevariable neighborhood search

Electronic Supplementary Material

Download File(s)
IJCS-2023-0009_ESM.pdf (306.1 KB)

References

[1]

T. Henke, M. G. Speranza, and G. Wäscher, The multi-compartment vehicle routing problem with flexible compartment sizes, Eur. J. Oper. Res., vol. 246, no. 3, pp. 730–743, 2015.
Crossref Google Scholar
[2]

B. I. Kim, S. Kim, and S. Sahoo, Waste collection vehicle routing problem with time windows, Comput. Oper. Res., vol. 33, no. 12, pp. 3624–3642, 2006.
Crossref Google Scholar
[3]

D. Rezgui, J. C. Siala, W. Aggoune-Mtalaa, and H. Bouziri, Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles, Comput. Ind. Eng., vol. 130, pp. 537–550, 2019.
Crossref Google Scholar
[4]

W. Jie, J. Yang, M. Zhang, and Y. Huang, The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology, Eur. J. Oper. Res., vol. 272, no. 3, pp. 879–904, 2019.
Crossref Google Scholar
[5]

S. Z. Aliahmadi, F. Barzinpour, and M. S. Pishvaee, A novel bi-objective credibility-based fuzzy model for municipal waste collection with hard time windows, J. Clean. Prod., vol. 296, p. 126364, 2021.
Crossref Google Scholar
[6]

M. Reed, A. Yiannakou, and R. Evering, An ant colony algorithm for the multi-compartment vehicle routing problem, Appl. Soft Comput., vol. 15, pp. 169–176, 2014.
Crossref Google Scholar
[7]

B. A. Davis and M. A. Figliozzi, A methodology to evaluate the competitiveness of electric delivery trucks, Transp. Res. Part E Logist. Transp. Rev., vol. 49, no. 1, pp. 8–23, 2013.
Crossref Google Scholar
[8]

M. Schneider, A. Stenger, and D. Goeke, The electric vehicle-routing problem with time windows and recharging stations, Transp. Sci., vol. 48, no. 4, pp. 500–520, 2014.
Crossref Google Scholar
[9]

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

D. V. Tung and A. Pinnoi, Vehicle routing–scheduling for waste collection in Hanoi, Eur. J. Oper. Res., vol. 125, no. 3, pp. 449–468, 2000.
Crossref Google Scholar
[11]

A. M. Benjamin and J. E. Beasley, Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities, Comput. Oper. Res., vol. 37, no. 12, pp. 2270–2280, 2010.
Crossref Google Scholar
[12]

T. Nuortio, J. Kytöjoki, H. Niska, and O. Bräysy, Improved route planning and scheduling of waste collection and transport, Expert Syst. Appl., vol. 30, no. 2, pp. 223–232, 2006.
Crossref Google Scholar
[13]

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.
Crossref Google Scholar
[14]

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.
Crossref Google Scholar
[15]

H. Asefi, S. Shahparvari, P. Chhetri, and S. Lim, Variable fleet size and mix VRP with fleet heterogeneity in integrated solid waste management, J. Clean. Prod., vol. 230, pp. 1376–1395, 2019.
Crossref Google Scholar
[16]

L. Liu and W. Liao, Optimization and profit distribution in a two-echelon collaborative waste collection routing problem from economic and environmental perspective, Waste Manag., vol. 120, pp. 400–414, 2021.
Crossref Google Scholar
[17]

M. Rabbani, H. Farrokhi-asl, and H. Rafiei, A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments, J. Intell. Fuzzy Syst., vol. 30, no. 3, pp. 1817–1830, 2016.
Crossref Google Scholar
[18]

L. C. Coelho and G. Laporte, Classification, models and exact algorithms for multi-compartment delivery problems, Eur. J. Oper. Res., vol. 242, no. 3, pp. 854–864, 2015.
Crossref Google Scholar
[19]

L. Wang, J. Kinable, and T. V. Woensel, The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips, Comput. Oper. Res., vol. 118, p. 104904, 2020.
Crossref Google Scholar
[20]

M. Ostermeier and A. Hübner, Vehicle selection for a multi-compartment vehicle routing problem, Eur. J. Oper. Res., vol. 269, no. 2, pp. 682–694, 2018.
Crossref Google Scholar
[21]

R. Lahyani, L. C. Coelho, M. Khemakhem, G. Laporte, and F. Semet, A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia, Omega, vol. 51, pp. 1–10, 2015.
Crossref Google Scholar
[22]

R. Eshtehadi, E. Demir, and Y. Huang, Solving the vehicle routing problem with multi-compartment vehicles for city logistics, Comput. Oper. Res., vol. 115, p. 104859, 2020.
Crossref Google Scholar
[23]

K. Heßler, Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes, Eur. J. Oper. Res., vol. 294, no. 1, pp. 188–205, 2021.
Crossref Google Scholar
[24]

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.
Crossref Google Scholar
[25]

M. Keskin and B. Çatay, A matheuristic method for the electric vehicle routing problem with time windows and fast chargers, Comput. Oper. Res., vol. 100, pp. 172–188, 2018.
Crossref Google Scholar
[26]

G. Macrina, L. D. P. Pugliese, F. Guerriero, and G. Laporte, The green mixed fleet vehicle routing problem with partial battery recharging and time windows, Comput. Oper. Res., vol. 101, pp. 183–199, 2019.
Crossref Google Scholar
[27]

M. Keskin, G. Laporte, and B. Çatay, Electric vehicle routing problem with time-dependent waiting times at recharging stations, Comput. Oper. Res., vol. 107, pp. 77–94, 2019.
Crossref Google Scholar
[28]

D. Goeke and M. Schneider, Routing a mixed fleet of electric and conventional vehicles, Eur. J. Oper. Res., vol. 245, no. 1, pp. 81–99, 2015.
Crossref Google Scholar
[29]

M. Ostermeier, T. Henke, A. Hübner, and G. Wäscher, Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions, Eur. J. Oper. Res., vol. 292, no. 3, pp. 799–817, 2021.
Crossref Google Scholar
[30]

Y. Shen, L. Peng, and J. Li, An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem, J. Syst. Eng. Electron., vol. 32, no. 2, pp. 365–379, 2021.
Crossref Google Scholar
[31]

M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst., Man, Cybern. B, vol. 26, no. 1, pp. 29–41, 1996.
Crossref Google Scholar
[32]

Z. Liu, F. Tian, L. Li, Z. Han, and Y. Li, Product search algorithm based on improved ant colony optimization in a distributed network, International Journal of Crowd Science, vol. 6, no. 3, pp. 128–134, 2022.
Crossref Google Scholar
[33]

R. Elshaer and H. Awad, A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants, Comput. Ind. Eng., vol. 140, p. 106242, 2020.
Crossref Google Scholar
[34]

N. A. Kyriakakis, M. Marinaki, and Y. Marinakis, A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem, Comput. Oper. Res., vol. 134, p. 105397, 2021.
Crossref Google Scholar
[35]

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, Transp. Res. Part D Transp. Environ., vol. 57, pp. 422–457, 2017.
Crossref Google Scholar
[36]

Y. Wu, F. Pan, S. Li, Z. Chen, and M. Dong, Peer-induced fairness capacitated vehicle routing scheduling using a hybrid optimization ACO-VNS algorithm, Soft Comput. A Fusion Found. Methodol. Appl., vol. 24, no. 3, pp. 2201–2213, 2020.
Crossref Google Scholar
[37]

M. A. Islam and Y. Gajpal, Optimization of conventional and green vehicles composition under carbon emission cap, Sustainability, vol. 13, no. 12, p. 6940, 2021.
Crossref Google Scholar
International Journal of Crowd Science
Volume 8 Issue 3,
September 2024
Pages 130-139
DOI: 10.26599/IJCS.2023.9100030
Cite this article:
Liu Z, Sun L, Zuo X, et al. Heterogeneous Electric Vehicle Routing Problem with Multiple Compartments and Multiple Trips for the Collection of Classified Waste. International Journal of Crowd Science, 2024, 8(3): 130-139. https://doi.org/10.26599/IJCS.2023.9100030

123

Views

11

Downloads

0

Crossref

0

Scopus

Altmetrics
Received: 28 March 2023
Revised: 24 October 2023
Accepted: 13 November 2023
Published: 19 August 2024
© 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