View of Optimizing unbalanced freight deliveries in transportation networks

УДК 656.073.7:519.852.33

DOI: 10.15587/1729-4061.2022.253791

Оптимизация несбалансированных грузовых перевозок на транспортных сетях

Г. С. Прокудин, А. А. Чупайленко, Т. Г. Хоботня, І. А. Ремех, А. А. Лямзин, М. С. Коваленко

Проведено порівняльний аналіз відомих методів приведення відкритих транспортних завдань до збалансованого виду з метою подальшої оптимізації вантажних перевезень. В них виявлено ряд істотних недоліків, які значною мі- рою звужують область їх використання. Запропоновано новий метод, назва- ний методом пропорційного перерозподілу обсягів перевезень вантажу між учасниками перевізного процесу, позбавлений виявлених недоліків.

Транспортна задача є окремим випадком загальної задачі лінійного про- грамування, до якої може бути застосовний один із методів її вирішення, а са- ме симплексний. Описано методику побудови симплексної таблиці на основі даних транспортної таблиці та алгоритм подальших симплекс-перетворень.

Найчастіше транспортне завдання задається у вигляді картосхеми роз- ташування транспортних вузлів відправлення та призначення вантажу. За- пропонована матрично-сітьова модель дозволяє звести сітьове уявлення до матричного вигляду з подальшим знаходженням оптимального плану переве- зень вантажу.

З метою виявлення пріоритетності методів зведення відкритих транспо- ртних завдань до збалансованого виду було вирішено 100 незбалансованих за обсягом перевезень вантажу транспортних задач. Це було здійснено за допо- могою спроектованої системи підтримки прийняття рішень з управління ван- тажними перевезеннями. У якості критерія обирався найкращий план ванта- жних перевезень. В результаті в 48 випадках кращим виявився симплексний метод, метод коефіцієнтів у 27, метод фіктивного вузла у 16 і різницевий ме- тод у 9 випадках. Використання системи підтримки прийняття рішень з управління вантажними перевезеннями дозволило підвищити ефективність у середньому на 25 %.

Ключові слова: транспортна сіть, оптимізація, фіктивний вузол, різнице- вий, коефіцієнтний, симплексний, прийняття рішень.

1. Введение

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

Not

a reprint

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

Также следует отметить то обстоятельство, что все известные и широко используемые на практике методы оптимизации грузовых перевозок применя- ются исключительно для матричной модели их представления, т.е. когда ис- ходные данные ТЗ сведены в транспортную таблицу (ТТ). А это, в свою оче- редь, предполагает сведение сетевого представления ТЗ к еѐ матричному виду, т.к. зачастую ТЗ на практике задаѐтся в виде картосхемы расположения транс- портных узлов отправления и назначения груза, т.е. в виде транспортной сети (ТС). Предварительным этапом в этом процессе является построение матрицы корреспонденций между всеми участниками транспортного процесса – постав- щиками и потребителями груза.

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

2. Анализ литературных данных и постановка проблемы

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

При этом процедура решения ТЗ состоит из следующих этапов:

– 1 этап: математическая формулировка ТЗ;

– 2 этап: поиск начального базового допустимого решения;

– 3 этап: оптимизация исходного базового допустимого решения, получен- ного на втором этапе.

В работе [1] предлагается новый подход к нахождению начального базово- го допустимого решения ТЗ. Он основан на совместном учѐте суммарных за- трат на перевозки грузов по строкам и столбцам ТТ. В качестве штрафов здесь могут выступать либо стоимость перевозки единицы груза, либо расстояние, либо время преодоления этого расстояния между ПО и ПН грузов. Сравнительное ис- следование на ряде ТЗ показывает, что новый подход обеспечивает такое же или лучшее начальное возможное решение, по сравнению с рядом существующих.

Перечисленная выше процедура решения ТЗ не учитывает одного суще- ственного условия, которое часто встречается на практике, а именно, несбалан- сированности объѐмов перевозки груза. В этом случае после первого этапа

For

reading

only

необходимо осуществлять дополнительный этап сведения несбалансированной по объѐмам перевозки груза ТЗ к закрытому виду.

