573:
44:
1005:
and there must be a common node in both paths. During the calculation of the access nodes, the search space (all visited nodes towards the top of the hierarchy) for each node can be stored without including transit nodes. When performing a query, those search spaces for start- and target node are checked for an intersection. If those spaces are
1004:
If the highest node of a shortest up-down-path in the hierarchy is not part of the set of transit nodes, then the query was local. This implies that neither the up-part of the path (beginning at the starting node) nor the down-part of the path (ending at the target node) can contain a transit node
71:
Because the number of such access nodes is small compared to the overall number of nodes in a road network, all shortest routes connecting those nodes with each other can be pre-calculated and stored. When calculating a shortest path therefore only routes to access nodes close to start and target
67:
starting at the same location always use the same small amount of access nodes close to the starting location to enter this network. In the same way, similar target locations are always reached by using the same access nodes close to them. This intuition only holds for long-distance travel. When
862:
The way access nodes are selected implies that if source and target are more than four grid cells apart, a transit node must be passed on the shortest path and the distance can be calculated as described above. If they lie closer together, a fallback-algorithm is used to obtain the distance.
886:
In the grid-based implementation outlined above, this results in 16 bytes of storage that is required for each node of the road graph. A full graph of the USA road network has 23,947,347 nodes. Therefore approx. 383 MB of storage would be required to store the distance tables.
497:
35:. Transit node routing is a static approach that requires pre-processing of pair-wise distances between important nodes in the graph (see below how those nodes are chosen). A dynamic approach has not been published.
507:
Short routes between close start and target locations may not require any transit nodes. In this case, the above framework leads to incorrect distances because it forces routes to visit at least one transit node.
196:
238:
323:
523:
Transit node routing is not an algorithm but merely a framework for speeding up route planning. The general framework leaves open a few questions that need to be answered to implement it:
976:, edges leaving previously found transit nodes aren't relaxed. When the search has no more upward nodes left to settle, those transit nodes that have been settled are the access nodes of
31:
Transit node routing as a framework was established in 2007 and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies and
515:
can be used. For given start and target locations, the locality filter decides, if transit node routing should be applied or if a fallback-routine should be used (local query).
883:
The pre-computed distances between each node and the corresponding access node as well as the pairwise distances between transit nodes need to be stored in distance tables.
105:
1130:
Bast, Holger; Funke, Stefan; Matijevic, Domagoj; Sanders, Peter; Schultes, Dominik (2007-01-06), "In
Transit to Constant Time Shortest-Path Queries in Road Networks",
824:
154:
315:
268:
1009:, transit node routing can be used because the up- and down-paths must meet at a transit node. Otherwise there could be a shortest path without a transit node.
994:
970:
950:
922:
844:
798:
778:
758:
738:
718:
698:
678:
658:
638:
618:
598:
540:
The following example implementations of this framework answer these questions using different underlying methods such as grouping nodes in cells of an overlay
288:
125:
904:
moves important nodes (i.e. nodes that are part of many shortest paths) to the top of the hierarchy. A set of transit nodes therefore can be selected as the
871:
Local queries are only needed if start and target already lie close together, therefore every suitable shortest-path algorithm such as
1242:
1202:
1149:
68:
travelling short distances, such access nodes might be never used because the fastest path to the target only uses local roads.
492:{\displaystyle d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{A}(s,u)+D_{T}(u,v)+d_{A}(v,t)}
159:
201:
1287:
1292:
1068:
Bast, H.; Funke, S.; Sanders, P.; Schultes, D. (2007-04-27). "Fast
Routing in Road Networks with Transit Nodes".
56:
1018:
973:
901:
872:
545:
60:
32:
28:
by pre-computing connections between common access nodes to a sub-network relevant to long-distance travel.
1030:
25:
59:
instead of e.g. urban roads. This sub-network can only be entered by using sparsely distributed access
1182:
1077:
1040:
561:
557:
541:
572:
64:
17:
84:
43:
1229:, Lecture Notes in Computer Science, vol. 4525, Springer Berlin Heidelberg, pp. 66–79,
1208:
1172:
1109:
1238:
1198:
1145:
1101:
1093:
1045:
576:
Access nodes (red dots) for a cell C (red) with inner area I (orange) and outer area O (blue)
1230:
1190:
1135:
1085:
803:
133:
293:
246:
1257:
1186:
1167:
Arz, Julian; Luxen, Dennis; Sanders, Peter (2013), "Transit Node
Routing Reconsidered",
1132:
2007 Proceedings of the Ninth
Workshop on Algorithm Engineering and Experiments (ALENEX)
1081:
979:
955:
935:
907:
829:
783:
763:
743:
723:
703:
683:
663:
643:
623:
603:
583:
273:
110:
1281:
1006:
1212:
1113:
952:
can be found by running the upward-search of the contraction hierarchy starting at
52:
1234:
1194:
1140:
1035:
1097:
1089:
1105:
854:
The set of transit nodes is exactly the union of all sets of access nodes.
1225:
Schultes, Dominik; Sanders, Peter (2007), "Dynamic
Highway-Node Routing",
47:
Multiple routes using the same access nodes to long-distance road network.
660:. Focusing on crossing nodes (ends of edges that cross the boundary of
51:
Long-distance travel usually involves driving along a subset of the
1177:
1134:, Society for Industrial and Applied Mathematics, pp. 46–59,
571:
42:
600:, a set of access nodes can be found by looking at an inner area
81:
Transit node routing starts with a selection of transit nodes
564:
square of all nodes is equally subdivided into square cells.
63:. When compared to one another, multiple long-distance
320:
A distance between two nodes can now be calculated as
1258:"9th DIMACS Implementation Challenge: Shortest Paths"
982:
958:
938:
910:
832:
806:
786:
766:
746:
726:
706:
686:
666:
646:
626:
606:
586:
326:
296:
276:
249:
204:
162:
136:
113:
87:
996:. Backward access nodes can be found analogously.
760:that are part of a shortest path from some node in
191:{\displaystyle {\overrightarrow {A}}(v)\subseteq T}
988:
964:
944:
916:
838:
818:
792:
772:
752:
732:
712:
692:
672:
652:
632:
612:
592:
491:
309:
282:
262:
233:{\displaystyle {\overleftarrow {A}}(v)\subseteq T}
232:
190:
148:
119:
99:
846:are chosen (red dots in the image to the right).
544:and a more sophisticated implementation based on
349:
1171:, Springer Berlin Heidelberg, pp. 55–66,
243:Now, pairwise distances between transit nodes
8:
924:highest nodes of the contraction hierarchy.
1176:
1139:
981:
957:
937:
909:
831:
805:
785:
765:
745:
725:
705:
685:
665:
645:
625:
605:
585:
468:
440:
412:
387:
359:
352:
325:
301:
295:
275:
254:
248:
205:
203:
163:
161:
135:
112:
86:
800:. As access nodes for an arbitrary node
1057:
156:dedicated sets of forward access nodes
1000:Which locality filter should be used?
875:or extensions thereof can be chosen.
858:Which locality filter should be used?
533:Which locality filter should be used?
290:and their corresponding access nodes
7:
1162:
1160:
1125:
1123:
1063:
1061:
1013:How should local queries be handled?
867:How should local queries be handled?
536:How should local queries be handled?
511:To prevent this kind of problem, a
240:are chosen from all transit nodes.
14:
552:Geometrical approach using grids
72:location need to be calculated.
932:Forward access nodes of a node
896:How are transit nodes selected?
850:How are transit nodes selected?
620:of 5x5 cells and an outer area
527:How are transit nodes selected?
1021:of the contraction hierarchy.
1017:Local queries use the regular
928:How are access nodes selected?
568:How are access nodes selected?
486:
474:
458:
446:
430:
418:
403:
397:
375:
369:
342:
330:
221:
215:
179:
173:
1:
891:Using contraction hierarchies
530:How are access nodes chosen?
270:and distances between nodes
100:{\displaystyle T\subseteq V}
1235:10.1007/978-3-540-72845-0_6
1195:10.1007/978-3-642-38527-8_7
1309:
317:are calculated and stored.
198:and backward access nodes
1141:10.1137/1.9781611972870.5
107:as a subset of all nodes
720:), the access nodes for
24:can be used to speed up
1227:Experimental Algorithms
1169:Experimental Algorithms
1090:10.1126/science.1137521
546:contraction hierarchies
33:contraction hierarchies
1262:users.diag.uniroma1.it
990:
966:
946:
918:
840:
820:
819:{\displaystyle v\in C}
794:
774:
754:
734:
714:
694:
674:
654:
634:
614:
594:
577:
493:
311:
284:
264:
234:
192:
150:
149:{\displaystyle v\in V}
121:
101:
48:
1031:Shortest path problem
991:
967:
947:
919:
902:contraction hierarchy
841:
826:all access nodes of
821:
795:
775:
755:
735:
715:
695:
675:
655:
635:
615:
595:
575:
560:-based approach, the
494:
312:
310:{\displaystyle d_{A}}
285:
265:
263:{\displaystyle D_{T}}
235:
193:
151:
122:
102:
46:
26:shortest-path routing
1041:Bidirectional search
980:
956:
936:
908:
873:Dijkstra's algorithm
830:
804:
784:
764:
744:
724:
704:
684:
664:
644:
640:of 9x9 cells around
624:
604:
584:
324:
294:
274:
247:
202:
160:
134:
127:of the road network.
111:
85:
22:transit node routing
1187:2013arXiv1302.5611A
1082:2007Sci...316..566B
740:are those nodes of
18:applied mathematics
1288:Routing algorithms
986:
962:
942:
914:
879:Space requirements
836:
816:
790:
770:
750:
730:
710:
690:
670:
650:
630:
610:
590:
578:
519:Concrete instances
489:
407:
307:
280:
260:
230:
188:
146:
117:
97:
49:
1046:Highway dimension
989:{\displaystyle v}
965:{\displaystyle v}
945:{\displaystyle v}
917:{\displaystyle k}
900:By definition, a
839:{\displaystyle C}
793:{\displaystyle O}
773:{\displaystyle C}
753:{\displaystyle I}
733:{\displaystyle C}
713:{\displaystyle O}
693:{\displaystyle I}
673:{\displaystyle C}
653:{\displaystyle C}
633:{\displaystyle O}
613:{\displaystyle I}
593:{\displaystyle C}
395:
367:
348:
283:{\displaystyle v}
213:
171:
120:{\displaystyle V}
76:General framework
1300:
1293:Graph algorithms
1272:
1271:
1269:
1268:
1254:
1248:
1247:
1222:
1216:
1215:
1180:
1164:
1155:
1154:
1143:
1127:
1118:
1117:
1065:
995:
993:
992:
987:
971:
969:
968:
963:
951:
949:
948:
943:
923:
921:
920:
915:
845:
843:
842:
837:
825:
823:
822:
817:
799:
797:
796:
791:
779:
777:
776:
771:
759:
757:
756:
751:
739:
737:
736:
731:
719:
717:
716:
711:
699:
697:
696:
691:
679:
677:
676:
671:
659:
657:
656:
651:
639:
637:
636:
631:
619:
617:
616:
611:
599:
597:
596:
591:
498:
496:
495:
490:
473:
472:
445:
444:
417:
416:
406:
396:
388:
368:
360:
316:
314:
313:
308:
306:
305:
289:
287:
286:
281:
269:
267:
266:
261:
259:
258:
239:
237:
236:
231:
214:
206:
197:
195:
194:
189:
172:
164:
155:
153:
152:
147:
126:
124:
123:
118:
106:
104:
103:
98:
1308:
1307:
1303:
1302:
1301:
1299:
1298:
1297:
1278:
1277:
1276:
1275:
1266:
1264:
1256:
1255:
1251:
1245:
1224:
1223:
1219:
1205:
1166:
1165:
1158:
1152:
1129:
1128:
1121:
1067:
1066:
1059:
1054:
1027:
1019:query algorithm
978:
977:
954:
953:
934:
933:
906:
905:
893:
881:
828:
827:
802:
801:
782:
781:
762:
761:
742:
741:
722:
721:
702:
701:
682:
681:
662:
661:
642:
641:
622:
621:
602:
601:
582:
581:
554:
521:
513:locality filter
505:
503:Locality filter
464:
436:
408:
322:
321:
297:
292:
291:
272:
271:
250:
245:
244:
200:
199:
158:
157:
132:
131:
130:For every node
109:
108:
83:
82:
78:
41:
12:
11:
5:
1306:
1304:
1296:
1295:
1290:
1280:
1279:
1274:
1273:
1249:
1243:
1217:
1203:
1156:
1150:
1119:
1056:
1055:
1053:
1050:
1049:
1048:
1043:
1038:
1033:
1026:
1023:
985:
961:
941:
913:
892:
889:
880:
877:
835:
815:
812:
809:
789:
769:
749:
729:
709:
689:
669:
649:
629:
609:
589:
580:For each cell
553:
550:
538:
537:
534:
531:
528:
520:
517:
504:
501:
500:
499:
488:
485:
482:
479:
476:
471:
467:
463:
460:
457:
454:
451:
448:
443:
439:
435:
432:
429:
426:
423:
420:
415:
411:
405:
402:
399:
394:
391:
386:
383:
380:
377:
374:
371:
366:
363:
358:
355:
351:
347:
344:
341:
338:
335:
332:
329:
318:
304:
300:
279:
257:
253:
241:
229:
226:
223:
220:
217:
212:
209:
187:
184:
181:
178:
175:
170:
167:
145:
142:
139:
128:
116:
96:
93:
90:
77:
74:
40:
37:
13:
10:
9:
6:
4:
3:
2:
1305:
1294:
1291:
1289:
1286:
1285:
1283:
1263:
1259:
1253:
1250:
1246:
1244:9783540728443
1240:
1236:
1232:
1228:
1221:
1218:
1214:
1210:
1206:
1204:9783642385261
1200:
1196:
1192:
1188:
1184:
1179:
1174:
1170:
1163:
1161:
1157:
1153:
1151:9781611972870
1147:
1142:
1137:
1133:
1126:
1124:
1120:
1115:
1111:
1107:
1103:
1099:
1095:
1091:
1087:
1083:
1079:
1076:(5824): 566.
1075:
1071:
1064:
1062:
1058:
1051:
1047:
1044:
1042:
1039:
1037:
1034:
1032:
1029:
1028:
1024:
1022:
1020:
1015:
1014:
1010:
1008:
1002:
1001:
997:
983:
975:
974:upward-search
972:. During the
959:
939:
930:
929:
925:
911:
903:
898:
897:
890:
888:
884:
878:
876:
874:
869:
868:
864:
860:
859:
855:
852:
851:
847:
833:
813:
810:
807:
787:
780:to a node in
767:
747:
727:
707:
687:
667:
647:
627:
607:
587:
574:
570:
569:
565:
563:
559:
551:
549:
547:
543:
535:
532:
529:
526:
525:
524:
518:
516:
514:
509:
502:
483:
480:
477:
469:
465:
461:
455:
452:
449:
441:
437:
433:
427:
424:
421:
413:
409:
400:
392:
389:
384:
381:
378:
372:
364:
361:
356:
353:
345:
339:
336:
333:
327:
319:
302:
298:
277:
255:
251:
242:
227:
224:
218:
210:
207:
185:
182:
176:
168:
165:
143:
140:
137:
129:
114:
94:
91:
88:
80:
79:
75:
73:
69:
66:
62:
58:
54:
45:
38:
36:
34:
29:
27:
23:
19:
1265:. Retrieved
1261:
1252:
1226:
1220:
1168:
1131:
1073:
1069:
1016:
1012:
1011:
1003:
999:
998:
931:
927:
926:
899:
895:
894:
885:
882:
870:
866:
865:
861:
857:
856:
853:
849:
848:
579:
567:
566:
555:
539:
522:
512:
510:
506:
70:
53:road network
50:
30:
21:
15:
1282:Categories
1267:2019-07-15
1052:References
1036:Hub labels
1178:1302.5611
1098:0036-8075
811:∈
393:←
385:∈
365:→
357:∈
225:⊆
211:←
183:⊆
169:→
141:∈
92:⊆
39:Intuition
1213:14371800
1114:16559205
1106:17463281
1025:See also
1007:disjoint
562:bounding
57:freeways
55:such as
1183:Bibcode
1078:Bibcode
1070:Science
1241:
1211:
1201:
1148:
1112:
1104:
1096:
65:routes
1209:S2CID
1173:arXiv
1110:S2CID
556:In a
61:nodes
1239:ISBN
1199:ISBN
1146:ISBN
1102:PMID
1094:ISSN
558:grid
542:grid
1231:doi
1191:doi
1136:doi
1086:doi
1074:316
700:or
548:.
350:min
16:In
1284::
1260:.
1237:,
1207:,
1197:,
1189:,
1181:,
1159:^
1144:,
1122:^
1108:.
1100:.
1092:.
1084:.
1072:.
1060:^
680:,
20:,
1270:.
1233::
1193::
1185::
1175::
1138::
1116:.
1088::
1080::
984:v
960:v
940:v
912:k
834:C
814:C
808:v
788:O
768:C
748:I
728:C
708:O
688:I
668:C
648:C
628:O
608:I
588:C
487:)
484:t
481:,
478:v
475:(
470:A
466:d
462:+
459:)
456:v
453:,
450:u
447:(
442:T
438:D
434:+
431:)
428:u
425:,
422:s
419:(
414:A
410:d
404:)
401:t
398:(
390:A
382:v
379:,
376:)
373:s
370:(
362:A
354:u
346:=
343:)
340:t
337:,
334:s
331:(
328:d
303:A
299:d
278:v
256:T
252:D
228:T
222:)
219:v
216:(
208:A
186:T
180:)
177:v
174:(
166:A
144:V
138:v
115:V
95:V
89:T
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
