Подскажите как/каким алгоритмом решать следующую задачу:
1) Есть город
2) В городе есть "Покупатели Б/У товары"
3) В городе есть "Продавцы Б/У товары"
4) Есть парк машин, которые могут доставлять товар от "продавцов" -> "покупателям"
Существует ряд ограничений:
1)Разный обьем машин
2)Разная грузоподъемность машин
3)Время работы машины(водителя и грузчиков) - (к примеру с 9 до 16)
4)Время в которое "Продавец" может отдать товар "Машине" (например: с 7 до 12)
5)Время в которое можно доставить товар "Покупателю" (например с 14 до 19)
Пример задачи:
Продавец Вася продает Старый телевизор (61х100х40 20кг), может отдать товар с 7 до 13
Продавец Петя продает Холодильник (56, 185, 43 30кг), может отдать товар с 8 до 12
Покупатель Миша покупает "Старый телевизор", время доставки с 12 до 15
Покупатель Дима покупает "Холодильник", время доставки с 13 до 18
Парк машин:
Машина 1 - Грузоподъемность 2000 кг, габариты 200х190х150
Машина 2 - Грузоподъемность 2000 кг, габариты 200х190х150
Должно учитываться время на:
1) Переезд между точками(местами загрузки и разгрузки тавара)
2) на загрузку и разгрузку товара
Пример ручного решения:
10.00 - "Машина 1" у Пети, загружают холодильник
11.00 - "Машина 1" у Васи, загружают телевизор
12.00 - "Машина 1" у Миши, выгружают телевизор
13.00 - "Машина 1" у Дима, выгружают Холодильник
В задачи нет единого "склада".
Нужно составить график для водителей - какой товар и у кого они забирают и кому отвозят, при этом минимизировать количество используемых машин.
На данном этапе более важен точный результат, чем скорость подсчета.
Для небольшого количества машин и событий решается динамическим программированием на графе событий.
Для большого количества - точного решения нет, но очень неплохо зарекомендовали генетические алгоритмы (результат субоптимален с ошибкой не более 3% от оптимального).
Рандомно. Она приходит к весьма неплохому состоянию буквально за 5-10% от общего времени расчета, а остальные 90% времени - шла собственно оптимизация. Поэтому решено было "закрыть глаза" на эти 10% потерь.
