An approach for solving a modification of the extended rapid transit network design problem
Tóm tắt
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.
Tài liệu tham khảo
Bruno G, Gendreau M, Laporte G (2002) A heuristic for the location of a rapid transit line. Comput Oper Res 29:1–12
Bruno G, Ghiani G, Improta G (1998) A multi-modal approach to the location of a rapid transit line. Eur J Oper Res 104:321–332
Escudero LF, Muñoz S (2008) Improvements on the extended rapid transit network design problem modelling. Technical Reports on Statistics and Decision Sciences, TR08/01, Universidad Rey Juan Carlos, Spain
Gendreau M, Laporte G, Mesa JA (1995) Locating rapid transit lines. J Adv Transp 29:145–162
Hamacher HW, Liebers A, Schöbel A, Wagner D, Wagner F (2001) Locating new stops in a railway network. Electron Notes Theor Comput Sci 50:1–11
Laporte G, Marín Á, Mesa JA, Ortega FA (2007) An integrated methodology for the rapid transit network design problem. In: Geraets F, Kroon L, Schoebel A, Wagner D, Zaroliagis CD (eds) Algorithmic methods for railway optimization. Lect notes comput sci, vol 4359. Springer, Berlin, pp 187–199
Laporte G, Mesa JA, Ortega FA (1997) Assessing the efficiency of rapid transit configurations. Top 5:95–104
Laporte G, Mesa JA, Ortega FA (2002) Locating stations on rapid transit lines. Comput Oper Res 29:741–759
Laporte G, Mesa JA, Ortega FA, Sevillano I (2005) Maximizing trip coverage in the location of a single rapid transit alignment. Ann Oper Res 136:49–63
Marín Á (2007) An extension to rapid transit network design problem. Top 15:231–241
Marín Á, García-Ródenas R (2008) Location of infrastructure in urban railway networks. Comput Oper Res. doi:10.1016/j.cor.2008.02.008