  The energy transition in transportation benefits from demand-based models to
determine the optimal placement of refueling stations for alternative fuel
vehicles such as battery electric trucks. A formulation known as the refueling
station location problem with routing (RSLP-R) is concerned with minimizing the
number of stations necessary to cover a set of origin-destination trips such
that the transit time does not exceed a given threshold. In this paper we
extend the RSLP-R by station capacities to limit the number of vehicles that
can be refueled at individual stations. The solution to the capacitated RSLP-R
(CRSLP-R) avoids congestion of refueling stations by satisfying capacity
constraints. We devise two optimization methods to deal with the increased
difficulty to solve the CRSLP-R. The first method extends a prior
branch-and-cut approach and the second method is a branch-cut-and-price
algorithm based on variables associated with feasible routes. We evaluate both
our methods on instances from the literature as well as a newly constructed
network and find that the relative performance of the algorithms depends on the
strictness of the capacity constraints. Furthermore, we show some runtime
improvements over prior work on uncapacitated instances.
