Решение онлайн задачи коммивояжера: Задача коммивояжера онлайн

Задача коммивояжера – научимся решать её на компьютере

Большинство задач дискретной оптимизации являются NP-трудными. Это значит, что в общем виде нет аналитического метода решения таких задач, а количество вариантов перебора растёт как экспонента от размерности задачи.

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

Задача коммивояжера

 Эта задача формулируется очень просто, однако, к сожалению, никто не знает точного метода её решения.

Пусть есть n городов, и заданы расстояния между любыми двумя городами. Маршрут, начинающийся и заканчивающийся в некотором городе, который включает в себя все остальные города ровно по одному разу, называется гамильтоновым циклом. Нужно найти гамильтонов цикл минимальной суммарной длины.

Название «задача коммивояжера» непосредственно связана с её неформальной постановкой. Пусть коммивояжер (странствующий торговец) живёт в некотором городе и по делам собирается посетить несколько других. Он хочет найти замкнутый маршрут минимальной длины, чтобы посетить все нужные ему города и вернуться домой.

По разного рода приближённым методам решения задачи коммивояжера написано тысячи статей, защищено сотни диссертаций, между составителями программ по решению этой задачи даже проводятся чемпионаты.

Рис.1. Замкнутый маршрут минимальной длины между крупными городами КитаяРис. 2. Логотип американской конференции по методам оптимизации – маршрут минимальной длины между столицами штатов

Задачи коммивояжера небольшой размерности можно решать на компьютере. Для этого нужно в поисковой строке google набрать запрос «задача коммивояжера онлайн». Например, сервис  позволяет решать онлайн задачи с количеством пунктов до 14. Этого вполне достаточно для курьера, составляющего план доставки товаров в течение дня.

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

Пусть турист, находящийся во Львове, хочет совершить турне по таким городам: Братислава, Будапешт, Вена, Краков, Прага.

Чтобы решить такую задачу, нужно предварительно подготовить исходные данные – узнать расстояния по автодорогам между всеми городами. Это можно сделать, например, при помощи сервиса www.della.ua/distance.

	Львов	Братислава	Будапешт	Вена	Краков	Прага
Львов	М	779	575	788	326	858
Братислава	779	М	200	80	455	328
Будапешт	575	200	М	243	395	525
Вена	788	80	243	М	464	323
Краков	326	455	395	464	М	535
Прага	858	328	595	323	535	М

В сервисе https://math. semestr.ru/kom/index.php выберем количество пунктов – 7, перенесём данные в появившуюся таблицу и нажимаем клавишу «далее».

В окне появляется линейка прокрутки с ходом решения, нас интересуют только выводы (в конце). Они такие:

В результате по дереву ветвлений гамильтонов цикл образуют рёбра:
(1,5), (5,6), (6,4), (4,2), (2,3), (3,1). 
Длина маршрута равна F(Mk) = 2039.
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера.

Переходя от цифр к названиям городов, получаем оптимальный маршрут Львов–Краков–Прага–Вена–Братислава–Будапешт–Львов, длина которого равна 2039 км. Поскольку матрица расстояний симметрична (т.е. d(i,j) = d(j,i)), то маршрут, пройденный в обратном направлении, будет иметь такую же длину.

Оказывается, решая задачу коммивояжера, можно уменьшать не только пройденное расстояние, но и время, затрачиваемое на последовательность операций. Здесь можно вспомнить о двух значениях английского слова «way». Первое – это путь, дорога. Второе – это способ сделать что-нибудь.

Рассмотрим такой пример. Пусть есть многофункциональное устройство (это может быть и кухонный комбайн, и производственный станок). Пусть на этом устройстве нужно выполнить несколько операций, порядок выполнения которых произвольный, так, чтобы суммарное время использования устройства и его приведения в исходное состояние было бы минимальным.

Заметим, что суммарное время выполнения операций не зависит от их последовательности (от перемены мест слагаемых сумма не меняется). Однако, перенастройка устройства с одной операции на другую зависит от порядка, в котором они будут выполняться.

Например, пусть на кухонном комбайне нужно выполнить две операции: 1) выжать яблочный сок, 2) измельчить лук для котлет. Заметим, что в этом случае следует выбрать последовательность действий яблоки–лук.

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

После окончания двух операций нужно будет помыть комбайн. Но, если выбрать последовательность действий лук–яблоки, то комбайн придётся мыть дважды – вряд ли кто-то захочет пить яблочный сок с лучным привкусом.

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

А до В равно расстоянию от В до А, но время переналадки от операции А к В не обязательно равно времени переналадки от В к А).

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

