Алгоритм маршрута перевозчика?

Question

[Xnter]

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

Comments

[Василий Банников]

Кажется, тут надо использовать матрицу расстояний, а уже на её основе строить маршрут своими алгоритмами, раз есть требование о том, что мы сначала должны загрузиться, а потом разгрузиться.
https://developers.google.com/maps/documentation/d...

Потом уже когда будет известна последовательность - уже обычный route api https://developers.google.com/maps/documentation/routes

[Xnter]

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

[Василий Банников]

Xnter, а это уже задача коммивояжера, как пишет ниже mayton2019

Есть много разных способов решения. На небольшом наборе данных можно даже полный перебор попробовать

Answer 1

[mayton2019]

Это - задача коммивояжера. Но с дополнениями. В классической постановке например
коммивояжер должен объехать все 50 штатов и при этом его путь по дорогам должен быть минимален.

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

Плюс есть еще гараж А и Б но для нас это не важно. Просто все генерируемые маршруты будут А .... Б. По шаблону.

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

Методов решения много. Чаще всего я слышал про генетические алгортмы и отжиг.
Они - очень похожи. Учитывая что в примере очень мало пунктов развозки то задача за 1 секунду
может быть решена генетикой причем точныйм и наилучшим образом.