Недавно, для решения сбалансированных ТЗ, были разработаны взвешен- ные алгоритмы альтернативной стоимости [2], особенность которых заключа- ется во введении спроса и предложения в виде весовых коэффициентов для контроля за потоками грузов. Эти алгоритмы не применимы для несбалансиро- ванных ТЗ при их балансировании с нулевой фиктивной стоимостью транспорти- ровки, как это делается в существующих классических подходах. Предлагается модифицированный динамически обновляемый взвешенный алгоритм на основе альтернативной стоимости [3], встроенный в метод наименьших затрат, который подходит как для сбалансированных, так и для несбалансированных TЗ.

В исследовании [4] описываются два наиболее известных метода сведения открытых ТЗ к сбалансированному виду:

– 1 метод: ввод дополнительного (фиктивного) пункта отправления (назна- чения) груза;

– 2 метод: уменьшение объема предложения (спроса) на величину несоот- ветствия у одного из ПО (ПН).

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

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

В работе [5] рассмотрены вопросы нахождения оптимальных планов гру- зовых перевозок с помощью линейного программирования и электронных таб- лиц, причѐм это рассмотрение носит сугубо экономический характер. Также в исследовании не раскрывается сущность математического аппарата преобразо- вания ТЗ к задаче линейного программирования и последующего нахождения оптимального плана грузовых перевозок.

В управлении конечной целью является принятие правильного решения лицом, которое принимает это решение (ЛПР), в тот момент, когда параметры транспортировки грузов неопределенны из-за глобализации и других неконтро- лируемых факторов. В исследовании [6] задача линейного программирования решается с использованием нечеткой линейной функции принадлежности, где верхнее и нижнее значения целей являются желаемыми целями. Однако в от- дельных случаях получаемые результаты не удовлетворяют ЛПР. Эта проблема может быть решена путѐм разработки соответствующей методики использова- ния симплексного метода, который может эффективно находить оптимальные планы грузовых перевозок как открытых, так и закрытых ТЗ.

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

Not

a reprint

работе [7] рассмотрены ТС, где каждый уровень связан с отдельной транспорт- ной системой, и показано, как меняется распределение трафика при настройке этого параметра по уровням. Модель прокладывает путь для дальнейшего ана- лиза оптимальных потоков и стратегий навигации в реальных многоуровневых сетях. Однако в исследовании рассмотрены только сбалансированные грузовые перевозки.

В исследовании [8] разработана модификация метода муравьиного алго- ритма для оптимизации маршрута перевозки с учетом транспортного потока на ТС. Предложенная модификация муравьиного алгоритма оптимизации маршру- та доставки грузов при изменении скорости транспортного потока на конкрет- ных участках ТС апробирована на примере конкретной уличной сети в задаче коммивояжѐра. Проведен количественный и сравнительный анализ решения за- дачи оптимизации маршрута доставки грузов в ТС с применением метода му- равьиного алгоритма и соответствующих результатов других существующих классических методов. Полученные результаты исследования показывают пер- спективность применения предложенной модификации муравьиного алгоритма для решения задач маршрутизации, в частности, для ТС, характеризующихся вы- сокой размерностью и динамичностью функциональных параметров. Это может быть решено за счѐт разработки системы поддержки принятия решений по управ- лению грузовыми перевозками на транспортных сетях, которая базируются на ис- пользовании современных средств информационных технологий [9].

3. Цели и задачи исследования

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

Для достижения поставленной цели необходимо решение следующих задач:

– разработать новый метод пропорционального перераспределения объе- мов перевозок груза между участниками перевозочного процесса для несбалан- сированных грузовых перевозок;

– усовершенствовать методику использования симплексного метода для нахождения оптимального плана грузовых перевозок;

– разработать технологию формирования матрично-сетевой модели опти- мизации несбалансированных грузовых перевозок на транспортных сетях;

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

4. Материалы и методы исследования

Объектом исследования является процесс несбалансированных грузовых перевозок на транспортных сетях.

