Het handelsreizigersprobleem, in het Engels traveling salesman problem (TSP) genaamd, is één van de bekendste problemen in operationeel onderzoek. Het kan als volgt worden geformuleerd: Als een handelsreiziger n plaatsen moet bezoeken, vind dan de kortste route via die plaatsen zodat iedere plaats precies eenmaal bezocht wordt. De afstanden tussen de verschillende plaatsen zijn gegeven.

Opgave (10 punten)

Definieer een klasse TSP. Deze klasse kan gebruikt worden voor het bepalen van de beste route op basis van de afstanden tussen de verschillende plaatsen.

Specificaties

• De naam van je programmaklasse moet TSP zijn.
• Je moet zelf bepalen welke instantievariabelen deze klasse moet bevatten (1 punt):
  • Hiervoor kijk je best naar de gevraagde methodes.
  • e mag er vanuit gaan dat start- en eindplaats steeds gegeven zijn. Deze kunnen wel gelijk zijn aan elkaar.
  • Elke plaats wordt minimaal en maximaal 1 keer bezocht
• Een constructor met als argumenten 4 String objecten (1 punt):
  • De eerste String bevat de naam van het bestand met de verschillende plaatsen. De bestandsnaam zal gebruikt worden bij het oproepen van de leesPlaatsen methode.
  • De tweede String verwijst naar de naam van het bestand met de afstanden tussen de verschillende plaatsen opgeslagen als een matrix. De bestandsnaam zal gebruikt worden bij het oproepen van de leesAfstanden methode.
  • De derde String verwijst naar de naam van de startplaats. Indien deze naam niet overeenstemt met een naam van een ingelezen Plaats wordt het programma afgesloten.
  • De vierde String verwijst naar de naam van de eindplaats. Indien deze naam niet overeenstemt met een naam van een ingelezen Plaats wordt het programma afgesloten.
• De methode leesPlaatsen (1 punt) met als argument een File object zal de plaatsen inlezen aan de hand van een txt file van de volgende vorm:

Essentiel Gent Centrum;Henegouwenstraat 2;9000;Gent
Essentiel Antwerp Centrum;Huidevettersstraat 57;2000;Antwerpen
Essentiel Antwerp Outlet;Kammenstraat 56;2000;Antwerpen
Essentiel Antwerp Berchem;Lombardenvest 39;2000;Antwerpen
Essentiel Knokke;Kustlaan 146A;8300;Knokke

• De methode leesAfstanden (1 punt) met als argument een File object zal de afstanden tussen de plaatsen inlezen aan de hand van een txt file. Onderstaand voorbeeld geeft de afstand tussen elk paar plaatsen. Voor elke plaats bevat het bestand een rij die aangeeft wat de afstand is tot een andere plaats (in volgorde zoals gegeven in het bestand ingeladen door leesPlaatsen), bijvoorbeeld tussen Essentiel Gent en Essentiel Knokke is de afstand 76,1 km.’

0;58.5;59;52;76.1
58.5;0;0.35;44.1;92.8
59;0.35;0;44.1;92.8
52;44.1;44.1;0;119
76.1;92.8;92.8;119;0

• De methode getAfstand (0,5 punt) bepaalt de afstand tussen plaats A (String argument 1) en plaats B (String argument 2). Indien de plaatsen niet gevonden worden, retourneert de methode 0.
• De methode initialiseerRoute (1 punt) zal op basis van de ingelezen plaatsen, de startplaats en de eindplaats een random route retourneren. De tussenstops kunnen random geshuffeld worden door gebruik te maken van de methode Collections.shuffle.
• De methode totaleAfstand (0.5 punt) met als argument een Route object berekent en retourneert de totale afstand van de opgegeven Route op basis van de ingelezen afstanden tussen de ingeladen plaatsen.
• De methode aantalMogelijkeRoutes (2 punten) retourneert het aantal verschillende routes. Om dit te bepalen maak je gebruik van een private methode faculteit die recursief geïmplementeerd is.

\[n! = \left\{ \begin{array}{ll} n (n-1)! & \mbox{als n > 1} \\ 1 & \mbox{als n = 1} \end{array} \right.\]

• De methode bepaalKortsteRoute (2 punten) retourneert de kortste route aan de hand van het volgende algoritme:
  • Verzamel alle mogelijke verschillende routes aan de hand van de initialiseerRoute-methode.
  • Bepaal de totaleAfstand voor elke route en sla deze op in het Route object.
  • Sorteer de lokale ArrayList van Routes
  • Retourneer de kortste Route

Opmerkingen en tips

• Het is zeker aan te raden om zelf een main methode toe te voegen die je verschillende methodes test.
• Je mag er vanuit gaan dat de gebruikte bestanden correct zijn. Indien een fout wordt gegooid bij het lezen wordt het programma afgesloten.
• Het klasse diagram toont enkel de publieke methodes. Het bevat geen instantievariabelen en private methoden van de klasse TSP.
• De methodes zijn zo gekozen dat ze je helpen bij oplossen van dit probleem. Dit wil bijvoorbeeld zeggen dat je in de methode bepaaldKortsteRoute zeker een andere methode zal moeten gebruiken.
• Het gebruikte algoritme voor het vinden van de snelste route is heel inefficient. In het vak Operations Research zal je zien hoe je dit beter kan aanpakken.