# Optimization

Optimization is finding one optimal configuration for a given system optimization 8 vans

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 on filtering

## iterating to the solution

We run over 500 spots and 8 drivers 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

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, 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 markov chain

energy evolution for single move engine

## extrude, phantom, canonical

We define a series of moves to re-sort ants across the network 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

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

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