A Clustering Approach for the Optimal Siting of Recharging Stations in the Electric Vehicle Routing Problem with Time Windows

Danny García Sánchez, Alejandra Tabares, Lucas Teles Faria, Juan Carlos Rivera and John Fredy Franco
Additional contact information
Danny García Sánchez: Department of Electrical Engineering, São Paulo State University (UNESP), Ilha Solteira, São Paulo 15385-000, Brazil
Alejandra Tabares: Department of Industrial Engineering, Los Andes University, Bogotá 111711, Colombia
Lucas Teles Faria: Department of Energy Engineering, São Paulo State University (UNESP), Rosana, São Paulo 19274-000, Brazil
Juan Carlos Rivera: Department of Mathematical Sciences, EAFIT University, Medellín 050022, Colombia
John Fredy Franco: Department of Electrical Engineering, São Paulo State University (UNESP), Ilha Solteira, São Paulo 15385-000, Brazil

Energies, 2022, vol. 15, issue 7, 1-19

Abstract: Transportation has been incorporating electric vehicles (EVs) progressively. EVs do not produce air or noise pollution, and they have high energy efficiency and low maintenance costs. In this context, the development of efficient techniques to overcome the vehicle routing problem becomes crucial with the proliferation of EVs. The vehicle routing problem concerns the freight capacity and battery autonomy limitations in different delivery-service scenarios, and the challenge of best locating recharging stations. This work proposes a mixed-integer linear programming model to solve the electric location routing problem with time windows (E-LRPTW) considering the state of charge, freight and battery capacities, and customer time windows in the decision model. A clustering strategy based on the k-means algorithm is proposed to divide the set of vertices (EVs) into small areas and define potential sites for recharging stations, while reducing the number of binary variables. The proposed model for E-LRPTW was implemented in Python and solved using mathematical modeling language AMPL together with CPLEX. Performed tests on instances with 5 and 10 clients showed a large reduction in the time required to find the solution (by about 60 times in one instance). It is concluded that the strategy of dividing customers by sectors has the potential to be applied and generate solutions for larger geographical areas and numbers of recharging stations, and determine recharging station locations as part of planning decisions in more realistic scenarios.

Keywords: charging stations; electric vehicles; k-means algorithm; location routing problem with time windows; mixed-integer linear programming; vehicle routing (search for similar items in EconPapers)
JEL-codes: Q Q0 Q4 Q40 Q41 Q42 Q43 Q47 Q48 Q49 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://www.mdpi.com/1996-1073/15/7/2372/pdf (application/pdf)
https://www.mdpi.com/1996-1073/15/7/2372/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jeners:v:15:y:2022:i:7:p:2372-:d:778533

Access Statistics for this article

Energies is currently edited by Ms. Agatha Cao

More articles in Energies from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().