Algorithms and Data Structures for Time-Dependent Networks

Environmental Systems Research Institute, Inc. Computer Science, 2001-02

Liaison(s): Dale Honeycutt
Advisor(s): Ran Libeskind-Hadas
Students(s): Kylie Evans ’03(TL), Nathaniel Dirksen, Melissa Chase ’03, Jacob Creed

ESRI provides tools for capturing, storing and analyzing networks of virtually any type, from highways to electrical wiring. This project augments ESRI’s system with the ability to represent networks where the cost of traversing an edge changes with time, and to solve shortest-path queries on these new time-dependent networks. This will allow ESRI’s customers to model bus schedules, rush-hour traffic, and similar phenomena, allowing greater accuracy in determining shortest paths.