Optmization Study Towards Synchronization in Public Transport

PROBLEM: 

There are several public transport lines departing from single stop point, headway for each line is given. 

The problem is to find optimal offset vector, i.e. departure times for each line.

SOLUTION: 

I was examining Matlab Optimization Toolbox – there are loads of different optimization methods to choose from.

I’ve created a data feed proper for Matlab, i.e. goal function , constrains, starting point, and so on.

Goal function is value of specified expression representing either regularity, either waiting times, either minimal gap between consequent departures.  In particular, poly-criteria problem three values were calculated as follows:

Gaps_Vector=GV

Cycle=60 [min]

Desired_Gap=Cycle/numel(GV)  

R=[sum((GV-Desired_Gap).^2) sum(Gaps_Vector.^2)/2 exp(2/(min(Gaps)^2+.1))]

R is a three-element vector with elements representing:

1.     Regularity Factor

2.     Waiting Time

3.     Min Departure Time 

In general problem is n-dimensional, where n is number of lines. If n=2 solution can be graphically represented as follows:

Objective Function (Offset); 2d case

Function is strictly periodic for each of three criteria. For calculation speed wisely adjusted constrains narrowing search for single period should be considered.

If n=3, the problem can be represented graphically as follows:

Objective Function (Offest Vector) ; 3d case

RESULTS:

I was testing optimization methods for the case of 7 lines with various offsets. Each analytical method failed to find optimum. Genetic algorithms had struggled and for 20% runs it managed to find optimum (default method settings). Simulated annealing calculation took long, but found the solution. Pattern search converged quickly and found optimum after 40 iterations, moreover optimum was robust for initial point.

I have also analyzed poly-criteria Pareto Frontiers. It has failed for most of GA multi-objective procedure runs. Optimal solution set was found for 10% of simulation: 

Pareto Frontier for multiobjective GA

  
CONCLUSIONS:
I only did early search for optimal model to represent objective function and appropriate method for optimization. Analythical method failed to suceed, and non-analythical struggled to succeed. In some cases genethic algorythms were succesful, in some Simulated Annealing. Pattern search were probably fastest and most reliable (although robust wasn't analyzed).
The only available method for multi-objective was GA and success was possible only if initial point was selected properly.