Travelling between cities …

December 19, 2011 at 12:29 am (probability, Uncategorized)
Tags: , , , , ,

Consider the standard plane lattice {\mathbb{Z}^2} and suppose that each point {(x,y) \in \mathbb{Z}^2} represents a city. Each city is connected to its {4} neighbors only and each edge {(AB)} carries a weight that represents the time it takes to go from city {A} to city {B}. A natural question is the following:

Given two (non-neighboring) cities on the map, how long does take to travel between them?

To make the problem more tractable, mathematicians usually assume that the time it takes to travel between neighboring cities are independent from each other and identically distributed according to a distribution {\mu(dt)}. In other words, each edge of the lattice {\mathbb{Z}^2} carries a random variable {T_{e}}. The random variables {\big\{ T_e \big\}_e} are {i.i.d} and distributed according to {\mu(dt)}. It takes

\displaystyle \begin{array}{rcl} \tau(A,B)\;=\; \inf \; \Big\{ \; \sum_{\text{path}}T_{e} \;: \text{paths between A and B} \; \Big\} \end{array}

to travel on the optimal route between city {A} and city {B}. The optimal route is usually called a geodesic. If one starts from the origin, one may wonder what are the cities that can be reached in less that {30} hours, say. On the next picture, each red dot represents a city that can be reached in less than {30} hours when the travel time between any two neighboring city is exponentially distributed with mean {1} hour.

One may also wonder how the optimal routes look like. On the next picture I have plotted {4.10^4} cities (the origin is the blue dotted city) and highlighted the optimal routes between the origin and each one of the cities on the border of the map.

Is it very different from the highway system around a typical city?

For those who want to play with this model, you can modify the quick and dirty Python code that can be found here. The study of these models is an active area of research.

4 Comments