London tube en GPS

De meesten kennen of gebruiken wel eens een GPS-navigatie systeem. De toepassing waarover dit artikel zal gaan is die van “plan je route”. Met deze applicatie kan je een reis plannen waarbij je verschillende punten moet passeren. Bijvoorbeeld je vertrekt in Antwerpen, je rijdt naar Brussel en wil het postkantoor van Wilrijk bezoeken én Technopolis in Mechelen. Je GPS zal nu een optimale route voorstellen, … met behulp van wiskunde.

AfbeeldingDe tak van de wiskunde die hier gebruikt wordt is de grafentheorie. Het voorbeeld dat ik hierboven gaf heeft natuurlijk een zeer logische oplossing en vergt geen hogere wiskunde. Je passeert eerst even het postkantoor in Wilrijk, en springt binnen in technopolis te Mechelen, waar je toch moet passeren om in Brussel te raken. Het zou nogal gek zijn dat je GPS je eerst naar Technopolis laat rijden, om dan terug te komen tot Wilrijk, waarna je van daar naar Brussel rijdt. Dit zou je veel meer tijd en brandstof kosten dan het logische, eerste plan. Maar als je enkele tientallen tussenstops moet maken is het al wat moeilijker om de kortste/snelste reisroute te berekenen.

Denk maar aan bedrijven zoals DHL of UPS. Zij hebben elke dag vele mensen op de baan die her en der pakjes moeten leveren. Als je elke werknemer elke dag enkele minuten sneller kan laten leveren door een optimale reisweg, kan je dit op enkele jaren miljoenen euro’s besparen. Dit wederom door besparing op brandstof en slijtage aan de banden door minder kilometers en omdat je dagelijks meer klanten kan bedienen natuurlijk.
De route die de chauffeurs moeten berekenen kan je zien als een wiskundige graaf. Hierbij beeld je elke bestemming af met een punt of cirkel, en elke weg tussen deze bestemmingen geven we weer als de lijnen die de cirkels verbinden.
AfbeeldingStel dat we bijvoorbeeld aan al de posten (“a” tot en met “i”) moeten leveren. Hoe weten we nu in welke volgorde dit het snelste zal gebeuren? Veronderstel dat ons startpunt in a ligt. Vertrekt onze bestelwagen richting punt b gevolgd door c of e, of doen we eerst d, om van daar naar i te rijden….., er zijn onnoemelijk veel opties. Ze allemaal 1 voor 1 afgaan kan letterlijk jaren duren. Eind jaren 90 berekenden wiskundigen de snelste manier om alle Duitse steden te bezoeken, 15.112 in totaal. Met behulp van computers vonden ze de oplossing, maar dit duurde geen uren, dagen of weken, maar liefst 22.6 jaar de tijd! Ze deden dit niet met zomaar een pc. Het klusje werd geklaard door meer dan 100 processors.

Een eerste stap richting de oplossing is de wegen een waarde geven. Deze waarde kan toegekend worden aan het aantal kilometers van de verbindingen… een weg met een waarde 20 is bijvoorbeeld 20 kilometer lang, één met waarde 10 is maar de helft zolang enz…. Als tijd je belangrijkste zorg is kan je bijvoorbeeld autosnelwegen een waarde 5 geven (ze nemen weinig tijd in beslag), en straten in drukke centra geef je een waarde van bijvoorbeeld 20 (hier ben je 4 maal zoveel tijd kwijt dan op de snelweg)…
Je kan ook een combinatie maken van tijd en afstand efficiëntie natuurlijk…
AfbeeldingNu kan je een wiskundig algoritme gebruiken om te bepalen welke route te nemen. Er zijn meerdere van deze algoritmes in de omgang, maar het bekendste zal Dijkstra’s algoritme zijn (dit wordt door de meeste GPS-systemen gebruikt). Indien je het algoritme in zijn werk wil zien kan je deze of deze site eens bezoeken. Simpel opgelost toch?…
Het probleem is dat het voor oefeningen met een groot aantal steden zelfs voor een computer zeer lang kan duren om de meest efficiënte volgorde te zoeken. Verder hebben we ook nog geen bewijs gevonden dat het wiskundige algoritme wel degelijk dé beste oplossing biedt. Het sluit vele oplossingen uit, en geeft je een van de betere antwoorden, maar het is dus nog steeds niet wiskundig bewezen dat het de allerbeste oplossing is.
Dit probleem is gekend als het handelsreizigersprobleem en een van de meest bekende en moeilijkste openstaande problemen in de wiskunde.

AfbeeldingIndien je denkt een systeem te hebben gevonden om dit raadsel te ontrafelen (of toch ook een heel goede benadering) kan je je misschien eens wagen aan de tube-challenge. Het is een wedstrijd rond het bekende metro systeem van Londen. Het hele ondergrondse tramnet telt er nu al 270 stations. De opzet van de wedstrijd is heel makkelijk: hoe snel kan jij alle stations bezoeken door enkel gebruik te maken van de trams die ertussen pendelen. Als je van de figuur van de leveranciers tracht te achterhalen hoeveel mogelijkheden er zijn, of de inspanningen leest rond het berekenen van het handelsreizigersprobleem, zal je ondervinden hoe immens moeilijk deze wedstrijd wel is. (voor de geïnteresseerden, het record staat nu op 13 uur, 20 minuten en 27 seconden).
De kaart van “the tube” zoals ze het hele ondergrondse tram-net (met het beroemde “mind the gap”) daar noemen wordt trouwens meestal weergegeven als een graaf. de bolletjes zijn de stations en de tramlijnen die ze verbinden zijn de gekleurde lijnen (zie boven).
Ook het Antwerpse openbare vervoersplan heeft nu zulk een weergave (zie onder).
Afbeelding
Misschien kunnen we de stad Antwerpen en de lijn wel warm maken voor een gelijkaardig idee. Wie kan er het snelst alle Antwerpse stations bezoeken? Een leuk idee om stad, openbaar vervoer én wiskunde te promoten.

DAAROM WISKUNDE
(lees ook Wiskunde en camerabewaking)

Giedts Tom

Advertisements

1 Comment

Filed under andere, Toepassingen voor elke dag, wiskunde in de natuur

One response to “London tube en GPS

  1. Pingback: De Chinese postbode en Pacman | waaromwiskunde

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s