×

Line planning with user-optimal route choice. (English) Zbl 1394.90088

Summary: We consider the problem of designing lines in a public transport system, where we include user-optimal route choice. The model we develop ensures that there is enough capacity present for every passenger to travel on a shortest route. We present two different integer programming formulations for this problem and discuss exact solution approaches. To solve large-scale line planning instances, we also implement genetic solution algorithms. We test our algorithms in computational experiments using randomly generated instances along realistic data as well as a realistic instance modeling, the German long-distance network. We examine the advantages and disadvantages of using such user-optimal solutions and show that our algorithms sufficiently scale with instance size to be used for practical purposes.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C90 Applications of mathematical programming
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming

Software:

CPLEX; LEMON; LinTim
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Altin, A.; Fortz, B.; Thorup, M.; Ümit, H., Intra-domain traffic engineering with shortest path routing protocols, 4OR, 4, 301-335 (2009) · Zbl 1188.90058
[2] Basar, T.; Srikant, R., A Stackelberg network game with a large number of followers, Journal of Optimization Theory and Applications, 115, 479-490 (2002) · Zbl 1031.91016
[3] Beltran, B.; Carrese, S.; Cipriani, E.; Petrelli, M., Transit network design with allocation of green vehicles: A genetic algorithm approach, Transportation Research Part C: Emerging Technologies, 17, 5, 475-483 (2009)
[4] Borndörfer, R.; Grötschel, M.; Pfetsch, M. E., A column-generation approach to line planning in public transport, Transportation Science, 41, 1, 123-132 (2007)
[5] Borndörfer, R.; Hoppmann, H.; Karbstein, M., Timetabling and passenger routing in public transport, Technical Report 15-31 (2015)
[6] Borndörfer, R.; Grötschel, M.; Pfetsch, M. E., Models for line planning in public transport, (Hickman, M.; Mirchandani, P.; Voß, S., Computer-aided systems in public transport. Computer-aided systems in public transport, Lecture notes in economics and mathematical systems, vol.600 (2008), Springer: Springer Berlin, Heidelberg), 363-378 · Zbl 1169.90314
[7] Borndörfer, R.; Karbstein, M., A direct connection approach to integrated line planning and passenger routing, Proceedings of the twelfth workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS). Proceedings of the twelfth workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS), OpenAccess series in informatics (OASIcs), vol.25, 47-57 (2012), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik · Zbl 1247.90029
[8] Bovy, P. H.; Stern, E., Route choice: Wayfinding in transport networks, vol.9 (2012), Springer Science & Business Media
[9] Brotcorne, L.; Labbé, M.; Marcotte, P.; Savard, G., A bilevel model for toll optimization on a multicommodity transportation network, Transportation Science, 35, 4, 345-358 (2001) · Zbl 1069.90502
[10] Bussieck, M., Optimal lines in public rail transport (1998), Technische Universität Braunschweig, Ph.D. thesis
[11] Bussieck, M. R.; Kreuzer, P.; Zimmermann, U. T., Optimal lines for railway systems, European Journal of Operational Research, 96, 1, 54-63 (1997) · Zbl 0926.90005
[12] Claessens, M. T.; van Dijk, N. M.; Zwanefeld, P. J., Cost optimal allocation of rail passenger lines, European Journal of Operational Research, 110, 474-489 (1998) · Zbl 0948.90097
[14] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Annals of Operations Research, 153, 1, 235-256 (2007) · Zbl 1159.90483
[15] Constantin, I.; Florian, M., Optimizing frequencies in a transit network: Anonlinear bi-level programming approach, International Transactions in Operational Research, 2, 2, 149-164 (1995) · Zbl 0868.90037
[16] Cordone, R.; Redaelli, F., Optimizing the demand captured by a railway system with a regular timetable, Transportation Research Part B: Methodological, 45, 2, 430-446 (2011)
[17] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[18] Delling, D.; Sanders, P.; Schultes, D.; Wagner, D., Engineering route planning algorithms, Algorithmics of large and complex networks, 117-139 (2009), Springer · Zbl 1248.90017
[19] dell’Olio, L.; Moura, J.; Ibeas, A., Bi-level mathematical programming model for locating bus stops and optimizing frequencies, Transportation Research Record: Journal of the Transportation Research Board, 1971, 23-31 (2006)
[20] Dollevoet, T.; Huisman, D.; Schmidt, M.; Schöbel, A., Delay management with rerouting of passengers, Transportation Science, 46, 1, 74-89 (2012)
[21] Ehrgott, M., Multicriteria optimization (2006), Springer Science & Business Media
[22] Fan, W.; Machemehl, R., Optimal transit route network design problem with variable transit demand: Genetic algorithm approach, Journal of Transportation Engineering, 132, 1, 40-51 (2006)
[23] Farahani, R. Z.; Miandoabchi, E.; Szeto, W. Y.; Rashidi, H., A review of urban transportation network design problems, European Journal of Operational Research, 229, 2, 281-302 (2013) · Zbl 1317.90047
[24] Gao, Z.; Sun, H.; Shan, L. L., A continuous equilibrium network design model and algorithm for transit systems, Transportation Research Part B: Methodological, 38, 3, 235-250 (2004)
[25] Goerigk, M.; Schachtebeck, M.; Schöbel, A., Evaluating line concepts using travel times and robustness, Public Transport, 5, 3, 267-284 (2013)
[26] Goerigk, M.; Schmidt, M.; Schöbel, A.; Knoth, M.; Müller-Hannemann, M., The price of strict and light robustness in timetable information, Transportation Science, 48, 2, 225-242 (2013)
[27] Goossens, J.-W.; van Hoesel, S.; Kroon, L., A branch-and-cut approach for solving railway line planning problems, Transportation Science, 38, 3, 379-393 (2004)
[28] Goossens, J.-W.; van Hoesel, S.; Kroon, L., On solving multi-type railway line planning problems, European Journal of Operational Research, 168, 2, 403-424 (2006) · Zbl 1101.90038
[29] Guan, J. F.; Yang, H.; Wirasinghe, S. C., Simultaneous optimization of transit line configuration and passenger line assignment, Transportation Research Part B: Methodological, 40, 10, 885-902 (2006)
[30] Harbering, J., Planning a public transportation system with a view towards passengers’ convenience (2016), University of Göttingen, Ph.D. thesis · Zbl 1349.90001
[33] Kara, B. Y.; Verter, V., Designing a road network for hazardous materials transportation, Transportation Science, 38, 2, 188-196 (2004)
[34] Konak, A.; Coit, D. W.; Smith, A. E., Multi-objective optimization using genetic algorithms: A tutorial, Reliability Engineering and System Safety, 91, 9, 992-1007 (2006)
[35] Korilis, Y. A.; Lazer, A. A.; Orda, A., Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking, 5, 161 (1997)
[36] Kroon, L.; Maróti, G.; Nielsen, L., Rescheduling of railway rolling stock with dynamic passenger flows, Transportation Science, 49, 2, 165-184 (2014)
[37] Laporte, G.; Marin, A.; Mesa, J. A.; Ortega, F. A., An integrated methodology for the rapid transit network design problem, Algorithmic methods for railway optimization. Algorithmic methods for railway optimization, Lecture notes in computer science, vol. 4359, 187-199 (2007), Springer: Springer Berlin, Heidelberg
[38] Laporte, G.; Mesa, J. A.; Ortega, F. A.; Sevillano, I., Maximizing trip coverage in the location of a single rapid transit alignment, Annals of Operations Research, 136, 1, 49-63 (2005) · Zbl 1114.90062
[39] Lee, H.; Song, Y.; Choo, S.; Chung, K.-Y.; Lee, K.-D., Bi-level optimization programming for the shipper-carrier network problem, Cluster Computing, 17, 3, 805-816 (2014)
[41] Migdalas, A., Bilevel programming in traffic planning: Models, methods and challenge, Journal of Global Optimization, 7, 4, 381-405 (1995) · Zbl 0844.90050
[42] Müller-Hannemann, M.; Schulz, F.; Wagner, D.; Zaroliagis, C., Timetable information: Models and algorithms, Algorithmic methods for railway optimization, 67-90 (2007), Springer
[43] Nachtigall, K.; Jerosch, K., Simultaneous network line planning and traffic assignment, (Fischetti, M.; Widmayer, P., Proceedings of the eighth workshop on algorithmic approaches for transportation modeling, optimization, and systems (2008)) · Zbl 1247.90058
[44] Otuzar, J.d. D.; Willumsen, L. G., Modelling transport (2011), J. Wiley & Sons Inc.: J. Wiley & Sons Inc. Chichester u. a. O.
[45] Patriksson, M., The traffic assignment problem: Models and methods (2015), Courier Dover Publications
[46] Pfetsch, M.; Borndörfer, R., Routing in line planning for public transport, (Haasis, H.-D.; Kopfer, H.; Schönberger, J., Operations research proceedings 2005. Operations research proceedings 2005, Operations research proceedings, vol. 2005 (2006), Springer: Springer Berlin, Heidelberg), 405-410 · Zbl 1114.90319
[47] Roughgarden, T., Stackelberg scheduling strategies, SIAM Journal on Computing, 33, 332 (2004) · Zbl 1080.90046
[48] Roughgarden, T., Selfish routing and the price of anarchy (2005), Massachusetts Institute of Technology
[49] Schmidt, M., Integrating routing decisions in network problems (2012), Universität Göttingen, Ph.D. thesis
[50] Schmidt, M., Simultaneous optimization of delay management decisions and passenger routes, Public Transport, 5, 125-147 (2013)
[51] Schmidt, M., Integrating routing decisions in public transportation problems. Integrating routing decisions in public transportation problems, Optimization and its applications, vol. 89 (2014), Springer · Zbl 1286.90024
[52] Schmidt, M.; Schöbel, A., The complexity of integrating routing decisions in public transportation models, Technical report (2012), Institute for Numerical and Applied Mathematics, University of Goettingen
[53] Schmidt, M.; Schöbel, A., Location of speed-up subnetworks, Annals of Operations Research, 223, 1, 379-401 (2014) · Zbl 1306.90023
[54] Schmidt, M.; Schöbel, A., The complexity of integrating routing decisions in public transportation models, Networks, 65, 3, 228-243 (2015) · Zbl 1390.90123
[55] Schmidt, M.; Schöbel, A., Timetabling with passenger routing, OR Spectrum, 37, 75-97 (2015) · Zbl 1308.90024
[56] Schöbel, A., Line planning in public transportation: Models and methods, OR Spectrum, 34, 3, 491-510 (2012) · Zbl 1244.90048
[57] Schöbel, A.; Scholl, S., Line planning with minimal transfers, Proceedings of the fifth Dagstuhl seminar workshop on algorithmic methods and models for optimization of railways, vol.06901 (2006)
[58] Scholl, S., Customer-oriented line planning (2005), Technische Universität Kaiserslautern, Ph.D. thesis
[59] Shimamoto, H.; Kurauchi, F., Optimisation of a bus network configuration and frequency considering the common lines problem, Journal of Transportation Technologies, 2, 03, 220 (2012)
[60] Shimamoto, H.; Murayama, N.; Fujiwara, A.; Zhang, J., Evaluation of an existing bus network using a transit network optimisation model: A case study of the Hiroshima city bus network, Transportation, 37, 5, 801-823 (2010)
[61] Siebert, M.; Goerigk, M., An experimental comparison of periodic timetabling models, Computers and Operations Research, 40, 10, 2251-2259 (2013) · Zbl 1348.90311
[62] Wilson, N. H.M.; Nuzzolo, A., Schedule-based dynamic transit modeling: Theory and applications, vol.28 (2013), Springer Science & Business Media
[63] Wood, R. K., Bilevel network interdiction models: Formulations and solutions, Wiley encyclopedia of operations research and management science (2011), John Wiley & Sons, Inc
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.