Algorithms for Itinerary Planning in Multimodal Transportation Networks

The itinerary planning problem in an urban public transport system constitutes a common routing and scheduling decision faced by travelers. The objective of this paper is to present a new formulation and an algorithm for solving the itinerary planning problem, i.e., determination of the itinerary th...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on intelligent transportation systems 2008-03, Vol.9 (1), p.175-184
Main Authors: Zografos, K.G., Androutsopoulos, K.N.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Athens
Context-aware services
Dynamic programming
Exact sciences and technology
Formulations
Heuristic algorithms
Information systems
Intelligent transportation systems
Itinerary planning
Legged locomotion
multicriteria
multimodal transportation network
Operational research and scientific management
Operational research. Management science
Path planning
Public transportation
Real time systems
Routing
Scheduling, sequencing
shortest path
Shortest path problem
Studies
Transportation networks
Urban planning
Walking
Windows (intervals)
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:The itinerary planning problem in an urban public transport system constitutes a common routing and scheduling decision faced by travelers. The objective of this paper is to present a new formulation and an algorithm for solving the itinerary planning problem, i.e., determination of the itinerary that lexicographically optimizes a set of criteria (i.e., total travel time, number of transfers, and total walking and waiting time) while departing from the origin and arriving at the destination within specified time windows. Based on the proposed formulation, the itinerary planning problem is expressed as a shortest path problem in a multimodal time-schedule network with time windows and time-dependent travel times. A dynamic programming-based algorithm has been developed for the solution of the emerging problem. The special case of the problem involving a mandatory visit at an intermediate stop within a given time window is formulated as two nested itinerary planning problems which are solved by the aforementioned algorithm. The proposed algorithm has been integrated in a Web-based journey planning system, whereas its performance has been assessed by solving real-life itinerary planning problems defined on the Athens urban public transport network, providing fast and accurate solutions.
ISSN:1524-9050
1558-0016
DOI:10.1109/TITS.2008.915650