Основной гипотезой исследования является предположение о том, что для повышения эффективности несбалансированных грузовых перевозок необходимо

For

reading

only

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

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

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

В результате теоретических исследований была разработано программное обеспечение спроектированной системы поддержки принятия решений по управлению грузовыми привозками на транспортных сетях. Программное обес- печение прошло экспериментальную проверку на реальных данных производ- ственной деятельности ряда автотранспортных предприятий ассоциации меж- дународных автомобильных перевозчиков Украины.

Полученные экспериментальные данные во многих случаях совпали с ре- зультатами производственной деятельности автотранспортных предприятий, участвующих в эксперименте, а в отдельных случаях показали лучший результат.

Всѐ это свидетельствует об адекватности предложенных моделей и методов.

5. Результати исследования процесса оптимизации несбалансирован- ных грузовых перевозок на транспортных сетях

5. 1. Коэффициентный метод сведения несбалансированных грузовых перевозок к сбалансированному виду

По определению ТЗ из m пунктов отправления (ПО) A1, A2, … , Am, в кото- рых сосредоточены запасы однородного груза в количествах, соответственно, a1, a2, … , am единиц, необходимо перевезти этот груз в n пунктов назначения (ПН) B1, B2, … , Bn в соответствии с поступившими от них заявками на b1, b2, … , bn единиц. Также предполагается, что сумма всех заявок равняется сумме всех запасов, а именно:

1 1

.

m n

i j

i j

a b

 





Матрица (таблица) стоимостей перевозок единицы груза между каждым ПО и каждым ПН задается следующим образом:

1 1 1 2 1

2 1 2 2 2

1 2

.

n

n

m m m n

с с с

c c c

c c c

(2)

Not

a reprint

А матрица (таблица) соответствующих объемов перевозок имеет следую- щий вид:

1 1 1 2 1

2 1 2 2 2

1 2

,

n

n

m m m n

x x x

x x x

x x x

(3)

где cij – стоимость перевозки единицы груза из Ai в Bj, a xij – количество груза, перевозимое из Ai в Bj.

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

Z=c11×x11+c12×x12+...+cmn×xmn=>min. (4) ТЗ, которая отвечает условию (1), называется закрытой или сбалансиро- ванной ТЗ.

Существуют два наиболее известных метода сведения открытых ТЗ к сба- лансированному виду, а именно: ввод дополнительного (фиктивного) ПО (ПН) груза – метод фиктивного узла; уменьшение объема предложения (спроса) на величину несоответствия у одного из ПО (ПН) – разностный метод.

Первый метод имеет два варианта применения, а именно, в первом вариан- те когда

1 1

,

m n

i j

i j

a b

 





1 1

.

m n

n i j

i j

b _ a b

 







пользуется, если

1 1

,

n m

j i

j i

b a

 





1 1

.

n m

m j i

j i

a _ b a

 







При этом в матрице стоимостей появляется, соответственно, либо допол- нительный столбец, либо дополнительная строка, всем елементам которых при- сваиваются нулевые стоимости перевозок.

ТЗ становится сбалансированной в случае ввода дополнительного ПН, но при этом частично или полностью не вывозится груз у отдельных ПО. ТЗ ста- новится также сбалансированной при вводе дополнительного ПО, но при этом частично или полностью не удовлетворяются заявки на получение груза неко- торыми ПН.

For

reading

only

Во втором методе, для приведения ТЗ к сбалансированному виду, модуль разности

1 1

| |

m n

i j

i j

a b

 





1 1

п р и ,

m n

i j

i j

a b

 

 

  



 

наибольшее значение предложения, либо у ПН

1 1

п р и ,

n m

j i

j i

b a

 

 

  



 

1 1

.

m n

i j

i j

a b

 





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

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

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

1 1

,

m n

i j

i j

a b

 





считывается коэффициент уменьшения объемов предложения:

1 1

1

.

m n

i j

i j

a m

i i

a b

k

a

 







 



(5)

После этого объемы предложения грузов всех ПО (i=1,m) уменьшаются до величин ^a_i^^1k_a^a_i и задача становится сбалансированной с теми же объе- мами заявок bj (j=1,n) и той же размерностью ТЗ.

