Optimization

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_engine
optimization_engine

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_connection

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:

map_pot
map_pot

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:

mallink_energy

class structure

We display the interdepency

module_mallink

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

opt_graph
opt_graph

optimization graph

The total energy of the system decreses

opt_nrg
opt_nrg

optimization energy

We consider a larger system

opt_nrg
opt_nrg

larger system

But after many iteration steps the solution is slowly approaching

opt_nrg
opt_nrg

optimization energy, slowly learning

Markov chain

To improve the acceptance rate of moves we introduce Markov Chains

markov_schema
markov_schema

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
markov_chain

Markov chain densities

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

markov_chain
markov_chain

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

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
optimization_8

optimization 8 vans

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

nrg_8
nrg_8

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

single spot move, solutions are a bit crowded

each driver start from a different k-mean cluster

start_clustering
start_clustering

distribution of the closest spot to a cluster

We have than a better separation of routes

single spot move
single spot move

single markov chain

single move energy
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

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

phantom move

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

nrg_canonical
nrg_canonical

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

canonical move