A Branch-and-Cut Algorithm for the Alternative Fuel Refueling Station Location Problem with Routing

Because of the limited range of alternative fuel vehicles (AFVs) and the sparsity of the available alternative refueling stations (AFSs), AFV drivers cooperatively deviate from their paths to refuel. This deviation is bounded by the drivers’ tolerance. Taking this behavior into account, the refueling station location problem with routing (RSLP-R) is defined as maximizing the AFV flow that can be accommodated in a road network by locating a given number of AFSs while respecting the range limitation of the vehicles and the deviation tolerance of the drivers. In this study, we develop a natural model for the RSLP-R based on the notion of length-bounded cuts, analyze the polyhedral properties of this model, and develop a branch-and-cut algorithm as an exact solution approach. Extensive computational experiments show that the algorithm significantly improves the solution times with respect to previously developed exact solution methods and extends the size of the instances solved to optimality. Using our methodology, we investigate the tradeoffs between covered vehicle flow and deviation tolerance of the drivers and present insights on deviation characteristics of drivers in a case study in California.