Problem des Handelsreisenden als Webservice / API / Library?

[Djon]

Hallo!

Ich habe eine kleine Adressenverwaltung in Qt/C++ geschrieben. Mit Hilfe dieser Anwendung werden die Adressen erfasst. Als zusätzliches Feature möchte ich die Adressen so sortieren, dass diese auf dem kürzesten Weg besucht werden können, also genau das, was das Problem des Handelsreisenden ausmacht. Kenn einer von euch ein Webservice / API / Library, die so eine Sortierung vornimmt?

Vielen Dank im Voraus!

Gruß Djon

[Tiamat]

Kann ich dir geben, hab ich mal in C programmiert. Kannste sicher leicht auf dein Problem zurechtschustern.


#include <stdio.h>
#include <stdlib.h>

#define MAX_STADT 100
#define true 1

int trip[MAX_STADT];
int tripCopy[MAX_STADT];
int distance[MAX_STADT][MAX_STADT];

/* zunächst wird hier eine primitive Route erzeugt, die von der 1. bis zur letzten Stadt verläuft, ohne darauf zu achten,
ob sie gut ist oder nicht. Der Algorithmus verbessert die Route ja im Laufe der Zeit */
void init()
{
int x, y;
for (x = 0; x < MAX_STADT; x++){
trip[x] = x;
tripCopy[x] = x;

for (y = x; y < MAX_STADT; y++){
distance[x][y] = distance[y][x] = rand() % 100; // hier kannst du deine Werte aus der Adressverwaltung übergeben
}
}
}

// Für die Route existiert weiterhin ein Kopie. Das ist wichtig, um den alten Zustand wiederherzustellen, falls der
// Algorithmus die Fitness nicht verbessern konnte.
void copyTrip()
{
int t;

for (t = 0;t < MAX_STADT; t++){
tripCopy[t] = trip[t];
}
}

// Fitnessfunktion: überprüft, wie lange die Route insgesamt ist
int getFitness()
{
int t;
int length=0;
for (t = 0; t < MAX_STADT - 1; t++){
length += distance[trip[t]][trip[t+1]];
}
length += distance[trip[MAX_STADT-1]][trip[0]];
return length;
}

// vertauscht zwei Städte im Random-Prinzip
void swapCity()
{
int swap;
int rnd1 = rand() % MAX_STADT;
int rnd2 = rand() % MAX_STADT;

swap = trip[rnd2];
trip[rnd2] = trip[rnd1];
trip[rnd1] = swap;
}

// Stellt den ursprünglichen Zustand wieder her
void undoSwap()
{
int t;
for (t = 0;t < MAX_STADT; t++){
trip[t] = tripCopy[t];
}
}

// Das Hillclimbing Verfahren hat das Manko oft in lokalen Optima stecken zu bleiben.
// Deswegen wird jede neue Hypothese mit einem neuen Startplatz initialisiert
void setNewStartPoint()
{
int x,end_cnt;

for (x = 0;x < MAX_STADT; x++){
trip[x] = x;
tripCopy[x] = x;
}
end_cnt = rand() % 10000;
for (x = 0;x < end_cnt; x++){
swapCity();
}
}

int main(void)
{
int lastFitness;
int fitness;
int bestFitness;
int individuumTimeCounter=0;
int indNr=0;

init();


lastFitness = getFitness();
bestFitness = lastFitness;

do{
swapCity();
// wenn sich die Fitness verschlechtert
if ((fitness = getFitness()) >= lastFitness){
undoSwap();
}

else{
// wenn sich die Fitness verbessert
lastFitness = fitness;
copyTrip();
if (lastFitness < bestFitness){
bestFitness = lastFitness;
}
}

individuumTimeCounter++;
// Nach 100000 Durchläufen wird eine neue Hypothese erzeugt
if (individuumTimeCounter == 100000){

printf("Fitness = %d IndividuumNr=%d bestFitness=%d\n",lastFitness, indNr, bestFitness);
individuumTimeCounter = 0;
indNr++;

setNewStartPoint();
lastFitness = getFitness();
}

}while(true);

return 0;
}

Gruß
Tiamat

[Djon]

Hallo!

Vielen Dank für den Algorithmus. Das einzige Problem, welches ich noch habe, sind die Entfernungen zwischen einzelnen Adressen. Diese sind mir im Programm nicht vorher bekannt :frown:

Gruß Djon

[Monger]

Geht es hier um real existierende Adressen? Sprich: irgendwelche Orte auf der Deutschlandkarte?

Wohl alle großen Kartendienste haben eine eigene API, d.h. auf jeden Fall mal Bing Maps und Google Maps / Earth. Die lassen sich auch benutzen, um Suchergebnisse in Koordinaten zu überführen, und dann den Routenplaner mit diesen Koordinaten zu füttern.


Edit: mal ein Beispiel für die Bing Api: http://www.microsoft.com/maps/isdk/ajax/

[Djon]

Hallo!

Ja, es geht um real existierende Adressen in Deutschland.


Gruß Djon

[pest]

Der Algorithmus von Tiamat wird doch schon bei einer kleinen Anzahl von Städten unhandlich, ist ja praktisch nicht besser als vollständige Evaluation.
"hab ich mal programmiert" klingt nach exakter Lösung in polynomialer Laufzeit.

[Tiamat]

Ähm du weißt schon, dass das Problem des Handlungsreisenden ein NP-schweres Problem ist? Dann wüsstest du auch dass heutige Rechner Jahre bräuchten, um das TSP-Problem mit 100 Städten vollständig zu überprüfen.

