International Journal of Crowd Science 2024, 8(1): 38-48 https://doi.org/10.26599/IJCS.2023.9100017

Open Access | Issue | Published: 27 February 2024

Multi-Compartment Electric Vehicle Routing Problem for Perishable Products

Show Author's Information Hide Author's Information Zhishuo Liu^¹(

), Yuqing Li^¹, Junzhe Xu^¹, Donglu Bai^¹

1School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Keywords:

electric vehicle, vehicle routing problem, multiple compartments, cold chain logistics, heterogeneous fleet, hybrid ant colony optimization

Cite this article:

Liu Z, Li Y, Xu J, et al. Multi-Compartment Electric Vehicle Routing Problem for Perishable Products. International Journal of Crowd Science, 2024, 8(1): 38-48. https://doi.org/10.26599/IJCS.2023.9100017

Download citation

EndNote(RIS)

BibTeX

115

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

N/A

CSCD

Abstract Full text About this article

Abstract

The study first proposes a heterogeneous fleet, multi-compartment electric vehicle routing problem for perishable products (MCEVRP-PP). We capture a lot of practical demands and constraints of the MCEVRP-PP, such as multiple temperature zones, the hard time window, charging more than once during delivery, various power consumption per unit of refrigeration, etc. We model the MCEVRP-PP as a mixed integer program and aim to optimize the total cost including vehicle fixed cost, power cost, and cooling cost. A hybrid ant colony optimization (HACO) is developed to solve the problem. In the transfer rule, the time window is introduced to improve flexibility in route construction. According to the features of multi-compartment electric vehicles, the capacity constraint judgment algorithm is developed in route construction. Six local search strategies are designed with time windows, recharging stations, etc. Experiments based on various instances validate that HACO solves MCEVRP-PP more effectively than the ant colony optimization (ACO). Compared with fuel vehicles and single-compartment vehicles, electric vehicles and multi-compartment electric vehicles can save the total cost and mileage, and increase utilization of vehicles.

Full text

Abstract

Full text

Outline

About this article

Multi-Compartment Electric Vehicle Routing Problem for Perishable Products

Show Author's information Hide Author's Information Zhishuo Liu^¹(

), Yuqing Li^¹, Junzhe Xu^¹, Donglu Bai^¹

1School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Abstract

Keywords: electric vehicle, vehicle routing problem, multiple compartments, cold chain logistics, heterogeneous fleet, hybrid ant colony optimization

References(41)

[1]

A. Osvald and L. Z. Stirn, A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food, J. Food Eng., vol. 85, no. 2, pp. 285–295, 2008.

DOI Google Scholar

[2]

K. Govindan, A. Jafarian, R. Khodaverdi, and K. Devika, Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food, Int. J. Prod. Econ., vol. 152, pp. 9–28, 2014.

DOI Google Scholar

[3]

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.

DOI Google Scholar

[4]

S. Wang, F. Tao, Y. Shi, and H. Wen, Optimization of vehicle routing problem with time windows for cold chain logistics based on carbon tax, Sustainability, vol. 9, no. 5, p. 694, 2017.

DOI Google Scholar

[5]

M. Babagolzadeh, A. Shrestha, B. Abbasi, Y. Zhang, A. Woodhead, and A. Zhang, Sustainable cold supply chain management under demand uncertainty and carbon tax regulation, Transp. Res. Part D Transp. Environ., vol. 80, p. 102245, 2020.

DOI Google Scholar

[6]

M. A. Figliozzi, The impacts of congestion on time-definitive urban freight distribution networks CO₂ emission levels: Results from a case study in Portland, Oregon, Transp. Res. Part C Emerg. Technol., vol. 19, no. 5, pp. 766–778, 2011.

DOI Google Scholar

[7]

P. Amorim, S. N. Parragh, F. Sperandio, and B. Almada-Lobo, A rich vehicle routing problem dealing with perishable food: A case study, TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, vol. 22, no. 2, pp. 489–508, 2014.

DOI Google Scholar

[8]

X. Wang, M. Wang, J. Ruan, and H. Zhan, The multi-objective optimization for perishable food distribution route considering temporal-spatial distance, Procedia Comput. Sci., vol. 96, no. 9, pp. 1211–1220, 2016.

DOI Google Scholar

[9]

P. Li, J. He, D. Zheng, Y. Huang, and C. Fan, Vehicle routing problem with soft time windows based on improved genetic algorithm for fruits and vegetables distribution, Discrete Dyn. Nat. Soc., vol. 2015, pp. 1–8, 2015.

DOI Google Scholar

[10]

N. Al Theeb, H. J. Smadi, T. H. Al-Hawari, and M. H. Aljarrah, Optimization of vehicle routing with inventory allocation problems in Cold Supply Chain Logistics, Comput. Ind. Eng., vol. 142, p. 106341, 2020.

DOI Google Scholar

[11]

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.

DOI Google Scholar

[12]

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

DOI Google Scholar

[13]

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.

DOI Google Scholar

[14]

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.

DOI Google Scholar

[15]

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.

DOI Google Scholar

[16]

A. E. Fallahi, C. Prins, and R. W. Calvo, A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, Comput. Oper. Res., vol. 35, no. 5, pp. 1725–1741, 2008.

DOI Google Scholar

[17]

J. E. Mendoza, B. Castanier, C. Guéret, A. L. Medaglia, and N. Velasco, Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands, Transp. Sci., vol. 45, no. 3, pp. 346–363, 2011.

