Project 2: Shortest Paths over Time

You're a next-generation web start-up, and you aim to out-do route-planners like Mapquest by providing time-sensitive routes. In particular, you have surveyed the road system to determine the expected travel time between pairs of endpoints based on the date and time information. Examples of time-sensitive information relevant to route-planning include:

• How much slower the main highways become during rush hour.
• Special traffic patterns that happen on holidays (e.g., certain crowded highways on the evening of Labor Day).
• Departure times for ferries. Missing a ferry means waiting for the next one, which adds latency.
• When construction on a link makes it slow, or even takes it out of service for a period.

Note that your survey won't include dynamic information, such as closures due to traffic accidents. Based on your survey, you have compiled a function $f(p,q,t)$. $T=f(p,q,t)$ means that traveling from $p$ to $q$ at time $t$ (measured in minutes past midnight on a fixed reference day) takes $T$ minutes. Thus, if you're at $p$ at time $t$, you can be at $q$ at time $t+T$ if you follow the link to $q$. Since teleportation has not yet been invented, we'll assume $f$ is always positive.

We model the road network as a directed graph, with nodes corresponding to geographic markers such as towns, and directed edges corresponding to one-way roads between markers. A two-way road is modeled as two one-way roads, which allows traffic to be worse in one direction than the other, i.e., $f(p,q,t)$ may be larger or smaller than $f(q,p,t)$. We assume without loss of generality that there is only one road from any given marker to any other marker. (If there were $n$ roads, we can just add new markers on $n-1$ of them.)

The journey is described by a start marker $S$, and an end marker $E$. The journey could start at any time, and the first part of your task is to calculate the shortest path from $S$ to $E$ for every possible departure time from $S$, to the minute granularity.

You will not know the function $f$, and will have to treat it as a ``black box.'' Nevertheless, you can make some reasonable assumptions about $f$. First

$$f(p,q,t) \leq \delta + f(p,q,t+\delta)$$

Informally, this equation means that $f$ already takes into account waiting at $p$ as a possible strategy. Waiting is reasonable, for example, if there's a link that's closed at time $t$, but due to open soon. Unless a link is permanently closed, $f$ will always have a finite value. (We're assuming that there is a place to wait, which might not be realistic in some cases, such as on a freeway.)

An interesting consequence of the equation above is that $f$ cannot have any downward discontinuities, where a link becomes suddenly faster. (Why?) Also, there is a limit to how rapidly $f$ can decrease. (What is the limit?) Upward discontinuities are still possible. (What would be a real-world example?)

These restrictions on $f$ may make the shortest-path computation simpler. For more information about how to compute shortest paths with time-varying delays, see http://portal.acm.org/citation.cfm?doid=79147.214078 and http://ieeexplore.ieee.org/iel5/10757/33902/01617378.pdf.

The second part of your task is to present a single page, static representation of the entire set of shortest paths between a fixed pair of points, where the start time could be anywhere in a 24-hour period. If this is an insufficient challenge, then also try to include the travel times in the representation. The representation should be intelligible when printed on a single letter-sized piece of paper. Imagine that this picture is a page in a street directory that a motorist uses to travel from $S$ to $E$. If special instructions are needed to interpret the diagram, then those instructions also need to appear on the page.

The shortest path may change a lot, or a little, depending on $f$. It may change at a few discrete times, or periodically. Alternative paths may share many markers or just a few. Your representation should be robust, and it will be tested with a variety of different geographies and functions $f$. Some of these will be unseen, i.e., only distributed after the final code submission deadline.

At the end of the project, the instructor will conduct a ``user study'' in which a variety of individuals (we'll decide in class what kind of people to approach) will be asked to evaluate the outputs from each group.

Hints: Project 2 from 2004 was looking at a related mapping problem. Some groups used accurate geographic maps, anticipating that users would bring some prior knowledge to interpreting the pictures. Others distorted the geometry to make the directions easier to draw. Yet others abandoned graphics altogether, and used plain text to show a table of numbers. Think carefully about the style of design you think is best. If you're ambitious, you could try to be adaptive, using a design style that is suited to the data.