Het handelsreizigersprobleem oplossen met Deep Learning

Masterstudent Erik van der Klooster schreef een blog over zijn afstudeerstage bij CQM.

 

Tijdens de afstudeerstage van mijn onderzoeksmaster heb ik bij CQM gewerkt aan het toepassen van Deep Learning op het ‘Travelling Salesman Problem’, oftewel het handelsreizigersprobleem:

“Gegeven n steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die precies één keer langs iedere stad komt en eindigt bij de eerste stad.”

Er is dus een handelaar die vanuit zijn woonplaats een aantal steden wil bezoeken om zijn spullen te verkopen en aan het eind van de dag wil de handelaar weer terugkomen in zijn woonplaats. Een voorbeeld van een handelsreizigersprobleem met 20 steden is weergegeven in de afbeelding hieronder. De steden zijn aangegeven met stippen en de route die de handelsreiziger aflegt is aangegeven met de rechte verbindingslijnen tussen de steden.
 

De route in de afbeelding is overduidelijk niet de meeste efficiënte route die die handelsreiziger kan afleggen. Daarom willen we deze route verbeteren door een 2-opt verbetering te maken. Een 2-opt verbetering bestaat uit het weghalen van twee verschillende verbindingen tussen twee steden en het toevoegen van twee nieuwe verbindingen. Een 2-opt verbetering levert bijvoorbeeld de volgende verbeterde route op:

In totaal kunnen er voor dit probleem op ongeveer 400 manieren twee verbindingen worden weggehaald en twee nieuwe verbindingen worden toegevoegd. Dit is ongeveer gelijk aan het aantal steden in het kwadraat. Het aantal mogelijke 2-opt verbeteringen stijgt dus sterk als het aantal steden groter wordt. Hierdoor wordt het vinden van een goede 2-opt verbetering steeds tijdrovender als het aantal steden groter wordt. Tijdens mijn afstudeerstage heb ik Deep Learning gebruikt om een minder tijdrovende manier de beste 2-opt verbetering te selecteren.

Deep Learning is een onderzoeksveld binnen Artificiële Intelligentie en Machine Learning. Deep Learning is ook al beschreven in een van onze eerdere blogposts. In het kort worden er bij Deep Learning neurale netwerken gebruikt. Een neuraal netwerk leert een probleem op te lossen door verbanden te halen uit voorbeelden. Deze voorbeelden mogen echter niet te veel van elkaar verschillen, anders kan het neurale netwerk geen verbanden tussen de voorbeelden leren.

De handelsreiziger in het probleem hierboven wil 20 steden bezoeken. Een andere handelsreiziger wil echter 40 steden bezoeken. Dit betekent dat een neuraal netwerkproblemen met 20 en 40 steden moet kunnen oplossen. Dit is echter niet mogelijk voor standaard neurale netwerken, want een probleem met 20 steden lijkt niet genoeg op een probleem met 40 steden. Dit bracht een interessante uitdaging met zich mee voor mijn afstudeerstage.

Als oplossing heb ik het handelsreizigersprobleem opgesplitst in meerdere delen. Het neurale netwerk leert eerst voor elke stad hoe de omgeving van die stad eruitziet. Vervolgens verzamelt het neurale netwerk alle omgevingen van de steden. Deze verzameling van omgevingen wordt dan gebruikt door het neurale netwerk om een rangschikking te maken van alle 2-opt verbeteringen.

De afbeelding hieronder laat voor een stad (in het groen) de 6 dichtstbijzijnde steden zien.
 

Door te focussen op de omgeving van elke stad ziet een handelsreizigersprobleem er voor een neuraal netwerk ongeveer hetzelfde uit ongeacht of het probleem uit 20 of 40 steden bestaat. Hierdoor is het neurale netwerk dat ik tijdens mijn afstudeerstage bij CQM ontwikkeld heb breed toepasbaar op handelsreizigersproblemen van verschillende groottes.

 

Doorontwikkeling van de neurale netwerken

Het handelsreizigersprobleem is een interessant theoretisch probleem, maar in de praktijk is het niet altijd even goed toepasbaar omdat er dan vaak lastige voorwaardes zijn waar aan voldaan moet worden. Wanneer deze zelflerende neurale netwerken verder worden doorontwikkeld, verwacht ik dat neurale netwerken in de nabije toekomst breed toegepast zullen worden door CQM op het handelsreizigersprobleem en vergelijkbare optimalisatieproblemen.

 

Wilt u meer weten over neurale netwerken, Deep Learning en de problemen die wij oplossen?

Neem dan contact op met consultants Matthijs Tijink of Frans de Ruiter. Zij vertellen u er graag alles over!

 

Afstudeerstage

Erik is (inmiddels afgestudeerd) onderzoeksmasterstudent Operationele Research aan de universiteit van Tilburg. Ben jij ook geïnteresseerd in een afstudeerstage bij CQM? Kijk dan op Stage lopen bij CQM
Heb jij zelf een goed idee voor een afstudeerstage of wil je afstuderen over dit onderwerp, neem dan contact op met Arjen Vestjens.

 

Aanbevolen

 

Op de hoogte blijven van het laatste nieuws?
Volg ons op LinkedIn of meld u aan en beheer hier de mailing die u van CQM wilt ontvangen.

 

 

Dr. Frans de Ruiter

Dr. Frans de Ruiter

Consultant