При превышении же спроса на груз над его предложением

1 1

,

n m

j i

j i

b a

 





рассчитывается соответствующий коэффициент уменьшения объемов спроса во всех ПН (j=1,n) следующим образом:

Not

a reprint

1 1

1

.

n m

j i

j i

b n

j j

b a

k

b

 







 



(6)

Затем эти объемы заявок уменьшаются до величин bj^*¹kb^*bj и ТЗ приобретает вид сбалансированной с теми же объемами запасов ai (i=1,m) и той же размерностью.

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

В качестве сравнительного анализа методов ниже рассмотрена ТЗ в виде трех заводов (ПО), выпускающих продукцию, распределяемую по четырем складам (ПН).

Также заданы затраты на перевозку единицы продукции от каждого завода к каждому складу (табл. 1). Необходимо минимизировать транспортные расхо- ды с условием того, что продукции требуется на 30 единиц больше, чем ее про- изводится. Для сравнения покажем применение всех перечисленных выше ме- тодов сведения ТЗ к закрытому виду.

Таблица 1

Исходная информация по транспортной задаче Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 10 8 9 10 80

№ 2 4 2 3 4 10

№ 3 3 4 5 4 50

Объемы заявок 20 50 40 60 140

170

Оптимизация грузовых перевозок в приведенной выше ТЗ в среде Excel будет иметь вид:

а) в случае фиктивного узла – ввода четвертого фиктивного завода (табл. 2);

б) в случае применения разностного метода – уменьшения объема самой большой заявки у четвѐртого склада (табл. 3);

в) в случае применения разностного метода – пропорционального умень- шения объема заявок всех складов (табл. 4);

г) в случае несбалансированности ТЗ (табл. 5).

For

reading

only

Таблица 2

Ввод четвертого фиктивного завода Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 0 41 39 0 80

№ 2 0 9 1 0 10

№ 3 20 0 0 30 50

№ 4 0 0 0 30 30

Объемы заявок

20 50 40 60

170 170

Транспортные затраты 880

Таблица 3

Уменьшение объема заявки у четвѐртого склада Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 0 22 40 18 80

№ 2 0 10 0 0 10

№ 3 20 18 0 12 50

Объемы заявок

20 50 40 30

140 140

Транспортные затраты 917

Таблица 4

Пропорциональное уменьшение объема заявок всех складов Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 0 15.41 32.94 31.65 80

№ 2 0 10.00 0 0 10

№ 3 16.47 15.77 0 17.76 50

Объемы заявок

16.47 41.18 32.94 49.41 140

140

Транспортные затраты 940

Лучший (минимальные транспортные затраты) результат показал метод фиктивного узла – 880 условных денежных единиц (у.д.е.), второй результат у разностного метода – 917 у.д.е., третий у коэффициентного метода – 940 у.д.е.

Самые большие транспортные затраты в 987 у.д.е. были получены после опти- мизации грузовых перевозок на несбалансированной ТЗ.

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

Not

a reprint

Таблица 5

Оптимизация грузовых перевозок при несбалансированном состоянии ТЗ Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 20 20 20 20 80

№ 2 0 3.33 3.33 3.33 10

№ 3 0 16.67 16.67 16.67 50

Объемы заявок

20 50 40 60 140

170

Транспортные затраты 987

5. 2. Методика использования симплексного метода для нахождения оптимального плана грузовых перевозок

Транспортная задача является частным случаем общей задачи линейного программирования (ОЗЛП), к которой может быть применим один из эффек- тивных методов решения ОЗЛП, а именно симплексный метод (СМ). Опишем разработанную методику использования СМ для нахождения оптимального плана грузовых перевозок.

Сначала транспортная таблица (ТТ), построенная на основании ТЗ из табл. 1, представляется в следующем виде (табл. 6).

Таблица 6

Транспортная таблица Склады

Заводы № 1 № 2 № 3 № 4 Объемы поставок

№ 1 10 8 9 10

x11 x12 x13 x14 80

