Возник вопрос поиска алгоритма для следующей задачи (условие составил сам по аналогии, изначально совсем другая отрасль, цифры, свойства):
На складе есть 1000 единиц товара, которые нужно успеть доставить за 3 часа.
Есть транспортная компания с 1000 автомобилей для доставки.
Время доставки товара и возврата автомобиля обратно на склад может занимать от 5 до 30 минут, автомобиль может взять только одну единицу товара.
Подготовка автомобиля (запуск) к первой доставке занимает 2 минуты.
Время работы автомобиля для доставки оплачивается почасово, допустим, один час стоит 100 рублей.
То есть, если отправить на доставку все 1000 машин, мы успеем все доставить максимум за 35 минут, то есть уложимся в 3 часа точно, но вот расходы будут огромными - 1000 автомобилей * 100 рублей = 100 000 рублей.
Нужно составить алгоритм, оптимизирующий расписание так, чтобы уложиться в 3 часа, но при этом затратить как можно меньше денег.
Задача вроде бы похожа на транспортную, но с некоторыми ограничениями (первый запуск автомобиля занимает 2 минуты, нужно уложиться в 3 часа). Может кто-нибудь сталкивался с аналогичной проблемой, или может подсказать, в какую сторону рыть?
Для правильного вопроса надо знать половину ответа
Задача сводится к разбиению исходного множества грузов на группы, суммарное время доставки которых не превосходит 2:58, но максимально близко к этой величине.
Точное решение - перебор всех вариантов - на таком количестве грузов неприменим.
Один из методов приближённого решения - жадный алгоритм. Рассортируем грузы по убыванию времени доставки. Заведём (1000/(178/30)) = 169 ячеек и для каждого груза из отсортированного списка будем просматривать ячейки начиная с первой на возможность добавления в неё груза с учётом ограничений.
Задача о назначениях, страница 163 и далее по сноскам.
Отличная книжка к слову сказать.
PS т.к у вас ситуация значительно проще и стоимость доставки не зависит от исполнителя - я бы попробовал для разнообразия попробовать следующий алгоритм: отсортировать заказы по убыванию времени доставки, и пробежаться по ним циклом, пытаясь найти максимальное количество наборов заказа имеющих итоговое время доставки 1-2-3 часа.
Впрочем не уверен что жесткий милиметраж имеет практический смысл, т.к в реальной логистике +-20% на время доставки это нормально.
Средний
