A survey-based approach for designing the lines of a rapid transit network

In this work we present an approach for designing the lines of a rapid transit network. Given the stations to be constructed and the links between them, a set of lines is generated by utilizing a greedy heuristic procedure that, taking into account the transfers that should be made by the users to arrive at their destinations, attempts to maximize an estimation for the number of trips through the rapid transit network. This estimation is done by means of a modification of the well-known Floyd–Warshall algorithm. The main contributions are the consideration of the results from a survey amongst the potential users of the rapid transit network, and the contemplation of the possibility of linking certain pairs of station locations by more than one line. We also report some computational experience on several randomly generated instances that shows that our approach can obtain better line designs and handle instances of larger size than some other procedures taken from the literature.