№ 2 4 2 3 4

x21 x22 x23 x24 10

№ 3 3 4 5 4

x₃₁ x₃₂ x₃₃ x₃₄ 50 Объемы заявок

20 50 40 60

140 170

Примечание: где xij – это объем груза, перевозимого от i-го его поставщи- ка к j-му его потребителю.

Следующим шагом грузовые перевозки сводятся к виду системы линейных уравнений, при этом уравнения записываются отдельно по строкам и столбцам ТТ:

For

reading

only

1 1 1 2 1 3 1 4

2 1 2 2 2 3 2 4

3 1 3 2 3 3 3 4

1 1 2 1 3 1

1 2 2 2 3 2

1 3 2 3 3 3

1 4 2 4 3 4

8 0 , 1 0 , 5 0 , 2 0 , 5 0 , 4 0 , 6 0 .

x x x x

x x x x

x x x x

x x x

x x x

x x x

x x x

   



    



    

    



    



   



    



(7)

Далее производится замена переменных x11→x₁, x12→x₂, … , x34→x₁₂ и добавляются к каждому уравнению дополнительные базовые переменные x13, x14, x15, x16, x17, x18 и x19. А для того чтобы полученная система уравнений была линейно-независимой и, как следствие, имела единственное решение, отбрасы- вается одно, например, последнее уравнение:

1 2 3 4

5 6 7 8

9 1 0 1 1 1 2

1 5 9

2 6 1 0

3 7 1 1

8 0 , 1 0 , 5 0 , 2 0 , 5 0 , 4 0 .

x x x x

x x x x

x x x x

x x x

x x x

x x x

    



     



     

    



    

    



(8)

Далее формируется первая симплексная таблица (СТ), которая приспосаб- ливается к листу таблицы Excel (рис. 1).

Рис. 1. Начальная симплексная таблица

После выполнения шести симплекс-преобразований получается результи- рующая СТ (рис. 2).

Полученный в результирующей СТ оптимальный план перевозок грузов переносится в ТТ (табл. 7).

Not

a reprint

Рис. 2. Результирующая симплексная таблица Таблица 7

Оптимальный план перевозок грузов в транспортной таблице Склады

Заводы

№ 1

№ 2

№

3 № 4 Объемы по-

ставок

№ 1

10 8 9 10

80 x2=

40

x3= 40

№ 2

4 2 3 4

10 x6=

10

№ 3

3 4 5 4

50 x9=

20

x12= 30 Объемы за-

явок 20 50 40 60

140 170

Транспортные затраты оптимального плана грузовых перевозок, получен- ного с помощью СМ на несбалансированной ТЗ, составляют 880 у.д.е. Это яв- ляется лучшим результатом из всех значений оптимальных планов, которые были получены после сведения несбалансированной ТЗ к сбалансированному виду изыми вышеприведѐнными методами.

Из этого можно сделать вывод о том, что усовершенствованная методика использования СМ метода для нахождения оптимального плана грузовых пере- возок может эффективно применяться и к несбалансированным ТЗ.

Экспериментальная апробация методики использования симплексного ме- тода для нахождения оптимального плана грузовых перевозок подтвердила эф- фективность еѐ применения в половине случаев (48 случаев из 100).

5. 3. Технология формирования матрично-сетевой модели оптимиза- ции несбалансированных грузовых перевозок на транспортных сетях

Зачастую ТЗ задаѐтся в виде картосхемы расположения транспортных уз- лов отправления и назначения груза. Ниже рассмотрена разработанная техноло- гия формирования матрично-сетевой модели (МСМ) оптимизации несбаланси- рованных грузовых перевозок на ТС, которая позволяет свести сетевое пред-

For

reading

only

ставление до матричного виду с последующим нахождением оптимального плану перевозок груза.

МСМ управления перевозками грузов на ТС включает в себя пять эта- пов [10].

В качестве демонстрации этих этапов ниже рассмотрена конкретная ТС (рис. 3).

