A lexicographic optimization approach to the deviation-flow refueling station location problem on a general network

The problem of setting up an Alternative Fuel (AF) refueling infrastructure along traffic networks is gaining more interest as AF powered vehicles are becoming more popular due to environmental and economic reasons. This study addresses the refueling station location problem with allowed deviations on a general network. The primary objective is to maximize the amount of flow covered by a given number of stations. Unlike the common practice of having a predetermined set of candidate station locations that may not necessarily hold an optimal solution, this study considers the characteristics of the traffic network and vehicle driving range to discretize the continuous version of the problem and select a finite set of candidate locations that guarantees optimality. This is done by finding the greatest common divisor, g, of the lengths of all edges in the network and half of the vehicle driving range. We prove that there is always an optimal solution where all refueling stations are located at distances that are integer multiples of g from network vertices. This result is used to define refueling sets along the network. The endpoints of these sets are then considered as candidate locations. A secondary objective is introduced to minimize the total travel distance of covered flows. This bi-objective approach does not only optimize the utility of available resources by maximizing covered flows, but also improves convenience, lowers travel cost, and reduces greenhouse gas emissions by minimizing the total travel distance. Finally, a numerical example is provided to illustrate the proposed methods.