Electric vehicle routing problem with backhauls considering charging station location and distribution system operation

  • Luis Carlos Cubides Universidad Tecnológica de Pereira
  • Andrés Arias Londoño Universidad Tecnológica de Pereira
  • Mauricio Granada Echeverri Universidad Tecnológica de Pereira
Keywords: Electric vehicles, smart grids, multi-objetive optimization, mixed integer lineal programming, distribution network


Logistics companies are largely encouraged to make greener their operations through an efficient solution with electric vehicles (EVs). However, the driving range is one of the limiting aspects for the introduction of EVs in logistics fleet, due to the low capacity provided by the batteries to perform the routes. In this regards, it is necessary to set up a framework to virtually increase this battery capacity by locating EV charging stations (EVCSs) along the transportation network for the completion of their routes. By the other side, the Distribution Network Operators (DNOs) express the concern associated with the inclusion of new power demands to be attended (installation of EVCSs) in the Distribution Network (DN), without reducing the optimal power supply management for the end-users. Under these circumstances, in this paper the Electric Vehicle Routing Problem with Backhauls and optimal operation of the Distribution Network (EVRPB-DN) is introduced and formulated as a mixed-integer linear programming model, considering the operation of the DN in conditions of maximum power demand. Different candidate points for the EVs charging are considered to recharge the battery at the end of the linehaul route or during the backhaul route. The problem is formulated as a multi-objective approach where the transportation and power distribution networks operation are modeled. The performance and effectiveness of the proposed formulation is tested in VRPB instance datasets and DN test systems from the literature. Pareto fronts for each instance are presented, using the ε-constraint methodology.


Download data is not yet available.

Author Biographies

Luis Carlos Cubides, Universidad Tecnológica de Pereira

MsC in Electrical Engineering, Program of Electrical Engineering, Technological University of Pereira, Pereira-Colombia, lccubides@utp.edu.co

Andrés Arias Londoño, Universidad Tecnológica de Pereira

PhD. in Engineering, Program of Electrical Engineering, Technological University of Pereira, Pereira-Colombia, andresarias@utp.edu.co

Mauricio Granada Echeverri, Universidad Tecnológica de Pereira

PhD in Electrical Engineering, Program of Electrical Engineering, Technological University of Pereira, Pereira-Colombia, magra@utp.edu.co


