Wie minimiere ich die Gesamtstrecke, die beim Transport von Waren zwischen Lagern zurückgelegt wird?

Question

Es gibt N Lagerhallen, die die Q [i] Menge eines Artikels an Tag 1 speichern. Am Tag 2 sind die Anforderungen für die Menge Q '[i] in jedem Warenlager. Im Grunde muss der Artikel zwischen Lagerhäusern bewegt werden, um die Beschränkung zu erfüllen. Die Entfernung zwischen Lagerhäusern ist bekannt. Welche Klasse von Algorithmen kann das lösen? Irgendwelche Zeiger? Ziel ist es, die zurückgelegte Strecke bei bewegten Gütern zu minimieren.

Answer 1

Dies ist ein klassisches Problem, das mit einem Min-Cost Max-Flow-Algorithmus gelöst wird. Sie erweitern Ihr Diagramm, indem Sie zwei zusätzliche Scheitelpunkte hinzufügen: eine Quelle und eine Senke. Von der Quelle bis zu allen Scheitelpunkten des ursprünglichen Graphen fügen Sie eine Kante mit der Kapazität Q[i] und Nullkosten hinzu. Von jedem Eckpunkt des ursprünglichen Graphen fügen Sie der Senke eine Kante mit der Kapazität Q'[i] und Nullkosten hinzu. Für die Kanten zwischen den Scheitelpunkten des ursprünglichen Diagramms legen Sie die Kapazität auf unendlich fest und berechnen den Abstand zwischen den entsprechenden Lagern und berechnen dann den minimalen Kosten-Max-Fluss. Der Fluss zwischen den Eckpunkten des ursprünglichen Graphen zeigt Ihnen an, wie viele Güter zwischen diesen beiden Lagern transportiert werden.

Einige Links:

1. wikipedia article etwa min-Cost-max-flow

2. Ein sehr gutes presentation (sie ein Problem ähnlich wie bei Ihnen dort hat, aber nicht identisch)

3. Hier a great article mit den Details einer sehr guten Umsetzung