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 (8 punten)

Definieer een klasse Route. Deze klasse kan gebruikt worden voor het opslaan van een route.

Specificaties

• De naam van je klasse moet Route zijn.
• De klasse bevat drie instantievariabelen (1 punt):
  • Een array van Plaats objecten (route) voor het bijhouden van de route
  • Een double totaleAfstand voor het bijhouden van de totale afstand van een route
• Je klasse bevat een constructor (2 punten) met als argumenten twee Plaats objecten en een ArrayList van Plaats tussenstops. De twee Plaats objecten komen overeen met de start- en eindplaats van de route. De ArrayList tussenstops wordt gebruikt om de route instantievariabele verder op te vullen.
• De klasse implementeert de Comparable Interface. De bijhorende compareTo methode kijkt naar de totale afstand van een route (1 punt). Routes worden met deze methode geordend van kortste afstand naar langste afstand.
• De methode getAantalPlaatsen retourneert het totaal aantal plaatsen van de route, inclusief stop en einde.
• De methodes getPlaats en setPlaats (1 punt):
  • De methode getPlaats retourneert het Plaats object van de route op de opgegeven plaats.
  • De methode setPlaats voegt op de gegeven plaats in de array een Plaats object toe.
• De methode getTussenStops (1 punt) retourneert een ArrayList met de tussenstop Plaatsen. Deze arraylist bevat dus niet start en einde.
• De methode toString ((1 punt)) retourneert een route als volgt:

==> [Naam start plaats] ==> [Naam stop 1] ==> [Naam stop 2] ==> [Naam stop 3] ==> [Naam stop 4] ==> ... ==> [Naam eindplaats]

• hashCode en equals (1 punt):
  • Overschrijf de methode hashCode (van Object) die geen parameters heeft. De methode geeft een geheel getal terug dat gebruikt zal worden voor hash-structuren te maken. Het verwachte gedrag van dit soort methode is dat de hash code gelijk zal zijn voor objecten die gelijk zijn en ongelijk voor objecten die ongelijk zijn. De methode hoort enkel gebruik te maken van de instantievariabele ‘route’.
  • Overschrijf de methode equals (van Object) die een Object object als parameter heeft. De methode geeft ‘true’ terug indien de meegegeven parameter niet ‘null’ is, een object van de klasse Plaats is én de instantievariabele route van beide objecten gelijk is. Dit wil zeggen dat de arrays even lang zijn en bovendien op elke plaats in de array een Plaats met dezelfde naam bevatten.

Opmerkingen en tips

• Het is toegelaten om accessor en mutator methodes toe te voegen aan je klasse indien je deze nodig hebt voor de implementatie van de TSP klasse.
• de hashCode en equals methode mag je genereren via IntelliJ maar zorg er voor dat je dit op een correcte manier doet.