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

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

Есть контрольные точки (более 200-300, далее будут только увеличиваться). На каждой из точек находится груз определенного веса (всегда приблизительный).  

Каждый день в наличии по 2-3 машины.  

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

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

После того как эти точки будут распределены, координаты будут скормлены яндекс.картам и построены оптимальные маршруты (если есть другие бесплатные решения для построения оптимального маршрута, то буду рад ознакомиться с ними).   

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

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

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

Вес груза - не единственный критичный параметр, кстати. Габариты и негабаритный груз, занимающий пол-машины, легко превращают теоретический расчет в тыкву.  
  

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

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

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

И если эти 200-300 точек на яндекс карте отображать, это очень плохое решение, яндекс с кластерами такое число не вывозит на слабом пк, а если в чистую выводить, то и на норм пк может не вывести, бери mapbox, либо leaflet. Яндекс карты и всех их гис сервисы это днище полное, причем по заоблачным ценам.