[ALG] berekening ideale route mbv postcode-afstand tabel

[mark_gl]

Ik heb een postcode-afstand tabel voor Nederland met 16 miljoen records. Een record bevat van postcode, naar postcode, afstand en reistijd.

Nu heb ik 30 adressen waar ik heen wil rijden en wil deze mbv die tabel zo ideaal mogelijk inplannen. Ik was aan het denken om naar het adres te rijden dat het verste weg ligt en dan naar het adres dat daar het dichtsbij ligt etc. etc. Uiteindelijk heb ik dan alle 30 adressen gehad.

Ik heb dit uitgetekend maar op papier is deze route dan toch niet zo ideaal (een groot rondje rijden is idealer dan de manier zoals ik bedacht had). Naar mijn mening kan ik dit echter niet berekenen met de huidige tabel die ik heb, maar misschien vergist ik me.

Gaarne jullie ideeën hieromtrent.

[Rac-On]

wat jij gewoon wil is een redelijk effectief pathfinding algoritme! Je graaf (wat staat waarmee in verbinding en wat "kost" die route) heb je al, dus nu nog even een leuk algoritme vinden en implementeren.
Anyway, scriptrequests mogen geloof ik niet hier, dus google eens naar pathfinding, probeer die algortimes te begrijpen en laat ze dan los op je tabel.
Ik denk echter wel dat je zelf een beetje moet sleutelen omdat je 16 bestemmingen hebt, dus enige programmeerervaring is wel handig denk ik.
Wat je wilt doen is van alle mogelijke volgorde-bestemmingen (dat zijn er 16!) de minst kostende route berekenen en dan kijken welke volgorde het beste is!
ow, volgens google: 16 ! = 2.09227899 × 10¹³

[ Voor 22% gewijzigd door Rac-On op 25-08-2005 12:22 ]

[Zoijar]

Dat is het traveling salesman problem, TSP ... vervelend probleem. Er zijn verschillende heuristieken voor een suboptimale oplossing, moet je maar even op google naar zoeken. Een optimale oplossing is niet te doen (NPC probleem). Hoewel... als je ooit nog van plan was om een fields medal te winnen is dit je kans.

[mark_gl]

Effe voor de duidelijk, ik vraag niet naar de kant-en-klare code maar naar de methode op welke manier ik dit kan berekenen.

[Gerco]

Dit klinkt als het Traveling Salesman Problem en dat is een NP-compleet probleem. Er rest je helaas niets dan alle mogelijkheden zo efficient mogelijk uit te proberen, er is geen shortcut naar de oplossing voor zover allerlei knappe koppen weten

Als je het kan oplossen, kun je $1 Miljoen winnen

edit:
Spuit 11, maar met links

[ Voor 5% gewijzigd door Gerco op 25-08-2005 12:26 ]

[.oisyn]

Dit heet het traveling salesperson probleem, en daar is geen exacte oplossing voor te vinden. Zoek er maar eens naar op google, zat info over te vinden (het is dan ook een schoolvoorbeeld )

.edit: right, iets met spuit en een getalletje enzo

[ Voor 14% gewijzigd door .oisyn op 25-08-2005 12:27 ]

[Zoijar]

rac-on schreef op donderdag 25 augustus 2005 @ 12:20:
ow, volgens google: 16 ! = 2.09227899 × 10¹³

Ja leuk is dat heh, stel dat je elke microseconde (bizar) een route kan checken, dan doe je er alsnog 231 dagen over

[.oisyn]

Oh right, ik las het als: 16 is ongelijk aan [groot getal]. Well duh! . Maar er stond dus 16 faculteit

[ Voor 19% gewijzigd door .oisyn op 25-08-2005 12:28 ]

[n00bs]

Veel te lastig om zelf te gaan bepalen, tenzij je een superheld bent in de Wiskunde, geef mij dus maar gewoon routenet.nl

[Maasluip]

mark_gl schreef op donderdag 25 augustus 2005 @ 12:25:
Effe voor de duidelijk, ik vraag niet naar de kant-en-klare code maar naar de methode op welke manier ik dit kan berekenen.

Kijk dan maar eens naar Maasluip in "Routes plannen"
Veel succes

[ Voor 3% gewijzigd door Maasluip op 25-08-2005 12:29 ]

[mark_gl]

