Может из теории расписаний?
Всем привет!
Подскажите как формально записать и можно ли точно решить следующую задачу.
1. С центрального склада выезжают M фур. Каждая фура должна объехать Ni (i=1..M) торговых точек. Порядок объезда известен и неизменен - товар загружен в фуру в соответствующем порядке. Время разгрузки каждой фуры в каждой торговой точке Tij известно. Время поездки от одной торговой точки до следующей для каждой фуры известно. Одновременно в каждой торговой точке может разгружаться только одна фура. Если фура выехала с центрального склада, то простаивать где-то в дороге или в торговой точке она не должна - приехала, разгрузилась, поехала дальше. Можно задерживать выезд только с центрального склада на Tk>=0 (k=1..M).
Необходимо так выбрать задержки выезда для всех фур с центрального склада, чтобы сумма Tk (k=1..M) была минимальна.
-----------
Пока, эвристически, решаем так.
Сортируем от большего к меньшему маршруты фур по времени в пути с учетом времени разгрузки в каждой торговой точке. Первая фура (с наибольшем временем в пути) выезжает без задержки. Для второй фуры определяем времена прибытия на торговые точки, находим накладки с первой фурой, находим из них самую длительную по времени, на столько сдвигаем выезд второй фуры с центрального склада. Затем опять проверяем накладки с первой фурой уже с учетом задержки. если накладки есть, то еще увеличиваем время задержки выезда второй фуры... Если накладок нет - переходим к определению задержки выезда третьей фуры. И т.д.
Такой вот "жадный" эвристический алгоритм...
Может у кого есть соображения как это все улучшить, или вообще точно решить?
|