ТС содержит 3 пункта отправления – А1, А2, и 4 пункта назначения – В1, В2, В3, В4 однородного груза. Расстояние между пунктами указано на соответству- ющих ребрах, объемы поставок и заявок груза проставлены в соответствующих графических объектах транспортных узлов.

80

50 10

2 20

40 30

50

1

1 1

А₁

А2

А3

В1 В2

В3

В4

Рис. 3. Транспортная сеть перевозок грузов

Первым этапом формирования МСМ будет составление массива расстоя- ний между соседними узлами ТС. Для этого достаточно указать расстояние от ПО до ПН каждого ребра графа в одном направлении, т. к. расстояние в обрат- ном направлении предполагается тем же (табл. 8).

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

Таблица 8

Массив расстояний между соседними узлами транспортной сети

№ п/п

П О

П Н

Рассто- яние

№ п/

п

П О

П Н

Рассто- яние

1 А

1

В

1

10 8 А

2

А

3

2

2 А

1

В

2

8 9 А

3

В

1

3

3 А

1

А

2

7 10 А

3

В

4

5

4 А

1

А

3

7 11 В

1

В

2

2

5 А

2

В

2

2 12 В

1

В

4

1

6 А

2

В

3

5 13 В

2

В

3

1

7 А

2

В

4

6 14 В

3

В

4

1

Not

a reprint

На втором этапе автоматически (посредством соответствующей програм- мы) по массиву расстояний строится матрица транспортных корреспонденций между всеми узлами ТС. Расстояние между не соседними (смежными) узлами проставляется равным бесконечности (табл. 9).

Матрица относительно ее главной диагонали носит симметричный харак- тер, вследствие не ориентированности транспортных корреспонденций.

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

Таблица 9

Матрица транспортных корреспонденций между всеми узлами транспортной сети Транспортные узлы А

1

А

2

А

3

В

1

В

2

В

3

В

А1 ∞ 7 7 1 4

0

8 ∞ ∞

А2 7 ∞ 2 ∞ 2 5 6

А₃ 7 2 ∞ 3 ∞ ∞ 5

В₁ 1

0

∞ 3 ∞ 5 ∞ 3

В2 8 2 ∞ 5 ∞ 1 ∞

В₃ ∞ 5 ∞ ∞ 1 ∞ 1

В4 ∞ 6 5 3 ∞ 1 ∞

Метод кратчайших маршрутов является методом третьего этапа формиро- вания МСМ. Этот метод (модифицированный метод Дейкстры), используя дан- ные матрицы корреспонденций (табл. 9), находит как значения кратчайших расстояний на ТС от каждого ПО до каждого ПН (табл. 10), так и соответству- ющие этим расстояниям маршруты, которые могут содержать промежуточные пункты на путях перемещения груза (рис. 4).

Таблица 10

Матрица кратчайших расстояний на ТС

ПО ПН В₁ В₂ В₃ В₄

А₁ 10 8 9 10

А2 4 2 3 4

А₃ 3 4 5 4

Четвертый этап состоит в составлении по полученным данным табл. 10 классической ТТ (табл. 11) и нахождении оптимального плана перевозок гру- зов, стоимость реализации которого составит 880 у.д.е.

Последним пятым этапом формирования МСМ является представление ре- зультатов найденного оптимального плана перевозок грузов на ТС (рис. 5).

For

reading

only

А₁ ⁴ В₁ = 10; А₂ ² В₂ ² В₁ = 4;

А1

 4 В2 = 8; А2

 2 В2 = 2;

А1

 8 В2

 1 В3 = 9; А2

 2 В2

 1 В3 = 3;

А1

 8 В2

 1 В3

 1 В4 = 10; А2

 2 В2

 1 В3

 1 В4 = 4;

А3

 3 В1 = 3;

А₃^{ 2} А₂^{ 2} В₂ = 4;

А3

 2 А2

 2 В2

 1 В3 = 5;

А3

 3 В1

 1 В4 = 4;

Рис. 4. Маршруты кратчайших расстояний Таблица 11

Оптимальный план перевозок грузов

ПО ПН В₁ В₂ В₃ В₄ Запаси

А1

10 8 9 10

