THESIS
2018
x, 73 pages : illustrations (some color) ; 30 cm
Abstract
Finding optimal routes in road networks is a fine example of the benefit people
acquire from the development of algorithms in our everyday lives. Shortest path
algorithms have been applied in route planning, nearest neighbor search and traffic
analysis among others. Given an origin and a destination in a road network, the
shortest path query returns the network path of minimum cost that connects the two
locations. Although the shortest path problem dates back to the sixties, today novel
routing algorithms for transportation networks emerge, mainly because of the fast
development of navigation systems, including the Global Positioning System (GPS).
The increasing demand on location based services has resulted in greater need for
efficient solutions changing the problem of findin...[
Read more ]
Finding optimal routes in road networks is a fine example of the benefit people
acquire from the development of algorithms in our everyday lives. Shortest path
algorithms have been applied in route planning, nearest neighbor search and traffic
analysis among others. Given an origin and a destination in a road network, the
shortest path query returns the network path of minimum cost that connects the two
locations. Although the shortest path problem dates back to the sixties, today novel
routing algorithms for transportation networks emerge, mainly because of the fast
development of navigation systems, including the Global Positioning System (GPS).
The increasing demand on location based services has resulted in greater need for
efficient solutions changing the problem of finding shortest paths on road networks,
to finding either the fastest or the most reliable paths. We examine collectively
these problems under three different settings based on the formulation of the edge
weights, namely the static, the time dependent and the probabilistic. The static
setting assumes constant edge weights, the time dependent model captures changes
in the network (e.g., traffic delays, peak/off-peak hours, construction sites etc.) by
assigning functions of time as edge costs, and the stochastic shortest path problem
models edge costs as random variables. In this work we emphasize on the stochastic
shortest path problem and its different approaches, as it is the most accurate way
to capture the uncertain nature of traffic systems.
Post a Comment