Kaggle Santa Challenge: Wéér een medaille voor CQM

15/01/2019

---

Het is een ware Kersttraditie bij CQM: deelnemen aan de jaarlijkse optimalisatiecompetitie die door Kaggle wordt uitgeschreven. We streden voor de vijfde keer mee en wonnen net als voorgaande jaren een medaille. Ditmaal eindigden we in de top 10%, wat beloond wordt met een bronzen medaille. Lees in deze blog waarom we mee doen en hoe we deze puzzel kraken.

 

Het probleem: Traveling Santa – Prime Paths

Ieder jaar bezoekt de Kerstman met zijn slee met rendieren alle steden om cadeautjes af te leveren. Het is dit jaar aan ons om de route van de Kerstman langs de steden te bepalen. Een correcte route doet elke stad precies 1 keer aan en start en eindigt op de Noordpool. Hoe korter de route, hoe beter. Tot zover is het een klassiek optimalisatieprobleem dat bekend staat als het Traveling Salesman Problem. In deze Santa Challenge is er echter een extra factor om rekening mee te houden. De steden zijn genummerd en in elke stad die is genummerd met een priemgetal, liggen wortels klaar voor de rendieren. Wortels om de energie op peil te houden. Want als een tiende stap in de route niet uit een priemstad komt, dan kost het 10% extra om bij volgende stad te komen. 
 

Onze motivatie

Waarom doen we mee? In de eerste plaats voor ons plezier: we zijn gepassioneerde puzzelaars en houden van een wiskundige uitdaging. Door als een team samen te werken in deze competitie leren we veel van elkaar. Ieder brengt zijn eigen ervaring en kwaliteiten in waar de anderen veel van kunnen leren.

In een wekelijkse brainstorm brengen we ideeën voor oplossingsstrategieën en data-analyses bij elkaar om vervolgens de implementatie te coördineren. Door middel van feedback op elkaars ideeën en werk komen nieuwe creatieve oplossingen naar boven en wordt de implementatie van de algoritmiek efficiënter. 

Aan het eind van de rit hebben we allemaal wat geleerd en zijn we een ervaring rijker. Klaar om dit in te zetten bij het volgende klantproject.

 

Onze aanpak

In het probleem moeten bijna 200.000 steden bezocht worden. Dat zijn er zo veel dat een exacte methode – een algoritme dat gegarandeerd de optimale oplossing geeft – geen zin heeft. Want zo’n methode zou bij zo veel steden te veel tijd nodig hebben om de oplossing te bepalen. Daarom is een aanpak die een goede startoplossing construeert en een bestaande oplossing kan verbeteren de juiste.

Als we de 200.000 steden grafisch weergeven krijgen we het volgende toepasselijke plaatje:

 
Een goede startoplossing bepalen we met standaardsoftware voor het Traveling Salesman Probleem (TSP). Daarbij negeren we de 10% boete als in de 10e stap niet vanuit een priem-stad komt. Dit lijkt redelijk want je mag verwachten dat deze extra factor slechts 0.91% impact heeft. Slechts 10% van de afstanden betreft namelijk een 10e stap, 91% van de getallen zijn niet priem en de boete is 10%. De startoplossing hebben we gegenereerd met Concorde TSP Solver.

Vanaf dit punt houden we wel rekening met de boete en met behulp van local-searchtechnieken gaan we de oplossing verbeteren. We hebben een groot aantal verbeterstappen geïmplementeerd. Dit is een greep uit wat we ingezet hebben:

• Omkeren: Draai de gehele route om. Omdat bij het maken van de startoplossing geen rekening gehouden wordt met de priemsteden op de 10e plek, is met 50% kans de omgekeerde route beter.
• City shift: Pak één stad en verschuif deze in de route naar een andere plek. Zo kun je een priemstad naar een 10e plek verplaatsen of zorgen dat de boete op een korter stuk valt.
• Optimize section: Knip een aantal opvolgende steden uit de route en bepaal met behulp van dynamic programming de optimale volgorde om deze steden weer terug te plaatsen.
• 2-Opt: Knip de route op twee plekken door en plak het stuk tussen de knippen er in omgekeerde richting weer in.
• 3-Opt: Knip de route op drie plekken door en verbind de delen op verscheidene manieren weer aan elkaar.
• Generalized 2-Opt: Voer een 2-Opt stap uit en zet tegelijkertijd de steden net voor en net na de knippen in de optimale volgorde.

Voor een succesvolle local search zijn een aantal factoren belangrijk. Het moet in de eerste plaats supersnel zijn om veel verbeterstappen te kunnen overwegen. Een goede implementatie is daarbij belangrijker dan een snelle computer, al is dat tweede natuurlijk een welkome toevoeging. In de tweede plaats moet de selectie van verbeterstappen zodanig zijn dat de kans op het vinden van een verbetering groot is. Het heeft bijvoorbeeld geen zin om twee steden te verbinden die geografisch ver uit elkaar liggen. 

Onze uiteindelijke oplossing ziet er als volgt uit:

Mooi resultaat

We hebben ook dit jaar veel geleerd en plezier gehad. Onze inspanningen worden beloond met een bronzen medaille omdat we in de top 10% eindigen van de bijna 1900 deelnemende teams en onze oplossing zit slechts 0.1% van de winnaar af. Een prestatie om trots op te zijn.

In eerdere edities wonnen we al een bronzen, een zilveren en twee gouden medailles. We draaien mee in de wereldtop wat betreft het oplossen van complexe optimalisatieproblemen en datasciencevraagstukken.

Jacob Jan

 

Lees ook

• CQM pakt gouden medaille in Kaggle competitie
• CQM trots op vierde plaats in Kaggle competitie
• Blog over local search met TSP - Prescriptive Analytics - deel 3
• Blog over het handelsreizigersprobleem oplossen met Deep Learning

 

• De originele opgave beschrijving
• Concorde TSP Solver