Portrait of Nagisa Sugishita

Nagisa Sugishita

Postdoctorate - HEC Montréal
Supervisor
Margarida Carvalho
Research Topics
Optimization

Publications

The Strength of Flow Refueling Location Problem Formulations and an Extension to Cyclic Routing
Nagisa Sugishita
Margarida Carvalho
Ribal Atallah
The Flow Refueling Location Problem (FRLP) is a stylized model for determining the optimal placement of refueling stations for vehicles with… (see more) 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.
2024-09-06
ArXiv (preprint)
arxiv.org
arxiv.org
The Strength of Fuel Refueling Location Problem Formulations
Nagisa Sugishita
Margarida Carvalho
Ribal Atallah
2024-09-06
ArXiv (preprint)
arxiv.org
arxiv.org