The strength of flow refueling location problem formulations and an extension to cyclic routing
4OR · 11.06.2026
DOI: 10.1007/s10288-026-00617-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift 4OR, online erschienen am 11.06.2026. Verfasst von Nagisa Sugishita und 2 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Gefördert von: NSERC, Hydro-Québec.
Abstract (Originalsprache)
The Flow Refueling Location Problem (FRLP) is a stylized model for determining the optimal placement of refueling stations for vehicles with limited travel ranges, such as hydrogen fuel cell vehicles and electric vehicles. A notable extension, the deviation FRLP, accounts for the possibility that drivers may deviate from their preferred routes to refuel or recharge. While solution techniques based on various mathematical programming formulations have been thoroughly explored for this extension, there is a lack of theoretical insights into the relationships and strengths of these formulations. In this work, for the deviation extension, we study two prominent FRLP formulations from the literature and compare their strengths in terms of linear programming (LP) relaxations. We show that the LP relaxation of one formulation yields a bound that is at least as tight as that of the other, which may explain its observed superior performance. Building on these insights, we address a common modeling assumption in the FRLP that requires drivers to use the same paths for their outbound and inbound trips. Specifically, we relax this assumption and introduce the cyclic FRLP, where drivers may use different paths in each direction. We show how existing formulations can be naturally extended to accommodate this setting and describe a branch-and-cut algorithm to solve the problem. We provide numerical experiments highlighting the benefits of such asymmetric routing. For example, in an instance based on the Californian network, the cyclic FRLP serves all demands using 30% fewer facilities than the original FRLP.
Förderung
- NSERC
- Hydro-Québec
Zitieren
APA
Sugishita, N., Carvalho, M., & Atallah, R. (2026). The strength of flow refueling location problem formulations and an extension to cyclic routing. 4OR. https://doi.org/10.1007/s10288-026-00617-2
Vancouver
Sugishita N, Carvalho M, Atallah R. The strength of flow refueling location problem formulations and an extension to cyclic routing. 4OR. 2026. doi:10.1007/s10288-026-00617-2
BibTeX
@article{Sugishita2026,
author = {Sugishita, Nagisa and Carvalho, Margarida and Atallah, Ribal},
title = {The strength of flow refueling location problem formulations and an extension to cyclic routing},
journal = {4OR},
year = {2026},
doi = {10.1007/s10288-026-00617-2}
}
EUVIMED