Stochastic capacity constraints in the flow-refueling location problem with variable driving range

Environmental concerns have led to rapid developments regarding the ow-refueling location problem (FRLP), the problem of positioning refueling stations in a road network as to maximise the volume of traffic that is able to successfully complete its trip. Though several stochastic versions of the FRLP have been proposed, increasing model realism by accounting for a variable driving range, so far no probabilistic models with capacitated stations exist. In this paper we argue why ordinary capacity constraints are overly restrictive in a stochastic setting, and derive a novel set of constraints that overcomes this issue by modelling the expected traffic volume that refuels at each station. As the resulting model is highly complex, an intuitive heuristic approach is presented. Numerical experiments on random networks suggest that using stochastic capacity constraints as compared to deterministic ones alters the optimal location choice and leads to substantial gains in covered traffic volume. The heuristic is shown to achieve near-optimal solutions in reduced time on small instances, whilst slightly outperforming the exact solution approach on large instances.