КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Матрица кратчайших расстояний между пунктами первого маршрута
Сгруппированные маршруты
Этап 2. Определяем рациональный порядок объезда пунктов каждого маршрута. Для этого строим таблицу матрицу, в которой по диагонали размещаем пункты, включаемые в маршрут, и начальный пункт А, а в соответствующих клетках – кратчайшие расстояния между ними (таб.11.2). Таблица 11.2
Начальный маршрут строим для трех пунктов матрицы, из которых один является пунктом отправления, а два других имеют наибольшие значения величины в строке суммы. Таким образом, в нашем примере начальный маршрут строим для трех пунктов матрицы АБКА. Пункт А входит, потому что является пунктом отправления грузов, а пункты Б и К имеют наибольшие значения величины, показанных в строке суммы (28,4; 30,1). Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму, и решаем, между какими пунктами его следует включать. В нашем примере пункт В из оставшихся имеет наибольшую сумму, и его надо вставить между А и Б, Б и К или К и А. Для этого для каждой пары пунктов необходимо найти величину приращения маршрута по формуле: Dkp = Ckj + Cjp – Ckp, где С – расстояние, км; j – индекс включаемого пункта; k – индекс первого пункта из пары; p – индекс второго пункта из пары. Из полученных значений выбирается минимальное, и пункт включения вставляется между теми пунктами, приращение которого окажется минимальным. При включении пункта В между первой парой пунктов А и Б, определяем размер приращения DАБ при условии, что j – В, k – А, p – Б. Тогда
DАБ = САВ + СВБ – САБ Подставляя значения из таблицы, получаем, что DАБ = 9,5 + 2,5 – 7 = 5 Таким же образом определяем размер приращения DБК и DКА DБК = СБВ + СВК - СБК = 2,5 + 5,2 – 7,7 = 0 Поскольку значение приращения DБК получилось равным нулю, дальнейшие расчеты уже необязательны, потому что меньше нуля значения уже не будет. Тогда из начального маршрута А-Б-К-А мы получаем А-Б-В-К-А. Используя этот метод и формулу приращения, определяем, между какими пунктами расположить пункты Е и З. Начнем с пункта З, так как размер суммы этого пункта больше. DАБ = 10,5 + 6,2 – 7 = 9,7 DБВ = 6,2 + 3,7 – 2,5 = 7,4 DКВ = 3,7 + 1,5 – 5,2 = 0 Таким образом, пункт З включается между пунктами В и К, и из маршрута А-Б-В-К-А мы получаем маршрут А-Б-В-З-К-А. И оставшийся пункт Е. DАБ = 8,4 + 5 – 7 = 6,4 DБВ = 5 + 4,1 – 2,5 = 6,6 DВЗ = 4,1 + 2,1 – 3,7 = 2,5 DЗК = 2,1 + 3,7 – 1,5 = 4,3 DКА = 3,6 + 8,4 – 12 = 0 Минимальным значением является DКА = 0, значит пункт Е включается между пунктами К и А. В результате мы имеем оптимальный маршрут развоза продукции А-Б-В-З-К-Е-А. Таким же методом определим кратчайший путь объезда пунктов по маршруту 2. В результате расчетов получим маршрут А-Ж-И-Д-Г-А. Порядок движения по полученным оптимальным маршрутам показан на рис.11.10.
Рис. 11.10. Схема полученных оптимальных маршрутов
Дата добавления: 2014-10-23; Просмотров: 1421; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |