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

Question

[bubaley]

Здравствуйте, описание задачи:

Есть контрольные точки (более 200-300, далее будут только увеличиваться). На каждой из точек находится груз определенного веса (всегда приблизительный).
Каждый день в наличии по 2-3 машины.
Необходимо распределить машины таким образом, чтобы с минимальными затратами (временными) забрать весь груз с этих точек и отгрузить на пункт вывоза. Причем одна машина забирает груз с ,приблизительно, 30-50 точек, то есть маршрут будет строиться с многократным посещением пункта отгрузки. Так же есть контрольные точки, которые обслуживаются только одной из трех машин.
Перед началом построения маршрутов известны расстояние между точками и приоритет вывоза.

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

Comments

[sim3x]

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

[bubaley]

sim3x, думаю через какой-нибудь сервис брать2 контрольные точки, прокладывать между ними маршрут, брать расстояние и сохранять в БД, со временем между каждыми точками будут сформированы расстояния. Хотя бы приблизительные

[hint000]

А ещё неплохо бы как-то учитывать пробки на дорогах. И состояние пробок всё время меняется. Так что красивый оптимальный маршрут внезапно превращается в полную жо... для водителя.
С учётом пробок задача усложняется настолько, что потребуется какой-нибудь Яндекс с бригадой программистов (ну или 2ГИС с бригадой программистов - тоже неплохо).
Предлагаю подойти к задаче с другой стороны. Человек может решать такие задачи эвристически, не хуже компьютера.
Вариант 1: нанять одну тётю-диспетчера, пусть распределяет точки по машинам и оперативно контролирует пробки по карте (всё те же Яндекс или 2ГИС), поддерживает связь с водителями. В помощь диспетчеру нужна всего лишь простенькая база данных по грузам, адресам и водителям, главное, чтоб интерфейс был удобный.
Вариант 2: (похуже) без диспетчера. Построить разумную систему мотивации, чтобы водители сами расхватывали заказы, как горячие пирожки. Примерно как Яндекс.Такси. Набрав кучку заказов, водитель сам уже будет смотреть по дорожной обстановке, куда ему лучше ехать прямо сейчас, а куда чуть позже. Надо только продумать момент, чтобы не оставалось таких точек, куда никто не захотел ехать.

[bubaley]

hint000, просто сейчас эта тетенька уже есть, они уже работают, но работаю в Excel
Нужно как-то предложить такое решение, чтобы они сказали "Вах, красота" и начали работать в единой системе.
Просто есть уже готовое программное решение которые выполняет другие функции этой организации. Теперь хотим чтобы можно было выполнять еще и логистические.
1. Что можно такого предложить этой тетеньке?) Сейчас тоже понимаю, что просто так оптимизировать не получится, тем более у этой тетеньки большой опыт в прокладке таких маршрутов. Разве удобного интерфейса ей хватит?)
2. Идея хорошая, обсудим с заказчиком, но ой мне кажется не одобрят)

[Александр Аксентьев]

Для это есть куча дорогих и не очень коммерческих сервисов. https://tech.yandex.ru/routing/
Непонятно как вы хотите на коленке оптимизировать ручную работу частично.
В любом случае нужна какая никакая интеграция с чем-то, на коленке на напишешь.
Не говоря уже про самописное решение какое-то.

[hint000]

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

Answer 1

[EVGENY T.]

Глава 14 книги Лафоре "Структуры данных и алгоритмы Java" посвящена данному вопросу - рекомендую ознакомиться.

Answer 2

[Adamos]

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

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

Answer 3

[CHolfield]

https://math.semestr.ru/simplex/simplex-standart.php

Answer 4

[grinat]

Osrm полностью бесплатное, у гугла есть условное платное(очень дешевое), есть еще куча аналогов с разными ценами. Они все в основном чисто маршрут считают, то есть с распределением груза самому придется разбираться. Делать самому построение маршрута по реальным дорогам, как тут народ советует, это анриал, потому что например единственная бесплатная база, откуда можно взять данные, это osm и она весить полгига по моему для всего мира, есть правда сборки для регионов, но там нужны нехилые ресурсы сервера и куча времени чтобы с их форматом разбираться. Для osrm кстати данные готовить то еще дело, можешь тупо с моего репо по рф забрать: https://gitlab.com/grinat/osrm-prepared-russia-data потому что если сервер osrm использовать, то он регулярно лежит.
И если эти 200-300 точек на яндекс карте отображать, это очень плохое решение, яндекс с кластерами такое число не вывозит на слабом пк, а если в чистую выводить, то и на норм пк может не вывести, бери mapbox, либо leaflet. Яндекс карты и всех их гис сервисы это днище полное, причем по заоблачным ценам.