Journal Home > Volume 2 , Issue 1
Complex System Modeling and Simulation 2022, 2(1): 18-34 https://doi.org/10.23919/CSMS.2022.0005
Open Access | Issue | Published: 30 March 2022

Robust Electric Vehicle Routing Problem with Time Windows under Demand Uncertainty and Weight-Related Energy Consumption

Show Author's Information Yindong Shen1( ),  Leqin Yu1,  Jingpeng Li2
Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
Division of Computer Science and Mathematics, University of Stirling, Stirling, FK9 4LA, UK
Keywords:
electric vehicle routing problem, time windows, uncertain demand, energy consumption model, robust optimization, adaptive large neighbourhood search
Cite this article:
Shen Y, Yu L, Li J. Robust Electric Vehicle Routing Problem with Time Windows under Demand Uncertainty and Weight-Related Energy Consumption. Complex System Modeling and Simulation, 2022, 2(1): 18-34. https://doi.org/10.23919/CSMS.2022.0005
Download citation
EndNote(RIS)
BibTeX

959

Views

848

Downloads

Citations

10

Crossref

N/A

WoS

11

Scopus

N/A

CSCD

Abstract Full text About this article

Vehicle routing problem with time windows (VRPTW) is a core combinatorial optimization problem in distribution tasks. The electric vehicle routing problem with time windows under demand uncertainty and weight-related energy consumption is an extension of the VRPTW. Although some researchers have studied either the electric VRPTW with nonlinear energy consumption model or the impact of the uncertain customer demand on the conventional vehicles, the literature on the integration of uncertain demand and energy consumption of electric vehicles is still scarce. However, practically, it is usually not feasible to ignore the uncertainty of customer demand and the weight-related energy consumption of electronic vehicles (EVs) in actual operation. Hence, we propose the robust optimization model based on a route-related uncertain set to tackle this problem. Moreover, adaptive large neighbourhood search heuristic has been developed to solve the problem due to the NP-hard nature of the problem. The effectiveness of the method is verified by experiments, and the influence of uncertain demand and uncertain parameters on the solution is further explored.


menu
Abstract
Full text
Outline
About this article

Robust Electric Vehicle Routing Problem with Time Windows under Demand Uncertainty and Weight-Related Energy Consumption

Show Author's information Yindong Shen1( ), Leqin Yu1, Jingpeng Li2
Key Laboratory of Image Processing and Intelligent Control, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
Division of Computer Science and Mathematics, University of Stirling, Stirling, FK9 4LA, UK

Abstract

Vehicle routing problem with time windows (VRPTW) is a core combinatorial optimization problem in distribution tasks. The electric vehicle routing problem with time windows under demand uncertainty and weight-related energy consumption is an extension of the VRPTW. Although some researchers have studied either the electric VRPTW with nonlinear energy consumption model or the impact of the uncertain customer demand on the conventional vehicles, the literature on the integration of uncertain demand and energy consumption of electric vehicles is still scarce. However, practically, it is usually not feasible to ignore the uncertainty of customer demand and the weight-related energy consumption of electronic vehicles (EVs) in actual operation. Hence, we propose the robust optimization model based on a route-related uncertain set to tackle this problem. Moreover, adaptive large neighbourhood search heuristic has been developed to solve the problem due to the NP-hard nature of the problem. The effectiveness of the method is verified by experiments, and the influence of uncertain demand and uncertain parameters on the solution is further explored.

Keywords: electric vehicle routing problem, time windows, uncertain demand, energy consumption model, robust optimization, adaptive large neighbourhood search

References(38)

1

M. Keskin and B. Çatay, Partial recharge strategies for the electric vehicle routing problem with time windows, Transportation Research Part C:Emerging Technologies, vol. 65, pp. 111–127, 2016.
DOI Google Scholar
2

G. B. Dantzig and J. H. Ramser, The truck dispatching problem, Management Science, vol. 6, no. 1, pp. 80–91, 1959.
DOI Google Scholar
3

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.
DOI Google Scholar
4
P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications, Second Edition. Philadelphia, PA, USA: SIAM, 2014.https://doi.org/10.1137/1.9781611973594
DOI
5

