A greedy heuristic method for minimising the number of transfers in a rapid transit network

Resumen

A modication of the extended rapid transit network design problem has recently been stated. Given a set of potential station locations and a set of potential links between them, this problem basically consists in selecting which stations and links to construct without exceeding the available budget, and determining a number of lines from them provided that whichever two locations are linked by one line at most, to maximise the total expected number of users. A two-stage approach has also been presented for solving this problem. In the rst stage an integer model is solved for selecting the stations and links to be constructed. In the second stage each selected link is assigned to a unique line, so that the number of lines going through each selected station is minimised. We present a greedy heuristic alternative method for the second stage above that attempts to minimise the number of transfers that should be done by the users to arrive at their destinations.