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

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.





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.