O. Bräysy and M. Gendreau, Vehicle routing problem with time windows, part I: Route construction and local search algorithms, Transportation Science, vol. 39, no. 1, pp. 104–118, 2005.
DOI Google Scholar
6

O. Bräysy and M. Gendreau, Vehicle routing problem with time windows, part II: Metaheuristics, Transportation Science, vol. 39, no. 1, pp. 119–139, 2005.
DOI Google Scholar
7
R. G. Conrad and M. A. Figliozzi, The recharging vehicle routing problem, presented at 2011 Industrial Engineering Research Conference, Norcross, GA, USA, 2011.
8

S. Erdoğan and E. Miller-Hooks, A green vehicle routing problem, Transportation Science, vol. 48, no. 1, pp. 100–114, 2012.
DOI Google Scholar
9

M. Schneider, A. Stenger, and D. Goeke, The electric vehicle-routing problem with time windows and recharging stations, Transportation Science, vol. 48, no. 4, pp. 500–520, 2014.
DOI Google Scholar
10

Y. Shen, L. Peng, and J. Li, An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem, Journal of Systems Engineering and Electronics, vol. 32, no. 2, pp. 365–379, 2021.
DOI Google Scholar
11

M. Keskin and B. Çatay, A matheuristic method for the electric vehicle routing problem with time windows and fast chargers, Computers&Operations Research, vol. 100, pp. 172–188, 2018.
DOI Google Scholar
12
R. Zhang, J. Guo, and J. Wang, A time-dependent electric vehicle routing problem with congestion tolls, IEEE Transactions on Engineering Management, doi: 10.1109/TEM.2019.2959701.https://doi.org/10.1109/TEM.2019.2959701
DOI
13

T. Bektaş and G. Laporte, The pollution-routing problem, Transportation Research Part B:Methodological, vol. 45, no. 8, pp. 1232–1250, 2011.
DOI Google Scholar
14
H. Preis, S. Frank, and K. Nachtigall, Energy-optimized routing of electric vehicles in urban delivery systems, in Operations Research Proceedings 2012, S. Heiber, M. Breitner, D. Rösch, C. Schön, J. –M. G. von der Schulenburg, P. Sibbertsen, M. Steinbach, S. Weber, and A. Wolter, eds. Berlin, Germany: Springer, 2014, pp. 583–588.https://doi.org/10.1007/978-3-319-00795-3_87
DOI
15

D. Goeke and M. Schneider, Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, vol. 245, no. 1, pp. 81–99, 2015.
DOI Google Scholar
16

P. Lebeau, C. De Cauwer, J. Van Mierlo, C. Macharis, W. Verbeke, and T. Coosemans, Conventional, hybrid, or electric vehicles: Which technology for an urban distribution centre? The Scientific World Journal, vol. 2015, p. 302867, 2015.
DOI Google Scholar
17

S. Pelletier, O. Jabali, and G. Laporte, The electric vehicle routing problem with energy consumption uncertainty, Transportation Research Part B:Methodological, vol. 126, pp. 225–255, 2019.
DOI Google Scholar
18
H. L. Ong, B. W. Ang, T. N. Goh, and C. C. Deng, A vehicle routing and scheduling problem with time windows and stochastic demand constraints, Asia Pacific Journal of Operational Research, vol. 14, no. 1, pp. 1−17, 1997.
19

M. S. Chang, A vehicle routing problem with time windows and stochastic demands, Journal of the Chinese Institute of Engineers, vol. 28, no. 5, pp. 783–794, 2005.
DOI Google Scholar
20

H. Lei, G. Laporte, and B. Guo, The capacitated vehicle routing problem with stochastic demands and time windows, Computers&Operations Research, vol. 38, no. 12, pp. 1775–1783, 2011.
DOI Google Scholar
21

J. Zhang, W. H. K. Lam, and B. Y. Chen, On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows, European Journal of Operational Research, vol. 249, no. 1, pp. 144–154, 2016.
DOI Google Scholar
22

