Оптимальное планирование кольцевых маршрутов с ограничениями на время движения транспортных средств

Формулировка задачи. Задача оптимального планирования в данном случае заключается в отыскании такого маршрута объезда п пунктов посещения, при котором охватывались бы все пункты, не один не посещался дважды и стоимость которого была минимальной. При этом, в отличие от задачи, сформулированной в п. 9.3, необходимо учесть временные ограничения, накладываемые на маршрут объезда продолжительностью рабочего дня. Типичной является ситуация, когда для объезда всех пунктов посещения по схеме коммивояжера и проведения погрузочно-разгрузочных работ (ПРР) потребуется время, большее чем продолжительность рабочего дня. Поэтому маршрут должен быть наилучшим образом разбит на несколько рейсов. Каждый рейс представляет собой участок маршрута, на котором транспортное средство объезжает несколько пунктов и возвращается в исходный пункт отправления, укладываясь по времени в заданную продолжительность рабочего дня.

Исходными данными к этой задаче являются:

  • • матрица (9.23) стоимости перевозок между пунктами назначения и отправления;
  • • матрица, затрачиваемых на перевозку временных ресурсов

где T.j — время, затрачиваемое на проезд между i-м и j-м пунктами назначения, диагональные элементы Ти матрицы Т характеризуют время выполнения погрузо-разгрузочных работ в i-м пункте назначения, элемент Т00 полагаем равным нулю. Матрица (9.37) может быть как симметрической, так и несимметрической.

Время на перевозку можно определить по средней скорости v движения ТС либо вводом в программу на основании статистических данных. Для оценки времени разгрузки (в задаче вывоза) или погрузки (в задаче завоза) может быть использована формула:

где inpp — среднее время разгрузки одной тонны груза, мин/т; Qt — масса груза для i-ro получателя, т; tQ — время на оформление документов.

Для того чтобы решение данной задачи существовало, необходимы выполнение условия (9.24) грузовместимости и для каждого пункта назначения выполнение условия

гарантирующего возможность доставки груза за заданное время Тр (например, 8 ч) с помощью простейшего одноточечного маршрута «туда и обратно».

Решение задачи характеризуется параметрами:

  • k — количество рейсов^ необходимое для выполнения всего плана перевозки;
  • • Цр ц2, ...,1^-, ..., .k — количество пунктов назначения, запланированных для каждого рейса;
  • • номера получателей

включенных в у'-й рейс и порядок их объезда.

В выражении (9.40) параметр Vf означает номер получателя, объезжаемого f-ш по порядку на ;-м рейсе. Для каждого из рейсов начальным и конечным пунктом назначения

является общий пункт отправления. Всю введенную нами совокупность параметров

назовем планом (маршрутом) перевозки. Параметры плана должны удовлетворять условиям:

которые означают объезд всех пунктов назначения; все числа — номера пунктов посещения, входящие в формулу (9.41), — должны быть различными.

Время, затрачиваемое на перевозку j-ш рейсом,

а время, затрачиваемое на ПРР, определяется выражением

Необходимо, чтобы сумма выражений (9.44) и (9.45) для каждого рейса не превосходила заданного ресурса

Целевая функция

характеризует стоимость плана перевозки.

Необходимо найти параметры плана (9.41), обращающие в минимум целевую функцию (9.47), при ограничениях (9.41), (9.43) и (9.46).

Оптимальный план имеет наглядную геометрическую иллюстрацию. Необходимо разделить п точек плоскости на группы, соединив каждую точку группы линией — маршрутом объезда (для данного рейса). Построенный план напоминает k-лепестковый цветок, построенный из начала координат. Каждый лепесток соответствует определенному рейсу.

Модель оптимизации. Дополним параметр состояния п. 9.3 введением дополнительной переменной — временною ресурса. Для каждого промежуточного k-vo шага и узла i Ф 0 определим параметр состояния двумя переменными:

где i{1, ..., п) — номер узла, из которого на данном шаге начинается движение, t е {0, 1, 2, ..., Гдгв8} — остаточный ресурс (до истечения ресурса Тр = 8 ч), которым располагает транспортное средство, начиная движение из i-го узла. Будем измерять остаточный ресурс дискретными величинами. При этом непрерывной переменной

соответствует дискретное значение времени с заранее выбранным шагом дискретизации по времени At. Здесь величина Тд res показывает, на сколько шагов дискретизации разбивается имеющийся ресурс. Непрерывные и дискретные величины будут обозначаться одними и теми же символами.

На k-м шаге движение может начаться из исходного пункта. В этом случае вводим параметр состояния