Ik was nog iets vergeten te vermelden. Er zijn namelijk 30 adressen die ik kan gebruiken echter op één dag kan ik maximaal 16 adressen bezoeken.

[TRON]

On-the-fly lijkt me dat nog al een zwaar probleem om op te lossen. Je kan denken om een multidimensionale adjacentiematrix te gaan bouwen. Eenmalig zoiets laten berekenen (kan ff duren )

[Rac-On]

mark_gl schreef op donderdag 25 augustus 2005 @ 12:29:
Ik was nog iets vergeten te vermelden. Er zijn namelijk 30 adressen die ik kan gebruiken echter op één dag kan ik maximaal 16 adressen bezoeken.

dan is het zeker niet zelf te berekenen.. voor zover het dat al was voordat je dit gepost had.. zie de post van Zoijar in "[ALG] berekening ideale route mbv postco..."

[ Voor 21% gewijzigd door Rac-On op 25-08-2005 12:33 ]

[Zoijar]

TRON schreef op donderdag 25 augustus 2005 @ 12:31:
On-the-fly lijkt me dat nog al een zwaar probleem om op te lossen. Je kan denken om een multidimensionale adjacentiematrix te gaan bouwen. Eenmalig zoiets laten berekenen (kan ff duren )

Till the end of the universe, and back ....

[alienfruit]

Ik heb dit eens opgelost gebruik te maken van beschikbare GIS data van Nederland (ging toen om een provincie). Het werkte prima, niet echt last gehad van de TSP

[TRON]

@Zoijar: Er zijn aardig wat mogelijkheden inderdaad, de matrix zal dan ook niet een van de kleinste worden

[mark_gl]

De makkelijkste manier is dus een externe dienst als routenet.nl aan te roepen .......

[DrClaw]

je wilt vast een practische oplossing, en niet een 'optimale' computer-oplossing.

dus stel ik voor, om de postcodes gewoon op een kaartje uit te printen en zelf, 'op het oog', je beste 16 eruit te prikken die je die dag gaat bezoeken.

en nu voor de computernerdo's
zoals al gezegd, het traveling salesman probleem is razend complex als je brute force het optimale pad wilt vinden. dus zijn er al algoritmes bedacht die dit hele gedoe versnellen, met behulp van regeltjes (zoals: als het pad zichzelf ergens kruist kan dit nooit een optimaal pad zijn) of doodgewoon een suboptimaal pad als oplossing te accepteren ( kijk eens naar ant systems of naar genetic programming ) . want ik denk dat in het geval van TS een suboptimaal antwoord ook goed is

[Rac-On]

drclaw schreef op donderdag 25 augustus 2005 @ 12:43:
je wilt vast een practische oplossing, en niet een 'optimale' computer-oplossing.

dus stel ik voor, om de postcodes gewoon op een kaartje uit te printen en zelf, 'op het oog', je beste 16 eruit te prikken die je die dag gaat bezoeken.

en nu voor de computernerdo's
zoals al gezegd, het traveling salesman probleem is razend complex als je brute force het optimale pad wilt vinden. dus zijn er al algoritmes bedacht die dit hele gedoe versnellen, met behulp van regeltjes (zoals: als het pad zichzelf ergens kruist kan dit nooit een optimaal pad zijn) of doodgewoon een suboptimaal pad als oplossing te accepteren ( kijk eens naar ant systems of naar genetic programming ) . want ik denk dat in het geval van TS een suboptimaal antwoord ook goed is

maar ik denk dat je hier, met een graaf met 16 miljoen records, 30 bestemmingen, iedere volgorde van bestemmingen is ok en de bestemmingen moeten over minimaal 2 dagen verdeeld worden met max 16 bestemmingen per dag, waarbij voor iedere dag het begin en eindpunt thuis moet zijn, een dusdanige hoeveelheid permutaties hebt dat ook een suboptimaal antwoord binnen afzienbare tijd berekend (zeg max 24 uur rekenen) niet veel beter zal zijn dan wat je zelf kan doen met een landkaart, 30 prikkertjes en een draadje (en gezond verstand uiteraard).

[ Voor 5% gewijzigd door Rac-On op 25-08-2005 12:48 ]

[mark_gl]

ik ben toch echt op zoek naar de optimaalste route

effe terugkomend op dat "traveling salesman probleem" hoe kan je middels een postcode-afstand tabel achterhalen of een pad zich kruist? heb ik daar geen coordinaten tabel voor nodig?

