A dynamic programming based heuristic for locating stops in public transportation networks

• This paper investigates the maximum covering location problem in networks.
• We introduce a heuristic nested dynamic programming procedure, which:
• Is fast, i.e., instances with up to 5000 customers are solved under five seconds.
• Finds near-optimal solutions, i.e., the maximum gap over all 3750 instance is only 2.05%.
• Is flexible, i.e., it is shown how to apply the procedure to a wide range of problem extensions.

The length of journey towards a bus stop or railway station greatly influences passenger satisfaction and, thus, the utilization of public transport offers. In this context, we investigate the maximum covering location problem in networks (MCLPN) where stops (or stations) are to be located in a given railway or bus network, such that the number of passengers reaching a stop within their particular coverage radius is maximized. Up to now, no specialized solution procedure directly addressing MCLPN exists, instead it is mainly referred to the well-known maximum covering location problem (MCLP), which, however, neglects the underlaying information of the given network structure. This paper exploits the network information, introduces a fast and efficient two-stage dynamic programming based heuristic specifically tailored to MCLPN, and compares it to existing procedures for MCLP. The results show that our heuristic delivers near optimal solutions, i.e., 87% of our test instances are solved to optimality, within a few seconds of computational time.