1920

A new model for minimizing the electric vehicle battery capacity in electric travelling salesman problem with time windows

The growing pollution in the environment and the negative shift in the global climate compel authorities to take action to protect the environment and human health. Transportation is one of the major contributors to this environmental decay. The harmful gases released to the air by the vehicles using petroleum fuel increase each day. One of the solutions is to make a gradual transition to electric vehicles. A major part of manufacturing an electric vehicle is to produce an efficient electric motor and battery for it. Reducing the manufacturing and operating costs of these components will result in reducing the overall costs of electric vehicles. In this study, a new variant of the electric travelling salesman problem with time windows (E-TSPTW) was proposed. The objective function of the problem is to minimize the required initial battery capacity of the electric vehicle. For this goal, a new energy consumption model considering the load of the vehicle was proposed with three scenarios. The proposed model was solved with a hybrid simulated annealing algorithm for all these scenarios. The performance of the proposed method was compared to the solutions found by a mixed integer linear programming model. The experimental results on the benchmark instances show that up to a 35% reduction in initial battery capacity, hence reduction in its cost is possible.

PDF

___

[1] Zhu M, Liu Z, Li J, Zhu SX. Electric vehicle battery capacity allocation and recycling with downstream competition. European Journal of Operational Research 2020; 283 (1): 365-379. doi: 10.1016/j.ejor.2019.10.040
[2] Juan AA, Mendez CA, Faulin J, De Armas J, Grasman SE. Electric vehicles in logistics and transportation: A survey on emerging environmental, strategic, and operational challenges. Energies 2016; 9 (2): 86. doi: 10.3390/en9020086
[3] Pelletier S, Jabali O, Laporte G. 50th anniversary invited article—goods distribution with electric vehicles: review and research perspectives. Transportation Science 2015; 50 (1): 3-22. doi: 10.1287/trsc.2015.0646
[4] Shaukat N, Khan B, Ali SM, Mehmood CA, Khan J et al. a survey on electric vehicle transportation within smart grid system. Renewable and Sustainable Energy Reviews 2018; 81: 1329–1349. doi: 10.1016/j.rser.2017.05.092
[5] Hu S, Chen P, Xin F, Xie C. Exploring the effect of battery capacity on electric vehicle sharing programs using a simulation approach. Transportation Research Part D: Transport and Environment 2019; 77: 164-177. doi: 10.1016/j.trd.2019.10.013
[6] Roberti R, Wen M. The electric traveling salesman problem with time windows. Transportation Research Part E: Logistics and Transportation Review 2016; 89: 32-52. doi: 10.1016/j.tre.2016.01.010
[7] Küçükoğlu İ, Dewil R, Cattrysse D. Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates. Expert Systems with Applications 2019; 134: 279-303. doi: 10.1016/j.eswa.2019.05.037
[8] Baek D, Chen Y, Macii E, Poncino M, Chang N. Battery-aware electric truck delivery route planner. In: IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED); Lausanne, Switzerland; 2019. pp. 1-6. doi: 10.1109/ISLPED.2019.8824835
[9] Erdogdu K, Karabulut K. Distance and energy consumption minimization in electric traveling salesman problem with time windows. In: 7th International Conference on Electrical and Electronics Engineering (ICEEE); Antalya, Turkey; 2020. pp. 160-164. doi: 10.1109/ICEEE49618.2020.9102602
[10] Potvin JY, Bengio S. The vehicle routing problem with time windows part II: genetic search. INFORMS Journal on Computing 1996; 8 (2): 165-172. doi: 10.1287/ijoc.8.2.165
[11] Doppstadt C, Koberstein A, Vigo D. The hybrid electric vehicle—traveling salesman problem with time windows. European Journal of Operational Research 2020; 284 (2): 675-692. doi: 10.1016/j.ejor.2019.12.031
[12] Goeke D, Schneider M. Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research 2015; 245 (1): 81-99. doi: 10.1016/j.ejor.2015.01.049
[13] Keskin M, Çatay B. Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies 2016; 65: 111-127. doi: 10.1016/j.trc.2016.01.013
[14] Cortés-Murcia DL, Prodhon C, Afsar HM. The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transportation Research Part E: Logistics and Transportation Review 2019; 130: 184-206. doi: 10.1016/j.tre.2019.08.015
[15] Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 1987; 35 (2): 254-265. doi: 10.1287/opre.35.2.254
[16] Xiao Y, Zuo X, Kaku I, Zhou S, Pan X. Development of energy consumption optimization model for the electric vehicle routing problem with time windows. Journal of Cleaner Production 2019; 225: 647-663. doi: 10.1016/j.jclepro.2019.03.323
[17] Macrina G, Laporte G, Guerriero F, Pugliese LDP. An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows. European Journal of Operational Research 2019; 276 (3): 971-982. doi: 10.1016/j.ejor.2019.01.067
[18] Markel T, Simpson A. Cost-benefit analysis of plug-in hybrid electric vehicle technology. World Electric Vehicle Journal 2007; 1 (1): 294-301. doi: 10.3390/wevj1010294
[19] Savelsbergh MWP. Local search in routing problems with time windows. Annals of Operations Research 1985; 4 (1): 285-305. doi: 10.1007/BF02022044
[20] Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by Simulated Annealing. Science 1983; 220 (4598): 671-680. doi: 10.1126/science.220.4598.671
[21] Kalyanmoy D. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering 2000; 186 (2): 311-338. doi: 10.1016/S0045-7825(99)00389-8
[22] Gendreau M, Hertz A, Laporte G, Stan M. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research 1998; 46 (3): 330-346. doi: 10.1287/opre.46.3.330