University of Twente Student Theses


Solving time-dependent shortest path problems in a database context

Sperb, Rodrigo Campi (2010) Solving time-dependent shortest path problems in a database context.

[img] PDF
Abstract:All around the world people experience delays due to bad traffic conditions. As a matter of fact, here in Netherlands, for instance, it is common sense to talk about the early morning pick time in the motorways and major roads just before people start their work duties. In this context, computation of shortest paths can no longer consider costs to traverse the network fixed, as traditionally, but rather as function of the time of the day. When these costs are known a priori (i.e., traffic condition information) the problem is usually referred to as time-dependent shortest path (TDSP). In this research two problem formulations are tackled: (1) a simple one-to-one TDSP for a given departure time (TDSP-GDT); and (2) One-to-one TDSP for a given interval of departure time (TDSP-LTT). A real-world time-dependent network from the Netherlands is used to test the developed solutions, and we implement the solutions in a database context. We make use of graph-theoretic approaches, more specifically an adaption of the famous Dijkstra’s algorithm for static shortest path, proposed in the literature. Preliminary results indicate that TDSP-GDT problems can be solved at reasonable computational time when opportunities of optimizing the computation are taken by removing unnecessary nodes in the graph (i.e., trivial graph simplification). On the other hand, TDSP-LTT has shown to be very expensive computationally and only rather limited request sizes could be solved in a reasonable amount of time. That triggered us toward finding faster ways of solving the problem, with the concept of graph simplification being taken to other levels. We theoretically define a graph simplification to traverse dense subgraphs in which the computations are found to slow down. A proof-of-concept performance test shows that a careful delineation of dense subgraphs, brings much better results in runtime, also allowing a broader range of requests sizes to be solved, though the developed solutions may still have limitations when applied to (real-world) large graphs. At any case, our investigation serves as a basis upon which further work can be developed until fully operational solutions for TDSP problems in a database context can eventually be reached. In this note, we discuss other possibilities that could be exploited to achieve such a goal, particularly focusing on how to compute faster, speed-up techniques by precomputing parts of the problem, as well as pointing out that other graph simplifications can still be devised. Keywords dynamic shortest path, spatial database, time-dependent routing, graphtheoretic approach, graph simplification, speed-up technique
Item Type:Essay (Master)
Faculty:ITC: Faculty of Geo-information Science and Earth Observation
Programme:Geoinformation Science and Earth Observation MSc (75014)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page