4551
правка
Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в дорожных сетях с транзитными узлами (посмотреть исходный код)
Версия от 11:41, 17 июня 2019
, 17 июня 2019→Наборы данных
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Помимо самого очевидного применения в автомобильных навигационных системах и серверных системах планирования маршрутов, маршрутизация при помощи транзитных узлов может применяться в нескольких других областях – например, для массового моделирования транспортных потоков и для различных задач оптимизации в логистике. | Помимо самого очевидного применения в автомобильных навигационных системах и серверных системах планирования маршрутов, маршрутизация при помощи транзитных узлов может применяться в нескольких других областях – например, для массового моделирования транспортных потоков и для различных задач оптимизации в логистике. | ||
== Открытые вопросы == | |||
До сих пор неизвестно, можно ли найти более эффективные множества транзитных узлов или лучший фильтр локальности для дальнейшейго улучшения производительности. Неясно также, может ли маршрутизация с использованием транзитных узлов успешно применяться к другим типам графов, отличным от дорожных сетей. В этом контексте было бы желательно получить какие-либо теоретические гарантии, применимые к любому графу, обладающему определенными свойствами. Для некоторых практических областей применения пригодилась бы динамическая версия маршрутизации с использованием транзитных узлов для работы с сетями, зависящими от времени, или непредсказуемыми изменениями весов дуг, вызванными, к примеру, заторами на дорогах. Последний сценарий может обрабатываться с помощью родственного подхода из работы [8], однако он работает гораздо медленнее, чем маршрутизация с использованием транзитных узлов. | |||
== Экспериментальные результаты == | |||
== Наборы данных == | == Наборы данных == | ||
Карта дорожной сети Европы была предоставлена компанией PTV AG, карта сети США была получена из файлов TIGER/Line [ ]. Оба графа также использовались в ходе 9-го конкурса DIMACS по реализации алгоритмов поиска кратчайших путей [1]. | |||
== Ссылка на код == | |||
Исходный код будет в свое время опубликован на сайте http://algo2.iti.uka.de/schultes/hwy/. | |||
== См. также == | |||
* [[Алгоритм поиска кратчайших путей в разреженных графах]] | |||
* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | |||
* [[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | |||
* [[Разработка алгоритмов для применения в больших сетях]] | |||
* [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | |||
* [[Географическая маршрутизация]] | |||
* [[Конкурс по реализации алгоритмов поиска кратчайших путей]] | |||
* [[Подход к составлению расписания при помощи кратчайших путей]] | |||
* [[Поиск кратчайших путей в планарных графах с отрицательными весами ребер]] | |||
* [[Алгоритм поиска кратчайших путей с единственным источником]] | |||
== Литература == | |||
1. 9th DIMACS Implementation Challenge: Shortest Paths. http://www.dis.uniroma1.it/~challenge9/(2006) | |||
2. Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Workshop on Algorithm Engineering and Experiments, 2007, pp. 46-59 | |||
3. Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007) | |||
4. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1 269-271 (1959) | |||
5. Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: 13th European Symposium on Algorithms. LNCS, vol. 3669, pp. 568-579. Springer, Berlin (2005) | |||
6. Sanders, P., Schultes, D.: Engineering highway hierarchies. In: 14th European Symposium on Algorithms. LNCS, vol. 4168, pp. 804-816. Springer, Berlin (2006) | |||
7. Sanders, P., Schultes, D.: Engineering fast route planning algorithms. In: 6th Workshop on Experimental Algorithms. LNCS, vol. 4525, pp. 23-36. Springer, Berlin (2007) | |||
8. Schultes, D., Sanders, P.: Dynamic highway-node routing. In: 6th Workshop on Experimental Algorithms. LNCS, vol. 4525, pp. 66-79. Springer, Berlin (2007) | |||
9. U.S. Census Bureau, Washington, DC: UA Census 2000 TIGER/Line Files. http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html (2002) | |||