Ещё одно неожиданное применение задачи коммивояжера состоит в составлении оптимального плана раскройки обоев. Те, кто когда-либо клеил обои, или хотя бы смотрел, как это делают другие, знают, что при проклейке возникает проблема подбора рисунка.

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

Рис. 3. Рулон с периодичным рисунком

Для каждого куска зададим координаты начала и конца, как если бы этот кусок вырезался с самого начала рулона.

Пусть требуется вырезать шесть таких кусков:

0-6, 2-8, 4-12, 7-12, 8-11, 9-16 (в дециметрах).

Назовём первым пунктом начало/конец операции раскройки, вторым – 1-й кусок, и т.д., седьмым – 6-й кусок:

№	1	2	3	4	5	6	7
	Нач./кон.	0-6	2-8	4-12	8-11	7-12	9-16

Назовём расстоянием между пунктами i и j ширину куска (в дециметрах), которую придётся вырезать и пустить в отходы при переходе от i-го пункта к j-му. Например, d(2,3) = 6, поскольку 2-й пункт заканчивается на отметке 6 дм, а 3-й начинается на 2 дм, следовательно, его надо выбирать уже на следующем метре рулона.

Между ними лежит полоса шириной 6 дм. В то же время d(3,2) = 2, поскольку 3-й пункт заканчивается на отметке 8 дм, а 2-й начинается на 0 дм на следующем метре. Здесь, как и в задаче переналадки, может нарушаться аксиома метрики.

Расстояние от 1-го пункта до всех остальных равно координате левого края соответствующего куска (например, d(1,3) = 2), а расстояние от всех пунктов до 1-го положим равным нулю (когда уже вырезаны все куски, то переходим в состояние «конец раскройки», при этом ничего не вырезаем, отходы равны нулю).  

Вычислим все остальные расстояния, занесём в таблицу и нажмём клавишу «далее».

В окне появляется линейка прокрутки с ходом решения, нас интересуют только выводы (в конце). Они такие:

В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,2), (2,7), (7,5), (5,4), (4,3), (3,6), (6,1) 
Длина маршрута равна F(Mk) = 6.
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера

Значит, при оптимальной раскройке отходы составят всего 60 см.

На основании полученного решения задачи коммивояжера составим план раскройки рулона. Он будет таким:

кусок 2 — отх. 30 см — кусок 7 — отх. 10 см — кусок 5 — отх. 20 см- кусок 4 — кусок 3 — кусок 6.

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

С.И. Доценко, кандидат физико-математических наук, старший научный сотрудник факультета компьютерных наук и кибернетики КНУ имени Тараса Шевченко

 

По теме:

Задачи теории расписаний. Где они возникают, и при чём тут «проклятие размерности»

Решение задачи коммивояжера с помощью метода ветвей и границ / Хабр

Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию, предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:

Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.

Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.

Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.

Кратко о методе — это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.

Исправленный алгоритм, для нахождения действительно минимального маршрута

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

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

