[Algemeen] Afstandentabel zelf maken?

[MrQcue]

Ik ben bezig om te bedenken hoe ik een zelfstandig een afstandentabel kan creeeren. Het is de bedoeling dat vanaf iedere bestaande 4 cijferige postcode naar een andere bestaande 4 cijferige postcode de afstand in een tabel komt te staan.

Nu schat ik dat er zo'n 8000 bestaande postcode-cijfer combinaties bestaan in nederland. Wanneer je dus vanaf iedere postcode tot iedere postcode de afstand in een tabel wilt opslaan dan leert een snelle rekensom dat er 8000 x 8000 records in de tabel komen.

Nu vraag ik me af of ik een bestaande offline routeplanner zou kunnen gebruiken met behulp van een soort macro programma die continu alle postcodes invult en de afstand opslaat. Een online routeplanner zou me meteen bannen als ik zoiets zou proberen.

Zou zoiets haalbaar zijn en welke routeplanner zou het meest geschikt zijn? Welke 'macro' programma zou in aanmerking kunnen komen en zijn er toevallig mensen geinteresseerd in zo'n tabel?

PS. Het maakt me niet uit of m'n pc 3 maanden bezig is om de tabel te vullen

[truegrit]

kan je niet de locatie van de verschillende postcodes opslaan om zo de afstand tussen 2 van die postcodes te berekenen als je ze daadwerkelijk nodig hebt?

[MrQcue]

Je bedoelt noorderbreedte en oosterlengte? Dit worden niet echt reeele getallen als je de afstand van Amsterdam naar Urk wilt weten.

Ik ben toch op zoek naar een oplossing die iets beter de afstand over land benaderd ipv hemelsbreed.

[brokenp]

Je zou eens kunnen kijken of je met de google maps api iets kan aanklooien http://www.google.com/apis/maps/

en wat het maximale aantal requests per dag is.

[chem]

Als je 4pp nauwkeurig wil werken dan leert postcode.nl je dat er 4000 4pp's zijn, en dus 16 miljoen combinaties.

Hoe ga je je postcode-centroïde berekenen? Is het nuttig dit zelf te doen ivm compleetheid (er is geen weg volgens je planner?) of uberhaupt kostenplaatje (dagenlang zelf klooien vs in 1x aanschaffen)?

Daarbij schend je ongetwijfeld enkele licentie-rechten als je dit gaat 'rippen'; van welke dienst of applicatie dan ook.

[ Voor 14% gewijzigd door chem op 27-12-2006 19:08 ]

[zwippie]

Nog even een (nattevinger) rekensommetje met misschien verkeerd gekozen getallen maar ok:

Jouw manier (kleine variatie misschien), alle postcodecombinaties met afstand.
4000 * 4000 / 2 records met elk:
- 2 indices naar een postcodecijferreeks, stel een index is 16 bit groot, dus 32 bits totaal
- 1 afstand in hele kilometers (als getal), 16 bits

Dan krijg je dus 8 miljoen records van elk 6 Byte = 46875KB = 45MB. (Exclusief db overhead )


Andere manier, postcodes met locatiegegevens, hieruit bereken je elke keer de afstand.
4000 records met elk:
- 1 postcode index, 16 bits
- locatiegegevens, meestal 3 floating point getalllen, zeg 3 * 32 bits = 96 bits

Dan krijg je dus 4000 records van elk 14 Byte = 55 KB.

Een flink verschil dus.


_{Disclaimer: misschien gaat een DB systeem nog wel wat efficiënter om met de grootte van een index of maak ik een domme denk of rekenfout.}

Edit: had bytes ipv bits geschreven en berekend, foutje! Het lijkt nu in ieder geval iets minder extreem, maar het verschil blijft groot.

[ Voor 10% gewijzigd door zwippie op 27-12-2006 22:27 ]

[MrQcue]

Ok, inkopen is wel een optie.

De prijs is vast gerechtvaardigd maar voor een hobby-project aan de hoge kant. Vandaar dat ik toch zelf iets wilde proberen. Google maps is nog in beta dus misschien niet snel een ban maar ik ben maanden bezig om 16 mljn requests te doen.

Ik zou het ook gedecentraliseerd kunnen uitvoeren en dat meerdere clients meehelpen om de database te vullen.

Toch wil ik nog even kijken of het mogelijk zou zijn met een offline routeplanner oid.

Misschien dat er verder nog meer mensen hun ideeen over hebben. Ik zal ze stuk voor stuk op een rij zetten en gaan afwegen op haalbaarheid, tijd en kosten

[Anoniem: 14829]

Uit de KPN postcode tabel van 7 jaar geleden:

code:

**** AANTAL BESTANDRECORDS 0616853; AANTAL BEBOUWDE REEKSEN 0597136 ****

Daar zitten wel een hoop dubbelen bij (even en oneven huisnummerreeksen), maar je zult aardig boven de 8000 combinaties komen. Hou 't maar op 300.000 of zo...

[ATS]

In elk geval kan je je aantal records halveren door niet de afstand van A naar B én die van B naar A op te nemen, maar aan te nemen dat dat elkaar niet veel zal maken.
@Afterlife: als je gelezen had, dan had je geweten dat de TS het wilde hebben op het niveau van de cijfers, en niet van de letters. Dat scheelt nogal...

[zwippie]

Goed punt, je hebt maar de helft van het aantal records nodig, maar dan zit je nog met een verschil van 46 GB tegen 28 MB als je zo'n tabel gaat maken. Volgens mij is zo'n tabel dus gewoon gekkenwerk...

[Anoniem: 14829]

