IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v56y2022i6p1432-1451.html
   My bibliography  Save this article

The Cheapest Ticket Problem in Public Transport

Author

Listed:
  • Anita Schöbel

    (Department of Mathematics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany; Fraunhofer Institute for Industrial Mathematics, 67663 Kaiserslautern, Germany)

  • Reena Urban

    (Department of Mathematics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany)

Abstract

Route choice models in public transport have been discussed for a long time. The main reason why a passenger chooses a specific path is usually based on its length or travel time. However, also the ticket price that passengers have to pay may influence their decision because passengers prefer cheaper paths over more expensive ones. In this paper, we deal with the cheapest ticket problem , which asks for a cheapest ticket to travel between a pair of stations. The complexity and the algorithmic approach to solve this problem depend crucially on the underlying fare structure ; for example, it is easy if the ticket price is proportional to the distance traveled (as in distance tariff fare structures), but may become NP-complete in zone tariff fare structures. We hence discuss the cheapest ticket problem for different variations of distance- and zone-based fare structures. We start by modeling the respective fare structure mathematically, then identify its main properties, and finally provide a polynomial algorithm, or prove NP-completeness of the cheapest ticket problem. We also provide general results on the combination of two fare structures, which is often observed in practice.

Suggested Citation

  • Anita Schöbel & Reena Urban, 2022. "The Cheapest Ticket Problem in Public Transport," Transportation Science, INFORMS, vol. 56(6), pages 1432-1451, November.
    • Handle: RePEc:inm:ortrsc:v:56:y:2022:i:6:p:1432-1451
    DOI: 10.1287/trsc.2022.1138
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2022.1138
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2022.1138?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:56:y:2022:i:6:p:1432-1451. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.