An approach for solving a modification of the extended rapid transit network design problem

In this paper we deal with a slight modification of the extended rapid transit network design problem to allow circular lines. A two-stage approach is proposed for solving this problem. In the first stage, an integer model is solved for selecting the stations to be constructed and the links between them. It drastically reduces the dimension of a modification of a 0–1 model given in the literature to adapt it to our problem. In the second stage, the line design problem is solved by means of a procedure that assigns each selected link to exactly one line under certain constraints. We report some computational experiments that show that our approach also produces a drastic reduction on the computational effort required for solving the modification of the 0–1 model given in the literature.