2. Теперь наше множество S разбиваем на множества — содержащие ребро с максимальным штрафом(S_w) и не содержащие это ребро(S_w/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества S_w/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества S_w примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для S_w равна сумме оценки затрат для S и r(h,k), где r(h,k) — сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.

Небольшая оптимизация — подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Теперь, собственно, об ошибках в той публикации

Ошибка была одна единственная — следует выбирать для разбиения множество с минимальной границей из всех возможных путей, а не из двух полученных в результате последнего разбиения детей.

Доказательство

Вернемся к картинке в начале поста:

А вот решение с исправленным алгоритмом:

Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать

График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:

График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.

Попробовать с подробным решением можно тут.
данные измерений были получены по 100 случайным матрицам. не слишком хорошее число, но общее представление обеспечивает.
Исходники на GitHub (обновлены).

Решение задачи коммивояжёра для доставки

Задача коммивояжёра (TSP) — это задача найти кратчайший и наиболее эффективный маршрут для человека, учитывая список конкретных пунктов назначения. Это хорошо известная алгоритмическая проблема в области компьютерных наук и исследований операций, имеющая важные практические приложения для логистики и доставки.

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

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

В вычислительной технике TSP привлекла столько внимания, потому что ее так легко описать, но так сложно решить. Фактически, он принадлежит к классу задач комбинаторной оптимизации, известных как NP-полные. Это означает, что TSP классифицируется как NP-сложный, потому что у него нет «быстрого» решения, а сложность расчета наилучшего маршрута возрастает по мере добавления дополнительных пунктов назначения.

Проблему можно решить, проанализировав каждый маршрут туда и обратно, чтобы определить кратчайший. Однако по мере увеличения числа пунктов назначения соответствующее количество круговых поездок превосходит возможности даже самых быстрых компьютеров. С 10 пунктами назначения может быть более 300 000 перестановок и комбинаций туда и обратно. С 15 пунктами назначения количество возможных маршрутов может превысить 87 миллиардов.

‍

Три самых популярных решения TSP

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

1. Подход грубой силы

Подход грубой силы, также известный как наивный подход, вычисляет и сравнивает все возможные перестановки маршрутов или путей для определения кратчайшего уникального решения. Чтобы решить TSP с использованием подхода грубой силы, вы должны рассчитать общее количество маршрутов, а затем нарисовать и перечислить все возможные маршруты. Рассчитайте расстояние каждого маршрута, а затем выберите самый короткий — это оптимальное решение.

2. Метод ветвей и границ

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

3. Метод ближайшего соседа

Это, пожалуй, самая простая эвристика TSP. Ключ к этому методу состоит в том, чтобы всегда посещать ближайший пункт назначения, а затем возвращаться в первый город после посещения всех остальных городов. Чтобы решить TSP с помощью этого метода, выберите случайный город, а затем найдите ближайший непосещенный город и отправляйтесь туда. После того, как вы посетили все города, вы должны вернуться в первый город. ‍

Как работают алгоритмы оптимизации маршрута для решения задачи коммивояжера.

Узнать больше.

Академические решения TSP

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

• Метод нулевого суффикса. ТСП.
• Алгоритм оптимизации на основе биогеографии: Этот метод разработан на основе стратегии миграции животных для решения проблемы оптимизации.
• Метаэвристический повторный локальный поиск с множественным перезапуском (MRSILS): Сторонники этого исследования утверждали, что метаэвристический MRSILS более эффективен, чем генетические алгоритмы, при использовании кластеров.
• Многоцелевой эволюционный алгоритм: Этот метод предназначен для решения нескольких TSP на основе NSGA-II.
• Мультиагентная система: Эта система предназначена для решения TSP N городов с фиксированным ресурсом.
   

Реальные приложения TSP

Несмотря на сложность решения задачи коммивояжера, она по-прежнему находит применение во всех вертикалях.

Например, решения TSP могут помочь сектору логистики повысить эффективность последней мили. Доставка «последней мили» — это последнее звено в цепочке поставок, когда товары перемещаются из транспортного узла, такого как депо или склад, к конечному потребителю. Доставка «последней мили» также является основным фактором затрат в цепочке поставок. В среднем это стоит 10,1 доллара, но клиент платит в среднем всего 8,08 доллара, потому что компании берут на себя часть затрат, чтобы оставаться конкурентоспособными. Таким образом, снижение этой стоимости напрямую влияет на прибыльность бизнеса.

Минимизация затрат на доставку «последней мили», по сути, доставка «последней мили» — это, по сути, Проблема маршрутизации транспортных средств (VRP ) . VVRP, обобщенная версия TSP, является одной из наиболее широко изучаемых задач математической оптимизации. Вместо одного лучшего пути он занимается поиском наиболее эффективного набора маршрутов или путей. Проблема может заключаться в нескольких складах, сотнях мест доставки и нескольких транспортных средствах. Как и в случае с TSP, определить лучшее решение для VRP сложно с точки зрения NP.

Реальные решения TSP и VRP

В то время как академические решения TSP и VRP нацелены на предоставление оптимального решения этих сложных NP-задач, многие из них непрактичны при решении реальных проблем, особенно когда речь идет о решении логистических задач последней мили.

Это потому, что академические решатели стремятся к совершенству, и поэтому для вычисления оптимальных решений требуется много времени — часы, дни, а иногда и годы. Если компании по доставке необходимо планировать ежедневные маршруты, им нужно решение маршрута в течение нескольких минут. Их бизнес зависит от этих решений по планированию маршрутов доставки, поэтому они могут доставить своих водителей и свои товары к двери как можно скорее.

Реальные решатели TSP и VRP используют алгоритмы оптимизации маршрутов, которые находят почти оптимальные решения за короткое время, предоставляя службам доставки возможность быстро и эффективно планировать маршруты.

Если вы хотите узнать больше о реальных решателях TSP и VRP, ознакомьтесь с приведенными ниже ресурсами 👇

API оптимизации маршрутов — TSP Solver

API оптимизации маршрутов — VRP Solver

Самая простая в использовании платформа оптимизации маршрутов для растущих компаний по доставке.

Узнать больше

Марк Куо

Марк Куо — основатель и генеральный директор Routific, платформы оптимизации маршрутов для растущих компаний по доставке. Наша миссия состоит в том, чтобы озеленить планету, сократив пробег и потребление топлива парками доставки. Обладая более чем десятилетним опытом работы в сфере доставки «последней мили», он консультировал сотни компаний по доставке по вопросам планирования их маршрутов и операций по доставке.

Все, что вам нужно знать в 2023 году

• Автор: Ракеш Патель
• Последнее обновление: 24 января 2023 г.

Опубликовано: 26 октября 2021 г. Ракеш Патель

Проблема коммивояжёра не нова для компаний, занимающихся доставкой. Его недавнее расширение потребовало от отраслевых экспертов найти оптимальные решения для облегчения операций по доставке.

Основная задача состоит в том, чтобы найти наиболее эффективные маршруты доставки с несколькими остановками. Без кратчайших маршрутов вашему агенту по доставке потребуется больше времени, чтобы добраться до конечного пункта назначения. Иногда могут возникнуть проблемы, если у вас есть несколько вариантов маршрута, но вы не можете распознать эффективный.

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

Содержание

• Что такое задача коммивояжера (TSP)?
• Общие задачи задачи коммивояжера (TSP)
• Какие есть популярные решения задачи коммивояжера?
• Каковы другие оптимальные решения задачи коммивояжера?
• Каковы некоторые реальные приложения задачи коммивояжера?
• Как TSP и VRP вместе создают проблемы?
• Может ли планировщик маршрутов решить проблему коммивояжера (TSP)?
• Часто задаваемые вопросы
• Заключение

Что такое задача коммивояжера (TSP)?

Задача коммивояжера (TSP) — это комбинаторная задача, которая касается поиска кратчайшего и наиболее эффективного маршрута для достижения определенного списка пунктов назначения.

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

Насколько сложно решить?

Решить TSP довольно сложно, так как он известен как NP-сложный, что означает отсутствие алгоритма полиномиального времени для его решения для большего количества адресов. Итак, с увеличением количества адресов сложность решения TSP возрастает в геометрической прогрессии.

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

Однако TSP можно устранить путем определения оптимизированного и эффективного пути с использованием алгоритмов аппроксимации или автоматизированных процессов.

Общие проблемы коммивояжера Задача (TSP)

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

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

• Во-вторых, возможны изменения в последнюю минуту. Иногда вы получаете дополнительные и срочные визиты, а иногда некоторые визиты откладываются или отменяются из-за недоступности клиента.

• Наконец, возникает математическая задача, задача комбинаторной оптимизации. Задача комбинаторной оптимизации — это задача, которую сложно решить с математической точки зрения, поскольку вам приходится иметь дело со многими переменными.

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

Какие есть популярные решения задачи коммивояжера?

Вот некоторые из почти оптимальных решений для поиска кратчайшего пути к задаче комбинаторной оптимизации.

1. Ближайший сосед (NN)

Метод ближайшего соседа, вероятно, является самой простой эвристикой TSP. Метод, которому следует этот алгоритм, гласит, что водитель должен начать с посещения ближайшего пункта назначения или ближайшего города. Как только все города в цикле будут пройдены, водитель может вернуться к начальной точке.

Решение TSP с использованием этого эффективного метода требует от пользователя случайного выбора города, а затем перехода к ближайшему не посещенному городу и так далее. Как только все города на карте будут покрыты, вы должны вернуться в город, из которого вы начали.

2. Алгоритм ветвей и границ

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

3. Алгоритм грубой силы

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

Каковы другие оптимальные решения задачи коммивояжера?

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

• Метод нулевого суффикса : Этот метод решает классическую симметричную TSP и был представлен индийскими исследователями.

• Многоцелевой эволюционный алгоритм : Этот метод решает TSP с использованием NSGA-II

• Алгоритм оптимизации на основе биогеографии : Этот метод основан на стратегии миграции животных для решения задач оптимизации.

• Мета-эвристический многократный перезапуск Итеративный локальный поиск : Этот метод утверждает, что этот метод более эффективен по сравнению с генетическими алгоритмами.

Продувочная TSP с использованием Upper

Необходимо постоянное решение для повторяющейся TSP? Зарегистрируйтесь в Upper, чтобы ваши продавцы всегда были в курсе. Откажитесь от ручного расчета и внедрите автоматизированный процесс прямо сейчас!

Начать бесплатную пробную версию

Каковы некоторые реальные приложения задачи коммивояжера?

Большинство предприятий отмечают рост числа проблем коммивояжёра (TSP) из-за проблем с доставкой на «последней миле». Доставка «последней мили» — это процесс доставки товаров со склада (или депо) в предпочтительное для клиента место. Принимая во внимание управление цепочкой поставок, доставка последней мили обходится вам в приличную сумму.

В то же время вам нужно пожертвовать финансовыми потерями, чтобы сохранить текущую позицию на рынке. Предположим, что доставка «последней мили» стоит вам 11 долларов, клиент заплатит 8 долларов, и вы понесете убытки. Это связано с предопределенными нормами, которые могут способствовать тому, чтобы клиент платил меньшую сумму.

Эта высокая стоимость доставки последней мили является результатом отсутствия программного обеспечения для решения задач маршрутизации транспортных средств (VRP). VRP находит для вас наиболее эффективные маршруты, чтобы эксплуатационные расходы не увеличивались. Таким образом, используя правильное программное обеспечение VRP, вам не придется беспокоиться о TSP.

Такое программное обеспечение для управления доставкой использует автоматизированный процесс, который не требует ручного вмешательства или расчетов для выбора наилучших маршрутов. Следовательно, это самый простой способ избавиться от проблемы коммивояжера (TSP).

Как TSP и VRP вместе создают проблемы?

Задача коммивояжера — задача оптимизации, изучаемая в теории графов и в области исследования операций. В этой задаче оптимизации все узлы или города на графе связаны прямыми ребрами или маршрутами. Вес каждого ребра указывает расстояние, пройденное на маршруте между двумя городами.

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

TSP часто изучается в обобщенной версии, которая представляет собой задачу определения маршрута транспортного средства. Это одна из наиболее широко разрабатываемых задач математической оптимизации. VRP занимается поиском или созданием набора маршрутов для сокращения времени, топлива и затрат на доставку.

Существует ли реальное решение для TSP и VRP?

Многие решения для TSP и VRP основаны на академических данных, что означает, что они не так практичны в повседневной жизни. Причина в том, что многие из них просто ограничены совершенством, но нуждаются в решении на основе динамического программирования. Поэтому, если предприятия действительно хотят избавиться от них, им нужен решатель TSP, интегрированный с программным обеспечением для оптимизации маршрутов.

Правильный решатель TSP поможет вам справиться с такими современными задачами. Он предлагает встроенные решения для планирования и оптимизации маршрута, чтобы ваш продавец не застрял во время доставки посылки. Кроме того, он оснащен эффективным алгоритмом, который обеспечивает правильные решения TSP. В результате менеджер по доставке может без проблем создать план маршрута за несколько минут.

Может ли планировщик маршрутов решить проблему коммивояжера (TSP)?

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

Но Upper Route Planner, программа оптимизации маршрута, устроена по-другому. У Upper есть все решения, которые вам нужны, когда речь идет о TSP.

Например, если вы отвечаете за планирование маршрутов доставки с более чем 500 остановками, все, что вам нужно сделать, это импортировать файл Excel или CSV с несколькими адресами в Верхний, просмотреть, назначить водителей доставки, оптимизировать и отправить одним щелчком мыши. Это решение для планирования маршрутов доставки экономит часы времени, затрачиваемые на планирование маршрутов доставки и их оптимизацию.

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

Верхний планировщик маршрутов

Простой в использовании планировщик маршрутов
, о котором все говорят

Начните бесплатную пробную версию

Часто задаваемые вопросы

TSP означает «задача коммивояжера», а VRP — это аббревиатура задачи маршрутизации транспортных средств. (ВРП). В индустрии доставки оба они широко известны по форме аббревиатуры.

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

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

Задача маршрутизации транспортных средств (VRP) снижает транспортные расходы, а также расходы водителей. Это поможет вам обслуживать больше клиентов с меньшим количеством автопарков и водителей. Таким образом, у вас нет никаких изменений во времени, затраченном на поездку.

Создайте оптимизированные маршруты с помощью Upper и попрощайтесь с коммивояжером Проблема

Как владелец бизнеса, если вы имеете дело с TSP и хотите избавиться от них, мы рекомендуем использовать средство решения TSP, такое как Upper Route Planner. Онлайн-планировщик маршрутов способен выбирать наиболее эффективные маршруты, независимо от того, насколько велик ваш TSP. Он имеет встроенный сложный алгоритм, который поможет вам получить оптимизированный путь за считанные секунды.

Таким образом, вы не станете жертвой таких реальных проблем и осуществите доставку в минимальное время. Планировщик маршрутов доставки Upper предлагает специальное приложение для водителей, которое гарантирует, что ваш продавец не ошибется и быстро завершит ожидающие доставки. Не просто соглашайтесь с нашими словами, заказывайте демо на Upper и разгоняйте TSP раз и навсегда.