Integer Linear Programming Formulations for the Problem of Minimum Allocation of Charging Stations

This work studies a variant of the Minimum Allocation Problem of Charging Stations (MIN-STATION) and a generalization of this variant. In the problem considered, it is sought to determine a minimum set of intermediate vertices for the installation of charging stations that allows driving unlabeled robots, with limited autonomy, from a set of origins to a set of destinations. The problem is recent, NP-difficult in general graphs and not yet addressed by Integer Linear Programming (PLI). A PLI-based, flow-based formulation on a range digraph is proposed. Next, a formulation for a generalization is presented that incorporates installation costs, heterogeneous autonomies and eligibility criteria between origins and destinations. In the experiments, the generalized formulation is parameterized to represent the base version, allowing the comparison of the performance of the two formulations in transport networks.