Routeplanner met Genetic Algorithm

Projectbeschrijving

In dit project heb ik samen met een klasgenoot een Proof of Concept ontwikkeld voor het oplossen van het handelsreizigersprobleem (TSP). Hierbij worden een genetic algorithm, brute force en nearest neighbour algoritme gecombineerd. Hierdoor kunnen de algoritmes met elkaar vergeleken worden.

De applicatie maakt gebruik van externe route-API’s om realistische afstanden en reistijden te verwerken in de optimalisatie.

Technieken

Technische uitdagingen

Een belangrijke uitdaging binnen dit project was het ontwerpen van een efficiënte representatie van routes binnen de populatie van het genetic algorithm.

Daarnaast vereiste het combineren van externe routegegevens met optimalisatielogica een zorgvuldige scheiding tussen datastructuren en evaluatiefuncties.

Resultaat

Het genetic algorithm biedt de beste combinatie van goede routes en efficiëntie. De andere algoritmen waren of te zwaar om met grotere datasets te werken, of gaven niet vaak genoeg een snelle route terug. Hierdoor wordt aangetoond dat deze aanpak geschikt is voor praktische optimalisatievraagstukken.

Screenshots

Hier is de simpele GUI voor de applicatie te zien. Deze is expres simpel gehouden aangezien het een Proof of Concept betreft.

Hier is de kaart te zien die wordt gegenereerd. Hierbij worden de routes weergeven met een simpele legenda erbij.