Metro Linea 5

This is the Santiago Metro Line 5:

Línea_5_-_Metro_de_Santiago

There are three kind of stations, R red, G green and M red/green. Between 6 and 9 hours and between 18 and 21 hours a train goes either along R and M stations, or along G and M stations. The rest of the time, trains stop at every station. This systems is part a “route express” program.

Is the route express system efficient ?

This turns out to be a highly non-trivial maths problem. First of all, we require to design an accurate model of the Santiago Metro Line 5.

Mathematical model:  

  1. We need to identify the passenger entrance rate to each station. It is certainly not a Poisson distribution, as there is not constant rate (it highly depends on the time) and moreover, the arrivals are not independent, because usually people enters in group. Actually, I currently do not know which discrete distribution would be the most appropriate. An obvious simplification is to consider it is Poisson with different rates depending on the time (example from 6 to 7, 7 to 8, etc.). In this case we could use some statistical test to adjust the rates at each station and at each hour. 
  2. We need to identify the passenger exit rate to each station. An ideal supposition is it that the exit rate at each station at the time n+12 \pmod{24} is equal to its entry rate at the time n. This would allows us to consider only entrance rates.
  3. Once we have established the entrance and exit rate we can evaluate the efficiency of the system. We consider a random passenger X, its expected travel time is \mathbb{E}(X)= \sum \mathbb{P}(going from the station a to the station b)\times Time(going from the station a to the station b), where the sum is over all possible combinations of a and b. The function Time does depend on the strategy of the model (i.e. which stations are R, G or M).

Choosing the optimal transportation plan:

A similar problem was addressed by the french mathematician Gaspard Monge in 1781.

  1. Each strategy of colouring stations by R, G, M will give a (optimal) travel time from the station a to the station b. We are no force in principle either to assign the same colouring for routes in opposite directions.
  2. In order to solve the problem we would need to check 2 \times 3^{30} different possibilities and choose the one that gives the smaller value of \mathbb{E}(X). As this is clearly impossible with modern computers, we need to design an efficient algorithm to solve this problem in a reasonable amount of time.

There is still the harder part of the work to be done in order to answer our original question. I wonder to know how strong are the assumptions by Metro de Santiago in order to determine its route express system.

Advertisements

Contraction Mapping Principle

The Contraction Mapping Principle is the most basic fixed point theorem in Analysis. It appeared in Banach Ph.D thesis published in 1922. We see this principle applied every time that we close an umbrella.

Theorem: Let (X, d) be a complete metric space and f:X\to X be a map such that  d(f(x),f(y) )< d(x,y)  for every x,y\in X. Then f has a unique fixed point in X. Moreover, for any x_0\in X the sequence of iterates x_0,f(x_0),f(f(x_0)),\ldots converges to the fixed point of f.

How is this related with closing an umbrella?

The contraction mapping principle tells us that we can close an umbrella, moreover, there is a unique direction along which it will (always) close.