Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.02.2011, 14:44
Новичок

Отправить личное сообщение для valeryvb Посмотреть профиль Найти все сообщения от valeryvb
 
Регистрация: 03.02.2011
Сообщений: 1

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

Такой вот "жадный" эвристический алгоритм...
Может у кого есть соображения как это все улучшить, или вообще точно решить?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите кто,что может... гость Реализация, исходники, языки 1 28.01.2010 15:38
Задачка по теории алгоритмов. гость Задачи 9 10.03.2009 22:31
Теория расписаний. Нестандартная задача. baninma Математические алгоритмы (другое) 2 16.12.2008 21:27
Автоматизированное составление расписаний с использованием генетических алгоритмов. GreatWizard Математические алгоритмы 1 28.04.2008 14:41
Подскажите, может существует другой алгоритм определения ширины многоугольника ViniPuh Математические алгоритмы 2 18.02.2008 19:55