Wie mache ich eine Mathe-Optimierung (TSP) in R, vielleicht mit optim()

Question

Ich arbeite an der Schaffung eines grundlegenden Reisen Verkäufer Problem (TSP) in R, aber ich habe nicht die richtigen Ressourcen gefunden, um mir zu helfen optim() mit importierten Daten. Oder vielleicht optim() ist nicht wirklich, was ich suche. Ich werde mein Beispiel teilen und hoffe, dass Sie mich entweder in die richtige Richtung weisen oder bei dem spezifischen Problem helfen können.

Es gibt eine Reihe von Orten, an denen ich versuche, die kürzeste Route zu finden. Jeder Standort muss einmal und nur einmal auf der Route besucht werden. Die Route muss am Ursprung beginnen und enden. Die möglichen Lösungen sind:

Von Herkunft> zu Location1> zu Location2> und zurück zur Herkunft oder

Von Herkunft> zu Location2> zu Location1> und

zu Herkunft zurück

Ich habe folgende importiert Daten in R:

distances <- read.csv("distances_test.csv") 

ORIGIN-----DESTINATION-----DISTANCE 

Origin-----Location2-------4.161917178 

Origin-----Location1-------31.16857564 

Location1--Location2-------30.75861336 

Location1--Origin----------31.16857564 

Location2--Location1-------30.75861336 

Location2--Origin----------4.161917178 

Jetzt versuche ich, um zu bestimmen, wie R zu sagen, dass:

die Zielfunktion die Summe o zu minimieren f die Entfernungen multipliziert mit x, wobei x eine Zuweisungsvariable (x = 0 oder 1) ist, die angibt, dass die spezifische Route ausgewählt wurde.

Die Einschränkungen sind:

(1) x zwischen 0 und 1 ist, x eine ganze Zahl ist (oder wenn es eine Verknüpfung mit Optim() ist, daß x ist binär, um anzuzeigen). (2) Summe von x über allen Ursprungsindizes = 1 (dh der LKW verlässt jeden Standort einmal) (3) Summe von x über alle Zielindizes = 1 (dh Lkw-Lkw kommt einmal an jedem Standort an) (4) initial Herkunft Index ist der Ursprung (5) endgültiger Zielindex ist der Ursprung

Mit optim(par, objective), ich bin nicht klar, was die Anfangsparameter wären oder wie würde ich diese Zielfunktion (dh min sum(i=1..n)sum(j=1...n) distance(i,j) * x(i,j))

Answer 1

R schreiben kann Ihnen helfen, wenn Sie mit der Funktion solve() arbeiten, wenn Sie TSP über den einfachen Simplex-Algorithmus lösen wollen. Sie können sich auch diese Website ansehen, auf der mehrere Heuristiken für dieses Problem existieren e implementiert in R. https://operatiology.wordpress.com/2014/05/15/traveling-salesman-problem-in-r/