Full cover charging station location problem with routing

Ömer Burak Kınay, Fatma Gzara and Sibel A. Alumur

Transportation Research Part B: Methodological, 2021, vol. 144, issue C, 1-22

Abstract: In this paper, a new full cover modeling framework is developed to design refueling station infrastructure, where the focus is on locating fast-charging stations for battery electric vehicles to enable long-distance transportation. A mathematical model is introduced to determine the optimal locations of these charging stations so that every origin-destination trip on a given transportation network is covered with respect to vehicle range. This full cover model allows deviations from the shortest paths and also determines an optimal route for each trip that requires the minimum total en route recharging. Two variants of this model are proposed: one that minimizes the total cost of locating charging stations and total en route recharging, and another that determines the locations of a predetermined number of stations to minimize the total en route recharging. Computational experiments performed on benchmark data sets validate that the proposed full cover models perform better than the maximum or set cover problem settings in the literature in terms of routing-related measures, such as total trip distance and maximum deviation from the shortest paths. A Benders decomposition algorithm is developed to optimally solve real-life instances of the problem. The Benders subproblem is identified as a many-to-many shortest path problem with an additional constraint that restricts the nodes that can be used to open facilities that are determined by the master problem. A new algorithmic methodology is developed to construct the dual solution for this subproblem and to generate non-dominated optimality cuts and strong valid inequalities for feasibility cuts. This novel algorithm accelerates the performance of the Benders algorithm up to 900 times over the tested large-size instances.

Keywords: Facility location; Refueling station; Charging station; Alternative fuel vehicles; Benders decomposition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261520304434
Full text for ScienceDirect subscribers only

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:eee:transb:v:144:y:2021:i:c:p:1-22

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2020.12.001

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().