Veel

Geograafiliste andmete marsruutimisalgoritm

Geograafiliste andmete marsruutimisalgoritm


Mul on Ameerika linnast välja võetud graafik: tipud tähistavad teede ristumiskohti, servad / kaared tähistavad ristmikke ühendavaid teelõike. Iga teelõigu jaoks on mul pikkus ja lubatud sõidukiirus. Lisaks kuuluvad teed erinevatesse klassidesse, näiteks maanteed / elamud / põhimaanteed /…

Otsin marsruutimisalgoritmi, mis teeb järgmist:

  • Arvutage iga ristmiku kohta paarikaupa reisi aja maatriks (st kui kaua kuluks ristmikust i ristmikuni j liikumiseks.
  • Küsige kiireimat marsruuti ristmikust i j-ni ja tagastab tee (servade / kaaride jada).
  • Algoritm peaks suutma värskendusi arvesse võtta. Näiteks kui teelõigul (x, y) on ülekoormus, mis pikendab selle eeldatavat sõiduaega või kui teelõik (x, y) blokeerub, tuleks andmekonstruktsioone järk-järgult uuendada, seeläbi ajakohastades kõiki mõjutatud lühimaid teid ( st uuenda kõik lühimad teed läbi (x, y)).

Vahemaa maatriksit küsitakse väga sageli, nii et see tuleks eelnevalt arvutada, kuid tegelike lühimate teede saab hiljem arvutada, kui see on tõhusam. Graafikus olevate sõlmede arv on umbes 5000–10000.

Lootsin, et inimesed saavad mind selle kohta kirjandusele viidata, eelistatult midagi, mille rakendamine ei võta nädalaid. Ilmselt võtab Dijkstra lihtsalt iga ristmiku käivitamine liiga kaua aega. Floyd-Warshalli kõigi paaride lühima tee algoritmi käivitamine võiks olla võimalus, kuid ma pole nii kindel, kuidas tulemust värskendada, kui ühe serva / kaare maksumus muutub. Pealegi näib see olevat aeglane lähenemine, kuna algoritm ignoreerib seda, et enamik marsruute läbib väikest teelõigute alamhulka.

Ma ei otsi tingimata täpset lähenemist. Piisab heast lähendusest. Kõik kirjandus- või algoritmikirjeldused on teretulnud. Eeldan, et igasugune marsruutimistarkvara vajab sarnast algoritmi. Mind huvitab peamiselt miski, mis töötab; see ei peaks tingimata olema nüüdisaegne.

Kui see pole õige koht küsimiseks, palun andke mulle sellest teada (eriti kui teate paremat kohta :)). Lihtsalt rõhutamaks: Ma ei otsi tarkvara / andmebaasipaketti, vaid algoritmi.


Siin on l mittetäielik algoritmide loend.

Hea võrdlus: https://arxiv.org/pdf/1504.05140.pdf

  • transiidisõlme marsruutimine (Bast jt)
  • kontraktsioonihierarhiad
  • Maanteede hierarhiad
  • A-täht koos kaarelippude ja maamärkidega (Goldberg jt)

Enamik neist on Vikipeedias.

Rakendamise seisukohast on kõige lihtsam A-Star'i vaatamisväärsused. Lihtsalt kasutage standardset A-tähte ja heuristikana võtke vahemaa orientiirideni.

Üksikasjad siin: http://www.fabianfuchs.com/fabianfuchs_ALT.pdf Page 7 ja võrrand 2.3.

Tutvuge prof Basti loengutega: https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012 (Võib-olla on ka uuemaid versioone).

- palun vabandage selle vastuse kohutav vorming. Kirjutage kommentaar ja ma parandan selle. Kirjutan mobiilist


Nii nagu ka Floyd-Warshall, võiksite kõigi paaride marsruutimisel kaaluda Johnsoni algoritmi. Dijkstra jooksmiseks igas ristmikus võiks alternatiiviks olla A * sõitmine, kuna viimast peetakse tavaliselt kiiremaks.

Soovitan teil vaadata pilti PgRoutingist, mis on PostGIS-i pistikprogramm. Piisavalt lihtne oleks oma andmed PostGIS-i importida. PgRoutingil on kümmekond algoritmi (sealhulgas Johnsoni, Dijkstra, A *, Shooting Star ja nende variandid), mis säästaks rakendamisel aega, mille võiksite kiiruste võrdlemiseks investeerida võrdlusmärgistamisse.


Vaadake avatud lähtekoodiga marsruutimismootorit GraphHopper (märkus: olen autor), mis peaks suutma teie probleemi kiiresti lahendada, kuna GraphHopper kasutab kontraktsioonihierarhiaid (CH). Kuid isegi ilma eeltöötlust nõudva CH-ta saab kasutada algoritmi üks paljudele ja lisada liiklusteabe ning see on endiselt kiire.

Ükski avatud lähtekoodiga Matrix API ei suuda sekunditega lahendada meelevaldseid maatrikseid suurusega 1000x1000 ja suuremat kogu Euroopas (kaasates kümneid miljoneid sõlme)! Ja selline väike graafik nagu teil on koos 5 000x5 000 maatriksitaotlusega, peaks olema hõlpsasti teostatav ka mõne sekundi jooksul - isegi kui kasutate (endiselt väga kiiret) avatud lähtekoodiga versiooni.


Vaata videot: Curso de Redes.. Algoritmos de routing.