Wie heißt diese logistische Variante von TSP?

Ich habe ein logistisches Problem, das als eine Variante von $\text{TSP}$ . Es ist so natürlich, ich bin sicher, es wurde in der Operations-Forschung oder ähnlichem untersucht. Hier ist eine Sichtweise auf das Problem.

Ich habe Lagerhäuser im kartesischen Flugzeug. Es gibt einen Pfad von einem Lager zu jedem anderen Lager, und die verwendete Entfernungsmetrik ist die euklidische Entfernung. Darüber hinaus gibt es verschiedene Artikel. Jeder Artikel kann in einer beliebigen Anzahl von Lagern vorhanden sein. Wir haben einen Sammler und wir bekommen einen Ausgangspunkt dafür, sagen wir den Ursprung . Der Sammler erhält eine Bestellung, also eine Liste der Gegenstände. Hier können wir davon ausgehen, dass die Liste nur unterschiedliche Elemente und jeweils nur eines enthält. Wir müssen die kürzeste Tour bestimmen , beginnend einige Anzahl der Lager zu besuchen , so dass die wir jeden Punkt auf der Bestellung abholen.n 1 ≤ i ≤ n $P$$n$$1 \leq i \leq n$$s$$(0,0)$$s$

Hier ist eine Visualisierung einer zufällig generierten Instanz mit . Lager sind mit Kreisen dargestellt. Rote enthalten Punkt , blaue Punkt und grüne Punkt . In Anbetracht etwas Ausgangspunkt und die Reihenfolge ( ), müssen wir eine rote, eine blaue und eine grüne Lager so der Auftrag abgeschlossen werden kann wählen. Aus Versehen gibt es in diesem Beispiel keine mehrfarbigen Lagerhäuser, sodass alle genau einen Artikel enthalten. Diese spezielle Instanz ist ein Fall von Set-TSP .$P = 35$$1$$2$$3$$s$$1,2,3$

Ich kann zeigen, dass das Problem tatsächlich -hard ist. Stellen Sie sich eine Instanz vor, in der sich jeder Artikel in einem anderen Lager . Die Bestellung ist so, dass sie jeden Artikel enthält. Jetzt müssen wir jedes Lager besuchen und die kürzeste Tour finden, die dies tut. Dies entspricht dem Lösen einer Instanz von .$\mathcal{NP}$$i$$P_i$$P_i$$\text{TSP}$

Ich bin mir sicher, dass dies schon früher untersucht wurde, da es zumindest im Zusammenhang mit Logistik, Routing und Planung so offensichtlich nützlich ist. Ich habe zwei Fragen:

1. Wie heißt das Problem?
2. Wie gut kann man hoffen, das Problem zu approximieren (unter der Annahme von )?$\mathcal{P} \neq \mathcal{NP}$

Ich bin ziemlich zufrieden mit dem Namen und / oder den Hinweisen auf das Problem. Vielleicht folgt die Antwort auf den zweiten Punkt leicht oder ich kann das selbst herausfinden.

Das Problem liegt in wenn die Anzahl der Elemente konstant ist.$\mathrm{P}$

Sei die Anzahl der Elemente (unabhängig von n ). Verwenden Sie für jede Bestellung von Artikeln das Backtracking, um alle zulässigen Routen auszuprobieren: Sie gehen zuerst durch ein Lager für den ersten Artikel (versuchen Sie alle Lager), dann durch ein Lager für den zweiten Artikel und so weiter.$K$$n$

Es gibt Bestellungen der Artikel. Sei W i die Anzahl der Lager für Artikel i . Die Anzahl von Routen ist Π K i = 1 W i ≤ Π K i = 1 n = n K . Daher ist die Laufzeit des obigen Algorithmus O ( K ! N K ) , was für festes K ein Polynom ist .$O(K!)$$W_i$$i$$\prod_{i=1}^K W_i \leq \prod_{i=1}^K n = n^K$$O(K! n^K)$$K$

