A.W. Renckens
Oplossingsmethoden 'Traveling Salesman Problem' gevisualiseerd.
Computeropdracht,
Rapport 2000.LT.5401, Transporttechnologie, Logistieke Techniek.
Het 'traveling salesman problem' (afgekort TSP) is een in de logistieke
techniek veel voorkomend probleem. De problematiek van het TSP is het
vinden van een optimale route tussen punten in een netwerk. Met behulp van
een computerprogramma kunnen benaderingen voor de optimale route gevonden
worden zonder al te veel rekentijd.
Het vinden van deze benaderde optimale route gebeurt in twee stappen. De
eerste stap is het genereren van een beginoplossing. In het geschreven
computerprogramma kan met behulp van een van vijf veel voorkomende
algoritmes (nearest neighbour node insertion, nearest node insertion,
farthest node insertion, sweep insertion, random insertion) een
beginoplossing worden gedefinieerd. De tweede stap is het verbeteren van
deze beginoplossing. Met twee veel voorkomende procedures (two optimality
en three optimality) kunnen in het computerprogramma de beginoplossingen
worden verbeterd.
De opdracht was het schrijven van een computerprogramma, dat de
oplossingsmethoden van het TSP visualiseert. Het programma dient dus in
eerste instantie om de problematiek van het TSP inzichtelijk te maken en
niet om werkelijk bestaande problemen om te lossen. Voor het schrijven van
het TSP programma is gebruik gemaakt van het softwarepakket Delphi. Met
Delphi kunnen applicaties voor Windows-omgevingen worden ontwikkeld met
minimale invoer van programmeercode Pascal.
Rapporten studenten Logistieke Techniek
Gewijzigd: 2000.11.13;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.