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

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

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

Вопрос:
Как распределить эти точки между автомобилями так, чтобы ускорить процесс вывоза?
После того как эти точки будут распределены, координаты будут скормлены яндекс.картам и построены оптимальные маршруты (если есть другие бесплатные решения для построения оптимального маршрута, то буду рад ознакомиться с ними).
Первоначально вижу задачу как задачу коммивояжера (есть стоимость точки и стоимость расстояния между ними). Но так как не сильно знаком с решением задач такого характера, прошу помочь вас.
  • Вопрос задан
  • 703 просмотра
Пригласить эксперта
Ответы на вопрос 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. Яндекс карты и всех их гис сервисы это днище полное, причем по заоблачным ценам.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
AGIMA Москва
от 150 000 до 250 000 ₽
СофтТелематика Москва
от 200 000 до 250 000 ₽
PitchMe Санкт-Петербург
от 250 000 ₽
20 сент. 2020, в 17:49
20000 руб./за проект
20 сент. 2020, в 17:15
500 руб./за проект
20 сент. 2020, в 14:43
350 руб./за проект