Oeps, sorry, niet gezien. Zal wel een gevalletje Kerstmist geweest zijn...

[Gomez12]

zwippie schreef op woensdag 27 december 2006 @ 20:45:
Goed punt, je hebt maar de helft van het aantal records nodig, maar dan zit je nog met een verschil van 46 GB tegen 28 MB als je zo'n tabel gaat maken. Volgens mij is zo'n tabel dus gewoon gekkenwerk...

Dat lijkt misschien zo, totdat je echt van postcode naar postcode wilt gaan en je erachter komt dat je bijna nooit hemelsbreed reist en dat je dus erg weinig hebt aan hemelsbrede afstanden...

[Anoniem: 183031]

@zwippie: Hierbij ga je uit van een database. Waarom geen gebruik maken van een simpel plat bestand wat je maakt. Dan kan het een stuk kleiner. Hieronder even een snel rekenvoorbeeld wat (nog) absoluut niet efficient is, maar wel kleiner .

Uitgaande van het feit dat er 4000 postcodes in Nederland bestaan en de route van A naar B gelijk is aan die van B naar A, zijn er dus 8 miljoen afstanden te bepalen.

Iedere postcode is te coderen m.b.v. 14 bits (= 16.384) dus voor 2 postcodes zijn er 28 bits nodig. Neem je voor een afstand 10 bits dan is de maximale afstand 1023 kilometer, voldoende voor in Nederland (lijkt me). Dus met 5 bytes is een afstand tussen twee postcodes te coderen. Dus in totaal past het geheel in 40 Mb.

Hierbij houd ik nog geen rekening met een index maar deze kan je ook zeer klein maken (< 1 Mb). Dus 46 Gb is misschien wat overdreven

[GlowMouse]

Anoniem: 183031 schreef op woensdag 27 december 2006 @ 21:17:
Iedere postcode is te coderen m.b.v. 14 bits (= 16.384) dus voor 2 postcodes zijn er 28 bits nodig. Neem je voor een afstand 10 bits dan is de maximale afstand 1023 kilometer, voldoende voor in Nederland (lijkt me). Dus met 5 bytes is een afstand tussen twee postcodes te coderen. Dus in totaal past het geheel in 40 Mb.

Inderdaad; bovendien is het statische data. Als je consequent de afstand opslaat postcode1 naar postcode2 met postcode1<=postcode2 en bovendien alles gesorteerd wegschrijft, heb je helemaal geen database nodig om zelf heel snel postcodes op te zoeken. Stel je hebt de postcodes 1 t/m 4 en je slaat dat in deze volgorde op (geen idee of aan de driehoeksongelijkheid wordt voldaan bij het voorbeeld):
postcode1|postcode2|afstand
1|1|0
1|2|1
1|3|4
1|4|4
2|2|0
2|3|3
2|4|1
3|3|0
3|4|1
4|4|0

Stel dat ieder record 38 bits inneemt en alle data achter elkaar staat, kun je heel snel de afstand a->b (a<=b) uitlezen op positie 38*[(a-1)*(aantal postcodes)+(b-a)]. In het echt moet je er dan nog wel rekening mee houden dat er gaten zitten in de tabel; afhankelijk van de snelheid kun je die wel of niet opvullen.

Voor het maken van de tabel kun je denk ik het beste AutoIt gebruiken. Je kunt daarmee met scripts allerlei toets/muisacties uit laten voeren. Het enige wat je dan nog nodig hebt is een offline up2date routeplanner.

[ Voor 9% gewijzigd door GlowMouse op 27-12-2006 21:37 ]

[MrQcue]

Eigenlijk is het de bedoeling in mijn geval om een systeem te maken die op basis van een postcode, alle postcodes binnen een bepaalde straal terug geeft.

Deze straal is een vaste optie tussen bijv. 5km 10km 25km 50km en 100km. Eigenlijk een systeem ala marktplaats waar je producten kunt zoeken bij jou in de buurt.

Ik zit te denken om uiteindelijk files te maken die de naam als zoiets krijgen -> 1020_5 Waarbij de eerste 4 cijfers voor de postcode staan en de 5 op het einde voor alle postcodes binnen die straal. Eventueel met een gzip erop (Ik ga het voor een webbased app gebruiken). Of alleen een file 1020 met daarbinnen postcodes binnen 5km, verderop alleen de uitbreiding naar 10km enz...

Het grootste probleem voor nu is eigenlijk de bron van de postcodes. Daarna zijn de mogelijkheden natuurlijk eindeloos.

[rsmits]

Is dit niets?
http://www.alextreme.org/projects/locatiedb/

Wellicht oud, maar een basis

[MrQcue]

Ik heb die inderdaad ook gevonden. Alleen daar zitten de coordinaten van de plaatsen bij waarbij alleen hemelsbreed afstanden te berekenen zijn. Ik probeer eerst om de afstanden te laten berekenen door een planner om een zo reeel mogelijk beeld te geven aan de bezoeker.

Mocht dit te moeilijk/groot of traag zijn dan zal er niets anders opzitten. Tot nog toe heb ik wel het idee dat dit te doen is met enige tijd en energie. Daarnaast vind ik het de moeite waard om het te proberen.

[zwippie]

Oef, ik heb inderdaad bytes ipv bits gebruikt. Dom dom dom. Gevalletje kerst dan maar weer.

[Anoniem: 118860]

Volgens mij ben je je blind aan het staren op details.

Ik zou eerst zorgen dat je je site/service in de lucht krijgt. Daarna kun je altijd nog gaan haarkloven over het afstandbepalingsalgoritme (Maar ik denk dat hemelsbreed voor een "bij u in de buurt" service al goed genoeg is).