На самом деле вы представили в своем вопросе четыре совершенно разных задачи, состоящих из двух основных задач с двумя подзадачами каждая.
Задача 1: движение по улице в одном направлении
В этом случае задача состоит в том, чтобы найти оптимальный маршрут с учетом набора улиц, которые нужно пройти только в одном направлении. Саму задачу можно разделить на две части.
Задача 1A: однонаправленный переход улицы с обязательным завершением
В этой задаче продавец должен пройти всю улицу, прежде чем перейти на следующую улицу. Для этой задачи каждая улица может быть смоделирована двумя ее конечными точками, и проблема может быть решена с помощью алгоритма TSP с одной модификацией. Когда алгоритм выбирает для рассмотрения одну конечную точку улицы, продавец перемещается на другую конечную точку улицы, и обе конечные точки отмечаются как выполненные.
Задача 1B: движение по улице в одном направлении с дополнительными боковыми проездами
Подобно Задаче 1A, за исключением того, что продавцу разрешено покинуть улицу, чтобы пересечь одну или несколько других улиц, прежде чем вернуться, чтобы пройти текущую улицу. Для этой задачи каждую улицу можно смоделировать как серию посещаемых точек, и решением является стандартный алгоритм TSP.
Задача 2: движение по улице в обоих направлениях
В этом случае задача состоит в том, чтобы найти оптимальный маршрут с учетом набора улиц, которые необходимо пройти в обоих направлениях или, по крайней мере, иметь достопримечательности с обеих сторон. Саму задачу можно разделить на две части.
Задача 2A: двунаправленный переход улицы с обязательным завершением
Это проблема почтальона и / или проблема смешанного транспорта. Представьте себе воображаемого почтальона, который начинает с грузовика, полного почты. На каждой улице часть почты загружается в сумку, которую почтальон пешком несет в каждый дом. Почтальон доставляет почту на одной стороне улицы, а затем возвращается к грузовику, доставляя почту на другой стороне улицы. Другими словами, коммивояжер должен вернуться в пункт отправления, чтобы продолжить использование альтернативного вида транспорта. Для этой задачи каждая улица может быть смоделирована двумя ее конечными точками, и проблема может быть решена с помощью алгоритма TSP с одной модификацией. Как только алгоритм учитывает одну конечную точку улицы, другая конечная точка исключается из рассмотрения.
Задача 2B: переход улицы в двух направлениях с переходом на другую сторону
Это самая сложная из четырех задач. Проблема здесь в том, что путешествие в географически близкую точку может не дать оптимального решения. Например, по сельской дороге переход в неположенном месте может быть законным и безопасным. Однако на бульваре с четырьмя полосами движения пешеходный переход может быть незаконным и чрезвычайно опасным. Кроме того, ожидание перерыва в движении транспорта, которое позволит совершить переход в неположенном месте, может иметь значительную временную задержку. Чтобы решить эту проблему, необходимо изменить алгоритм TSP, включив в него функцию стоимости. В обычном алгоритме TSP стоимость проезда между двумя точками пропорциональна расстоянию между ними. Но для этой задачи алгоритм должен сначала рассмотреть каждую пару точек и вычислить стоимость проезда между этими двумя точками. Затем можно использовать стандартный алгоритм TSP для поиска оптимального маршрута на основе этих затрат.
person
user3386109
schedule
04.04.2014
