The Multi-Stop Station Location Problem: Exact Approaches

The multi-stop station location problem (MSLP) aims to place stations such that a set of trips is feasible with respect to length bounds while minimizing cost. Each trip consists of a sequence of stops that must be visited in a given order, and a length bound that controls the maximum length that is possible without visiting a station. Installing stations and detours cause costs that are to be minimized. The MSLP relates to problems in transportation and telecommunications where strategic decisions (such as the placement of charging stations) depend on operational considerations (such as offering a certain set of planned trips). In this paper, we introduce exact approaches to solve the MSLP to optimality. First, we introduce an arc-based mixed-integer program (MIP) that captures the problem and can be solved with any MIP solver. In addition, we propose pattern-based formulations that we solve by branch-price-and-cut. We conduct experiments on randomly generated instances to evaluate the performance of our approaches and show that the pattern-based formulations outperform the compact MIP formulation. In addition, we show that a nested branch-price-and-cut approach is able to solve a practically relevant instance in the context of siting charging stations for an intercity bus service.