Коммивояжер (TSP) для линейных маршрутов, снегоочиститель
В типичном алгоритме TSP у нас есть несколько точек, и мы хотим путешествовать в оптимальном порядке. Точки, обозначающие домохозяйства, клиентов и т. Д., В основном - это точки на карте.
Вместо точек у меня есть линии для оптимизации. Снегоочиститель является хорошим примером, когда вам нужно путешествовать по нескольким улицам. И самое большое отличие состоит в том, что для каждого путешествия конечная точка отличается от начальной точки. Моя попытка состояла в том, чтобы просто принять начальную точку в качестве единственного узла в каждом путешествии. Но, очевидно, всякий раз, когда ваш маршрут / линия довольно длинная, вы заканчиваете в отдаленной точке от вашего старта. И решение больше не близко к оптимальному.
Я посмотрел на некоторые компании, которые обеспечивают оптимизацию маршрута. Их решение - просто разбить линии на близкие точки; и обрабатывать каждую строку как узлы, близкие друг к другу. Я думаю, что это не сработает, когда вам нужно ехать по двум сторонам улицы или когда вы приближаетесь к другой улице.
Интересно, есть ли хитрость моделирования или какой-либо другой способ решения этой проблемы?
2 ответа
Вы фактически представили четыре совершенно разные задачи в своем вопросе, состоящие из двух основных задач с двумя подзадачами каждая.
Задача 1: однонаправленное движение по улицам
В этом случае задача состоит в том, чтобы найти оптимальный маршрут с учетом набора улиц, которые нужно пройти только в одном направлении. Эта проблема сама по себе может быть разделена на две проблемы.
Задача 1А: однонаправленное движение по улицам с обязательным завершением
В этой задаче продавец должен пройти всю длину улицы, прежде чем идти на следующую улицу. Для этой задачи каждая улица может быть смоделирована двумя конечными точками, и проблема может быть решена с помощью алгоритма TSP с одной модификацией. Когда алгоритм выбирает одну конечную точку улицы для рассмотрения, продавец перемещается на другую конечную точку улицы, и обе конечные точки отмечаются как выполненные.
Задача 1B: однонаправленное движение по улицам с дополнительными обходами
Аналогично Задаче 1А, за исключением того, что продавцу разрешено покинуть улицу, чтобы пересечь одну или несколько других улиц, прежде чем вернуться к завершению текущей улицы. Для этой задачи каждая улица может быть смоделирована как серия посещаемых точек, и решением является стандартный алгоритм TSP.
Задача 2: двунаправленное движение по улицам
В этом случае задача состоит в том, чтобы найти оптимальный маршрут с учетом набора улиц, которые необходимо пройти в обоих направлениях или, по крайней мере, иметь точки интереса с обеих сторон. Эта проблема сама по себе может быть разделена на две проблемы.
Задача 2А: двунаправленное движение по улицам с обязательным завершением
Это проблема почтальона и / или проблема смешанного вида транспорта. Рассмотрим воображаемого почтальона, который начинает с грузовика, полного почты. На каждой улице часть почты загружается в сумку, которую почтальон несет пешком в каждый дом. Почтальон доставляет почту на одной стороне улицы, а затем возвращается к грузовику, доставляя почту на другой стороне улицы. Иными словами, коммивояжер должен вернуться в пункт отправления, чтобы продолжить использовать альтернативный вид транспорта. Для этой задачи каждая улица может быть смоделирована двумя конечными точками, и проблема может быть решена с помощью алгоритма TSP с одной модификацией. Как только алгоритм учел одну конечную точку улицы, другая конечная точка снимается с рассмотрения.
Задача 2B: двунаправленное движение по улицам с пешеходным движением
Это самая сложная из четырех задач. Проблема здесь в том, что путешествие к географически близкой точке может не дать оптимального решения. Например, на сельской дороге пешеходная прогулка может быть законной и безопасной. Тем не менее, на бульваре с четырьмя переулками, пешеходная дорожка может быть незаконной и чрезвычайно опасной. Кроме того, при ожидании перерыва в трафике может произойти значительная задержка, что может привести к попыткам сойти с ума. Чтобы решить эту проблему, алгоритм TSP должен быть модифицирован, чтобы включить функцию стоимости. В обычном алгоритме TSP стоимость перемещения между двумя точками пропорциональна расстоянию между ними. Но для этой задачи алгоритм должен сначала рассмотреть каждую пару точек и вычислить стоимость перемещения между этими двумя точками. Затем стандартный алгоритм TSP можно использовать для поиска оптимального маршрута на основе этих затрат.
Я не думаю, что TSP - правильная проблема. Вы ищете путь Эйлера - путь, который проходит через все ребра графа. В TSP вы ищете гамильтонов путь, путь, который проходит через все вершины.
Хорошей новостью является то, что найти Эйлерову тропу относительно легко. Может не быть одного, которое проходит через каждый край ровно один раз, но это также очень легко обнаружить.