[DrClaw]

dat zei ik al, kaartje printen met de 30 bestemmingen erop, en dan 'op het oog' je bestemmingen van vandaag uitzoeken.

die hele 16miljoen records doen helemaal niet ter zake voor het probleem. er zijn er 'maar' 30. de coordinaten haal je wel uit je 16miljoenregelbestand, maar dat zijn dus maar 30 db queries. gedaan in 1 seconde.

TS, zitten we nu voor jou je programmeeropgave te doen ?

hier een linkje naar een ant systems thesis voor een 25 stedenprobleem, en een 100 stedenprobleem (zag ik zo op het eerste gezicht) : http://joost.student.utwente.nl/thesis/

[ Voor 21% gewijzigd door DrClaw op 25-08-2005 12:52 ]

[mark_gl]

het probleem is dat ik de coordinaten niet heb en dus moet doen met de tabel die ik nu heb en/of een andere tabel gaan aanschaffen.

offtopic: nee we zitten te discussieren over een theoretische oplossing ........

[ Voor 25% gewijzigd door mark_gl op 25-08-2005 12:53 ]

[RSchellhorn]

Toevallig pas een practicum over iets dergelijks gedaan (TU Delft, IN3530 Netwerk Optimalisering). Hier ging het om een Vehicle Routing probleem (met tijdvensters), wat een variant is op het TSP.

De truuk is genoegen te nemen met niet de allerbeste oplossing, maar een goede schatting van het beste resultaat. Om zo'n schatting te bepalen moet je eerst een "Start oplossing" bepalen, die je later eventueel kan verbeteren dmv Local Search technieken. Een start oplossing is vrij snel te bepalen in veel gevallen, maar geven ook niet onder alle omstandingheden een goed resultaat. Local Search kost veel rekentijd, maar kan je route ook enorm verbeteren.

Voorbeeld algoritmes voor een startoplossing zijn:
- Het Saving algoritme van Clark & Write ( 1964 )
- Sweep algoritme van Gillet en Miller ( 1974 )

En voor local search zou je een "Swap" algoritme kunnen proberen.

[ Voor 3% gewijzigd door RSchellhorn op 25-08-2005 13:02 ]

[Woy]

mark_gl schreef op donderdag 25 augustus 2005 @ 12:52:
het probleem is dat ik de coordinaten niet heb en dus moet doen met de tabel die ik nu heb en/of een andere tabel gaan aanschaffen.

Als je de onderlinge afstanden hebt dan hoef je niet de locaties te weten om het in een kaartje weer te kunnen geven. Je kunt het alleen niet op de kaart van b.v. nederland laten zien. Maar de onderlinge locaties kun je natuurlijk makkelijk uitrekenen.

Verder denk ik dat het idd niet mogenlijk is om de optimale oplosing hiervoor snel uit te kunnen rekenen.

[Pino]

mark_gl schreef op donderdag 25 augustus 2005 @ 12:49:
ik ben toch echt op zoek naar de optimaalste route

effe terugkomend op dat "traveling salesman probleem" hoe kan je middels een postcode-afstand tabel achterhalen of een pad zich kruist? heb ik daar geen coordinaten tabel voor nodig?

Of een pad kruist is niet relevant. Je zet bij alle plaatsen waar je heen moet de afstand naar elke andere plaats.

code:

             40km
A----------------------------C
|                        /     \
| 50km         /               \
|           /                    \  80km
|       /     30km                \
|    /                             \
B/-----------------------------------D
                60km

[Rac-On]

drclaw schreef op donderdag 25 augustus 2005 @ 12:50:
die hele 16miljoen records doen helemaal niet ter zake voor het probleem. er zijn er 'maar' 30. de coordinaten haal je wel uit je 16miljoenregelbestand, maar dat zijn dus maar 30 db queries. gedaan in 1 seconde.

