Travelling Salesman Problem (TSP)

Travelling Salesman Problem

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 tools
  • I share my stuff at



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?

Routing problem

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

Super PC


What do we schedule?

Grocery and other deliveries

Grocery delivery

Warehouse distribution

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


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:

Powered by: Revealjs