Экономико-математические модели задачи маршрутизации

Рассмотрим три постановки маршрутизации, формулируемые как общая задача линейного программирования.

Первая постановка [18]. Она рассмотрена в предыдущем параграфе и представляет собой получение допустимых комбинаций маршрутов без привязки их к автотранспортным предприятиям. Условно назовем эту постановку «кольцевая маршрутизация» (условность объясняется тем, что маршруты в общем случае могут быть и не кольцевыми, но это не влияет ни на постановку, ни на модель, ни на методы ее решения).

Как уже показано ранее, под допустимостью понимается соблюдение выдвигаемых требованиями практики ограничений. В первую очередь к ним относятся следующие ограничения:

• • по протяженности маршрутов L_s: она может быть выражена и через время пребывания автомобиля в наряде Г_н; при этом учитывается время пребывания подвижного состава в пунктах Л и В. под погрузкой и разгрузкой
• • по звенности маршрутов By. иногда это зависит от конкретных условий, в которых решается задача; тогда первое ограничение является более общим и исключает второе;
• • по количеству груза, потребному к перевозке из пунктов погрузки в пункты разгрузки, хр
• • по наличию автомобилей в местах их размещения;

• по соответствию 1-видов перевозимых грузов г-модели подвижно состава: эта зависимость может быть выражена двояким образом: либо таблично, например второй, четвертый и пятый виды грузов перевозятся на первой модели подвижного состава, либо матрично в виде матрицы ||a_r|. ||_R, соответствия с элементами a_d = {1, 0}, где единица показывает, что /-груз может быть перевезен на r-модели подвижного состава, нуль — /-груз на r-модели перевозиться не может;

• • по пропускной способности пунктов погрузки, разгрузки и размещения подвижного состава: пропускная способность зависит как от вида транспортируемого груза и моделей подвижного состава, так и от конкретных условий, в которых осуществляется перевозочный процесс (например, оснащенность в механизмах пунктов погрузки и разгрузки);
• • по времени доставки грузов в пункты разгрузки и отправления грузов в пунктах погрузки: иногда это ограничение можно выразить через величины пропускных способностей у потребителей и поставщиков.

Иногда реальные ситуации выдвигают ограничения, которые определяются сложившейся организацией перевозочного процесса и заданной структурой принятия решений. К ним могут относиться, например, ограничения по допустимой нижней границе коэффициента использования пробега на получаемых комбинациях маршрутов, по обязательному вывозу определенного объема груза из пунктов погрузки, по учету количества прикрепленного к нему подвижного состава и т. п. Такие ограничения можно отнести к числу преходящих, субъективных, временных, которые по мере совершенствования планирования, организации и управления процесса перевозки грузов исчезают и перестают быть обязательными. Тем не менее в некоторых случаях учет подобных ограничений обязателен и необходим; без них практическая задача становится неосуществимой и нереальной.

Вернемся к первой постановке. Должны быть заданы объемы потребных к перевозке грузов от А_;-пунктов погрузки в^{.-пункты} разгрузки, {х^.}, число линий равно Q_t(t = 1: х); обозначим грузопотоки индексом t, x_t (t = 1: х). Известна матрица расстояний пробегов без груза от В₍-пунктов разгрузки до Д.-пунктов погрузки, |4-|_nm; значит, могут быть рассчитаны издержки, доходы, прибыль, коэффициент использования пробега на маршрутах, т. е. любой необходимый коэффициент (как в стоимостной, так и в натуральной формах) линейного уравнения целевой функции.

Считаем, что известны технические скорости движения автомобилей с грузом и без груза, время простоя подвижного состава под погрузкой-разгрузкой; заданы и такие ограничения, как время пребывания автомобиля на линии и некоторые другие. Пусть {s = 1: JV} — множество номеров допустимых комбинаций маршрутов. Процесс формирования и способы получения этого множества будут показаны в дальнейшем. Необходимо, достигая оптимального значения заданной целевой функции, перевезти по маршрутам предъявленный к поставке план {х^}.

В общем виде маршрут движения транспорта запишем как последовательность определенным образом соединенных друг с другом грузопотоков (линий) х₍:

