Pendeltouren beim Savings erfahren "schummeln" in Ordnung?

[AshCatchem]

Guten Abend zusammen, ich habe mein erstes "Savingsverfahren" implementiert, allerdings habe ich keine Pendeltouren gebildet. Rein formell sollen zu jedem Punkt i Pendeltouren [0,i,0] gebildet werden, wobei 0 das Depot darstellt. Diese Pendeltouren werden nach einem bestimmten Verfahren unter Berücksichtigung von Restriktionen zusammengeführt. Aus [0,3,0] und [0,8,0] wird also [0,3,8,0]. Mir war das zusammenführen der Touren und Löschen der Nullen ehrlich gesagt etwas zu umständlich und so habe ich erst die Tour [0,0] gebildet und dann immer an die vorletzte Stelle im Array den nächsten vorgesehenen Punkt eingefügt. Am Ende kommt mit weniger Rechenaufwand dasselbe raus und die Vorgehensweise ist bis auf die tourenbildung identisch. Sollte ich das ganze nochmal neu aufrollen, damit ich das ganze auch als Savingsverfahren bezeichnen darf oder passt das so?

 

[mihe7]

Wie Du Touren abbildest, spielt für das Verfahren keine Rolle. Was Du "schummeln" nennst, kann man auch als optimierte Abbildung bezeichnen, wobei man noch weiter gehen kann.

Jede Tour beginnt und endet am Depot. Insofern ist es nicht notwendig, das Depot explizit in der Tour darzustellen. [i] wäre dann nichts anderes als die Darstellung der Tour depot -> i -> depot, [2,3] dagegen depot -> 2 -> 3 -> depot.

Wenn für die Berechnung der Kosten (z. B. Strecke in km) die Richtung keine Rolle spielt, brauchst Du Dir nur die Kosten für die einfache Fahrt merken und kannst für die Pendeltouren sofort das Doppelte dieser Kosten ansetzen.

Die Ersparnis von [2,3] ggü. [2],[3] ist dann kosten([2])+kosten([3])-kosten([2,3]), wobei kosten([2])=2*kosten(depot, 2) und kosten([3])=2*kosten(depot, 3) wäre. Dagegen ist kosten([2,3])=kosten(depot,2)+kosten(2,3)+kosten(3, depot), wobei kosten(3, depot) == kosten(depot, 3) gelten würde.

Daraus folgt eine Ersparnis von kosten(depot, 2) + kosten(depot, 3) - kosten(2, 3)