On designing connected rapid transit networks reducing the number of transfers

¹ Departamento de Estadística e Investigación Operativa, Universidad Rey Juan Carlos, 28933 Móstoles ( Madrid), Spain
laureano.escudero@urjc.es
² Corresponding author. Departamento de Estadística e Investigación Operativa, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid, 28040 Madrid, Spain
smunoz@estad.ucm.es

Received: 25 October 2010
Accepted: 1 December 2011

Abstract

In this paper we introduce some improvements on an approach that we described elsewhere for solving a modification of the well-known extended rapid transit network design problem. Firstly, we propose an integer programming model for selecting the stations to be constructed and the links between them, in such a way that a connected rapid transit network is obtained. Secondly, we consider a linear 0-1 programming model for determining a route of minimum length in the rapid transit network between certain pairs of locations, and present a greedy heuristic procedure which attempts to minimize an estimation of the total number of transfers that should be made by the users to arrive at their destinations. We also report several computational experiments that show that this procedure can significantly reduce the estimated total number of transfers required for the solutions obtained using our previous approach.