×

zbMATH — the first resource for mathematics

An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem. (English) Zbl 1391.90049
Summary: We model and solve the railway rapid transit network design and line planning (RRTNDLP) problem, which integrates the two first stages in the railway planning process. The model incorporates costs relative to the network construction, fleet acquisition, train operation, rolling stock and personnel management. This implies decisions on line frequencies and train capacities since some costs depend on line operation. We assume the existence of an alternative transportation system (e.g., private car, bus, bicycle) competing with the railway system for each origin-destination pair. Passengers choose their transportation mode according to the best travel times. Since the problem is computationally intractable for realistic size instances, we develop an adaptive large neighborhood search (ALNS) algorithm, which can simultaneously handle the network design and line planning problems considering also rolling stock and personnel planning aspects. The ALNS performance is compared with state-of-the-art commercial solvers on a small-size artificial instance. In a second stream of experiments, the ALNS is used to design a railway rapid transit network in the city of Seville.

MSC:
90B06 Transportation, logistics and supply chain management
90B80 Discrete location and assignment
90C11 Mixed integer programming
90C10 Integer programming
90C90 Applications of mathematical programming
Software:
AlphaECP; Bonmin
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R. K.; Ergun, Ö.; Orlin, J. B.; Punnen, A. P., A survey of very large-scale neighborhood search techniques, Discr Appl Math, 123, 1, 75-102, (2002) · Zbl 1014.68052
[2] Blanco, V.; Puerto, J.; Ramos, A., Expanding the Spanish high-speed railway network, Omega, 39, 2, 138-150, (2011)
[3] Boisvert, R. F.; Howe, S. E.; Kahaner, D. K., Gams: a framework for the management of scientific software, ACM Trans Math Softw, 11, 4, 313-355, (1985) · Zbl 0587.68030
[4] Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C., An algorithmic framework for convex mixed integer nonlinear programs, Discr Optim, 5, 2, 186-204, (2008) · Zbl 1151.90028
[5] Brueckner, J. K., Transport subsidies, system choice and urban sprawl, Region Sci Urban Econ, 35, 6, 715-733, (2005)
[6] Bruno, G.; Gendreau, M.; Laporte, G., A heuristic for the location of a rapid transit line, Comput Oper Res, 29, 1-12, (2002) · Zbl 1026.90058
[7] Bruno, G.; Ghiani, G.; Improta, G., A multi-modal approach to the location of a rapid transit line, Eur J Oper Res, 104, 2, 321-332, (1998) · Zbl 0955.90058
[8] Bussieck, M.; Kreuzer, P.; Zimmermann, U., Optimal lines for railway systems, Eur J Oper Res, 96, 54-63, (1997) · Zbl 0926.90005
[9] Bussieck, M. R.; Lindner, T.; Lübbecke, M. E., A fast algorithm for near cost optimal line plans, Math Methods Oper Res, 59, 2, 205-220, (2004) · Zbl 1138.90434
[10] Canca, D.; Barrena, E.; Algaba, E.; Zarzo, A., Design and analysis of demand-adapted railway timetables, J Adv Transp, 48, 2, 119-137, (2014)
[11] Canca, D.; De-Los-Santos, A.; Laporte, G.; Mesa, J., A general rapid network design, line planning and fleet investment integrated model, Ann Oper Res, 35-53, (2014)
[12] Claessens, M. T.; van Dijk, N. M.; Zwaneveld, P. J., Cost optimal allocation of rail passenger lines, Eur J Oper Res, 110, 3, 474-489, (1998) · Zbl 0948.90097
[13] Coelho, L. C.; Cordeau, J.-F.; Laporte, G., The inventory-routing problem with transshipment, Comput Oper Res, 39, 11, 2537-2548, (2012) · Zbl 1251.90030
[14] Cordeau, J.-F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transp Sci, 32, 4, 380-404, (1998) · Zbl 0987.90507
[15] Cowie, J., The british passenger railway privatisationconclusions on subsidy and efficiency rom the first round of franchises, J Transp Econ Policy, 43, 1, 85-104, (2009)
[16] De-Los-Santos, A.; Laporte, G.; Mesa, J.; Perea, F., Simultaneous frequency and capacity setting in uncapacitated metro lines in presence of a competing mode, Transp Res Proc, 3, 289-298, (2014)
[17] Dufourd, H.; Gendreau, M.; Laporte, G., Locating a transit line using tabu search, Locat Sci, 4, 1-19, (1996) · Zbl 0927.90064
[18] Gallo, M.; Montella, B.; D’Acierno, L., The transit network design problem with elastic demand and internalisation of external costsan application to rail frequency optimisation, Transp Res Part C: Emerg Technol, 19, 6, 1276-1305, (2011)
[19] García-Archilla, B.; Lozano, A.; Mesa, J. A.; Perea, F., GRASP algorithms for the robust railway network design problem, J Heurist, 19, 2, 1-24, (2013) · Zbl 1365.90165
[20] García-Ródenas R, Garzón-Astolfi A, Marín A, Mesa JA, Ortega FA. Analysis of the parameters of transfers in rapid transit network design. In: Kroon L, Möhring R, editors, 5th Workshop on algorithmic methods and models for optimization of railways, Germany: Schloss Dagstuhl; 2006.
[21] Gendreau, M.; Laporte, G.; Mesa, J. A., Locating rapid transit lines, J Adv Transp, 29, 2, 145-162, (1995)
[22] Goossens, J.-. W.; van Hoesel, S.; Kroon, L., On solving multi-type railway line planning problems, Eur J Oper Res, 168, 2, 403-424, (2006) · Zbl 1101.90038
[23] Guan, J.; Yang, H.; Wirasinghe, S., Simultaneous optimization of transit line configuration and passenger line assignment, Transp Res Part BMethodol, 40, 10, 885-902, (2006)
[24] Guihaire, V.; Hao, J., Transit network design and schedulinga global review, Transp Res Part APolicy Pract, 42, 10, 1251-1273, (2008)
[25] Jeroslow R. and Lowe J. Modelling with integer variables In: Bernhard Korte, Klaus Ritter (Eds.), Mathematical programming at Oberwolfach II. Mathematical programming studies vol. 22, 1984, Springer, Berlin, Heidelberg, 167-184. ISBN: 978-3-642-00914-3 (Print), 978-3-642-00915-0 (Online) · Zbl 0554.90081
[26] Kermanshahi S, Shafahi Y, Mollanejad M, Zangui M. Rapid transit network design using simulated annealing. In: 12th World conference on transportation research. Portugal: Lisbon; 2010. p. 1-15.
[27] Laporte, G.; Marín, A.; Mesa, J. A.; Ortega, F. A., An integrated methodology for the rapid transit network design problem, (Geraets, F.; Kroon, L.; Schöebel, A.; Wagner, D.; Zaroliagis, C., Algorithmic methods for railway optimization. Lecture notes in computer science, vol. 4359, (2007), Springer Berlin, Heidelberg), 187-199
[28] Laporte, G.; Marín, A.; Mesa, J. A.; Perea, F., Designing robust rapid transit networks with alternative routes, J Adv Transp, 45, 1, 54-65, (2011)
[29] Laporte, G.; Mesa, J. A.; Ortega, F.; Pozo, M., Locating a metro line in a historical city centre: application to Sevilla, J Oper Res Soc, 60, 1462-1466, (2009)
[30] Laporte, G.; Mesa, J. A.; Ortega, F.; Sevillano, I., Maximizing trip coverage in the location of a single rapid transit alignment, Ann Oper Res, 136, 1, 49-63, (2005) · Zbl 1114.90062
[31] Laporte, G.; Pascoal, M., Path based algorithms for metro network design, Comput Oper Res, 62, 78-94, (2015) · Zbl 1348.90157
[32] Li, Z.-. C.; Lam, W. H.K.; Wong, S. C.; Sumalee, A., Design of a rail transit line for profit maximization in a linear transportation corridor, Transp Res Part ELogist Transp Rev, 48, 1, 50-70, (2012)
[33] López-Ramos F. Conjoint design of railway lines and frequency setting under semi-congested scenarios [Ph.D. thesis]. Polytechnic University of Catalonia; 2014.
[34] López-Ramos, F., Integrating network design and frequency setting in public transportation networksa survey, SORT, 38, 2, 181-214, (2014) · Zbl 1301.90006
[35] Marín, A.; García-Ródenas, R., Location of infrastructure in urban railway networks, Comput Oper Res, 36, 5, 1461-1477, (2009) · Zbl 1179.90209
[36] Marín, A.; Mesa, J. A.; Perea, F., Integrating robust railway network design and line planning under failures, (Ahuja, R. K.; Möhring, R. H.; Zaroliagis, C. D., Robust and online large-scale optimization. Lecture notes in computer science, vol. 5868, (2009), Springer-Verlag Berlin, Heidelberg), 273-292 · Zbl 1266.90046
[37] Matisziw, T. C.; Murray, A. T.; Kim, C., Strategic route extension in transit networks, Eur J Oper Res, 171, 2, 661-673, (2006) · Zbl 1090.90010
[38] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp Sci, 40, 4, 455-472, (2006)
[39] Ryoo, H.; Sahinidis, N. V., A branch-and-reduce approach to global optimization, J Global Optim, 8, 107-139, (1996) · Zbl 0856.90103
[40] Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report. Glasgow: University of Strathclyde; 1997.
[41] Sridhar, S.; Linderoth, J.; Luedtke, J., Locally ideal formulations for piecewise linear functions with indicator variables, Oper Res Lett, 41, 6, 627-632, (2013) · Zbl 1287.90039
[42] Van Nes, R.; Bovy, P. H.L., Importance of objectives in urban transit-network design, Transp Res RecJ Transp Res Board, 1735, 25-34, (2000)
[43] Vuchic, V. R., Planning and economics, Urban transit operations, (2005), Wiley Hoboken, NJ
[44] Westerlund, T.; Pörn, R., Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim Eng, 3, 253-280, (2002) · Zbl 1035.90051
[45] Wirasinghe S, Vandebona U. Planning of subway transit systems. In: Ceder A, editor, Proceedings of the 14th international symposium on transportation and traffic theory. Jerusalem, Israel: Transportation Research Institute, Pergamon; 1999. p. 759-77.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.