Пусть y_s — искомая интенсивность на s-маршруте или грузопоток на s-маршруте, или количество автомобилей, работающих на s-маршруте; a_[s — коэффициенты выпуска, показывающие, какое количество t-груза перевозится (или выпускается), если s-маршрут имеет единичную интенсивностьy_s = 1; c_s — критерии оптимальности использования с единичной интенсивностью s-маршрута. Тогда запишем постановку задачи кольцевой маршрутизации:

где N — множество допустимых маршрутов.

Равенства показывают, что любой из предъявленных к перевозке грузов будет доставлен из пунктов А. в пункты В. в требуемом объеме.

Если требование постановки грузов в объеме не является строго обязательным, то равенства (4.38) могут быть заменены следующими формулами:

Очевидно, соотношения материального баланса могут быть выражены как неравенствами, так и равенствами.

Граничные условия:

т.е. целевая функция, где с₍ — коэффициент эффективности использования s-маршрутов при транспортировании грузов х₍.

В результате решения задачи (4.38)—(4.40) получаем оптимальные (относительно выбранного для конкретной задачи критерия c_s) маршруты транспортирования грузов х₍.

Данная постановка не нуждается в иллюстрации на условном примере, так как в предыдущем параграфе достаточно подробно разобрана аналогичная задача.

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

Недостатками данной постановки являются:

• • возможность получения нецелочисленного решения, т. е. интенсивности технологических способов у_$ > 0 могут принимать значения, не равные целым числам; в случае, если переменные выражаются, например, в автомобилях, получение не целых чисел равносильно невозможности использовать оптимальное решение на практике. Так, число y_s = 2,43 свидетельствует о том, что на s-маршруте необходимо иметь 2,43 автомобиля. Очевидно, что в подобных случаях округление чисел до целых будет приводить к погрешностям в расчетах^[1] и значительным отклонениям от оптимального варианта; в дальнейшем будет разработан метод достижения целочисленного решения;
• • существенно большее число переменных задач, т. е. количество маршрутов в общем случае может быть весьма значительным: для данной постановки возможное число комбинаций маршрутов равно

где к — заданное число линий x_t или соотношений материального баланса; В — звенность s-маршрутов; область допустимых маршрутов N, как правило, несколько меньше, чем область возможных комбинаций N < N, при этом чем больше ограничений, выдвигаемых практикой, тем меньше число N, но все равно выражать матрицу коэффициентов «затрат-выпуска» в явном виде не представляется возможным, поэтому требуется разработка методов, учитывающих матричную структуру задачи: ее разреженность (число положительных a_ts > 0 крайне мало) и вытянутость (число столбцов матрицы значительно больше, чем количество строк: N > к); в дальнейшем будут описаны некоторые из методов решения задач именно с такой структурой;

• неполнота постановки, так как при формировании маршрутов учитываются только пробеги автомобилей без груза, и полученные оптимальные маршруты еще требуется прикрепить к автотранспортным предприятиям. Это приводит к необходимости решений единой (по информационным, технологическим, организационно-управленческим принципам) задачи в два изолированных этапа, причем на каждом из этапов достигается цель по собственному критерию оптимальности.

Вторая постановка [1]. Назовем ее маршрутизацией с учетом ограничения подвижного состава на автотранспортных предприятиях или маршрутизацией с прикреплением к автотранспортным предприятиям.

Полагаем заданными грузопотоки х₍ (t = 1: к). Они, как и в предыдущей постановке, могут быть либо заданы, либо получены предварительным решением ряда транспортных задач: закрепление потребителей за поставщиками; матрица расстояний пробегов без груза от Bj.-пунктов разгрузки до Д.-пунктов погрузки, ||Д||_пт; пункты размещения подвижного состава D_k (к = 1: р) с имеющимися транспортными средствами, количество которых может быть выражено через d_k (в случае, если в D^-автотранспортном предприятии имеется R-типов подвижного состава, то такой П_/(-пункт условно разбиваем на Л-пунктов, в каждом из которых будет находиться только один определенный тип подвижного состава); матрицы расстояний от П,.-автотранспортных предприятий до Д-пунктов погрузки, ||c_fcl||_pm — первый нулевой пробег от В-пунктов разгрузки до ВДавтотранспортных предприятий, ||с_;*||_пр —второй нулевой пробег; кроме того, считаем известными технические скорости движения подвижного состава с грузом и без груза, время простоя автомобилей под погрузкой и разгрузкой в пунктах Д и Bj, время пребывания подвижного состава на линии и ряд других параметров.

Теперь можно в общем виде записать постановку задачи маршрутизации с учетом ограничений подвижного состава на автотранспортных предприятиях.

Пусть необходимо найти неотрицательные интенсивности маршрутов транспортировки грузов:

Если удовлетворяются ограничения на имеющийся парк подвижного состава в автотранспортных предприятиях D_k, то.

Если заявленный к перевозке груз из пунктов Д и В. доставлен в требуемом количестве х₍, то.

и достигается оптимальное значение линейной целевой функции.

где c_s — количественный показатель использования s-маршрута с искомой интенсивностьюy_s.

Необходимо помнить, что при определении коэффициентов линейной формы c_s возможны различные пути объезда пунктов (а оттуда и различные размеры затрат), входящих в s-маршрут, для случая, когда B_s> 3. Тогда находим минимальный путь следования автомобиля по s-маршруту (это необходимо и для случаев, когда в качестве показателя с_$ принимаем и стоимостные показатели). Пусть имеем маршрут, состоящий из трех линий (В = 3) и началом в пункте погрузки А_;, в который автомобиль подается из автотранспортного предприятия D_y

Возможны два пути следования (движение автомобиля показано стрелками):

• первый (рис. 4.12), где величина порожнего пробега равна.

• второй (рис. 4.13), где порожний пробег равен.

Теперь для определения окончательного варианта движения автомобиля по данному маршруту выбираем min (с_х; с₂). Очевидно, что для случая В = 4^[2] необходимо выбирать уже из шести возможных путей объезда.

Третья постановка. Рассмотрим комплексную линейную модель оптимизации перевозки грузов автомобильным транспортом или комплексную маршрутизацию. Объясним смысл такого названия. Как было установлено ранее и как это принято при сложившейся организации управления и планирования перевозочного процесса, решению о маршрутизации предшествует (или может предшествовать) задача закрепления потребителей однородного (и взаимозаменяемого) груза за поставщиками. В результате закрепления, как правило, осуществляемого сбытовыми организациями, получаем потребный объем перевозок грузов х₍. от А-пунктов погрузки в В₍.-пункты разгрузки, обозначаемые как грузопотоки или линии x_t.

Знание величины x_t является исходной информацией для решения задачи кольцевой маршрутизации, а если, кроме этого, заданы ограничения на наличие подвижного состава d_k в пунктах их размещения D_k, то может быть поставлена задача маршрутизации с прикреплением маршрутов к автотранспортным предприятиям.

Рис. 4.12. Путь следования 1.

Рис. 4.13. Путь следования 2.

Последовательное, поэтапное и изолированное решение задач оптимизации потоков и маршрутизации, хотя на каждом этапе при этом и достигается наилучший вариант, как уже указывалось, не гарантирует получения общего оптимума при совместном функционировании транспортных и обслуживаемых организаций. Первая попытка (описанная в работе [20]) решения подобной проблемы, сведенной при ее формулировке к постановке транспортной задачи линейного программирования, позволяла комплексно решать единую задачу закрепления и маршрутизации. Но в данной постановке невозможно учесть ряд практических ограничений, а это является наиболее существенным недостатком. До настоящего времени не удалось формализовать процесс формирования комбинаций маршрутов, что не позволяет на всех стадиях планирования использовать средства современной вычислительной техники.

В работе [15] была предложена комплексная линейная модель оптимизации поставок грузов на автомобильном транспорте, постановка которой и позволяет решать задачи транспортной логистики. Считаем заданными:

• • объемы поставок грузов в А.-пунктах погрузки, обозначим их через a_f(i = 1: т), в случае если А,-поставщик отпускает не один, а L видов грузов, такой пункт условно разбиваем на L пунктов таким образом, чтобы любой А₍.-пункт отгружал только один вид продукции;
• • объемы потребления грузов в В^пунктах разгрузки, обозначим их через Ь.(/ = 1: п);
• • количество ходового подвижного состава в пунктах их размещения D_k, обозначим через d_k(k = 1: р); в случае если в D^-автотранспортном предприятии имеется не один, а R-типов подвижного состава, то такой пункт условно разбиваем на R-пунктов так, чтобы каждое D (.-автотранспортное предприятие выпускало на линию только один тип автомобилей;
• • матрицы кратчайших расстояний между пунктами поставок грузов А₍. и пунктами их потребления — 11 с~ тп (расстояния пробегов с грузом); между R-пунктами разгрузки и Д.-пунктами погрузки — ||^cj’t||_nm (расстояния пробегов без груза); между Д-пунктами разгрузки и Г^-автотранспортными предприятиями — Ы|_пр (расстояния вторых нулевых пробегов); между D^-автотранспортными предприятиями и А₍-пунктами погрузки— Ik;llpm (расстояния первых нулевых пробегов); tp t' — время простоя под погрузкой и разгрузкой в пунктах А₍ и В, при этом учитывается, какой вид груза и тип подвижного состава из автотранспортного предприятия находится под погрузкой-разгрузкой; время пребывания автомобиля на линии Т_н и т. д., т. е. практически все возможные ограничения, возникающие при планировании транспортно-логистических систем.

Теперь не представляет сложности в общем виде формулировать постановку комплексной задачи маршрутизации. Пусть необходимо найти неотрицательные интенсивности допустимых маршрутов транспортировки грузов.

чтобы удовлетворялись соотношения материального баланса:

• на ходовой парк подвижного состава в автотранспортных предприятиях D_k

• на заявленный к поставке груз в пунктах погрузки А_;

• на потребный к доставке груз в пункты разгрузки В.

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

где с. — количественный показатель эффективности s-маршрута с единичной интенсивностью.

Необходимо заметить, что в общем случае коэффициенты выпуска d_b, a_js, Ь., показывающие, сколько используется ресурсов из пунктов D_k, А₍, В- при реализации с единичной интенсивностью технологического способа s, зависят не только от числа заездов подвижного состава в пункты D_k, А₍, В., но и от грузоподъемности используемого на s-маршруте подвижного состава, от использования грузоподъемности автомобиля.

Постановка комплексной задачи планирования перевозочного процесса позволяет:

• • учесть практически все ограничения, возникающие при оперативном планировании работы автомобильного транспорта;
• • решать единую комплексную задачу по единому критерию оптимальности. При этом возможно использовать в качестве критерия любой показатель работы автомобильного транспорта, как стоимостный, так и натуральный: прибыль, общий пробег автомобиля, издержки, время простоя под погрузкойразгрузкой и др.;
• • решая общую задачу линейного программирования, находить не только оптимальное решение, но и получать значительный объем дополнительной объективной информации (двойственные оценки ресурсов в пунктах D_k, А_р Bj), в основном связанной с выявлением узких мест производства (дефицит подвижного состава, недостаточная пропускная способность погрузочно-разгрузочных механизмов и пр.). Кроме количественной информации, решение позволяет определить, с какой величиной потерь связано наличие таких узких мест;
• • решить задачу рационального распределения подвижного состава (из числа имеющихся) по маршрутам при оперативном планировании перевозок грузов [12].

Сфера оперативного планирования автотранспорта ограничивается нулевыми пробегами и пробегами без груза, в то время как пробег автомобиля с грузом зависит от качества планирования в сбытовых организациях, что часто приводит к нерациональному использованию подвижного состава, усложненнему прохождению необходимой информации, столкновению интересов автотранспортных и сбытовых организаций.

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

• [1] Для случая перевозок больших объемов массовых грузов округление значений переменных ys до целых не будет приводить к существеннымпогрешностям.
• [2] В общем случае формула определения числа возможных путей следования равна (В -1)!