Az útvonaltervezés művészete

Navigáció – GPS. Előszó: Mi akik már több éve használunk navigációs szoftvereket tudjuk, hogy ezek a legtöbb esetben nem az általunk használt leggyorsabb útvonalat használják, hanem egy algoritmus által…

…legjobbnak ítélt utat, ami legtöbbször a közelében sincs a valóban leggyorsabb/legrövidebb útvonalnak. A Here szoftver tervezői ezen próbálnak változtatni. A cikkből az is kiderül, hogy Londonban érdemes-e Here szoftvert használni az utazáshoz… Íme:

Egy-egy útvonal kiválasztása néha nagyon szubjektív és személyes döntéseken alapul. Egy taxisofőr számára a legjobb útvonal nagyon más lehet, mint amit a HERE útvonaltervező algoritmusa kiszámít, vagy amit az utasa – vagy éppen a tisztelt Olvasó választana. Ez az oka annak, hogy a HERE útvonaltervezői csapatának kutatói és fejlesztői alaposan tanulmányozzák azokat az útvonalakat, amelyeket az általuk kidolgozott útvonaltervező algoritmus kiválaszt – szeretnék megtudni, mennyire célszerűek ezek az útvonalak, hogy ezáltal továbbfejlesszék, még személyre szabottabbá és a körülményekhez még jobban alkalmazkodóvá tegyék őket.

Jelenleg Bangkoktól Szöulig és Londontól Rio de Janeiróig egyszerre a világ negyven városában zajlik az útvonaltervezés minőségének elemzése, és a tervek szerint hamarosan számos további város is bekerül majd a programba.

A közelmúltban érdekes kísérlet zajlott Londonban: összehasonlították a HERE útvonaltervező algoritmusa által kiszámított útvonalakat a londoni taxisok vizsgaanyagaként használt híres Blue Book („Kék Könyv”) fejből megtanulandó útvonalaival. A HERE mérnökei mind a 320 útvonalat digitalizálták, hogy egy számítógépes modell segítségével összehasonlíthassák őket azzal, ahogyan a HERE tervezi meg őket

here_bluebook

A HERE legrövidebb útvonalai a Blue Bookban szereplő útvonalakhoz képest. A sok sárga és zöld vonal a HERE algoritmusa és a Blue Book közötti nagyfokú vagy teljes egyezést jelöli.

here_bluebook2

Színkód: A pirostól zöldig terjedő skála azt mutatja, hogy milyen mértékben egyezik a HERE által tervezett útvonal azzal, amit a helybeli taxisok választanak.

– A londoni taxisofőröket arra képzik ki, hogy a Blue Bookban szereplő, a távolság alapján meghatározott legrövidebb útvonalat használják. Az összehasonlító tesztek során örömmel tapasztaltuk, hogy a HERE legrövidebb útvonal üzemmódja következetesen megegyezett a Blue Book ajánlásával – magyarázza Pedro Campos, a HERE útvonaltervezői minőségellenőrző csapatának egyik guruja

here_bluebook3

A világoskék vonal a HERE által kiszámított legrövidebb útvonal, mely tökéletesen egyezett a Blue Book ajánlásával. Ez azt jelenti, hogy a HERE által kiszámított útvonal a Blue Book minden egyes kötelezően érintendő (a képen zölddel jelölt) útvonalpontján áthaladt. Érdemes ezt összehasonlítani a sötétkék vonallal, mely nem más, mint a HERE által kiszámított leggyorsabb útvonal – ez 0 százalékos egyezést mutatott a Blue Bookhoz ajánlásával.

– Más városokban, ahol nincs olyan segédeszközünk, mint a londoni Blue Book, kiválasztottunk 200, kiindulási pontból és célállomásból álló útvonalat. Ezután felkértünk egy nagy helyismerettel rendelkező helyi sofőrt (általában a regionális térképért és egyéb tartalmakért felelős csapatunk valamelyik tagját, hiszen ők a térképen szereplő utak szó szerint minden centiméterén végighajtottak már), hogy adják meg, ők melyik útvonalat választanák a kétszáz pontpár között, majd összehasonlítjuk őket azzal, amit a HERE útvonaltervező algoritmusa generál – mesél tovább Pedro.

