Robust Line Planning in Case of Multiple Pools and Disruptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Robust Line Planning in Case of Multiple Pools and Disruptions

  • Conference paper
Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6595))

Abstract

We consider the line planning problem in public transportation, under a robustness perspective. We present a mechanism for robust line planning in the case of multiple line pools, when the line operators have a different utility function per pool. We conduct an experimental study of our mechanism on both synthetic and real-world data that shows fast convergence to the optimum. We also explore a wide range of scenarios, varying from an arbitrary initial state (to be solved) to small disruptions in a previously optimal solution (to be recovered). Our experiments with the latter scenario show that our mechanism can be used as an online recovery scheme causing the system to re-converge to its optimum extremely fast.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bessas, A., Kontogiannis, S., Zaroliagis, C.: Incentive-compatible robust line planning. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 85–118. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  2. Bessas, A., Kontogiannis, S., Zaroliagis, C.: Robust Line Planning in case of Multiple Pools and Disruptions (January 2011), http://arxiv.org/abs/1101.2770

  3. Dienst, H.: Linienplanung im spurgeführten Personenverkehr mit Hilfe eines heuristischen Verfahrens. PhD thesis, Technische Universität Braunschweig (1978)

    Google Scholar 

  4. Goossens, J., van Hoesel, C., Kroon, L.: A branch and cut approach for solving line planning problems. Transportation Science 38, 379–393 (2004)

    Article  Google Scholar 

  5. Kelly, F.: Charging and rate control for elastic traffic. European Transactions on Telecommunications 8, 33–37 (1997)

    Article  Google Scholar 

  6. Kelly, F., Maulloo, A., Tan, D.: Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49, 237–252 (1998)

    Article  MATH  Google Scholar 

  7. Schöbel, A., Scholl, S.: Line Planning with Minimal Traveling Time. In: Proc. 5th Workshop on Algorithmic Methods and Models for Optimization of Railways – ATMOS 2005 (2005)

    Google Scholar 

  8. Schöbel, A., Schwarze, S.: A Game-Theoretic Approach to Line Planning. In: Proc. 6th Workshop on Algorithmic Methods and Models for Optimization of Railways – ATMOS 2006 (2006)

    Google Scholar 

  9. Scholl, S.: Customer-oriented line planning. PhD thesis, Technische Universität Kaiserslautern (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. R.A. Computer Technology Institute, Patras University Campus, N. Kazantzaki Str., 26500, Patras, Greece

    Apostolos Bessas, Spyros Kontogiannis & Christos Zaroliagis

  2. Computer Science Department, University of Ioannina, 45110, Ioannina, Greece

    Spyros Kontogiannis

  3. Department of Computer Engineering and Informatics, University of Patras, 26500, Patras, Greece

    Apostolos Bessas & Christos Zaroliagis

Authors
  1. Apostolos Bessas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Spyros Kontogiannis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christos Zaroliagis
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Systemics "Antonio Ruberti", Sapienza University of Rome, Via Ariosto 25, 00185, Rome, Italy

    Alberto Marchetti-Spaccamela

  2. Communication Systems Engineering Department, Ben-Gurion University of the Negev, POB 653, 84105, Beer-Sheva, Israel

    Michael Segal

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bessas, A., Kontogiannis, S., Zaroliagis, C. (2011). Robust Line Planning in Case of Multiple Pools and Disruptions. In: Marchetti-Spaccamela, A., Segal, M. (eds) Theory and Practice of Algorithms in (Computer) Systems. TAPAS 2011. Lecture Notes in Computer Science, vol 6595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19754-3_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-19754-3_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-19753-6

  • Online ISBN: 978-3-642-19754-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics