Lijst in volgorde van snelste route

[IkBenErOokWeer]

Hoi,

Ik ben een hobbyist in het maken van php scripts, nu wil mijn werkgever graag dat ik een webapp schrijf waarmee hij een .xls met adressen (ongeveer 50 adressen per keer) upload en dat de webapp de geoptimaliseerde route uitzoekt en deze lijst op geoptimaliseerde route weer in een xls uitprint.

Ik heb een soort van webapi gemaakt waarmee ik vanuit een .xls de adressen op leesbaar formaat kan aanbieden waarna ik handmatig moet knippen en plakken op een website die deze vervolgens op geoptimaliseerde route zet waarna ik deze gegevens weer upload naar de webapp waar alle gegevens weer samen komen en daar een uitgebreide .xls bestand uit rolt.

Het probleem is dat ik geen geschikte manier/api heb gevonden meer dan 25 adressen om een geoptimaliseerde route direct met het script te laten communiceren waardoor extra handelingen worden uitgesloten.
Is er een goede api te vinden hiervoor of moet ik afstanden via google maps te verkrijgen en dan zelf een route te maken? en hoe kan ik dit het beste doen?

Hebben jullie ideeën waarmee ik aan de slag kan gaan?

[Stoffel]

Of er ergens een API is die dat kan weet ik zo niet, maar als je hoeft het wiel niet opnieuw uit te vinden als je het zelf wil doen. Kijk eens naar Travelling salesman. Het is een heel bekend vraagstuk met genoeg voorbeelden die via Google wel te vinden zijn.

[Woy]

Defineer eerst eens wat beter wat een "Geoptimaliseerde route" is. Als ik puur op deze beschrijving af moet gaan lijkt het wel op het "traveling salesman problem", en dat is niet eenvoudig optimaal op te lossen. Je zult dan met een heuristiek moeten gaan werken, of het moeten gaan brute-forcen.

[Sick Nick]

Met 50 adressen is het op zich prima te doen om gewoon alle combinaties te proberen, wil je iets efficienter aan de slag dan zijn er genoeg heuristische methodes om dat te doen. Je hebt dan niet 100% zeker de snelste route maar iets wat er erg dicht bij in de buurt komt met flink minder CPU kracht.

[Stoffel]

Misschien kun je hier eens naar kijken: http://code.google.com/p/google-maps-tsp-solver/

[IkBenErOokWeer]

Woy schreef op maandag 05 maart 2012 @ 11:50:
Defineer eerst eens wat beter wat een "Geoptimaliseerde route" is.

Ze moeten rolcontainers bij mensen omwisselen, dus zijn +- 50 adressen per dag, dus een zo kort mogelijke route lijkt mij ideaal omdat het toch allemaal in 1 gemeente is.
Deze bakken staan de hele dag buiten dus er hoeft geen rekening met tijd rekening gehouden worden, en met volume hoeft ook geen rekening gehouden worden.
Voorheen deden ze dit door middel van postcodes op volgorde te zetten maar dit werkte niet goed, en mijn huidige webapp vergt nog wat handmatige handelingen die ik nu moet proberen wegwerken.

[GlowMouse]

Sick Nick schreef op maandag 05 maart 2012 @ 12:01:
Met 50 adressen is het op zich prima te doen om gewoon alle combinaties te proberen

want 50! is niet zo groot? Je moet het echt slimmer doen, Concorde TSP solver is waarschijnlijk een goede keus.

[Stoffel]

GlowMouse schreef op maandag 05 maart 2012 @ 14:51:
[...]

want 50! is niet zo groot? Je moet het echt slimmer doen, Concorde TSP solver is waarschijnlijk een goede keus.

Je moet er wel even rekening mee houden dat je niet gewoon de afstanden hemelsbreed in zo'n solver kunt stoppen en verwachten dat je er de slimste route uit krijgt. Je rijdt namelijk niet in een rechte lijn maar hebt te maken met wegen die ook nog eens niet allemaal handig (éénrichtingsverkeer e.d.) zijn om te nemen.

Het stukje code van MIT dat ik hierboven plaatste maakt gebruik van de kaarten en api van Google Maps om dat voor elkaar te krijgen. Ik kan het zo gauw niet vinden, maar volgens mij houdt Concorde TSP solver daar geen rekening mee, toch?

[GlowMouse]

Stoffel schreef op maandag 05 maart 2012 @ 15:00:
[...]


Je moet er wel even rekening mee houden dat je niet gewoon de afstanden hemelsbreed in zo'n solver kunt stoppen en verwachten dat je er de slimste route uit krijgt. Je rijdt namelijk niet in een rechte lijn maar hebt te maken met wegen die ook nog eens niet allemaal handig (éénrichtingsverkeer e.d.) zijn om te nemen.

Het stukje code van MIT dat ik hierboven plaatste maakt gebruik van de kaarten en api van Google Maps om dat voor elkaar te krijgen. Ik kan het zo gauw niet vinden, maar volgens mij houdt Concorde TSP solver daar geen rekening mee, toch?

Google-maps-tsp-solver is een algoritme gecombineerd met een manier om de afstandenmatrix te verkrijgen, Concorde is alleen een algoritme waar je zelf een afstandenmatrix aan moet voeren.

[Sick Nick]

GlowMouse schreef op maandag 05 maart 2012 @ 14:51:
[...]

want 50! is niet zo groot? Je moet het echt slimmer doen, Concorde TSP solver is waarschijnlijk een goede keus.

Met de huidige CPU kracht is 50! niet bizar veel nee, stel dat het 2 minuten duurt op een Core i5 quadcore is dat nog steeds prima aangezien het slechts 1 keer per dag hoeft te gebeuren toch?

[pedorus]

slap gelul

---

Ik zou kijken naar iets op basis van Openstreetmap-data. pgrouting, OsmSharp, of dit ofzo. Google maps api moet je waarschijnlijk voor betalen in dit geval.

[MSalters]

Gezien "werkgever" wordt er sowieso betaald; als Google een euro per geplande route kost dan is dat waarschijnlijk nog steeds goedkoper dan zelf hobbyen.

Of spaar je de moeite: TomTom WORKsmart™

[DukeBox]

Klink ook een beetje als Microsoft Mappoint.