Arrival time dependent routing policies in public transport

We present a routing system that considers uncertainties, which are prevalent in any real transport system. Given desired departure or arrival times and a utility function representing the traveller’s preferences, our method computes not just a single path through the network, but a more sophisticat...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-12, Vol.251, p.93-102
Main Authors: Bérczi, Kristóf, Jüttner, Alpár, Laumanns, Marco, Szabó, Jácint
Format: Article
Language:English
Subjects:
Policies
Polynomials
Public policy
Public transport
Public transportation
Route planning
Routing
Routing policy
Stochastic route planning
Time dependence
Transportation networks
Travel time
Utility function
Utility functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a routing system that considers uncertainties, which are prevalent in any real transport system. Given desired departure or arrival times and a utility function representing the traveller’s preferences, our method computes not just a single path through the network, but a more sophisticated and adaptive journey plan called routing policy. For each stop and time instance, a policy specifies the list of services that the passenger is recommended to take. We show that the problem of finding an optimal policy is NP-hard. We also give a polynomial-time algorithm for a relaxation of the problem when the number of recommended services is limited at each stop and time. A computational case study for the public transport network of Budapest shows that the obtained routing policies can lead to substantial travel time savings compared to deterministic plans, and that considering multiple service policies leads to an improvement compared to previous solutions using single-service policies.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.05.031