Как я могу написать алгоритм для оптимизации маршрута доставки, если доставка не задерживается?
Мой брат только начал работу по доставке, в настоящее время у него максимум 6 доставок в день, и поставки сгруппированы по трем категориям: 6 утра - полдень, полдень - 6 вечера и в любое время. Это заставило меня задуматься о том, как каждое утро он планирует оптимальный маршрут, чтобы убедиться, что доставка не опаздывает, а также минимизировать время, необходимое для завершения.
Поэтому я хотел придумать алгоритм, который мог бы сделать это, учитывая список доставок (широта, долгота, минимальное время доставки и максимальное время доставки). Я решил, что это кажется трудным делом, особенно потому, что API-интерфейсы Google GeoCoding и Directions имеют ограниченное количество вызовов в сутки.
Таким образом, чтобы упростить, я вернулся к переменному количеству блоков времени, которые не проходят через круг, и решил, что я согласен с предположением, что самое короткое общее расстояние равно самому короткому общему времени. Я знаю, что первый блок времени начинается с места, где мы забираем грузовик, но я не знаю, где он должен заканчиваться, потому что кратчайший путь, достигающий каждой точки в блоке времени, начинающегося при получении грузовика, может привести к очень далеко от ближайшей доставки следующего временного блока, и я не знаю, какую из поставок в следующем временном блоке использовать в качестве "последней" доставки первого временного блока.
Я надеюсь, что я объяснил это достаточно хорошо, чтобы это было понятно, и ради этого вопроса, пожалуйста, игнорируйте блок времени в любое время, так как я могу просто просеять их позже, где бы они ни увеличивали общее расстояние (по большей части, но я займусь одной проблемой за раз). Кроме того, несмотря на то, что в настоящее время у моего брата только около 6 доставок в день, я надеялся найти решение, которое не будет экспоненциально медленнее при добавлении доставок, чтобы оно могло поддерживать больше доставок, если бы оно могло обрабатывать 100, что было бы более чем достаточно.
Если вы думаете, что есть еще лучший (более простой, но все же дает правильные результаты) способ решения проблемы, а не переменное число непересекающихся временных блоков, я также хотел бы услышать об этом.
Спасибо!