На k-м шаге из состояния S формируется маршрут вида (9.29), где в отличие от задачи п. 9.3 промежуточные узлы ik _ v ..., ix могут включать один или несколько нулевых узлов.

Воспользуемся тем же подходом, основанным на упорядочении целевой функции и запоминании L кратчайших маршрутов. Уравнения для ЦФ r-го ранга на k-м шаге из состояния S Ф S0 имеет вид

где minr{...} означает, как и в выражении (9.31), r-е наименьшее значение последовательности, заключенной в фигурные скобки. Члены последовательности формируются путем перебора по переменным X = (/, v) [см. пояснения к (9.31)], / = 1, 2, ..., п, v = 1, 2, ..., L. Здесь слагаемое

I

означает стоимость маршрута, исходящего из узла f (в который просматривается возможность перехода) с измененным значением временного ресурса

Временной ресурс изменен на время движения по направлению i —> / и погрузо-разгрузочные работы в /-м узле. Элементы последовательности

означают стоимость возврата в исходный пункт с учетом присоединения к дуге i —> 0 маршрута (S0) ранга v, исходящего из

нулевого узла. Переход i —» 0 означает в процессе поиска плана окончание рейса.

При поиске минимумов в выражении (9.50) принимаются во внимание лишь те значения переменных X, при которых выполняются условия

исключающие повторный заезд в i-й узел. Кроме того, все маршруты Mrk , формирующие множество запоминаемых маршрутов, должны различаться между собой. Слагаемые (9.51) в выражении (9.50) учитываются лишь при значениях временноуго ресурса

достаточного для завоза груза в /-й узел. Аналогично элемент (9.53) оптимизируемой последовательности учитывается при условии t > TiQ. В противном случае значения целевой функции (9.50) полагаются равными бесконечности. Отметим, что в силу этого свойства конечное значение целевой функции мы фактически получим при временном ресурсе

Найденный согласно выражению (9.50) оптимальный маршрут определяется путем присоединения к уже найденному (k - ^-шаговому маршруту (припасовывание) нового отрезка

Здесь параметры Xopt = (/opt, uopt) — оптимальные значения переменных /, V.

Для начального состояния SQ на k-м шаге уравнения ЦФ имеют виды

где переменная оптимизации X = (/, v) принимает те же значения, что и в выражении (9.51).

Найденный из состояния SQ оптимальный маршрут г-го ранга записывается следующим образом:

Эта операция означает формирование начала рейса. Начальные условия для процедуры оптимизации определяются при k = 1. Все начальные значения г-х целевых функций равны бесконечности, за исключением ЦФ первого ранга:

Решение осуществляется за k = 2п шагов. Это позволяет учесть тот случай, когда в силу временных ограничений для объезда каждого пункта требуется отдельный рейс. Как правило, решение включает меньшее чем п число рейсов. При значении k > п + 1 начинается поиск оптимальных маршрутов. Для этого проводится проверка на допустимость маршрутам* (0) — самого короткого из замкнутых рейсов, исходящих из нулевого узла.

Это делается путем подсчета количества нулей г0 в маршруте. Если rQ = k - п, то маршрут допустимый и охватывает все пункты назначения. Этот маршрут и соответствующее значение ЦФ (S0) запоминается и используется для сравнения с аналогичными маршрутами, находимыми на следующих шагах. При k = 2п поиск прекращается. Найденный последним маршрут является оптимальным маршрутом объезда п пунктов назначения с учетом ограничений по времени.

Примеры оптимальных кольцевых маршрутов с ограничениями на время рейса. Реализации 1-4

Рис. 9.8. Примеры оптимальных кольцевых маршрутов с ограничениями на время рейса. Реализации 1-4

Разработка программы и примеры. На основе описанного алгоритма на языке «Turbo Pascal» была разработана программа нахождения оптимального кольцево-

го маршрута объезда с учетом ограничений по времени. Временной ресурс Тр = 8 ч, шаг дискретизации At = 1 ч. На рис. 9.8 приведены примеры найденных программой маршрутов. Маршруты найдены для случая п = 6 пунктов назначения. Координаты пунктов назначения разыграны случайным образом на квадрате со стороной [- а, а], а = 100 км. Центр квадрата совпадал с распределительным центром. Представлено четыре плана для четырех, отмеченных цифрами, вариантов (реализаций) расположения пунктов назначения. Во всех случаях объезд всех пунктов одним кольцевым маршрутом оказался невозможным, поскольку потребовалось бы значительно большее время, чем располагаемый ресурс.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >