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

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

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

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

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

Модель подвижного состава

Вид перевозимого груза

1

2, 4,5

2

1,3,5

R

1,2,1

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

'S4V. 1 Г

1

2

3

4

5

L

1

1

1

1

2

1

1

1

R

1

1

1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • [1] Для случая перевозок больших объемов массовых грузов округление значений переменных ys до целых не будет приводить к существеннымпогрешностям.
  • [2] В общем случае формула определения числа возможных путей следования равна (В -1)!
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >