Optimization is finding one optimal configuration for a given system

optimization_8 optimization 8 vans

optimization task

We have to find the most efficient distribution tasks among drivers to minimize costs and maximize revenue


optimization problem

optmimization engine

We need to reduce the drive time and focus on most interesting spots

routing efficiency

We first add all the spots a van could see and we calculate the most optimal route connecting the spots


spot connection

spot prioritization

Prediction should define the layers where we are most confident about the revenues for a given time and weather condition

We define the revenue as:


potential of that area for a given weekday and shift number

μdeployndeployEdeploy + μcollectncollectEcollect

Where μ is the potential to add or remove a scooter at a certain spot, E is the revenue per scooter, n is the number of scooters

and the costs as:

lrideclenght + nstopscstops

Where l is the lenght, n the number of stops and c empirical parameters.

The energy calculation considers the single paths and the interaction among them:


class structure

We display the interdepency


solve problem

We can toggle the activation of the spot and recalculate the energy and apply the Metropolis algorithm to see whether the move is convenient


optimization graph

The total energy of the system decreses


optimization energy

We consider a larger system


larger system

But after many iteration steps the solution is slowly approaching


optimization energy, slowly learning

Markov chain

To improve the acceptance rate of moves we introduce Markov Chains


Markov schema

We multiply the Markov chain matrix with itself to condense iteration probabilities and set up a threshold to consider only the most important links

We calcualte at first a really dense Markov chain (first power) and we increase the power (until five) to have a sparse Markov chain


Markov chain densities

We than use a sparse Markov chain with around 7 links per node


sparse markov chain

From the Markov chain we create a cumulative probability which is getting simpler while increasing the number of iterations

cumulative probability

cumulative probability on filtering

iterating to the solution

We run over 500 spots and 8 drivers

optimization_8 optimization 8 vans

and iterate over different solutions


optimization 8 vans

We can control the energy evolution and check the aymptotic behaviour of the curves.


energy history with 8 vans

single task move

The engine was at first focusing on single task move which was making convergency pretty slow. We started than introducing new moves and initial set up

single spot move

single spot move, solutions are a bit crowded

each driver start from a different k-mean cluster


distribution of the closest spot to a cluster

We have than a better separation of routes

single spot move

single markov chain

single move energy

energy evolution for single move engine

extrude, phantom, canonical

We define a series of moves to re-sort ants across the network

series_moves series of moves

For speeding up operations we introduce a series of moves to improve run time and convergency.

Extruding is suggesting a chain following the Markov Chain probability

extrude move

extrude move

With extrusion we dicrease calculation time to 1/10 getting to the same run time as routific.

We realize that sometimes some routes get trapped in a local minimum and we can’t get complete the occupancy of the van. Therefore we introduce phantom drivers so we have the option to discard uncomplete runs

phantom move

phantom move

Depending on the stage of the solution certain solutions are more appropriate than others


energy distribution for canonical simulations

To further improve convergence of solution we move to gran canonical simulation where we continously introduce and remove routes until we get to the best complete solution

canonical move

canonical move