Covering Population Areas by Railway Stops

We study the installation of new stops (or stations) along existing links in public transportation, e.g. railway systems. This improves the coverage level of the system, i.e., the number of people living near some stop. On the other hand, additional cost is incurred and travel times tend to increase. We model this as a network location problem, where the network corresponds to the transportation links. Our main contribution is to model the population distribution by a system of compact subsets in the plane, the population areas. The goal is to cover all these areas with as few stops as possible along the railway tracks.We present an efficient algorithm for finding an optimal solution in the case of a single edge and show its applicability to real world problems.