Abstract
This paper deals with a real world application that consists in the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles including new constraints, denoted VRP-HFCC. This problem is defined by a set of customers that have to be served by a mixed fleet of vehicles composed of heterogenous fleet of Electric Vehicles (EVs) with distinct battery capacities and operating costs, and a set of identical Conventional Vehicles (CVs). The EVs could be charged during their trips in the available charging stations, which offer charging with a given technology of chargers and time dependent charging costs. Charging stations are also subject to operating time windows constraints. EVs are subject to the compatibility constraints with the available charging technologies and they could be partially charged. 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 to minimize the total travel and charging costs. The developed multi-start algorithm is based on the Iterated Local Search metaheuristic which uses a Large Neighborhood Search with two different insertion strategies in the Local Search procedure. Different implementation schemes of the proposed method are tested on a set of real data instances with up to 550 customers as well as on generalized benchmark instances.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
Aissat, K., Oulamara, A.: A posteriori approach of real-time ridesharing problem with intermediate locations. In: proceedings of ICORES 2015 (2015)
Artmeier, A., Haselmayr, J., Leucker, M., Sachenbacher, M.: The optimal routing problem in the context of battery-powered electric vehicles. In: Workshop CROCS at CPAIOR-10, 2nd International Workshop on Constraint Reasoning and Optimization for Computational Sustainability (2010)
Bashash, S., Moura, S.J., Forman, J.C., Fathy, H.K.: Plug-in hybrid electric vehicle charge pattern optimization for energy cost and battery longevity. J. Power Sources 196, 541–549 (2010)
Erdogan, S., Miller-Hooks, E.: A green vehicle routing problem. Transp. Res. Part E 48, 100–114 (2012)
Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G.: A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transp. Res. Part E Logistics. Transp. Rev. 71, 111–128 (2014)
Goeke, D., Schneider, M., Professorship, D.S.E.A.: Routing a mixed fleet of electric and conventional vehicles. Technical report, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL) (2014)
Hassin, R., Keinan, A.: Greedy heuristics with regret, with application to the cheapest insertion algorithm for the tsp. Oper. Res. Lett. 36(2), 243–246 (2008)
Hiermann, G., Puchinger, J., Hartl, R.F.: The electric fleet size and mix vehicle routing problem with time windows and recharging stations. Technical report, Working Paper (2014). http://prolog.univie.ac.at/research/publications/downloads/Hie_2014_638.pdf. Accessed 17 July 2014
Lin, C., Choy, K., Ho, G., Chung, S., Lam, H.: Survey of green vehicle routing problem: Past and future trends. Expert. Syst. Appl. 41, 1118–1138 (2014)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated Local Search. Springer, New York (2003)
Millner, A.: Modeling lithium ion battery degradation in electric vehicles. In: 2010 IEEE Conference on Innovative Technologies for an Efficient and Reliable Electricity Supply (CITRES), pp. 349–356. IEEE (2010)
Pisinger, D., Ropke, S.: Large neighborhood search. Handbook of Metaheuristics, pp. 399–419. Springer, New York (2010)
Sassi, O., Oulamara, A.: Joint scheduling and optimal charging of electric vehicles problem. In: Murgante, B., Misra, S., Rocha, A.M.A.C., Torre, C., Rocha, J.G., Falcão, M.I., Taniar, D., Apduhan, B.O., Gervasi, O. (eds.) ICCSA 2014, Part II. LNCS, vol. 8580, pp. 76–91. Springer, Heidelberg (2014)
Schneider, M., Stenger, A., Goeke, D.: The electric vehicle routing problem with time windows and recharging stations. Technical report, University of Kaiserslautern, Germany (2012)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998)
Ramdane cherif, W., Haj Rachid, M., Bloch, C., Chatonnay, P.: New notation and classification scheme for vehicle routing problems. RAIRO (2014, to appear). doi:10.1051/ro/2014030
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Sassi, O., Cherif-Khettaf, W.R., Oulamara, A. (2015). Multi-start Iterated Local Search for the Mixed Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles. In: Ochoa, G., Chicano, F. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2015. Lecture Notes in Computer Science(), vol 9026. Springer, Cham. https://doi.org/10.1007/978-3-319-16468-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-16468-7_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16467-0
Online ISBN: 978-3-319-16468-7
eBook Packages: Computer ScienceComputer Science (R0)