Алгоритм для транспортной задачи?

Question

[lightsuner]

Подскажите как/каким алгоритмом решать следующую задачу:
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" у Дима, выгружают Холодильник

В задачи нет единого "склада".

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

На данном этапе более важен точный результат, чем скорость подсчета.

Answer 1

[Андрей]

Для небольшого количества машин и событий решается динамическим программированием на графе событий.
Для большого количества - точного решения нет, но очень неплохо зарекомендовали генетические алгоритмы (результат субоптимален с ошибкой не более 3% от оптимального).

Comments

[lightsuner]

Вроде моя задача классифицируется как "vehicle routing problem with pickup and delivery (VRPPD)" - wiki4city.ieis.tue.nl/index.php?title=VRPPD.

На сайте написан вариант решения "tabu search meta-heuristic". Не знаете ли вы про tabu search, и чем он лучше/хуже генетического алгоритма?

[Андрей]

В русскоязычной литературе - "поиск с запретами". В нашем проекте с ним не сравнивали, поэтому ничего сказать не могу ни в плюс ни в минус.

[lightsuner]

Еще вопрос, вы первую популяцию генерируете "рандомно" или тоже используете какой-то алгоритм?

[Андрей]

Рандомно. Она приходит к весьма неплохому состоянию буквально за 5-10% от общего времени расчета, а остальные 90% времени - шла собственно оптимизация. Поэтому решено было "закрыть глаза" на эти 10% потерь.

Answer 2

[Михаил]

Как вариант: посмотрите в сторону задачи о ранце.

Answer 3

[xseven]

Если я правильно помню, то данная задачу относится к задачам линейного программирования (вроде поддкласс теории оптимизации, но могу путать).

Скорее всего подобная задача будет решаться чем-то похожим на симплекс метод