Abstract
In this paper, we address the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles, denoted VRP-MFHEV. This problem is motivated by a real-life industrial application and it is defined by a mixed fleet of heterogenous Electric Vehicles (EVs) having distinct battery capacities and operating costs, and identical Conventional Vehicles (CVs) that could be used to serve a set of geographically scattered customers. The EVs could be charged during their trips at the depot and in the available charging stations, which offer charging with a given technology of chargers and propose different charging costs. EVs are subject to the compatibility constraints with the available charging technologies and they could be partially charged. The objective is to minimize the number of employed vehicles and to minimize the total travel and charging costs. To solve the VRP-MFHEV, we propose a Multi-Start Iterated Tabu Search (ITS) based on Large Neighborhood Search (LNS). The LNS is used in the tabu search of the intensification phase and the diversification phase of the ITS. Different implementation schemes of the proposed method including best-improvement and first-improvement strategies, are tested on generalized benchmark instances. The computational results show that ITS produces competitive results, with respect to results obtained in previous studies, while the computational time remains reasonable for each instance. Moreover, using LNS in the intensification phase of ITS seems improving the generated solutions compared to using other neighborhood search procedures such as 2opt.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Aissat, K., Oulamara, A.: A posteriori approach of real-time ridesharing problem with intermediate locations. In: Proceedings of ICORES 2015 (2015)
Sassi, O., Oulamara, A.: Simultaneous electric vehicles scheduling and optimal charging in the business context: Case study. In: IET, IET (2014)
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)
Erdogan, S., Miller-Hooks, E.: A green vehicle routing problem. Transport. Res. Part E 48, 100–114 (2012)
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)
Schneider, M., Stenger, A., Goeke, D.: The electric vehicle routing problem with time windows and recharging stations. Technical report, University of Kaiserslautern, Germany (2012)
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)
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 (accessed July 17, 2014), http://prolog.univie.ac.at/research/publications/downloads/Hie_2014_638.pdf (2014)
Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G.: A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review 71, 111–128 (2014)
Sassi, O., Oulamara, A.: Joint scheduling and optimal charging of electric vehicles problem. In: Murgante, B., et al. (eds.) ICCSA 2014, Part II. LNCS, vol. 8580, pp. 76–91. Springer, Heidelberg (2014)
Sassi, O., Cherif-Khettaf, W.R., Oulamara, A.: Multi-start iterated local search for the mixed fleet vehicle routing problem with heterogenous electric vehicles. In: Ochoa, G., Chicano, F. (eds.) EvoCOP 2015. LNCS, vol. 9026, pp. 138–149. Springer, Heidelberg (2015)
Sassi, O., Ramdane Cherif-Khettaf, W., Oulamara, A.: Vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles and time dependent charging costs. Technical report, hal-01083966 (2014)
Misevičius, A.: Using iterated tabu search for the traveling salesman problem. Information Technology and Control 32, 29–40 (2004)
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)
Pisinger, D., Ropke, S.: Large neighborhood search. In: Handbook of metaheuristics, pp. 399–419. Springer (2010)
Li, F., Golden, B., Wasil, E.: A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers & Operations Research 34, 2734–2742 (2007)
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). Iterated Tabu Search for the Mix Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles. In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management Sciences. Advances in Intelligent Systems and Computing, vol 359. Springer, Cham. https://doi.org/10.1007/978-3-319-18161-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-18161-5_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18160-8
Online ISBN: 978-3-319-18161-5
eBook Packages: EngineeringEngineering (R0)