– Ahol jelentős eltérést tapasztalunk, ott tovább vizsgálódunk, hogy kitaláljuk, mi lehet a különbség oka. Rio de Janeiróban például kiderült, hogy a HERE általában a gyorsforgalmi utakat vette számításba, míg a helybeliek inkább a másodrendű utakat választották.

– Azt láttuk, hogy a riói sofőrök inkább elkerülik a gyorsforgalmi utakat, mert azt feltételezik, hogy azokon úgyis mindig dugó van, függetlenül attól, hogy ez így van-e vagy sem. Most azon dolgozunk, hogy kiderítsük, vajon a rendszerünk miért nem így működik, és hogy módosítanunk kell-e az algoritmus működését azért, hogy ritkábban ajánlja a gyorsforgalmi utakat – mondja Pedro

here_rio

A riói útvonalelemzések eredménye. Itt bizony jóval több sárga és narancsszínű vonal látható, mint Londonban.

here_rio2

A HERE által tervezett (kék) útvonal Rióban a gyorsforgalmi úton halad, míg a helyi profik inkább a közvetlenebb, másodlagos utakat használják (zöld vonal).

A csapat számára fontos másik tanulság Dél-Koreából származott, ahol a sofőrök megszokták, hogy a kereszteződések előtt direkte erre a célra szolgáló megforduló sávokat használják. A HERE algoritmusa általában kerüli a megfordulást, ami a legtöbb helyen rendben is van, de Dél-Koreában jelentősen rontotta az útvonaltervezés minőségét. Ez is újabb példa arra, hogy miképpen segít hozzá az útvonaltervezés minőségének elemzése a helyi igények és vezetési szokások megértéséhez. Míg a londoni Blue Book egyértelműen a távolság alapján számított legrövidebb útvonalat részesíti előnyben, vannak más szempontok is, melyek alapján útvonalat lehet tervezni – például az idő, az üzemanyag-fogyasztás vagy az útvonal esztétikai erényei.

– Persze kompromisszumra mindig szükség van. Egy útvonal nem lehet a leggyorsabb, legrövidebb, legszebb, leggazdaságosabb és legkönnyebben követhető egyszerre, ezért választani kell, hogy melyik szempont a legfontosabb – magyarázza Pedro. – Például a leggyorsabb útvonal üzemmódban csak az út időbeli hosszát vesszük figyelembe, és a többi szemponttól függetlenül az abszolút leggyorsabban megtehető útvonalat próbáljuk kiválasztani.

Az útvonal „humanizálása”

A HERE útvonaltervezés-minőségért felelős csapata pillanatnyilag olyan modelleket használ, melyek a HERE algoritmusát egy referencia-útvonalhoz hasonlítják, de arra készülnek, hogy a jövőben a HERE által generált útvonalakat azokkal is összevessék, melyeket a helyi autósok valós időben a leggyakrabban választanak.

– Innen már csak egy lépés, hogy az útvonal igazodjon az adott sofőr személyes preferenciáihoz, és figyelembe vegye, hogy az illető milyen úttípusokon közlekedik legszívesebben, persze a többi sofőr viselkedésének függvényében is – mondja Pedro.

Pedro és csapata már azonosított is kilenc olyan szempontot, mely alapján egy-egy átlagos sofőr eldönti, hogy egy adott útvonal jó vagy rossz – ilyen például az egyszerű követhetőség, a menetidő, az utazás kényelme és az érintett helyek szépsége.

Például vannak, akik nem szeretnek balra, nagy ívben kanyarodni, és ha az autó érzékeli, hogy ilyen helyzetekben gyakrabban eltévednek, az egyénre szabott útvonaltervező algoritmus olyan útvonalat fog kiválasztani, melyben a lehető legkevesebb bal kanyar van. Mások számára, akik inkább gyorsan szeretnek haladni, de nem zavarja őket, ha az útvonal cserébe kissé bonyolultabb, a HERE bátran ajánl majd merészebb manővereket is, ha ezért cserébe hamarabb eljuthatnak az úti céljukhoz.

Forrás: 360.here.com
Fordítás: Zsolto

Szólj hozzá te is a cikkhez!

Weboldalunk használatával jóváhagyja a cookie-k használatát a Cookie-kkal kapcsolatos irányelv értelmében.