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

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

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

Вопрос:
Как распределить эти точки между автомобилями так, чтобы ускорить процесс вывоза?
После того как эти точки будут распределены, координаты будут скормлены яндекс.картам и построены оптимальные маршруты (если есть другие бесплатные решения для построения оптимального маршрута, то буду рад ознакомиться с ними).
Первоначально вижу задачу как задачу коммивояжера (есть стоимость точки и стоимость расстояния между ними). Но так как не сильно знаком с решением задач такого характера, прошу помочь вас.
  • Вопрос задан
  • 1000 просмотров
Пригласить эксперта
Ответы на вопрос 4
Beshere
@Beshere
Разработчик
Глава 14 книги Лафоре "Структуры данных и алгоритмы Java" посвящена данному вопросу - рекомендую ознакомиться.
Ответ написан
Комментировать
Adamos
@Adamos
Теоретические маршруты по Яндексу могут напрочь разбиться о реальность. Для сложной схемы желательно GPS-трекеры на этих машинах и эвристические данные везде, где они есть.
Вес груза - не единственный критичный параметр, кстати. Габариты и негабаритный груз, занимающий пол-машины, легко превращают теоретический расчет в тыкву.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы