A Bilevel Approach to Frequency Optimization in Public Transportation Systems

Authors Agustin Arizti, Antonio Mauttone, Maria E. Urquhart



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.7.pdf
  • Filesize: 498 kB
  • 13 pages

Document Identifiers

Author Details

Agustin Arizti
  • Universidad de la República, J. Herrera y Reissig 565, Montevideo, Uruguay
Antonio Mauttone
  • Universidad de la República, J. Herrera y Reissig 565, Montevideo, Uruguay
Maria E. Urquhart
  • Universidad de la República, J. Herrera y Reissig 565, Montevideo, Uruguay

Cite AsGet BibTex

Agustin Arizti, Antonio Mauttone, and Maria E. Urquhart. A Bilevel Approach to Frequency Optimization in Public Transportation Systems. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.ATMOS.2018.7

Abstract

We consider the problem of frequency optimization in transit systems, whose objective is to determine the time interval between subsequent buses for a set of public transportation lines. We extend an existing single level model by adding a constraint on bus capacities, while maintaining user choice on routes by means of an assignment sub-model. The resulting formulation is bilevel, and is transformed into a mixed integer linear programming formulation (MILP) that can be solved to optimality for small-sized problem instances, using standard MILP techniques. We study different variants of the same formulation to better understand the bilevel nature of the model and its application to real settings.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
Keywords
  • transportation
  • public transport capacity
  • transit frequency optimization
  • mixed integer linear programming
  • bilevel programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. José M. Arroyo. Bilevel programming applied to power system vulnerability analysis under multiple contingencies. IET Generation, Transmission and Distribution, 4(2):178-190, 2010. URL: http://dx.doi.org/10.1049/iet-gtd.2009.0098.
  2. Jonathan F. Bard. Practical bilevel optimization. Kluwer, 1998. Google Scholar
  3. Luis Baringo and Antonio J. Conejo. Transmission and Wind Power Investment. IEEE Transactions on Power Systems, 27(2):885-893, 2012. URL: http://dx.doi.org/10.1109/TPWRS.2011.2170441.
  4. Avishai Ceder and Nigel H. M. Wilson. Bus network design. Transportation Research B, 20(4):331-344, 1986. Google Scholar
  5. Manuel Cepeda, Roberto Cominetti, and Michael Florian. A frequency-based assignment model for congested transit networks with strict capacity constraints: characterization and computation of equilibria. Transportation Research B, 40(6):437-459, 2006. Google Scholar
  6. Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of Operations Research, 153(1):235-256, 2007. Google Scholar
  7. Isabelle Constantin. L’optimisation des fréquences d’un réseau de transport en commun. Doctorate thesis on informatics, Université de Montréal, 1992. Google Scholar
  8. Isabelle Constantin and Michael Florian. Optimizing frequencies in a transit network: a nonlinear bi-level programming approach. International Transactions in Operational Research, 2(2):149-164, 1995. Google Scholar
  9. Joaquín de Cea and Enrique Fernández. Transit assignment for congested public transport systems: An equilibrium model. Transportation Science, 27(2):133-147, 1993. Google Scholar
  10. Guy Desaulniers and Mark D. Hickman. Public transit. Transportation, 14:69-127, 2007. URL: http://dx.doi.org/10.1016/S0927-0507(06)14002-5.
  11. El-Ghazali Talbi. Metaheuristics for Bi-level Optimization. Studies in Computational Intelligence, 482, 2013. Google Scholar
  12. José Fortuny-Amat and Bruce McCarl. A representation and economic interpretation of a two-level programming problem. Journal of the Operational Research Society, 32:783-792, 1981. Google Scholar
  13. Ziyou Gao, Huijun Sun, and Lian Long Shan. A continuous equilibrium network design model and algorithm for transit systems. Transportation Research B, 38(3):235-250, 2004. Google Scholar
  14. Lina P. Garcés, Antonio J. Conejo, Raquel García-Bertrand, and Rubén Romero. A bilevel approach to transmission expansion planning within a market environment. IEEE Transactions on Power Systems, 24(3):1513-1522, 2009. URL: http://dx.doi.org/10.1109/TPWRS.2009.2021230.
  15. Guido Gentile, Michael Florian, Younes Hamdouch, Oded Cats, and Agostino Nuzzolo. The Theory of Transit Assignment: Basic Modelling Frameworks, pages 287-386. Springer International Publishing, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-25082-3_6.
  16. Ricardo Giesen, Héctor Martínez, Antonio Mauttone, and María E. Urquhart. A method for solving the multi-objective transit frequency optimization problem. Journal of Advanced Transportation, 50, 2017. URL: http://dx.doi.org/10.1002/atr.1461.
  17. Fred Glover. Tabu search part I. ORSA Journal on Computing, 1(3):190-206, 1989. Google Scholar
  18. Marc Goerigk and Marie Schmidt. Line planning with user-optimal route choice. European Journal of Operational Research, 259:424-436, 2017. Google Scholar
  19. Carola Leiva, Juan Carlos Muñoz, Ricardo Giesen, and Homero Larrain. Design of limited-stop services for an urban bus corridor with capacity constraints. Transportation Research B, 44(10):1186-1201, 2010. Google Scholar
  20. Héctor Martínez, Antonio Mauttone, and María E. Urquhart. Frequency optimization in public transportation systems: formulations and metaheuristic approach. European Journal of Operational Research, 236(1):27-36, 2014. URL: http://dx.doi.org/10.1016/j.ejor.2013.11.007.
  21. Antonio Mauttone and María E. Urquhart. A multi-objective metaheuristic approach for the transit network design problem. Public Transport, 1(4):253-273, 2009. Google Scholar
  22. Sang Nguyen and Stefano Pallottino. Equilibrium traffic assignment for large scale transit networks. European Journal of Operational Research, 37(2):176-186, 1988. Google Scholar
  23. Francisco Ruisánchez, Luigi dell’Olio, and Angel Ibeas. Design of a tabu search algorithm for assigning optimal bus sizes and frequencies in urban transport services. Journal of Advanced Transportation, 46(4):366-377, 2012. Google Scholar
  24. Heinz Spiess and Michael Florian. Optimal strategies: a new assignment model for transit networks. Transportation Research B, 23(2):83-102, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail