Shortest Path Routing in Transportation Networks with Time-Dependent Road Speeds

Costas Constantinou, Georgios Ellinas, Christos Panayiotou, Marios Polycarpou

2016

Abstract

This paper deals with the subject of shortest (in terms of traveling time) path routing in transportation networks, where the speed in the network’s roads is a function of the time interval. These networks are encountered in practice when the roads’ speed has been measured for several time instants during a large period of time (e.g., an entire year). In this way, time-dependent speed patterns can be derived for the network’s roads, that constitute an estimation of the network’s future behavior. For shortest path routing in these networks, the traveling time on the network’s roads must be calculated according to the time instant of departure. Conventional approaches perform this calculation under the assumption that the road’s speed has a constant (possibly distinct) value inside each time interval. In the work presented here, the assumption that the road’s speed is linear (possibly distinct) function of time inside each time interval, is considered. Under this assumption, a procedure is proposed that derives the traveling time on the network’s roads according to the time instant of departure. It is combined with Dijkstra’s algorithm, resulting in a practically applicable algorithm for optimal shortest path routing for the type of networks investigated in this work.

Paper Citation

in Harvard Style

Constantinou C., Ellinas G., Panayiotou C. and Polycarpou M. (2016). Shortest Path Routing in Transportation Networks with Time-Dependent Road Speeds . In Proceedings of the International Conference on Vehicle Technology and Intelligent Transport Systems - Volume 1: VEHITS, ISBN 978-989-758-185-4, pages 91-98. DOI: 10.5220/0005807000910098

in Bibtex Style

@conference{vehits16,
author={Costas Constantinou and Georgios Ellinas and Christos Panayiotou and Marios Polycarpou},
title={Shortest Path Routing in Transportation Networks with Time-Dependent Road Speeds},
booktitle={Proceedings of the International Conference on Vehicle Technology and Intelligent Transport Systems - Volume 1: VEHITS,},
year={2016},
pages={91-98},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005807000910098},
isbn={978-989-758-185-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Vehicle Technology and Intelligent Transport Systems - Volume 1: VEHITS,
TI - Shortest Path Routing in Transportation Networks with Time-Dependent Road Speeds
SN - 978-989-758-185-4
AU - Constantinou C.
AU - Ellinas G.
AU - Panayiotou C.
AU - Polycarpou M.
PY - 2016
SP - 91
EP - 98
DO - 10.5220/0005807000910098