On designing connected rapid transit networks reducing the number of transfers
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 4, pp. 315-338.

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.

DOI : 10.1051/ro/2011116
Classification : 90B06, 90B80, 90C10, 90C35
Mots-clés : station and link location, line designing, degree of a node, transfer, greedy heuristic procedure 
@article{RO_2011__45_4_315_0,
     author = {Escudero, Laureano Fernando and Mu\~noz, Susana},
     title = {On designing connected rapid transit networks reducing the number of transfers},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {315--338},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {4},
     year = {2011},
     doi = {10.1051/ro/2011116},
     mrnumber = {2881358},
     zbl = {1235.90024},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2011116/}
}
TY  - JOUR
AU  - Escudero, Laureano Fernando
AU  - Muñoz, Susana
TI  - On designing connected rapid transit networks reducing the number of transfers
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2011
SP  - 315
EP  - 338
VL  - 45
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2011116/
DO  - 10.1051/ro/2011116
LA  - en
ID  - RO_2011__45_4_315_0
ER  - 
%0 Journal Article
%A Escudero, Laureano Fernando
%A Muñoz, Susana
%T On designing connected rapid transit networks reducing the number of transfers
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2011
%P 315-338
%V 45
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2011116/
%R 10.1051/ro/2011116
%G en
%F RO_2011__45_4_315_0
Escudero, Laureano Fernando; Muñoz, Susana. On designing connected rapid transit networks reducing the number of transfers. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 4, pp. 315-338. doi : 10.1051/ro/2011116. http://archive.numdam.org/articles/10.1051/ro/2011116/

[1] M.H. Baaj and H.S. Mahmassani, An AI-based approach for transit route system planning and design. J. Adv. Transp. 25 (1991) 187-209.

[2] M.R. Bussieck, P. Kreuzer and U.T. Zimmermann, Optimal lines for railway systems. Eur. J. Oper. Res. 96 (1997) 54-63. | Zbl

[3] M.R. Bussieck, T. Winter and U.T. Zimmermann, Discrete optimization in public rail transport. Math. Program. 79 (1997) 415-444. | MR | Zbl

[4] M. Cepeda, R. Cominetti and M. Florian, A frequency-based assignment model for congested transit networks with strict capacity constraints : characterization and computation of equilibria. Transp. Res. Part B 40 (2006) 437-459.

[5] L.F. Escudero and S. Muñoz, An approach for solving a modification of the extended rapid transit network design problem. Top 17 (2009) 320-334. | MR | Zbl

[6] L.F. Escudero and S. Muñoz, An approach for designing connected rapid transit networks considering transfers. Technical Reports on Statistics and Decision Sciences TR09/01, Universidad Rey Juan Carlos, Móstoles, Madrid, Spain (2009).

[7] R. García, A. Garzón-Astolfi, Á. Marín, J.A. Mesa and F.A. Ortega, Analysis of the parameters of transfers in rapid transit network design, in 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, edited by L.G. Kroon and R.H. Möhring, Oasics 2. Saarbrücken (2006). | Zbl

[8] J.F. Guan, H. Yang and S.C. Wirasinghe, Simultaneous optimization of transit line configuration and passenger line assignment. Transp. Res. Part B 40 (2006) 885-902.

[9] V. Guihaire and J.K. Hao, Transit network design and scheduling : A global review. Transp. Res. Part A 42 (2008) 1251-1273.

[10] G. Laporte, Á. Marín, J.A. Mesa and F. Perea, Designing robust rapid transit networks with alternative routes. J. Adv. Transp. 45 (2011) 54-65.

[11] G. Laporte, J.A. Mesa, F.A. Ortega and F. Perea, Planning rapid transit networks. Socio-Econ. Plan. Sci. 45 (2011) 95-104. | Zbl

[12] G. Laporte, J.A. Mesa, F.A. Ortega and I. Sevillano, Maximizing trip coverage in the location of a single rapid transit alignment. Ann. Oper. Res. 136 (2005) 49-63. | MR | Zbl

[13] C.E. Mandl, Evaluation and optimization of urban public transportation networks. Eur. J. Oper. Res. 5 (1980) 396-404. | MR | Zbl

[14] Á. Marín, An extension to rapid transit network design problem. Top 15 (2007) 231-241. | MR | Zbl

[15] Á. Marín and R. García-Ródenas, Location of infrastructure in urban railway networks. Comput. Oper. Res. 36 (2009) 1461-1477. | Zbl

[16] H. Spiess and M. Florian, Optimal strategies : A new assignment model for transit networks. Transp. Res. Part B 23 (1989) 83-102.

[17] J.G. Wardrop, Some theoretical aspects of road traffic research. ICE Proceeding Engineering Divisions 1 (1952) 325-362.

Cité par Sources :