E. Berhan, B. Beshah, D. Kitaw, and A. Abraham, Stochastic vehicle routing problem: A literature survey, Journal of Information&Knowledge Management, vol. 13, no. 3, p. 1450022, 2014.
DOI Google Scholar
23
M. Gendreau, O. Jabali, and W. Rei, Chapter 8: Stochastic vehicle routing problems, in Vehicle Routing: Problem, Methods, and Applications, Second Edition, P. Toth and D. Vigo, eds. Philadelphia, PA, USA: SIAM, 2014, pp. 213–239.https://doi.org/10.1137/1.9781611973594.ch8
DOI
24

M. Gendreau, O. Jabali, and W. Rei, Future research directions in stochastic vehicle routing, Transportation Science, vol. 50, no. 4, pp. 1163–1173, 2016.
DOI Google Scholar
25

U. Ritzinger, J. Puchinger, and R. F. Hartl, A survey on dynamic and stochastic vehicle routing problems, International Journal of Production Research, vol. 54, no. 1, pp. 215–231, 2016.
DOI Google Scholar
26

J. Oyola, H. Arntzen, and D. L. Woodruff, The stochastic vehicle routing problem, a literature review, part I: Models, Euro Journal on Transportation and Logistics, vol. 7, no. 3, pp. 193–221, 2017.
DOI Google Scholar
27

J. Oyola, H. Arntzen, and D. L. Woodruff, The stochastic vehicle routing problem, a literature review, part II: Solution methods, Euro Journal on Transportation and Logs, vol. 6, no. 4, pp. 349–388, 2017.
DOI Google Scholar
28

I. Sungur, F. Ordóñez, and M. Dessouky, A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Transactions, vol. 40, no. 5, pp. 509–523, 2008.
DOI Google Scholar
29

C. Lee, K. Lee, and S. Park, Robust vehicle routing problem with deadlines and travel time/demand uncertainty, Journal of the Operational Research Society, vol. 63, no. 9, pp. 1294–1306, 2012.
DOI Google Scholar
30

C. E. Gounaris, W. Wiesemann, and C. A. Floudas, The robust capacitated vehicle routing problem under demand uncertainty, Operations Research, vol. 61, no. 3, pp. 677–693, 2013.
DOI Google Scholar
31

C. E. Gounaris, P. P. Repoussis, C. D. Tarantilis, W. Wiesemann, and C. A. Floudas, An adaptive memory programming framework for the robust capacitated vehicle routing problem, Transportation Science, vol. 50, no. 4, pp. 1239–1260, 2014.
DOI Google Scholar
32

C. Hu, J. Lu, X. Liu, and G. Zhang, Robust vehicle routing problem with hard time windows under demand and travel time uncertainty, Computers&Operations Research, vol. 94, pp. 139–153, 2018.
DOI Google Scholar
33

P. Munari, A. Moreno, J. D. L. Vega, D. Alem, and J. Gondzio, The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method, Transportation Science, vol. 53, no. 4, pp. 1043–1066, 2019.
DOI Google Scholar
34

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, vol. 40, no. 4, pp. 455–472, 2006.
DOI Google Scholar
35

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Computers&Operations Research, vol. 34, no. 8, pp. 2403–2435, 2007.
DOI Google Scholar
36

D. Taş, N. Dellaert, T. van Woensel, and T. de Kok, The time-dependent vehicle routing problem with soft time windows and stochastic travel times, Transportation Research Part C:Emerging Technologies, vol. 48, pp. 66–83, 2014.
DOI Google Scholar
37

E. Demir, T. Bektas, and G. Laporte, An adaptive large neighbourhood search heuristic for the pollution-routing problem, European Journal of Operational Research, vol. 223, no. 2, pp. 346–359, 2012.
DOI Google Scholar
38

Z. Yu, P. Zhang, Y. Yu, W. Sun, and M. Huang, An adaptive large neighborhood search for the larger-scale instances of green vehicle routing problem with time windows, Complexity, vol. 2020, p. 8210630, 2020.
DOI Google Scholar
Publication history
Copyright
Rights and permissions

Publication history

Published: 30 March 2022
Issue date: March 2022

Copyright

© The author(s) 2022

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