Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд

Abstract

Розглянуто задачі пошуку оптимальних маршрутів мережами громадського транспорту. Наведено підходи до подання розкладу за допомогою графів у залежних від часу задачах пошуку оптимальних шляхів для залізничних і авіамереж. Проаналізовано типові задачі пошуку оптимальних шляхів у залежних від часу мережах.

Рассмотрены задачи поиска оптимальных маршрутов сетями общественного транспорта. Приведены подходы для представления расписания с помощью графов в зависимых от времени задачах поиска оптимальных путей для железнодорожных и авиасетей. Проанализированы типовые задачи поиска оптимальных путей в зависимых от времени сетях.

We consider the problem of optimal dynamic time-dependent route planning in public transport networks. The paper describes approaches to represent schedule within graphs for the time-dependent shortest path problems in rail and air networks. Common types of timedependent shortest path problems in dynamic networks are reviewed.