Составление маршрута на основе расписания при помощи алгоритма кратчайших путей: различия между версиями

В упрощенной модели предполагается, что пересадка между поездами не занимает времени. В более реалистичной модели задается определенное минимальное время пересадки на каждой станции. Кроме того, необходимо определить целевую функцию оптимизационной задачи. Должен ли маршрут быть как можно более быстрым, или как можно более дешевым, или содержать как можно меньше пересадок? Существуют различные способы решения этой задачи, рассмотренные в [ ]; все они берут начало в многоцелевой оптимизации – например, ограничения на ресурсы или решения, оптимальные по Парето. С практической точки зрения предпочтения пассажира обычно трудно смоделировать математически, и можно позволить пользователю самому выбрать лучший вариант из множества разумных маршрутов. Например, можно вычислить все маршруты, не уступающие какому-либо другому маршруту по всем рассматриваемым аспектам. На практике оказывается, что в реальных расписаниях количество таких маршрутов не слишком велико, поэтому такой подход является вычислительно реализуемым и полезным для пассажира [5]. Кроме того, структура тарифов у большинства железных дорог довольно сложна [ ] – в основном потому, что тарифы обычно не аддитивны, то есть не являются суммой тарифов частей поездки.