У меня есть проблема, которая беспокоит меня долгое время и пока не может найти лучший подход к ней.
Я надеюсь, что это лучшее место, чтобы задать такой вопрос.Если нет, пожалуйста, направьте меня в лучшее место: D.
Проблема :
У вас есть город с M магазинами и N курьерами и Q заказами для доставки.
M в [0, 10 ^ 3], N в [0, 10 ^ 3] и Q в [0, 10 ^ 4].
Каждый заказ имеет следующие данные
(time_to_pick_up Ti , delivery_location (xi, yi) , shops_location (x, y) ).
Каждый курьер имеетstart_location (cx, cy)
Запрос :
1) Найдите соответствие (порядок курьеров), которое минимизирует общее использование или курьеров.
2) Найти соответствие (заказ курьеров), которое минимизирует общее время ожидания для всех заказов (время ожидания = (time_when_delivered - time_to_pick_up))
NOTE :
- заказ не может быть забран до времени time_to_pick_up
- курьер не может получить более 1 заказа (он должен доставить заказ до начала нового заказа)
- все курьеры имеютта же скорость
Заранее благодарен за любую помощь.
Я думаю, что это проблема, которую компании такси (как Uber) уже решили для своих клиентов.Я пробовал разные жадные подходы в оптимизации комплектации курьеров, но я думаю, что это довольно далеко от лучшего решения.Я попытался сопоставить проблему с проблемой сопоставления двудольных графов, но безуспешно.