Создание автобусного маршрута

Question

Что такое хороший алгоритм или класс алгоритмов, которые можно использовать для создания автобусного маршрута?

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

Я бы хотел, чтобы алгоритм имел по крайней мере следующие характеристики:

• дает относительнооптимизированный путь (я понимаю, что проблема, вероятно, завершена NP, поэтому хорошая эвристика в порядке)
• Может работать с частями пути, имеющими разный вес (например, время для прохождения по этой части пути)
• Может быть вынужден использовать заданную начальную и конечную точку (я не думаю, что это будет такой проблемой)

Код, который может это сделать, или что-то вроде этого будетприветствуется (особенно в C #), но хороший алгоритм сам по себе подойдет.

Примечание: Хотя существует много алгоритмов, которыеМожно найти кратчайший путь между двумя точками, я не знаю порядок, в котором я хочу остановиться.Таким образом, если я не буду использовать комбинацию двух алгоритмов (что я сомневаюсь в этом), эти алгоритмы не делают то, что я хочу (если вы думаете, что они делают, пожалуйста, объясните).

Редактировать: Предположим, я знаю все остановки, которые нужно сделать.

Answer 1

Кажется, что способ сделать это включает использование алгоритма Флойда-Варшалла, а затем использование алгоритма, который используется для решения задачи коммивояжера.

Это решает проблему всех «необязательных»вершины (пересечения) и использование алгоритма коммивояжера для определения порядка, в котором должны быть достигнуты остановки.

Answer 2

Вы, вероятно, можете использовать алгоритм коммивояжера с небольшой модификацией / допущением здесь, чтобы обратиться к точке # 2 (часть пути, имеющая различные веса).

Допустим, путь от точки «A» к точке «B» имеет 2 веса (скажем, трафик в определенный момент времени)

Несмотря на то, что это единственный путь, мы можем упростить задачу, предполагая "виртуальную вершину", точку "C", которая находится между "A" и "B", которая будет иметь фиксированные веса в каждом из ребер.

A ------- Вес = 10 ------ C ------ Вес = 15 ------ B

На этом новом графике запустите алгоритм коммивояжера.

Answer 3

Автобусные маршруты создаются людьми, а не компьютерами. Только люди знают, кому нужно путешествовать, где и как часто. Вам нужны как минимум такие данные, чтобы подумать о поиске набора маршрутов, который будет оптимальным для потребностей людей. В связи с этим я думаю, что ваш вопрос недоопределен.

Answer 4

Я использовал алгоритм Джикстры: http://en.wikipedia.org/wiki/Dijkstras_algorithm

Стоимость проезда по краю - это не только расстояние, но и время, в течение которого «следующий» автобус отходит от данного узла.Примечание. Возможно, вы уже находитесь в автобусе, когда он останавливается на узле.