X2=50 X3=30 80 А2

4 2 3 4

X7=10 10 А3

3 4 5 4

X9=20 X12=30 50

Заявки 20 50 40 30

80

50 10

2 20

40 30

50

1

1 1

А1

А2

А₃

B1 B2

B3

B4

80

40 50 10

30

Рис. 5. Оптимальный план перевозок грузов на транспортной сети

Транспортные потоки на рис. 5 распределятся следующим образом: из 80 условных грузовых единиц (у.г.е.), которые отправлены из А₁, 50 у.г.е. останет- ся в В2, а 30 у.г.е. транзитом отправятся в В3; 10 у.г.е., которые отправлены из

Not

a reprint

А2, транзитом через В2 отправятся в В3; из 50 у.г.е., которые отправлены из А3, 20 у.г.е. останется в В1, а 30 у.г.е. транзитом отправятся в В4.

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

Технология прошла экспериментальную проверку как для транспортных задач малой и средней размерности (то 10 до 100 транспортных узлов), так и для транспортных задач большой размерности (от 101 до 600 транспортных уз- лов) – транспортной системы Украины.

5. 4. Система поддержки принятия решений по управлению грузовы- ми привозками на транспортных сетях

В качестве примера ниже рассмотрена пошаговая работа системы под- держки принятия решений (СППР) управления несбалансированными грузо- выми перевозками на транспортной сети Украины:

– 1-й шаг: выбор ПО и ПН и задание объемов поставки и потребления гру- за (на рис. 6 общий спрос на груз превышает его общее предложение на 30 у.г.е.);

– 2-й шаг: поиск кратчайших маршрутов перевозки груза (рис. 7);

– 3-й шаг: выбор оптимального плана перевозки груза (рис. 8);

– 4-й шаг: построение оптимального плана перевозки груза (рис. 9).

Рис. 6. Выбор пунктов отправления/назначения и задание объемов поставки груза

For

reading

only

Рис. 7. Кратчайшие маршруты перевозки груза

Рис. 8. Выбор оптимального плана перевозки груза

Рис. 9. Оптимальный план перевозки груза

Используя в качестве ПО города Винница, Киев и Черкассы, а в качестве ПН города, Запорожье, Ровно, Сумы и Черновцы, при этом изменяя объемы по- ставки и потребления груза, ниже рассмотрены примеры применения всех вы- шеперечисленных методов приведения открытых ТС к сбалансированному ви- ду, а также симплексного метода и матрично-сетевой модели оптимизации не- сбалансированных грузовых перевозок на транспортных сетях:

а) в случае использования метода фиктивного поставщика/потребителя по- лучим (рис. 10, а, б);

б) в случае использования разностного метода получим (рис. 11, а, б);

Not

a reprint

в) в случае использования коэффициентного метода коэффициентов полу- чаем (рис. 12, а, б).

а

б

Рис. 10. Результаты роботы системы поддержки принятия решений при исполь- зовании метода фиктивного поставщика/потребителя: а – выбор оптимального

плана перевозки груза; б – оптимальный план перевозки груза

For

reading

only

б

Рис. 11. Результаты роботы системы поддержки принятия решений при использовании разностного метода: а – выбор оптимального плана перевозки

груза; б – оптимальный план перевозки груза

На рис. 13 представлена блок-схема алгоритма работы системы поддержки принятия решений.

а

б

Рис. 12. Результаты роботы системы поддержки принятия решений при исполь- зовании метода коэффициентов: а – выбор оптимального плана перевозки гру-

за; б – оптимальный план перевозки груза

С целью выявления приоритетности рассмотренных выше методов сведе- ния несбалансированных грузовых перевозок к сбалансированному виду с по- мощью СППР было решено 100 реальных ТЗ по нахождению оптимальных планов перевозок грузов.

В результате в качестве метода сведения этих открытых ТЗ к сбалансиро- ванному виду был использован: симплексный метод в 48 случаях, метод коэф- фициентов в 27, метод фиктивного поставщика/потребителя в 16 и разностный метод в 9 случаях.

Not

a reprint