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

 

УДК 656.07

 

Е. Е. Витвицкий, доктор технических наук, профессор

Р. Е. Шипицына, асрирант

Сибирский государственный автомобильно-дорожный университет, Омск

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

Ключевые слова: методы оптимизации, планирование, транспортная задача линейного программирования, методы решения.

 

Введение

Транспорт является одним из приоритетных направлений науки и технологий. В прогнозе научно-технологического развития Российской Федерации на период до 2030 г. области исследований «Транспорт» уделяется особое внимание [1], в частности планированию транспортных систем.

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

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

 

Решение транспортной задачи линейного программирования

Для решения транспортной задачи сначала определяется опорный план груженых ездок (далее – опорный план), затем путем его совершенствования определяется оптимальный план возврата порожних автомобилей (далее – оптимальный план) [2].

Существуют различные методы определения начального опорного и оптимального планов. Приведем пример решения транспортной задачи линейного программирования. Опорный план составим методом минимального элемента, оптимальный – методом потенциалов [4].

Задача. Имеется три поставщика (грузоотправителя) A_i , i = 1,2,3, объем товаров у которых составляет a_i тонн. От указанных поставщиков нужно перевезти груз в пять магазинов (грузополучателям) В _j , j = 1,2,3,4, потребность каждого из магазинов составляет b_j тонн. Все указанные пункты между собой связаны транспортной сетью. Удельные показатели эффективности использования каждой транспортной коммуникации C_ij известны, данные представлены в матрице 1.

Наличие груза у поставщиков: a₁ = 320, a₂ = 280, a₃ = 250.

Потребность в грузе у магазинов: b₁=150, b₂=140, b₃=110, b₄=230, b₅=220.

Решение. Пусть х _ij – объем груза, выраженный в тоннах, который перевозится от поставщика А _i к потребителю (в магазин) В _j. Задача заключается в достижении минимума расходов на перевозку, т. е. в минимизации транспортной работы, выраженной в тонно-километрах. Формальная математическая модель транспортной задачи [5] имеет вид

(2)

система ограничений [5]

(3)

	(4)
	(5)

Модель транспортной задачи называется закрытой (сбалансированной) в случае, если суммарный объем грузов у поставщиков и суммарный объем потребностей в пунктах назначения равны [5]:

(6)

Для разрешимости ТЗЛП необходимо и достаточно, чтобы условие (6) выполнялось.

В данном примере условие (6) выполняется, так как суммарный объем груза у грузоотправителей равен 850 т, суммарная потребность грузополучателей также 850 т. Имеем задачу закрытого типа.

В таблице 1 представлена матрица исходных данных транспортной задачи.

 

Таблица 1. Матрица исходных данных

Магазины (грузополучатели)	Поставщики (грузоотправители)			Потребность груза, т
	А1	А2	А3
В1	20	29	6	150
В2	23	15	11	140
В3	20	16	10	110
В4	15	19	9	230
В5	24	29	8	220
Наличие груза, т	320	280	250	850

 

При решении были использованы следующие условные обозначения: количественный излишек нераспределенного груза от грузоотправителя А _i – А _i ^*, нехватка в перевозке груза грузополучателю В _j – B_j ^*.

Для составления опорного плана используем метод минимального элемента (наименьшей стоимости). Находим в таблице 1 незанятую клетку с минимальным расстоянием (3;1), где 3 – номер столбца, 1 – номер строки). Помещаем в клетку (3;1) наименьшее из чисел А₃^*= 250 и В₁^*= 150. Аналогично поступаем для следующих незанятых клеток с минимальным расстоянием:

(3;5): А₃^*= 100 и В₅^*= 220;

(1;4): А₁^*= 320 и В₄^*= 230;

(2;2): А₂^*= 280 и В₂^*= 140;

(2;3): А₂^*= 140 и В₃^*= 110;

(1;5): А₁^*= 90 и В₅^*= 120;

(2;5): А₂^*= 30 и В₅^*= 30.

Таким образом, получен опорный план, представленный в таблице 2.

 

Таблица 2. Опорный план груженых ездок

Магазины (грузополучатели)	Поставщики (грузоотправители)			Потребности груза, т
	A1	A2	A3
В1	20 0	29 0	6 150	150
В2	23 0	15 140	11 0	140
В3	20 0	16 110	10 0	110
В4	15 230	19 0	9 0	230
В5	24 90	29 30	8 100	220
Запасы груза, т	320	280	250	850

 

Значение целевой функции опорного плана (подразумевающее минимизацию затрат на перевозку) согласно формуле (2) составляет:

Р = 230×15 + 90×24 + 140×15 + 110×16 + 30×29 + 150×6 + 100×8 = = 12040000,0 тонно-километров.

Найдем оптимальный план методом потенциалов. Число занятых клеток должно соответствовать количеству, определяемому выражением: суммарное количество поставщиков и потребителей за вычетом единицы, для рассматриваемого случая (3 + 5 – 1 = 7). В данном случае по данным таблицы 2, подсчитав число занятых клеток, получаем 7. Следовательно, опорный план груженых ездок является невырожденным.

Введем обозначения: U_i – потенциал i-го склада; V_j – потенциал j-го магазина [6]. В таблицу добавим столбец U_i – потенциал i-го склада, строку V_j – потенциал j-гомагазина.

Необходимо определить потенциалы, просматривая все загруженные (занятые) клетки и используя соотношение 7 [5], полагая при этом, что U₁ = 0:

(7)

Получили:

U₁= 0;

V₄= C_1,4 – U₁ = 15;

V₅ = C_1,5 – U₁ = 24;

U₂ = C_2,5 – V₅ = 5;

U₃ = C_3,5 – V₅ = –16;

V₂ = C_2,3 – U₂ = 10;

V₃ = C_3,2 – U₂ = 11;

V₁ = C_3,2 – U ₃ = 22.

Следующим шагом было определение значения оценок свободных клеток, которые представляют собой разницу между прямыми и косвенными тарифами [3]:

S_1,1 = C_1,1 – (U₁ + V₁) = –2;

S_1,2 = C_1,2 – (U₁ + V₂) = 13;

S_1,3 = C_1,3 – (U₁ + V₃) = 9;

S_2,1 = C_2,1 – (U₂ + V₁) = 2;

S_2,4 = C_2,4 – (U₂ + V₄) = –1;

S_3,2 = C_3,2 – (U₃+ V₂) = 17;

S_3,3 = C_3,3 – (U₃ + V₃) = 15;

S_3,4 = C_3,4 – (U₃ + V₄) = 10.

C отрицательными оценками получилось две клетки – клетка (1;1) и клетка (2;4), выбираем с наименьшей оценкой (клетка (1;1)) и строим для нее контур (цикл). Вершины контура должны лежать в занятых клетках. Потенциальная клетка – та, в которую нужно перенести груз. Потенциальная клетка всегда со знаком «минус». По контуру для перемещения выбирается минимальный объем груза из клеток, составляющих вершины контура [6]. После перемещения груза объемом 90 тонн по контуру получили новый план возврата порожних автомобилей. Проверили, соответствует ли он критерию оптимизации путем перерасчета потенциалов и определения оценок свободных клеток. Чтобы можно было сделать вывод о том, что полученный план является оптимальным, необходимо, чтобы выполнялось неравенство

(8)

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

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

Р = 11770000,0 тонно-километров.

Ранее на основе исходных данных этой задачи была решена ТЗЛП: опорный план был составлен методом двойного предпочтения, а оптимальный план методом МОДИ [6]. Результаты решений представим в таблице 4.

 

Таблица 3. Оптимальный план возврата порожних автомобилей

Магазины (грузополучатели)	Поставщики (грузоотправители)			Потребности груза, т
	A1	A2	A3
В1	20 120	29 0	6 30	150
В2	23 0	15 140	11 0	140
В3	20 0	16 110	10 0	110
В4	15 200	19 30	9 0	230
В5	24 0	29 0	8 220	220
Запасы груза, т	320	280	250	850

 

Таблица 4. Результаты решения ТЗЛП

Критерии сравнения	Методы построения опорного плана
	Метод наименьшей стоимости	Метод двойного предпочтения
Количество итераций, ед.	32	33
Трудоемкость, человеко-часов	0,33	0,16
Полученный результат, тонно-километр	12040000,0	12850000,0
	Методы построения оптимального плана
Критерии сравнения	Метод потенциалов	Метод МОДИ
Количество итераций, ед.	93	66
Трудоемкость, человеко-часов	1,5	1,0
Полученный результат, тонно-километр	11770000,0	11770000,0

 

Выводы

По результатам расчетов и данным таблицы 4 можно утверждать:

1) что количество итераций при нахождении опорного плана методом наименьшей стоимости на 1 единицу меньше, чем при нахождении опорного плана методом двойного предпочтения;

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

3) полученный результат опорного плана, найденного методом наименьшей стоимости меньше на 810000,0 тонно-километров, чем при нахождении опорного плана методом двойного предпочтения;

4) количество итераций при нахождении оптимального плана методом потенциалов в 1,4 раза больше, чем количество итераций при нахождении оптимального плана методом МОДИ;

5) трудоемкость расчетов при нахождении оптимального плана методом потенциалов на 50 % выше, чем методом МОДИ;

6) полученный при нахождении оптимального плана результат, выраженный в тонно-километрах, одинаков при использовании обоих методов: метода потенциала и метода МОДИ.

 

Список использованных источников

1. Прогноз научно-технологического развития Российской Федерации на период до 2030 года (утв. Правительством РФ) // КонсультантПлюс (дата обращения: 01.04.2021). – Текст : электронный.

2. Аникин, Б. А. Логистика. – Млсква : Проспект, 2016. – 406 с.

3. Бродецкий, Г. Л. Экономико-математические методы и модели в логистике. Процедуры оптимизации : учебное пособие / Г. Л. Бродецкий, Д. А. Гусев. – Москва : Академия, 2012. – 195 с.

4. Палий, И. А. Теория вероятностей : учебное пособие. – Москва : ИНФРА-М, 2012. – 236 с.

5. Палий, И. А. Введение в линейное программирование : учебное пособие. – Омск : СибАДИ, 2007. – 200 с.

6. Проектирование автотранспортных систем доставки грузов / В. И. Николин, С. М. Мочалин, Е. Е. Витвицкий, И. В. Николин ; под ред. проф. В. И. Николина. – Омск : СибАДИ, 2001. – 184 с.

 

Сравнительная оценка автотранспортного грузового комплекса в Хабаровском и Приморском краях

 

УДК 656.13

 

П. П. Володькин, доктор технических наук, профессор

А. С. Рыжова, кандидат экономических наук, доцент

Тихоокеанский государственный университет, Хабаровск

004167@pnu.edu.ru, chefra@mail.ru

 

 

Рассмотрены особенности транспортного комплекса Хабаровского и Приморского краев. Проанализированы предложения на рынке автомобильных грузовых перевозок на основе мощностей действующих предприятий, а также динамика объемов перевозок и грузооборота автомобильного транспорта Хабаровского и Приморского краев за 2015–2019 гг.

Ключевые слова: транспорт, автомобильный транспорт, транспортная логистика, транспортная инфраструктура.

 

Введение

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

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

Грузооборот российского транспорта показывает стабильный рост на протяжении последних нескольких лет. В 2018 г. грузооборот российского транспорта по Российской Федерации увеличился на 2,8 %, а объем перевезенных грузов – на 2,4 %. В 2019 г. рост продолжился [1].

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

Теоретическая часть

Формирование предложения на рынке автомобильных грузовых перевозок Хабаровского и Приморского краев происходит на основе мощностей действующих предприятий [4, 5].

Большее количество легковых автомобилей зарегистрировано на территории Приморского края (1701 ед.), однако грузовых автомобилей больше на территории Хабаровского края (8758 ед.). Количество организаций, имеющих собственные грузовые автомобили, примерно одинаково по обоим краям – 758 единиц в Хабаровском и 765 единиц в Приморском крае.

Практическая часть

Предложение на рынке грузовых автомобильных перевозок анализируемых регионов формируется исходя из наличия технически исправных грузовых автомобилей и их грузоподъемности. Скорректировав отчетные показатели числа грузовых автомобилей на предприятиях с учетом этого замечания, получим величину, в первом приближении характеризующую предложение грузового автомобильного транспорта на Дальнем Востоке [4, 5].

При этом количество технически исправных автомобилей в Хабаровском крае 7915 из 8758, т.е. коэффициент технической готовности по краю 0,9. В Приморском крае 6692 технически исправных грузовых автомобилей из 7595 единиц, значение коэффициента технической готовности не многим меньше и составляет 0,88. Количество технически исправных грузовых автомобилей в Хабаровском крае больше на 1223 единицы, соответственно, грузоподъемность выше на 28725 т [6].

Из данных по объему перевозок и грузооборота автомобильного транспорта анализируемых регионов видно, что объем перевезенных грузов автомобильным транспортом в Хабаровском крае больше объема в Приморском крае, однако наблюдается тенденция снижения.

Выводы

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

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

 

Список использованных источников

1. Обзор отрасли грузоперевозок в России за 2019 год. – URL: https://www.ey.com/Publication/vwLUAssets/ey-transportation-services-2019-rus/$FILE/ey-transportation-services-2019-rus.pdf

2. Официальный сайт Министерства транспорта и дорожного хозяйства Хабаровского края. – URL: https://mintrans.khabkrai.ru/

3. Официальный сайт Правительства Приморского края. – URL: https://www.primorsky.ru/

4. Официальный сайт Управления федеральной службы государственной статистики по Хабаровскому краю, Магаданской области, Еврейской автономной области и Чукотскому автономному округу. – URL: https://habstat.gks.ru/

5. Официальный сайт территориального органа Федеральной службы государственной статистики по Приморскому краю. – URL: https://primstat.gks.ru/.

6. Официальный сайт Федеральной службы государственной статистики РФ. – URL: https://rosstat.gov.ru/