hangt er van af, zijn die 16miljoen regels een set waarmee voor iedere postcode-combinatie de afstand te vinden is, of zijn die 16miljoen record meer strepen in een net en moet je er dus meerdere samenvoegen om van a naar b de totale kosten te weten?[

mark_gl schreef op donderdag 25 augustus 2005 @ 12:52:
het probleem is dat ik de coordinaten niet heb en dus moet doen met de tabel die ik nu heb en/of een andere tabel gaan aanschaffen.

offtopic: nee we zitten te discussieren over een theoretische oplossing ........

bij een postcode de plaatsnaam vinden is zo gebeurd, en dan kan je ze op de kaart zetten. Dit is echt de snelste oplossing, maar helaas niet geldig als we het over een theoretisch probleem hebben

[Anoniem: 143036]

Je zou het met het dijkstra algoritme op kunnen lossen, Nu heb ik een ander vraag je hoe kom je aan die data. Want ik ben daar ook naar opzoek.

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Wij hebben een kaart interface van mapserver (en kaarten) postcode zou een leuke toevoegeing zijn.

Alvast bedankt

[Woy]

Dijkstra's algoritme was toch een algoritme om met zo'n goedkoop mogenlijk pad van het ene punt naar een andere te komen in een graaf?

Hier is de kortste route van het ene punt naar het andere punt wel bekend maar moet er een route over meerdere punten berekend worden.

[Cavorka]

30x Routenet route laten bepalen, alle 30 printen, lijm, schaar en knutselen maar!

Beetje flauw misschien, maar als je 30x een route op een kaartje hebt met dezelfde schaal en over elkaar legt... Ik denk dat dat dan sneller is dan een ingewikkeld algoritme te gaan schrijven (lang niet zo leuk, maar wel effieicient). Hoe snel moet je de totale route hebben, en is het echt een serieus probleem, of alleen een uitdaging?

[Woy]

Cavorka schreef op donderdag 25 augustus 2005 @ 14:12:
30x Routenet route laten bepalen, alle 30 printen, lijm, schaar en knutselen maar!

Beetje flauw misschien, maar als je 30x een route op een kaartje hebt met dezelfde schaal en over elkaar legt... Ik denk dat dat dan sneller is dan een ingewikkeld algoritme te gaan schrijven (lang niet zo leuk, maar wel effieicient). Hoe snel moet je de totale route hebben, en is het echt een serieus probleem, of alleen een uitdaging?

Dan heb je alleen alle routes vanaf je startpunt. Dan is het nog steeds niet makkelijk om de kortse route te berekenen die langs alle punten loopt. Je weet tenslotte niet in welke volgorde je ze af moet.

Maar met 30 punten over de kaart verdeeld is het met de hand ook niet makkelijk om de optimale route te vinden hoor. Met een klein aantal punten is dat nog wel te doen. Maar dan is het ook nog wel haalbaar om het brute force uit te rekenen.

[Cavorka]

Goed punt, had ik niet aan gedacht.

Hm, dus dan krijg je 30 + 29 + 28 + ... + 3 + 2 + 1 losse routes. Dat is wel een beetje veel om met de hand te gaan zitten uitvogelen. Je kan ze namelijk ook twee kanten op rijden.

[mark_gl]

hangt er van af, zijn die 16miljoen regels een set waarmee voor iedere postcode-combinatie de afstand te vinden is, of zijn die 16miljoen record meer strepen in een net en moet je er dus meerdere samenvoegen om van a naar b de totale kosten te weten

de tabel ziet er als volgt uit

code:

van postcode | naar postcode | afstand  | duur
----------------------------------------------
      1000         1000           0         0
      1000         1001         500        34

[ Voor 8% gewijzigd door mark_gl op 25-08-2005 14:29 ]

[Rac-On]

mark_gl schreef op donderdag 25 augustus 2005 @ 14:27:
[...]


de tabel ziet er als volgt uit

code:

van postcode | naar postcode | afstand  | duur
----------------------------------------------
      1000         1000           0         0
      1000         1001         500        34

wat ik bedoel is als je van postcode 1500 naar 2500 wil, is er dan een entry:
1500 2500 Xkm Yminuten
of moet je een optelsom maken van
1500 1000 Xkm Yminuten
1000 2000 Xkm Yminuten
2000 2500 Xkm Yminuten
dat is redelijk van invloed op de moeilijkheid van je probleem namelijk...

[mark_gl]

wat ik bedoel is als je van postcode 1500 naar 2500 wil, is er dan een entry:
1500 2500 Xkm Yminuten
of moet je een optelsom maken van
1500 1000 Xkm Yminuten
1000 2000 Xkm Yminuten
2000 2500 Xkm Yminuten
dat is redelijk van invloed op de moeilijkheid van je probleem namelijk...

je hoeft niks op te tellen "1500 - 2500" staat gewoon als record in de tabel met de afstand en tijdsduur

[mark_gl]

Nu heb ik een ander vraag je hoe kom je aan die data. Want ik ben daar ook naar opzoek

De tabel is ingekocht.

[.oisyn]

De vraag is: als je van postcode x naar postcode y wilt, staat die (x,y) combinatie dan gegarandeerd in de tabel of moet je een postcode z vinden zodat je de afstanden (x, z) en (z, y) kunt gebruiken?

Als alle postcodes (van 1000 t/m 9999) dan zouden er 9000² = 81.000.000 records nodig zijn. Nou weet ik dat niet alles gebruikt wordt, maar als er 16 miljoen records zijn betekent dat dat er slechts 4000 verschillende postcodes in de database staan, dat lijkt me een beetje weinig (of is dit wel reëel voor nederland?)

/wederom laat

[mark_gl]

De vraag is: als je van postcode x naar postcode y wilt, staat die (x,y) combinatie dan gegarandeerd in de tabel of moet je een postcode z vinden zodat je de afstanden (x, z) en (z, y) kunt gebruiken?

Als alle postcodes (van 1000 t/m 9999) dan zouden er 9000² = 81.000.000 records nodig zijn. Nou weet ik dat niet alles gebruikt wordt, maar als er 16 miljoen records zijn betekent dat dat er slechts 4000 verschillende postcodes in de database staan, dat lijkt me een beetje weinig (of is dit wel reëel voor nederland?)

/wederom laat

Zoals ik begrepen heb van het bedrijf waar we dit ingekocht hebben bevat de tabel alleen postcodes van adressen dus geen postbussen, etc. vandaar er slecht 16 miljoen records inzitten.

Hier hebben we ook genoeg aan, aangezien je geen route gaat uitrekenen naar een postbus

[ Voor 18% gewijzigd door mark_gl op 25-08-2005 14:42 ]

[Rac-On]

mark_gl schreef op donderdag 25 augustus 2005 @ 14:36:
[...]


je hoeft niks op te tellen "1500 - 2500" staat gewoon als record in de tabel met de afstand en tijdsduur

owkee, dat was dus mijn vraag.. het maakt het in ieder geval makkelijker, maar ik denk dat het feit dat je met 16 bestemming al 16! mogelijke routes hebt en je ook nog eens met de verdeling van 30 bestemmingen over 2 dagen zit, het redelijk onmogelijk maakt.
maar goed, verdiep je eens in de in dit topic genoemde problemen/algoritmes zou ik zeggen.

[Woy]

Cavorka schreef op donderdag 25 augustus 2005 @ 14:25:
Goed punt, had ik niet aan gedacht.

Hm, dus dan krijg je 30 + 29 + 28 + ... + 3 + 2 + 1 losse routes. Dat is wel een beetje veel om met de hand te gaan zitten uitvogelen. Je kan ze namelijk ook twee kanten op rijden.

Was het maar zo dat je maar 30 + 29 + 28 + ... + 3 + 2 + 1 verschillende routes had want dat zijn er maar 435 mogenlijkheden en dat is makkelijk met de computer door te rekenen.

Je hebt 30 * 29 * 28 * ... * 3 * 2 * 1 oftewel 30! mogenlijk verschillende combinaties die je door moet rekenen ( Even geen rekenening gehouden dat je het over twee dagen verdeel ).

Nou zitten daar wel alle routes 2 maal in omdat het in een rondje niet uithaalt of je linksom of rechtsom rijdt maar dan nog is het onmogenlijk om alle mogenlijkheden door te rekenen.

[djluc]

Zou je niet iets kunnen doen als:
tabelletjes maken als:
1 -> 2 = 30km
1 -> 3 = 50km
1 -> 4 = 10km

Vervolgens sorteer je deze en pak je de laatste:
1 -> 3 = 50km
1 -> 2 = 30km
1 -> 4 = 10km

Je neemt dan dus de van 1 naar 4, dus 10km. Vervolgens maak je dus eenzelfde tabelletje voor nummer 4. Daar laat je de 1 dan dus weg. Vervolgens houdt je nog maar een beperkt aantal routes over lijkt mij? Eventueel kan je nog een aantal alternatieven controleren.

[Rac-On]

djluc schreef op donderdag 25 augustus 2005 @ 15:43:
Zou je niet iets kunnen doen als:
tabelletjes maken als:
1 -> 2 = 30km
1 -> 3 = 50km
1 -> 4 = 10km

Vervolgens sorteer je deze en pak je de laatste:
1 -> 3 = 50km
1 -> 2 = 30km
1 -> 4 = 10km

Je neemt dan dus de van 1 naar 4, dus 10km. Vervolgens maak je dus eenzelfde tabelletje voor nummer 4. Daar laat je de 1 dan dus weg. Vervolgens houdt je nog maar een beperkt aantal routes over lijkt mij? Eventueel kan je nog een aantal alternatieven controleren.

nee, want de som daarvan is niet per se de snelste route. sterker nog, de kans dat deze de snelste route is is rete klein.
@rwb: uitgaande van 16 bestemmingen op een dag, heb je 16! mogelijke routes. Daar zitten alle routes dubbel in, dus 16!/2. 16! routes narekenen a 1 miliseconde per route is volgens Zoijar 231 dagen werk, dus als je brute forces heb je voor 1 dag 231/2 = ruim 160 dagen nodig. En dan is 1 miliseconde per route nog niet eens haalbaar

[Woy]

rac-on schreef op donderdag 25 augustus 2005 @ 15:50:
[...]

nee, want de som daarvan is niet per se de snelste route. sterker nog, de kans dat deze de snelste route is is rete klein.
@rwb: uitgaande van 16 bestemmingen op een dag, heb je 16! mogelijke routes. Daar zitten alle routes dubbel in, dus 16!/2. 16! routes narekenen a 1 miliseconde per route is volgens Zoijar 231 dagen werk, dus als je brute forces heb je voor 1 dag 231/2 = ruim 160 dagen nodig. En dan is 1 miliseconde per route nog niet eens haalbaar

Maar je weet niet welke 16 punten het best samen gaan dus je moet alsnog alle 30 punten doen wat dus 30!/2 volgordes oplevert die je allemaal op 3 verschillende manieren over 2 dagen kunt verdelen ( dag1: 16, dag2: 14. Dag 1 en 2 15 en Dag 1: 14, dag 2: 16 )

dus dan heb je (30!/2) * 3 mogenlijkheden die je door moet rekenen en dat gaat nog een heeeeeeeeel erg stuk langer duren om door te rekenen.

[Rac-On]

rwb schreef op donderdag 25 augustus 2005 @ 16:04:
[...]

Maar je weet niet welke 16 punten het best samen gaan dus je moet alsnog alle 30 punten doen wat dus 30!/2 volgordes oplevert die je allemaal op 3 verschillende manieren over 2 dagen kunt verdelen ( dag1: 16, dag2: 14. Dag 1 en 2 15 en Dag 1: 14, dag 2: 16 )

dus dan heb je (30!/2) * 3 mogenlijkheden die je door moet rekenen en dat gaat nog een heeeeeeeeel erg stuk langer duren om door te rekenen.

en dan vergeet je nog mee te rekenen dat heb eindpunt van de eerste dag en het vertrekpunt van de 2de dag ook nog eens zo dicht mogelijk bij de "thuisbasis" moet liggen, wat nog een extra factor met zich mee brengt.
ergo:
30 prikkers op een grote landkaart en dan even inschatten wat handig is, is een stuk haalbaarder dan een algoritme schrijven.
Sommige dingen is de mensen nogsteeds beter in dan de gemiddelde compu..

[Woy]

rac-on schreef op donderdag 25 augustus 2005 @ 16:17:
[...]

en dan vergeet je nog mee te rekenen dat heb eindpunt van de eerste dag en het vertrekpunt van de 2de dag ook nog eens zo dicht mogelijk bij de "thuisbasis" moet liggen, wat nog een extra factor met zich mee brengt.

Daar moet je met de afstand bereken wel rekening mee houden ja maar het levert geen extra mogenlijkheden op want het start/eindpunt staat altijd vast. Je kunt alleen kiezen om op een dag 14,15 of 16 adressen te doen.

[djluc]

rac-on schreef op donderdag 25 augustus 2005 @ 15:50:
[...]

nee, want de som daarvan is niet per se de snelste route. sterker nog, de kans dat deze de snelste route is is rete klein.

Ik zou toch echt iets dergelijks gaan proberen om zo al een enorme hoeveelheid uit te sluiten. Je hoeft hiervoor uiteraard niet alleen de korste afstanden te nemen. Je kan ook bijvoorbeeld de laagste 3 ofzo nemen. Daar kom je onderzoekend wel achter. Het is duidelijk dat we niet een brute-force op alle data kunnen doen, dus moeten we die toch enigzins gaan minimaliseren.

[curry684]

Zolang je alleen die afstanden hebt kun je niets en is het brute-force rossen maar. Als je ook de coordinaten hebt, die je gewoon bij www.postcode.nl kunt bestellen (of voor een erg outdated versie even [rml]jvhaarst in "[ alg] Koppeling GPS-positie <-> straatna..."[/rml] lezen), kun je een algoritme bouwen dat aannames maakt op basis van die coordinaten en vervolgens daarmee het probleem stukken behapbaarder maakt. Dat algoritme wordt ook wel A* (a-star) genoemd en is in alle game-engines de methode waarmee legers en spelers automatisch om meren en bergen lopen

[Woy]

curry684 schreef op vrijdag 26 augustus 2005 @ 02:54:
Zolang je alleen die afstanden hebt kun je niets en is het brute-force rossen maar. Als je ook de coordinaten hebt, die je gewoon bij www.postcode.nl kunt bestellen (of voor een erg outdated versie even [rml]jvhaarst in "[ alg] Koppeling GPS-positie <-> straatna..."[/rml] lezen), kun je een algoritme bouwen dat aannames maakt op basis van die coordinaten en vervolgens daarmee het probleem stukken behapbaarder maakt. Dat algoritme wordt ook wel A* (a-star) genoemd en is in alle game-engines de methode waarmee legers en spelers automatisch om meren en bergen lopen

Als je de afstanden onderling hebt kun je zelf toch coordinaten uitrekenen? Dat die coordinaten niet de coordinaten op een kaart zijn haalt niet zoveel uit. Dus dan kan je toch een A* algoritme toepassen.

[Anoniem: 3652]

rwb schreef op vrijdag 26 augustus 2005 @ 08:58:
[...]

Als je de afstanden onderling hebt kun je zelf toch coordinaten uitrekenen? Dat die coordinaten niet de coordinaten op een kaart zijn haalt niet zoveel uit. Dus dan kan je toch een A* algoritme toepassen.

En hoe zit het dan met bochtige wegen? In dat geval is de afstand in de postcode tabel (veel?) groter de afstand hemelsbreed.

Maar even practisch gedacht, je kunt ook beginnen met een random route, de afstand hiervan op te slaan, vervolgens nog een variant proberen en indien deze korter is, deze nieuwe route als "de" route te gebruiken. Je krijgt (waarschijnlijk) niet de meest ideale route, maar volgens mij krijg je vrij snel een redelijk goede route. En hoe langer je dit algoritme laat draaien, hoe beter je uiteindelijke route wordt.

[curry684]

rwb schreef op vrijdag 26 augustus 2005 @ 08:58:
[...]

Als je de afstanden onderling hebt kun je zelf toch coordinaten uitrekenen? Dat die coordinaten niet de coordinaten op een kaart zijn haalt niet zoveel uit. Dus dan kan je toch een A* algoritme toepassen.

De coordinaten zelf nemen niet mee of je binnen of buiten de bebouwde kom gaat, of 5 of 20 stoplichten tegenkomt, of je wellicht dit stuk snelweg bij Rotterdam maar 80 mag etc. De gegeven afstand tussen de postcodes moet leading blijven wat dat betreft. De coordinaten staan je enkel toe te cheaten waarmee je vooraannames kunt doen om zo snel mogelijk bij je doel te komen, iets wat in het zuivere handelsreizigersprobleem niet kan, en daarom kun je dus met A* het benodigd aantal te berekenen routes enorm verkleinen. Blijft tot op zekere hoogte wel gewoon brute force though als je een echt optimale oplossing zoekt....

[Woy]

curry684 schreef op vrijdag 26 augustus 2005 @ 10:27:
[...]

De coordinaten zelf nemen niet mee of je binnen of buiten de bebouwde kom gaat, of 5 of 20 stoplichten tegenkomt,

Nee maar er staat nergens dat hij deze gegevens in zijn algroritme mee wil nemen. Want alle andere mogenlijkheden die ik hier lees houden daar ook geen rekening mee. Wat ik begrijp wil hij de volgorde alleen bepalen aan de hand van deze gegevens, dus dan kan je nooit rekening houden met de daadwerkelijke route die er gereden moet worden.

[curry684]

rwb schreef op vrijdag 26 augustus 2005 @ 11:29:
[...]

Nee maar er staat nergens dat hij deze gegevens in zijn algroritme mee wil nemen. Want alle andere mogenlijkheden die ik hier lees houden daar ook geen rekening mee. Wat ik begrijp wil hij de volgorde alleen bepalen aan de hand van deze gegevens, dus dan kan je nooit rekening houden met de daadwerkelijke route die er gereden moet worden.

mark_gl schreef op donderdag 25 augustus 2005 @ 12:15:
Ik heb een postcode-afstand tabel voor Nederland met 16 miljoen records. Een record bevat van postcode, naar postcode, afstand en reistijd.

Nu ik het trouwens zie, pijnlijke tabel als je bedenkt dat NL 600k postcodes telt en je dus met 360000000000 records zit? Hij zal vast alleen aangrenzende of 4p postcodes bevatten

[Woy]

curry684 schreef op vrijdag 26 augustus 2005 @ 11:33:
[...]


[...]



Nu ik het trouwens zie, pijnlijke tabel als je bedenkt dat NL 600k postcodes telt en je dus met 360000000000 records zit? Hij zal vast alleen aangrenzende of 4p postcodes bevatten

Volgens mij staan in de database alleen het numerieke gedeelte van de postcode ( Dus je kan al niet eens precies de locatie bepalen met de routeplanner ). Dus dan zijn er maximaal 10K postcodes. En in werkelijkheid zijn dat er natuurlijk nog een stuk minder.

Maar aangezien je dan toch geen exacte locatie hebt kun je natuurlijk ook nooit goed een reistijd berekenen.

[ Voor 9% gewijzigd door Woy op 26-08-2005 11:40 ]

[mark_gl]

Nu ik het trouwens zie, pijnlijke tabel als je bedenkt dat NL 600k postcodes telt en je dus met 360000000000 records zit? Hij zal vast alleen aangrenzende of 4p postcodes bevatten

klopt, postcode-afstand tabel is inderdaad 4 posities (wordt anders veel te veel records).

[Rac-On]

curry684 schreef op vrijdag 26 augustus 2005 @ 02:54:
Zolang je alleen die afstanden hebt kun je niets en is het brute-force rossen maar. Als je ook de coordinaten hebt, die je gewoon bij www.postcode.nl kunt bestellen (of voor een erg outdated versie even [rml]jvhaarst in "[ alg] Koppeling GPS-positie <-> straatna..."[/rml] lezen), kun je een algoritme bouwen dat aannames maakt op basis van die coordinaten en vervolgens daarmee het probleem stukken behapbaarder maakt. Dat algoritme wordt ook wel A* (a-star) genoemd en is in alle game-engines de methode waarmee legers en spelers automatisch om meren en bergen lopen

ik ken het algoritme niet, maar is het ook geschikt om te bepalen in welke volgorde je het beste een X aantal punten langs kunt gaan?

[Woy]

mark_gl schreef op vrijdag 26 augustus 2005 @ 12:13:
[...]


klopt, postcode-afstand tabel is inderdaad 4 posities (wordt anders veel te veel records).

Daarom zou het handig zijn als je alleen de posities van de postcodes had. Dan kan je daarna zelf wel de benodigde afstanden berekenen. Dan had je aan een tabel met 600K postcodes en locaties genoeg gehad.

[Kaalaamaazoo]

Even een vraagje, hoe komt u aan de tabel met de afstanden tussen die postcodes. Ik moet voor een kilometer registratie database de afstand tussen twee postcodes weten, een tabel als deze zou de oplossing zijn.

Groeten,

Joost

[Gerco]

@Kaalaamaazoo:
Die tabel kun je hier kopen. Eenmalige aanschaf vanaf €1300,- abonnementen vanaf €650,- voor 3 jaar.

[ Voor 29% gewijzigd door Gerco op 13-05-2006 12:15 ]

[Creepy]

Kaalaamaazoo schreef op zaterdag 13 mei 2006 @ 12:05:
Even een vraagje, hoe komt u aan de tabel met de afstanden tussen die postcodes. Ik moet voor een kilometer registratie database de afstand tussen twee postcodes weten, een tabel als deze zou de oplossing zijn.

Groeten,

Joost

Zie ook -NMe- in "De afstand tussen twee postcodes."