Планирование грузовых автомобильных перевозок. Алгоритмы ускоренного планирования.

Три схемы перевозочного процесса

Математическая постановка задачи ДАНО: n - количество пунктов доставок c ij расстояние от пункта i до пункта j

, где U i и U j - произвольные вещественные значения

Целевая функция В качестве целевой функции могут быть и другие экономические показатели.

Определение времени доставки груза где - время погрузки у j-го грузоотправителя, - время движения с грузом от i-го до j-го пункта - время разгрузки у i-го грузополучателя k - количество пунктов разгрузки - время на холостой пробег до j-го развозочного маршрута - перерывы поставщика - перерывы потребителя

Пример ТРЕБУЕТСЯ: из пунктов a и b доставить груз в пункты b1- b1и в требуемом кол-ве согласно таблице 1 Пу нкт раз гру зки b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15Все го Ко л- во, т

РЕШЕНИЕ: 1) т. к. имеетя 2 пункта поставки и 15 пунктов приёма груза, то используем схему «многие ко многим» 2) решим транспортную задачу на основе данных таблицы 2, где дано расстояние между пунктами : Пун кт пог руз ки b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15 a a

3) критерием оптимальности в задаче является минимум транспортной работы в ткм Поэтому из таблицы 2 для каждого b i мы выбираем такое a1 или а2, чтобы расстояние между ними было минимальным и проставляем величину груза в соответствующую ячейку. Получим таблицу 3, где отражены объёмы перевозок: Пун кт пог руз ки b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15Все го a a

4) решим задачу маршрутизации (коммивояжера) и определим длины маршрутов и порядок объезда пунктов на нём, основываясь на расстояниях между рассматриваемыми на маршруте пунктами

Первый маршрут: a1-b15-b11-b3-b6-b9-b14-b5-b7-b2-a1 (28 км) Второй маршрут: a2-b8-b12-b1-b13-b4-a2 (26 км)

5) зададим временные ограничения, среднее значение, среднее квадратическое отклонение (СКО) и закон распределения случайных величин.

6) Рассчитаем время движения: где - время погрузки в нач. пункте, - время движения на i-ом участке, i кол-во участков движения на маршруте, - время на разгрузку в j-ом пункте разгрузки, j кол- во пунктов разгрузки где l i длина i-го участка в км, V i - скорость на i-ом участке, км/ч

Т.к. время погрузки в пункте a1 подчиняется нормальному закону, то: где - нормально распределённая случайная величина Итак: Считая, что автомобиль начнёт погрузку в 9.00, то движение он начнёт в = Расстояние a 1 b 15 (первые два пункта первого маршрута) 2 км, из предыдущих таблиц.

Рассчитаем скорость V 1 на первом участке по формуле V1= среднее знач. + ơ x ѯ ', где ѯ '=-0,127 Подставляя найденную скорость в формулу, получим: τ1 =2/30,6825=0,0652 ч=4мин Таким образом, в пункт b15 автомобиль прибудет в =11.25 Время разгрузки подчиняется экспоненциальному закону и потому рассчитывается по формуле: где ѯ – равномерно распределённое случ. число в [0,1]

Следовательно в пункте b15 разгрузка закончится в =11.28 Аналогичным образом определяем временные интервалы для следующих пунктов первого маршрута. Реализуя описанный алгоритм 10 раз для первого маршрута, получим следующую таблицу:

Недостатки алгоритма Трудоёмкость Полученный оптимальный маршрут может не отвечать требованиям клиентов по срокам доставки груза Возможные изменения в соглашении с поставщиками (времени, места разгрузки и т.д.)

Ускоренные методы 1) для решения транспортной задачи используется метод аппроксимации Фогеля 2) для составления маршрута метод воображаемого луча (метод Свира) 3) для решения «задачи коммивояжера» - ускоренный метод ветвей и границ 4) проводится оценка интервалов времени прибытия ср-ва и времени окончания разгрузки для каждого потребителя по формулам: для верхней границы - для нижней границы -

Пример ТРЕБУЕТСЯ: из пунктов a1 a2 перевезти груз восьми получателям b1-b8 в объёме Q. Данные:

РЕШЕНИЕ: предположим, что по существующему распределению за пунктом a1 закреплены b2,b3,b4,b7, за a2 b1,b5,b6,b8 Общая длина маятниковых маршрутов равна 180 км, а пробег с грузом 90 км Транспортная работа: Поэтому:

Применим метод Фогеля.

По завершении метода получим допустимую программу распределения: в числителе объём перевозок в соответствующий пункт (Q), в знаменателе -расстояние перевозки (l). Общее расстояние по маятниковым маршрутам: Т.к. то P= 0.25x x x8=61.2 ткм

Набор пунктов в маршрут (метод Свира) Положим грузоподъёмность средства 2.2 т В квадратных скобках потребность получателя в тоннах.

Ускоренный метод ветвей и границ Определим кратчайшие расстояния между пунктами в одном маршруте: применим метод для a1,b1,b2 и b4

Сумма констант, равная 28, является нижней границей

Определим оценки всех элементов как сумму наименьших значений в строке и столбце, на пересечении которых стоит элемент. Нижняя граница второго подмножества равна сумме значений нижней границы разделяемого мн-ва (28) и величины оценки a1b1, т. е =44

В рез-те преобразований получим: выбирая, например, пару b1b4, увеличим протяжённость мн-ва на 1 (44+1=45). Вычёркиваем соответствующие столбец и строку. Появилась константа 1, значит увеличиваем нижнюю границу на 1.

Получившуюся матрицу 2*2 легко решается. Недостающие пары b4b2 b2a1 полученный маршрут: a1b1-b1b4-b4b2-b2a1, протяжённость 45 км

Определение временных интервалов Для определения временных интервалов прибытия транспорта в пункты воспользуемся формулами Скорость движения, время простоя при погрузке/разгрузке представлены в таблице:

Среднее значение времени движения определяется как отношение расстояния перевозки (12 км для a1b2) к среднему значению скорости: Коэффициент вариации для тех. Скорости 0.08 из таблицы, поэтому СКО времени движения = 0.39 *0.08=0.03 ч t β определяется в зависимости от установленной вероятности нахождения затрат времени в расчётных пределах (табличные данные)

Предположим t β= 1.5, тогда верхняя граница времени доставки: Нижняя граница:

Итог 1) высокая степень надёжности рез-та ускоренных методов, простота и практичность

Спасибо за внимание