DOI Google Scholar

[18]

M. Alinaghian and N. Shokouhi, Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search, Omega, vol. 76, pp. 85–99, 2018.

DOI Google Scholar

[19]

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.

DOI Google Scholar

[20]

J. Chen and J. Shi, A multi-compartment vehicle routing problem with time windows for urban distribution—A comparison study on particle swarm optimization algorithms, Comput. Ind. Eng., vol. 133, pp. 95–106, 2019.

DOI Google Scholar

[21]

P. Avella, M. Boccia, and A. Sforza, Solving a fuel delivery problem by heuristic and exact approaches, Eur. J. Oper. Res., vol. 152, no. 1, pp. 170–179, 2004.

DOI Google Scholar

[22]

F. Cornillier, F. F. Boctor, G. Laporte, and J. Renaud, An exact algorithm for the petrol station replenishment problem, J. Oper. Res. Soc., vol. 59, no. 5, pp. 607–615, 2008.

DOI Google Scholar

[23]

F. Cornillier, F. F. Boctor, G. Laporte, and J. Renaud, A heuristic for the multi-period petrol station replenishment problem, Eur. J. Oper. Res., vol. 191, no. 2, pp. 295–305, 2008.

DOI Google Scholar

[24]

F. Cornillier, G. Laporte, F. F. Boctor, and J. Renaud, The petrol station replenishment problem with time windows, Comput. Oper. Res., vol. 36, no. 3, pp. 919–935, 2009.

DOI Google Scholar

[25]

F. Cornillier, F. Boctor, and J. Renaud, Heuristics for the multi-depot petrol station replenishment problem with time windows, Eur. J. Oper. Res., vol. 220, no. 2, pp. 361–369, 2012.

DOI Google Scholar

[26]

S. Efthymiadis, N. Liapis, and G. Nenes, Solving a heterogeneous fleet multi-compartment vehicle routing problem: A case study, Int. J. Syst. Sci. Oper. Logist., vol. 10, no. 1, p. 2190474, 2023.

DOI Google Scholar

[27]

L. Chen, Y. Liu, and A. Langevin, A multi-compartment vehicle routing problem in cold-chain distribution, Comput. Oper. Res., vol. 111, pp. 58–66, 2019.

DOI Google Scholar

[28]

S. Martins, M. Ostermeier, P. Amorim, A. Hübner, and B. Almada-Lobo, Product-oriented time window assignment for a multi-compartment vehicle routing problem, Eur. J. Oper. Res., vol. 276, no. 3, pp. 893–909, 2019.

DOI Google Scholar

[29]

M. Bruglieri, F. Pezzella, O. Pisacane, and S. Suraci, A variable neighborhood search branching for the electric vehicle routing problem with time windows, Electron. Notes Discrete Math., vol. 47, pp. 221–228, 2015.

DOI Google Scholar

[30]

M. Keskin and B. Çatay, Partial recharge strategies for the electric vehicle routing problem with time windows, Transp. Res. Part C Emerg. Technol., vol. 65, pp. 111–127, 2016.

DOI Google Scholar

[31]

M. Erdem and Ç. Koç, Analysis of electric vehicles in home health care routing problem, J. Clean. Prod., vol. 234, pp. 1471–1483, 2019.

DOI Google Scholar

[32]

T. Erdelić, T. Carić, M. Erdelić, and L. Tišljarić, Electric vehicle routing problem with single or multiple recharges, Transp. Res. Procedia, vol. 40, pp. 217–224, 2019.

DOI Google Scholar

[33]

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.

DOI Google Scholar

[34]

A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, The electric vehicle routing problem with nonlinear charging function, Transp. Res. Part B Methodol., vol. 103, pp. 87–110, 2017.

DOI Google Scholar

[35]

X. Zuo, Y. Xiao, M. You, I. Kaku, and Y. Xu, A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function, J. Clean. Prod., vol. 236, p. 117687, 2019.

DOI Google Scholar

[36]

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.

DOI Google Scholar

[37]

A. Verma, Electric vehicle routing problem with time windows, recharging stations and battery swapping stations, EURO J. Transp. Logist., vol. 7, no. 4, pp. 415–451, 2018.

DOI Google Scholar

[38]

Z. Liu, X. Zuo, M. Zhou, W. Guan, and Y. Al-Turki, Electric vehicle routing problem with variable vehicle speed and soft time windows for perishable product delivery, IEEE Trans. Intell. Transp. Syst., vol. 24, no. 6, pp. 6178–6190, 2023.

DOI Google Scholar

[39]

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.

DOI Google Scholar

[40]

S. Zhang, M. Chen, and W. Zhang, A novel location-routing problem in electric vehicle transportation with stochastic demands, J. Clean. Prod., vol. 221, pp. 567–581, 2019.

DOI Google Scholar

[41]

Y. Xiao, X. Zuo, I. Kaku, S. Zhou, and X. Pan, Development of energy consumption optimization model for the electric vehicle routing problem with time windows, J. Clean. Prod., vol. 225, pp. 647–663, 2019.

DOI Google Scholar

About this article

Publication history

Rights and permissions

Publication history

Received: 23 May 2023

Revised: 03 October 2023

Accepted: 05 October 2023

Published: 27 February 2024

Issue date: March 2024

Copyright

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/).