Vehicle Routing Problem with Mixed Fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs

Authors: Ons Sassi, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara

Abstract:

In this paper, we consider the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles and time dependent charging costs, denoted VRP-HFCC, in which a set of geographically scattered customers have to be served by a mixed fleet of vehicles composed of a heterogenous fleet of Electric Vehicles (EVs), having different battery capacities and operating costs, and Conventional Vehicles (CVs). We include the possibility of charging EVs in the available charging stations during the routes in order to serve all customers. Each charging station offers charging service with a known technology of chargers and time dependent charging costs. Charging stations are also subject to operating time windows constraints. EVs are not necessarily compatible with all available charging technologies and a partial charging is allowed. Intermittent charging at the depot is also allowed provided that constraints related to the electricity grid are satisfied. The objective is to minimize the number of employed vehicles and then minimize the total travel and charging costs. In this study, we present a Mixed Integer Programming Model and develop a Charging Routing Heuristic and a Local Search Heuristic based on the Inject-Eject routine with different insertion methods. All heuristics are tested on real data instances.

Keywords: charging problem, electric vehicle, heuristics, local search, optimization, routing problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1099756

References:

[1] K. Aissat and A. Oulamara, “A posteriori approach of real-time rideshar- ing problem with intermediate locations,” in proceedings of ICORES 2015, 2015.
[2] O. Sassi and A. Oulamara, “Simultaneous electric vehicles scheduling and optimal charging in the business context: Case study.” IET, 2014.
[3] O. Sassi and Oulamara, “Joint scheduling and optimal charging of elec- tric vehicles problem,” in Computational Science and Its Applications– ICCSA 2014. Springer, 2014, pp. 76–91.
[4] S. Pelletier, O. Jabali, and G. Laporte, “Goods distribution with electric vehicles: Review and research perspectives,” 2014.
[5] M. Ramezani, M. Graf, and H. Vogt, “A simulation environment for smart charging of electric vehicles using a multi-objective evolutionary algorithm,” in Information and Communication on Technology for the Fight against Global Warming, vol. ICT-GLOW 2011, LNCS 6868, 2011, p. pp. 5663.
[6] J. Lee, G. Park, H. Kwak, and H. Jeon, “Design of an energy con- sumption scheduler based on genetic algorithms in the smart grid,” in Computational Collective Intelligence. Technologies and Applications, vol. ICCCI 2011, Part I, LNCS 6922, 2011, p. 438447.
[7] J. Kang, S. J. Duncan, and D. N. Mavris, “Real-time scheduling tech- niques for electric vehicle charging in support of frequency regulation,” Procedia Computer Science, vol. 16, pp. 767 –775, 2013.
[8] P. Toth and D. Vigo, The vehicle routing problem. Siam, 2001.
[9] C. B. e. P. W.Ramdane cherif, M. Haj Rachid, “New notation and classification scheme for vehicle routing problems,” RAIRO, vol. DOI 10.1051/ro/2014030, p. To appear, 2014.
[10] A. Artmeier, J. Haselmayr, M. Leucker, and M. Sachenbacher, “The optimal routing problem in the context of battery-powered electric vehicles,” in Workshop CROCS at CPAIOR-10, 2nd International Work- shop on Constraint Reasoning and Optimization for Computational Sustainability, 2010.
[11] S. Erdogan and E. Miller-Hooks, “A green vehicle routing problem,” Transport. Res., vol. Part E 48, pp. 100–114, 2012.
[12] C. Lin, K. Choy, G. Ho, S. Chung, and H. Lam, “Survey of green vehicle routing problem: Past and future trends,” Expert. Syst. Appl., vol. 41, pp. 1118–1138, 2014.
[13] M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle routing problem with time windows and recharging stations,” University of Kaiserslautern, Germany, Tech. Rep., 2012.
[14] D. Goeke, M. Schneider, and D. S. E. A. Professorship, “Routing a mixed fleet of electric and conventional vehicles,” Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL), Tech. Rep., 2014.
[15] G. Hiermann, J. Puchinger, and R. F. Hartl, “The electric fleet size and mix vehicle routing problem with time windows and recharging stations,” Working Paper. Accessed July 17, 2014. URL: h ttp://prolog. univie. ac. at/research/publications/downloads/Hie 2014 638. pdf, Tech. Rep., 2014.
[16] A´ . Felipe, M. T. Ortun˜o, G. Righini, and G. Tirado, “A heuristic ap- proach for the green vehicle routing problem with multiple technologies and partial recharges,” Transportation Research Part E: Logistics and Transportation Review, vol. 71, pp. 111–128, 2014.
[17] S. Bashash, S. J. Moura, J. C. Forman, and H. K. Fathy, “Plug-in hybrid electric vehicle charge pattern optimization for energy cost and battery longevity,” Journal of Power Sources, vol. 196, pp. 541–549, 2010.
[18] A. Millner, “Modeling lithium ion battery degradation in electric vehi- cles,” in Innovative Technologies for an Efficient and Reliable Electricity Supply (CITRES), 2010 IEEE Conference on. IEEE, 2010, pp. 349–356.
[19] R. Hassin and A. Keinan, “Greedy heuristics with regret, with applica- tion to the cheapest insertion algorithm for the tsp,” Operations Research Letters, vol. 36, no. 2, pp. 243–246, 2008.
[20] M. Dell’Amico, M. Monaci, C. Pagani, and D. Vigo, “Heuristic ap- proaches for the fleet size and mix vehicle routing problem with time windows,” Transportation Science, vol. 41, no. 4, pp. 516–526, 2007.