Ein Simulated Annealing-Verfahren für das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen

Der Beitrag stellt ein Simulated Annealing-Verfahren zur Lösung des um Zeitfensterrestriktionen erweiterten Standardproblems vor. Die Zielfunktion berücksichtigt zwei Zielkriterien, die Minimierung der Fahrzeuganzahl als primäres und die Minimierung der Gesamtentfernung als sekundäres Kriterium. In der ersten Stufe eines zweistufigen Verfahrensansatzes wird daher zunächst -ohne Berücksichtigung der Gesamtentfernung - ein Tourenplan mit minimaler Fahrzeuganzahl berechnet. Von diesem Tourenplan ausgehend wird dann in der zweiten Stufe die von den Fahrzeugen zurückzulegende Gesamtentfernung minimiert. Der Focus des Beitrags liegt auf den in der ersten Verfahrensstufe getroffenen problembezogenen Entwurfsentscheidungen, die insbesondere die verwendeten Nachbarschaftsstrukturen und die entwickelte Kostenfunktion betreffen. Zur Bewertung des entwickelten Simulated Annealing-Verfahrens werden einschlägige Benchmarkprobleme von SOLOMON (1987) berechnet und die Ergebnisse mit den besten bekannten Lösungen verglichen.