• Guten Start ins Wintersemester 2024/2025

Traveling Salesman Problem

Unser Sponsor SAP 4 Students
Unser Sponsor
vielleicht kann mir jemand bei meinem Problem weiterhelfen:

Die Restriktionen im Skript legen für für das Modell fest, dass es sich um eine Rundreise handelt. Wie erkennt der Algorithmus aber, dass das Depot mit y(0) nicht nur Startpunkt, sondern auch Endpunkt ist?

Meiner Ansicht nach dürfte nach Restriktion 2.2.5 mit 1<y(i)<n das Lager nicht mehr in die Betrachtung mit einbezogen werden?

Vielen Dank im Voraus!
 
Der Algorithmus erkennt, dass die Rundreise im Depot endet durch die 1. Nebenbedingung.
NB (2.2.2) legt fest, dass vom letzten Kunden noch die Rückfahrt zum Depot erfolgen muss, ansonsten wäre die Summe aller Xi0 = 0 und damit diese Nebenbedingung nicht erfüllt.

NB (2.2.5) hat damit nichts zu tun, weil das Depot nicht enthalten ist, da i nicht gleich 0 gilt.
 
Dr Franke Ghostwriter
Stimmt, und da ja dann die Hilfsvariable y um eins erhöht wird (nach jedem Kundenbesuch) wird automatisch die zulässige Lösung generiert.

Danke für die Antwort!
 

Weiter lesen

Oben