[1] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications, vol. 18. Society for Industrial and Applied Mathematics, 2014.
[2] S. Ropke and D. Pisinger, “A unified heuristic for a large class of Vehicle RoutingPproblems with Backhauls,” Eur. J. Oper. Res., vol. 171, no. 3, pp. 750–775, 2006.
[3] M. Goetschalckx and C. Jacobs-Blecha, “The vehicle routing problem with backhauls,” Eur. J. Oper. Res., vol. 42, no. 1, pp. 39–51, 1989.
[4] M. L. Fisher, R. Jaikumar, and L. N. Van Wassenhove, “A multiplier adjustment method for the generalized assignment problem,” Manage. Sci., vol. 32, no. 9, pp. 1095–1103, 1986.
[5] P. Toth and D. Vigo, “An exact algorithm for the vehicle routing problem with backhauls,” Transp. Sci., vol. 31, no. 4, pp. 372–385, 1997.
[6] A. Mingozzi, S. Giorgi, and R. Baldacci, “An exact method for the vehicle routing problem with backhauls,” Transp. Sci., vol. 33, no. 3, pp. 315–329, 1999.
[7] C. H. Dharmakeerthi, N. Mithulananthan, and T. K. Saha, “Modeling and planning of EV fast charging station in power grid,” in 2012 IEEE Power and Energy Society General Meeting, 2012, pp. 1–8.
[8] Z. Liu, F. Wen, and G. Ledwich, “Optimal Planning of Electric-Vehicle Charging Stations in Distribution Systems,” IEEE Trans. Power Deliv., vol. 28, no. 1, pp. 102–110, Jan. 2013.
[9] G. Wang, Z. Xu, F. Wen, and K. P. Wong, “Traffic-Constrained Multiobjective Planning of Electric-Vehicle Charging Stations,” IEEE Trans. Power Deliv., vol. 28, no. 4, pp. 2363–2372, Oct. 2013.
[10] J. C. Paz, M. Granada-Echeverri, and J. Willmer Escobar, “The multi-depot electric vehicle location routing problem with time windows,” Int. J. Ind. Eng. Comput., vol. 9, no. 1, pp. 123–136, 2018.
[11] A. Arias, M. Granada, and C. A. Castro, “Optimal probabilistic charging of electric vehicles in distribution systems,” IET Electr. Syst. Transp., vol. 7, no. 3, pp. 246–251, Sep. 2017.
[12] R. G. Conrad and M. A. Figliozzi, “The recharging vehicle routing problem,” in Proceedings of the 2011 Industrial Engineering Research Conference, 2011, p. 8.
[13] D. Goeke and M. Schneider, “Routing a mixed fleet of electric and conventional vehicles,” Eur. J. Oper. Res., vol. 245, no. 1, pp. 81–99, Aug. 2015.
[14] W. Feng and M. Figliozzi, “An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: A case study from the USA market,” Transp. Res. Part C Emerg. Technol., vol. 26, pp. 135–145, Jan. 2013.
[15] M. Schiffer and G. Walther, “The electric location routing problem with time windows and partial recharging,” Eur. J. Oper. Res., vol. 260, no. 3, pp. 995–1013, Aug. 2017.
[16] M. Pfriem and F. Gauterin, “Less range as a possible solution for the market success of electric vehicles in commercial fleets,” in 2013 World Electric Vehicle Symposium and Exhibition (EVS27), 2013, pp. 1–8.
[17] J. Martínez-Lao, F. G. Montoya, M. G. Montoya, and F. Manzano-Agugliaro, “Electric vehicles in Spain: An overview of charging systems,” Renew. Sustain. Energy Rev., vol. 77, pp. 970–983, Sep. 2017.
[18] A. R. AbulaWafa, A. ElaGarably, and W. A. F. Mohamed, “Impacts of uncoordinated and coordinated integration of electric vehicles on distribution systems performance,” in 2017 Nineteenth International Middle East Power Systems Conference (MEPCON), 2017, pp. 337–364.
[19] J. F. Franco, M. Sanchez, M. J. Rider, and others, “Un modelo de optimización no lineal para el problema de la recarga de vehículos eléctricos híbridos en sistemas de distribución,” in The 10-Th Latin-American Congress On Electricity Generation and Transmission - CLAGTEE 2013, 2013, pp. 1–6.
[20] N. Z. Xu and C. Y. Chung, “Reliability Evaluation of Distribution Systems Including Vehicle-to-Home and Vehicle-to-Grid,” IEEE Trans. Power Syst., vol. 31, no. 1, pp. 759–768, Jan. 2016.
[21] J. F. Franco, M. J. Rider, M. Lavorato, and R. Romero, “Optimal Conductor Size Selection and Reconductoring in Radial Distribution Systems Using a Mixed-Integer LP Approach,” IEEE Trans. Power Syst., vol. 28, no. 1, pp. 10–20, Feb. 2013.
[22] Y. Shi, T. Sun, and D. Feng, “The economic impact of electric vehicle routing and charging strategy on traffic-power integrated networks,” in IECON 2017 - 43rd Annual Conference of the IEEE Industrial Electronics Society, 2017, pp. 453–458.
[23] Y. V Haimes, “On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization,” IEEE Trans. Syst. Man. Cybern., vol. SMC-1, no. 3, pp. 296–297, Jul. 1971.
[24] A. T. Pozos, M. L. de Oliveira, J. F. F. Baquero, and M. J. R. Flores, “A mixed-binary linear formulation for the distribution system expansion planning problem,” in 2014 IEEE PES Transmission & Distribution Conference and Exposition - Latin America (PES T&D-LA), 2014, pp. 1–6.
[25] R. Fourer, D. M. Gay, and B. W. Kernighan, “A Modeling Language for Mathematical Programming,” Manage. Sci., vol. 36, no. 5, pp. 519–554, May 1990.
[26] S. Civanlar, J. J. Grainger, H. Yin, and S. S. H. Lee, “Distribution feeder reconfiguration for loss reduction,” IEEE Trans. Power Deliv., vol. 3, no. 3, pp. 1217–1223, Jul. 1988.
How to Cite
Cubides, L., Arias Londoño, A., & Granada Echeverri, M. (2019). Electric vehicle routing problem with backhauls considering charging station location and distribution system operation. TecnoLógicas, 22(44), 1-20. Retrieved from https://revistas.itm.edu.co/index.php/tecnologicas/article/view/1186
Research Papers