Vairāk

Palīdziet izvēlēties piemērotu maršrutēšanas dzinēju

Palīdziet izvēlēties piemērotu maršrutēšanas dzinēju


Es veidoju maršruta plānošanas sistēmu, bet man vēl jāizlemj, kādu maršrutēšanas dzinēju es izmantošu. Līdz šim esmu atradis pgrouting un neo4j.

Man ir maršruta tīkls postgresql/postgis datu bāzē (importēts no formas faila). Esmu veicis vaicājumus, lai iegūtu mezglus (galapunkti veidiem, kur jums jāizlemj, kurā virzienā iet vai strupceļi) un lai iegūtu malas (bieži veidotas vairākos secīgos veidos). Visas manas malas ir divvirzienu.

Mans galvenais mērķis ir aprēķināt maršrutus šajā tīklā, izmantojot A-zvaigznes algoritmu, kur attālums = izmaksas.

Mana sajūta man saka, ka grafiku datu bāze, piemēram, neo4j, ir pareizais ceļš (jo šķiet, ka tā ir izveidota tieši šim nolūkam), taču šķiet, ka tie pēc noklusējuma neatbalsta A-zvaigzni, kā arī nav īstas ģeometrijas izjūtas. . Tas šķiet labāk piemērots sociālajiem tīkliem, nevis kartēm.

  • Vai pgrouting atbilstu manām vajadzībām?
  • Vai tas ir pietiekami ātrs, lai veiktu vaicājumus ( +-2000 mezgli, +-4000 malas)? Parasti tas būtu dažas ms A-zvaigznei, bet es neesmu pārliecināts par šo ieviešanu sql.
  • Vai A-zvaigznes grupēšana dod man mezglu un malu sarakstu?
  • Lielākajā daļā piemēru, ko es redzu par grupēšanu, es ievēroju, ka pēc maršruta aprēķināšanas parasti ir komandu saraksts (piemēram, "Pie X pagriezieties pa kreisi utt."). Vai pgrouting to rada vai tas ir no citas sistēmas?

Cerams, ka kāds var sniegt kādu informāciju par to, kādu sistēmu izvēlēties. Neo4j, pgrouting vai kāda cita sistēma.


Pašlaik pētniecības darba nolūkos es pētu to pašu problēmu kā jūs. Pirms es sāku pārbaudīt šīs divas datu bāzes, man bija tāds pats pieņēmums kā jums. Šī Neo4j grafiku datu bāze būtu ideāls risinājums šāda veida problēmām. Un daļēji tā ir, bet ar daudzām problēmām.

Pirmā problēma ir tā, ka A-Star tiek ieviests tikai tad, ja izmantojat iegulto datu bāzi, nevis izmantojot REST API (serveri). Ja vēlaties izmantot Neo4j ar REST API, tiek atbalstīts tikai Dijkstra algoritms. Otra problēma ir Neo4j aparatūras atmiņas prasības. Lai maršrutētu (Dijkstra) "lielākos" tīklos, jums ir nepieciešams daudz RAM. Lielam tīklam es domāju kaut ko līdzīgu Vācijas OSM ceļu datu bāzes lielumam. Esmu palaidis testus 6 GB RAM serverī (tas ir viss, kas man pašlaik ir), un tikai mazākus tīklus varēja novirzīt bez OutOfMemory izņēmuma kļūdām. "Mazie" tīkli manos testa gadījumos ir, piemēram, OSM ceļu datu bāze Austrijai vai Horvātijai. Vienlaicīgi vaicājumi, kurus joprojām neesmu testējis ar Neo4j.

Visas šīs problēmas nepastāv pgRouting. Atmiņa nav šāda problēma, bet vienlaicīgi vaicājumi palielina nepieciešamo atmiņas apjomu. Piemēram, ja jums ir divi vienlaicīgi pieprasījumi, ir nepieciešams dubultā atmiņas apjoms. Tā nebija problēma pat Vācijas OSM datu kopai, pgRouting bez problēmām novirzīja visus vienlaicīgos pieprasījumus.

Veiktspēja: vairumā gadījumu Neo4j pārspēj pgRouting. Bet tikai tad, ja dotajai datu kopai ir pietiekami daudz atmiņas un ja visi mezgli un attiecības ir atmiņā (karstā palaišana). Veiktspējas palielināšanās/samazināšanās ir atkarīga no daudziem faktoriem, bet galvenokārt no tīkla lieluma un attāluma (apiņi) starp avotu un mērķa mezglu.

Jūsu tīkla izmērs ir diezgan mazs, tāpēc jums nevajadzētu rasties problēmām ar atmiņu. Iespējams, Neo4j nav slikta izvēle, bet jums ir jāpielāgojas "nedaudz" atšķirīgam datu modelim nekā standarta relāciju datu bāzēs.

Lai atbildētu uz jautājumiem:

  • Programmā pgRouting jums nav jāuztraucas par AStar ieviešanu SQL, kas jau ir ieviests.
  • Jā, pgRouting var sniegt mezglu un malu sarakstu
  • Es nedomāju, ka pgRouting var sniegt jums šādu informāciju, neveicot pielāgotu darbu saistībā ar vaicājumiem. Bet varbūt es kļūdos, varbūt kāds to ir izdarījis un var jums vairāk palīdzēt šajā jautājumā.

Es nezinu, vai tas jums tieši palīdzēs, bet viens no ātrākajiem atrastajiem maršrutēšanas serveriem ir osm2po. Tas darbojas ar OSM datu kopu un ir diezgan ātrs. Pašlaik tiek ieviesta tikai dijkstra, bet arī izstrādātājs paziņoja par AStar. Es ceru, ka daži no šiem jautājumiem jums palīdzēs. :)


Varat arī apskatīt mūsu RW Net 4 pakotni (www.routeware.dk). Tā var veikt šādus īsākā ceļa aprēķinus, izmantojot A* tieši no SHP faila. Pamata pakete 500 eiro apmērā šķiet pietiekama jūsu vajadzībām.