TY - GEN
T1 - UniALT for regular language constrained shortest paths on a multi-modal transportation network
AU - Kirchler, Dominik
AU - Liberti, Leo
AU - Pajor, Thomas
AU - Calvo, Roberto Wolfler
PY - 2011/12/1
Y1 - 2011/12/1
N2 - Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (DRegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate DRegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.
AB - Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (DRegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate DRegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.
KW - ALT
KW - Multi-modal
KW - Regular language
KW - Shortest path
KW - Time-dependency
U2 - 10.4230/OASIcs.ATMOS.2011.64
DO - 10.4230/OASIcs.ATMOS.2011.64
M3 - Conference contribution
AN - SCOPUS:84873714040
SN - 9783939897330
T3 - OpenAccess Series in Informatics
SP - 64
EP - 75
BT - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011
T2 - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011
Y2 - 8 September 2011 through 8 September 2011
ER -