Wenn die Anzahl der Elemente in linear sein kann , ist das Problem mindestens so schwer zu approximieren wie T S P : Sie können eine Instanz von T S P nehmen , für jeden Scheitelpunkt ein Element erstellen, wie Sie es notiert haben, und dann zusätzliche Scheitelpunkte hinzufügen sehr weit weg von allen anderen Scheitelpunkten, um n aufzublasen (und daher genügend Elemente zuzulassen, dass jeder Scheitelpunkt der T S P -Instanz ein anderes Element hat), ohne die Härte der Annäherbarkeit von T S P zu zerstören . Beachten Sie, dass wenn Ihre Punkte in der euklidischen Ebene liegen, dies Ihnen nicht wirklich hilft, da es ein P T A $n$$TSP$$TSP$$n$$TSP$$TSP$$PTAS$für planare .$TSP$

Dieses Problem kann unter anderem als Beispiel für das Problem des reisenden Käufers angesehen werden. ist eine Verallgemeinerung von TSP und wurde zuerst von T. Ramesh, Travelling Buyer Problem, 1981, vorgeschlagen. Das Problem ist wie folgt:$\text{TPP}$$\text{TSP}$

Wir erhalten eine Menge von Märkten und eine Menge von N = { 1 , . . . , n } von Produkten. Außerdem erhalten wir c i j , die Kosten für die Reise von Stadt i nach Stadt j , und nicht negative d i j , die Kosten für ein Produkt i auf dem Markt j . Der Käufer startet in seiner Heimatstadt (z. B. Stadt 1 ) und reist zu einer Teilmenge der$M = \{ 1, ..., m \}$$N = \{ 1, ..., n \}$$c_{ij}$$i$$j$$d_{ij}$$i$$j$$1$ Städte und kauft jedes der n Produkte in den Städten, die er besucht, und kehrt in seine Heimatstadt zurück. Ziel ist es, eine Tour für den Käufer zu finden, bei der die Summe der Reise- und Kaufkosten minimiert wird.$m$$n$

In der ursprünglichen Frage sind Lager also Märkte. Jeder auf einem Markt verfügbare Artikel hat den gleichen Preis. Wenn Artikel auf einem Markt j nicht verfügbar ist , wird sein Preis d i j auf einen hohen Wert gesetzt.$i$$j$$d_{ij}$

$\text{TSP}$$\text{TPP}$$\text{TSP}$$\text{TPP}$$(1-o(1))\ln n$$\mathcal{P} = \mathcal{NP}$R. Ravi und FS Salman, Approximationsalgorithmen für das Problem des reisenden Käufers und seine Varianten im Netzwerkdesign, 1999 . Der Wikipedia-Eintrag für TPP enthält auch Links zu einigen heuristischen Ansätzen.

Was Sie beschrieben haben, klingt eher nach einem Planungsproblem in der KI. Es klingt wie das, was mit einer Planungssprache wie STRIPS , ADL, PDDL usw. modelliert werden könnte. Nach der Modellierung kann der Plan durch einen von vielen Planungsalgorithmen / Heuristiken gelöst werden, bei denen es sich typischerweise um Algorithmen zur Suche nach Zustandsräumen handelt. Die Wiki-Links sollten Ihnen den Einstieg erleichtern. Ein Planungskapitel in einem AI-Lehrbuch kann ebenfalls hilfreich sein. Ein Beispiel für einen PDDL-Planer ist die GraphPlanner-Software .

Zugegeben, einige ziemlich entartete Instanzen dieses Problems können TSP entsprechen. Dieses Problem ist im Allgemeinen nicht dasselbe wie TSP und es ist auch kein TSP. Sowohl in TSP als auch in Set TSP ist die Menge der zu besuchenden Städte (Lagerhäuser) vordefiniert. Hier geht es uns nicht wirklich darum, welche Lager besucht werden, sondern darum, einen Auftrag so billig und effizient wie möglich zu erfüllen. Sie könnten Aufträge haben, die nicht erfüllt werden können. Ein Planer wird in einem solchen Fall mit einem leeren oder einem Teilplan zurückkommen - einem Bericht über die Nichterfüllbarkeit. Es ist allgemein bekannt, dass das Problem der Planerfüllbarkeit PSPACE-vollständig ist. In TSP oder Set TSP gibt es immer eine optimale Tour - diese ist jedoch möglicherweise nicht eindeutig.