Das ist hier aus der Gattung der Optimierungsalgorithmen der billigste Vertreter, der Hillclimber und der liefert in der Form bereits nach 100 Individuen gute Resultate. Ab dem 500. Individuum wird hier kaum mehr ne bessere Lösung gefunden, was net heißt, dass man die optimale Route gefunden hat, aber welches Random-Verfahren verspricht das schon.

[Pinoccio]

Ähm du weißt schon, dass das Problem des Handlungsreisenden ein NP-schweres Problem ist?Ich bin mir recht sicher, daß pest das weiß. ;-)
Es gibt bessere Startszenarien als eine zufällige Auswahl. (MST zum Beispiel). Und so schlecht ist das Verfahren auch nicht, da einfach umzusetzen.

Was zum klicken und Spielen (http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm).

mfg

[Djon]

Hallo!

Ich habe mal grob überschlagen: Für die Berechnung kommen meisten nur ca. 10 Städte / Orte zusammen und das müsste mein Rechner noch gerade so schaffen :-)

Gruß Djon

[pest]

die 3.628.800 Möglichkeiten bei 10 Städten solltest du einfach alle ausprobieren um die garantiert kürzeste Route zu ermitteln.

[Djon]

Hallo!

Ja, die Anzahl an Möglichkeiten ist eigentlich überschaubar... Jetzt noch die Frage welche API ich von meinem Programm aus nutzen könnte, um die Entfernung, also keine Luftlinie, sondern die normale Entfernung die man mit dem Auto zurücklegen müsste, zwischen zwei Städten / Dörfern zu bestimmen.

Gruß Djon

[Exxtreme]

Bei sowas wird man um Geokodierung nicht herumkommen. Da würde ich eher schauen ob es fertige Libraries zu kaufen gibt. Die haben dann sehr hochoptimierte Algorithmen zur Routen-/Tourenplanung. Ist im Endeffekt viel billiger als selbst sowas zu implementieren.

[Monger]

Wie ich bereits geschrieben habe: spricht irgendwas gegen die Bing Maps Services? Wenn die Anfrage an einen Webservice kein Problem darstellt, wäre das wahrscheinlich die einfachste Lösung.


Wenn du das alles "offline" machen wolltest, kommt da ja auch einiges an Datenmengen zusammen. Wahrscheinlich musst du ja mindestens mal die gesamte Deutschlandkarte parat haben.

[Tiamat]

Ich bin mir recht sicher, daß pest das weiß. ;-)
Es gibt bessere Startszenarien als eine zufällige Auswahl. (MST zum Beispiel). Und so schlecht ist das Verfahren auch nicht, da einfach umzusetzen.

Was zum klicken und Spielen (http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm).

mfg

Das Verfahren find ich richtig gut, arbeitet auch richtig fix.

[DocEW]

die 3.628.800 Möglichkeiten bei 10 Städten solltest du einfach alle ausprobieren um die garantiert kürzeste Route zu ermitteln.
Sind sogar nur 362.880, weil die Anfangsstadt egal ist, oder?

[pest]

ups...ja stimmt, bei einer rundtour betrachtet man die erste stadt als festgelegt

ist genauso, wie wenn sich n leute im kreis aufstellen, dann gibt es (n-1)! möglichkeiten

[Pinoccio]

ups...ja stimmt, bei einer rundtour betrachtet man die erste stadt als festgelegt

ist genauso, wie wenn sich n leute im kreis aufstellen, dann gibt es (n-1)! möglichkeitenNaja. Je nach konkreter Formulierung sind es noch weniger Routen, da die beiden Rundtouren 1231 und 1321 vermutlich gleich lang sind.
(Google Maps Routenplan: Berlin - Köln - München - Hamburg - Berlin: 2216 km, 20:31 h (http://maps.google.de/maps?f=d&source=s_d&saddr=Berlin&daddr=k%C3%B6ln+to:m%C3%BCnchen+to:hamburg+to:berlin&hl=de&geocode=FY1xIQMdSKTMACkBWQM_N06oRzFwO15bRiAhBA%3BFfhKCQMdKDNqACnlL6tpkSW_RzHwdyp K_GAnBA%3BFXaL3gIdGrOwACnZX4yj-XWeRzF9mLF9SrgMAQ%3BFZcqMQMdl3WYACm5Exh-g2GxRzGgOtZ78j0mBA%3BFY1xIQMdSKTMACkBWQM_N06oRzFwO15bRiAhBA&gl=de&mra=ls&sll=51.745485,10.18562&sspn=3.238236,7.849731&ie=UTF8&z=7) gegenüber Berlin - Hamburg - München - Köln - Berlin: 2219 km und 20:25 h (http://maps.google.de/maps?f=d&source=s_d&saddr=berlin&daddr=hamburg+to:m%C3%BCnchen+to:k%C3%B6ln+to:berlin&hl=de&geocode=FY1xIQMdSKTMACkBWQM_N06oRzFwO15bRiAhBA%3BFZcqMQMdl3WYACm5Exh-g2GxRzGgOtZ78j0mBA%3BFXaL3gIdGrOwACnZX4yj-XWeRzF9mLF9SrgMAQ%3BFfhKCQMdKDNqACnlL6tpkSW_RzHwdypK_GAnBA%3BFY1xIQMdSKTMACkBWQM _N06oRzFwO15bRiAhBA&mra=ls&sll=51.151786,10.415039&sspn=26.354153,62.797852&ie=UTF8&z=7))

mfg

[pest]

ja wenn man von einem symmetrischen tsp ausgeht wären es (n-1)!/2

[ScottManDeath]

Notfalls aus den Postleitzahlen der Adressen eine grobe Distanz ermitteln.