Travelling Salesman Problem (TSP)

Who's sharing experience

Gediminas Morkevičius aka @l3pp4rd

• I code with - GO, Java, C
• Less with PHP, javascript at the moment
• Hardcore - ViM, Arch Linux, DWM user
• Fan of suckless.org tools
• I share my stuff at github.com/l3pp4rd

At DATA-DOG

In partnership with Satalia

We solve hard problems

We are developing sofware for grocery supply chain

Which compared to Maxima in baltic states

is at least 5 times bigger

has around 200 depots in the region we work with

What are we doing there?

• Routing solution
• Scheduling
• Optimization

and these are hard problems

Vehicle routing problems

How many possible routes there may be within 24 points?

Other routing problems

1. Speed at specific hour
2. Blocked or restricted roads or zones, public events
3. Right hand turns
4. Types of roads, size
5. Unexpected time at door time spent

First of all, you have to lower the number of possibilities

and make trade offs

A similar solution to our - Oracle ORS uses a Super-PC with 400 CPUs

Scheduling

What do we schedule?

Grocery and other deliveries

Warehouse distribution

Imagine a schedule..

Lets make it harder

Every drop may be allocated to a time slot

main scheduling operations

1. GET available slots
2. POST slot reservation
3. PATCH slot reservation
4. DELETE slot reservation
5. GET schedule itinerary

Optimization

Currently we have around several methods of optimization

customized ILP algorithm, but everywhere there are trade offs

cannot lock actively updated schedule for long running optimization

probably every depot should have a different kind of optimization

Maybe Ant colony optimization algorithms

there are many interesting things we will try

Hopefully producing similar results

Thank you

Slides are available at: slides.gediminasm.org

Powered by: Revealjs