TY - GEN
T1 - A label correcting algorithm for the shortest path problem on a multi-modal route network
AU - Kirchler, Dominik
AU - Liberti, Leo
AU - Wolfler Calvo, Roberto
PY - 2012/8/1
Y1 - 2012/8/1
N2 - We consider shortest paths on a realistic multi-modal transportation network where restrictions or preferences on the use of certain modes of transportation or types of roads arise. The regular language constraint shortest path problem deals with this kind of problem. It models constraints by using regular languages. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (DRegLC). In this paper we present a new label correcting algorithm (lcSDALT) with a speed-up, in our setting, of a factor 3 to 30 in respect to (DRegLC) and up to a factor 2 in respect to a similar algorithm.
AB - We consider shortest paths on a realistic multi-modal transportation network where restrictions or preferences on the use of certain modes of transportation or types of roads arise. The regular language constraint shortest path problem deals with this kind of problem. It models constraints by using regular languages. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (DRegLC). In this paper we present a new label correcting algorithm (lcSDALT) with a speed-up, in our setting, of a factor 3 to 30 in respect to (DRegLC) and up to a factor 2 in respect to a similar algorithm.
UR - https://www.scopus.com/pages/publications/84864372013
U2 - 10.1007/978-3-642-30850-5_21
DO - 10.1007/978-3-642-30850-5_21
M3 - Conference contribution
AN - SCOPUS:84864372013
SN - 9783642308499
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 236
EP - 247
BT - Experimental Algorithms - 11th International Symposium, SEA 2012, Proceedings
T2 - 11th International Symposium on Experimental Algorithms SEA 2012
Y2 - 7 June 2012 through 9 June 2012
ER -