Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/325202 
Year of Publication: 
2024
Citation: 
[Journal:] EURO Journal on Transportation and Logistics (EJTL) [ISSN:] 2192-4384 [Volume:] 13 [Issue:] 1 [Article No.:] 100128 [Year:] 2024 [Pages:] 1-15
Publisher: 
Elsevier, Amsterdam
Abstract: 
We consider the price-optimal earliest arrival problem in public transit (POEAP) in which we aim to calculate the Pareto-set of journeys with respect to ticket price and arrival time in a public transportation network. Public transit fare structures are often a combination of various fare strategies such as, e.g., distance-based fares, zone-based fares or flat fares. The rules that determine the actual ticket price are often very complex. Accordingly, fare structures are notoriously difficult to model, as it is in general not sufficient to simply assign costs to arcs in a routing graph. Research into POEAP is scarce and usually either relies on heuristics or only considers restrictive fare models that are too limited to cover the full scope of most real-world applications. We therefore introduce conditional fare networks (CFNs), the first framework for representing a large number of real-world fare structures. We show that by relaxing label domination criteria, CFNs can be used as a building block in label-setting multi-objective shortest path algorithms. By the nature of their extensive modeling capabilities, optimizing over CFNs is NP-hard. However, we demonstrate that adapting the multi-criteria RAPTOR (McRAP) algorithm for CFNs yields an algorithm capable of solving POEAP to optimality in less than 400 ms on average on a real-world dataset. By restricting the size of the Pareto-set, running times are further reduced to below 10 ms.
Subjects: 
Multi-objective shortest path
Fare structure
Public transportation
Monoid
Conditional fare network
Ticket graph
RAPTOR
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.