Задача наименьшего расстояния с длиной как функции времени

10

мотивация

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

Нам всем известна классическая «задача кратчайшего пути»: ориентированный граф с длинами и двумя вершинами , найдите кратчайший путь между и (т. е. путь, минимизирующий общую длину ребра). Предполагая неотрицательные длины ребер, существуют различные алгоритмы, и проблема проста.w eR + 0 ,G=(V,E)s , t V s tweR0+,eEs,tVst

Это хорошая модель для случая, когда мы идем, например. Вершины являются перекрестком в нашей сети дорог, и каждый край имеет фиксированную длину - например, в метрах. Другая возможная интерпретация весов - это время, которое требуется нам, чтобы перейти от одной из его вершин к другой. Это интерпретация, которая меня интересует сейчас.we

проблема

Теперь я хочу смоделировать следующую ситуацию. Я хочу путешествовать из пункта А в пункт Б в городе на общественном транспорте и минимизировать время . Сеть общественного транспорта может быть легко смоделирована как ориентированный граф, как и следовало ожидать. Интересной частью являются граничные веса (это время модели) - общественный транспорт (например, автобусы) отправляется только через определенные интервалы, которые различны для каждой остановки (вершина на графике). Другими словами - веса ребер не постоянны, они меняются в зависимости от времени, когда мы хотим использовать ребро.

Как смоделировать эту ситуацию: у нас есть ориентированный граф и функция веса ребер которая принимает время в качестве аргумента и возвращает время , необходимое для использования ребра на нашем пути. Например, если шина от вершины до вершины уходит в момент времени и это занимает раз, а мы достигаем вершины в момент времени , то - это вес ребра. Ясно, что .w : E × R + 0R + 0G=(V,E) w:E×R0+R0+u t = 10 5 v t = 8 w ( v u , 8 ) = 7 w ( v u , 10 ) = 5vut=105vt=8w(vu,8)=7w(vu,10)=5

Определить общий вес пути немного сложно, но мы можем сделать это рекурсивно. Пусть - направленный путь. Если то . В противном случае , где - без . Это естественное определение, соответствующее реальной ситуации. k = 1 w ( P ) =P=v1v2vk1vkk=1w ( P ) = w ( P ) + w ( v k - 1 v k , w ( P ) ) P P v kw(P)=0w(P)=w(P)+w(vk1vk,w(P))PPvk

Теперь мы можем изучить эту проблему при различных предположениях о функции . Естественным предположением является которое моделирует «ожидание time».w ( e , t ) w ( e , t + Δ ) + Δ  для всех  e E , Δ 0 , Δw

w(e,t)w(e,t+Δ)+Δ for all eE,Δ0,
Δ

Если функция «ведет себя хорошо», возможно, можно свести эту проблему к классической проблеме кратчайшего пути. Но мы могли бы спросить, что происходит, когда весовые функции становятся дикими. А что если мы отбросим предположение об ожидании?

Вопросов

Мои вопросы следующие.

  • Обсуждалась ли эта проблема раньше? Это кажется естественным.
  • Есть ли какие-либо исследования по этому поводу? Мне кажется, что существуют различные подзадачи, которые необходимо задать и изучить - в основном, в отношении свойств весовой функции.
  • Можем ли мы свести эту проблему (возможно, при некоторых предположениях) к классической проблеме кратчайшего пути?
JS_
источник
Вот естественный базовый подход, с которым можно сравнивать больше ответов на уровне исследований. Модель это как проблема достижимости путем дискретизации единицы времени в коллекцию моментов , и сделать новый граф с вершинами . Затем вы можете поместить ребра где . Это уже эффективно для многих случаев использования (например, с расписанием автобусов, вы просто позволяете быть временем, когда автобусы приходят / покидают свои остановки), но не всегда работает идеально (учитывая, что постоянно меняется в течение время), и медленно, если велико. V = T × V ( t 0 , v 0 ) ( t 1 , v 1 ) t 1 = w ( ( v 0 , v 1 ) , t 0 ) T w TTV=T×V(t0,v0)(t1,v1)t1=w((v0,v1),t0)TwT
Эндрю Морган
Один простой вариант этой задачи (где веса ребер линейно зависят от времени) называется « параметрический кратчайший путь ».
Нил Янг

Ответы:

8

Это известно как проблема «кратчайшего пути, зависящего от времени». Действительно исследование было сделано для этой проблемы; см., например, классическую статью Орды и Рома, а также недавнюю статью SODA, в которой доказывается, что когда весовая функция каждого ребра кусочно-линейная, полиномиального размера, то кратчайший путь между двумя фиксированными точками изменяется раз.nΘ(logn)

Алгоритм Дейкстры действительно может быть использован для этой проблемы, когда применяется политика ожидания, то есть ожидание в узле, если это уменьшает конечное время прибытия. Без политики ожидания ситуация намного хуже: кратчайший путь может быть непростым, подпуть кратчайшего пути не может быть кратчайшим между двумя конечными точками подпути, пути, проходящие через бесконечное число ребер, могут иметь конечное время прибытия и т. Д. Снова посмотрите статью Орды и Рома для дальнейшего обсуждения.

Сянь-Чжи Чан 張顯 之
источник
3

Вам известна проблема «кратчайших неубывающих путей»? Он был определен для моделирования таких ситуаций, как эти. Хотя это немного менее выразительно по сравнению с вашей формулировкой, есть быстрые подсказки для этого.

Райан Уильямс
источник
1

Если вы предполагаете, что времена являются интегральными (что имеет смысл в случае общественного транспорта), вы можете создать сеть с расширенным временем, аналогичную той, которая была предложена Ford-Fulkerson для максимального потока во времени (или самого быстрого потока) и вместо этого найдите кратчайший путь в этом графе.

гелий
источник