Efficient Heuristic Algorithms for Location of Charging Stations in
Electric Vehicle Routing Problems

Gustavo GATICA¹ , Gerardo AHUMADA¹, John Willmer ESCOBAR², Rodrigo LINFATI^3*
¹ Facultad de Ingeniería, Universidad Andres Bello, Santiago de Chile, 7591538, Chile
ggatica@unab.cl
²Departamento de Contabilidad y Finanzas, Universidad del Valle, Cali, 760001, Colombia
john.wilmer.escobar@correounivalle.edu.co
³Departamento de Ingeniería Industrial, Universidad del Bío-Bío, Concepción, 4030000, Chile
rlinfati@ubiobio.cl (^*Corresponding author), Chile

ABSTRACT: Eco-responsible transportation contributes at making a difference for companies devoted to product delivery operations. Two specific problems related to operations are the location of charging stations and the routing of electric vehicles. The first one involves locating new facilities on potential sites to minimise an objective function related to fixed and operational opening costs. The other one, electric vehicle routing problem, involves the consolidation of an electric-type fleet in order to meet a particular demand and some guidelines to optimise costs. It is determined by the distance travelled, considering the limited autonomy of the fleet, and can be restored by recharging its battery. The literature provides several solutions for locating and routing problems and contemplates restrictions that are closer to reality. However, there is an evident lack of techniques that addresses both issues simultaneously. The present article offers four solution strategies for the location of charging stations and a heuristic solution for fleet routing. The best results were obtained by applying the location strategy at the site of the client (relaxation of the VRP) to address the routing problem, but it must be considered that there are no displacements towards the recharges. Of all the other three proposals, K-means showed the best performance when locating the charging stations at the centroid of the cluster.

KEYWORDS: Heuristics, VRP, Electric vehicle, K-means.

>>FULL TEXT: PDF

CITE THIS PAPER AS:
Gustavo GATICA, Gerardo AHUMADA, John Willmer ESCOBAR, Rodrigo LINFATI^*, Efficient Heuristic Algorithms for Location of Charging Stations in Electric Vehicle Routing Problems, Studies in Informatics and Control, ISSN 1220-1766, vol. 27(1), pp. 73-82, 2018. https://doi.org/10.24846/v27i1y201808