Основы решения транспортных задач об оптимальных перевозках

 ОСНОВЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ  ОБ ОПТИМАЛЬНЫХ ПЕРЕВОЗКАХ

 

В автотранспортное предприятие поступила заявка на перевозку грузов на завтрашний день.

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

 

2.1 Математическая постановка задачи

 

Рассмотрим и сформулируем в математической форме условие транспортной задачи. Потребителям Б1, Б2, ...., Бj, ...., Бn  требуется груз в количествах b1, b2, ....., bj, ....., bn (т) единиц, который имеется или производится у поставщиков A1, A2, ......, Ai, ......, Am в количествах a1, a2, ......., ai, ......, am (т) единиц соответственно. Обозначим через qij объём перевозок из i-ого пункта отправления в j-ый  пункт назначения. Объём перевозок известен для всех пунктов ( задана заявка на перевозки грузов, см. таблицу 1.). Расстояние между поставщиками и потребителями известно (см. таблицу 2.) и составляет lij (км). В процессе выполнения перевозок в пунктах назначения Б1, Б2, ...., Бj, ...., Бn после разгрузки автомобилей будет образовываться порожняк в количествах b`1, b`2, ....., b`j, ....., b`n который надо направить в пункты A1, A2, ......, Ai, ......, Am в количествах a`1,a`2,…a`j,….a`m.

 С методической точки для  решения задачи удобней пользоваться  понятием “ездка”. Поэтому за  единицу измерения будет приниматься  ездка автомобиля с грузом  и без него.

В задаче будет выполняться условие:

                m                                                            n                                                                             

b`j = bj = S qij , где j=1,2,......,n     и      a`i = ai = S qij , где i=1,2,......,m    ,

                1                                                                                           1

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

Исходные данные для решения транспортной задачи  приведены в таблицах N No -1, 2, 3. 

 

Таблица 2.1.  - Заявка на перевозку грузов (в тоннах).

Пункт отправления	А1	А1	А1	А2	А3	А4	А4	А5	А5	А6	А6
Пункт назначения	Б1	Б7	Б8	Б2	Б5	Б3	Б4	Б1	Б3	Б5	Б6
Объём перевозок	189	81	81	81	81	36	54	108	54	54	54

 

 

Таблица 2.2-  Расстояния между пунктами отправления и назначения ( в км).

	Пункт   назначения
Пункт отправления	Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8	АТП
А1	5	1	7	8	4	2	14	15	3
А2	5	13	8	6	3	1	7	3	1
А3	12	4	14	13	11	4	12	10	12
А4	16	7	15	15	13	5	15	12	2
А5	9	1	13	6	1	1	4	1	10
А6	3	1	5	3	8	10	3	2	15
АТП	8	17	16	11	4	6	9	9	--

Таблица 2.3. - Расчётные нормативы.

Показатель	Обозначение	Значение
Грузоподъёмность	q	5
Коэффициент использования грузоподъёмности	g	0,9
Время в наряде * (в часах)	Тн	12,5
Среднетехническая скорость (в км/час)	Vт	24
Простой под погрузкой и выгрузкой на одну ездку с грузом (мин)	t пв	85

  *   Примечание.  Допустимое  отклонение ± 35 минут.

** Примечание.  Используется автомобиль  ЗИЛ-130 грузоподъёмностью 5 тонн.

 

2.2 Математическая запись задачи

 

Обозначим через Xij количество порожняка (в автомобиле - ездках) предназначенного  к отправке из пункта разгрузки Бj в пункт погрузки Ai , тогда суммарный холостой пробег автомобиля из всех пунктов с наличием порожняка во все пункты его подачи будет иметь вид:

                              n    m                                                                 

S S Xij * lij à min.                                                                 (2.1)

                               j=1 i=1                     

  Условие полного удовлетворения спроса на порожняк каждого пункта отправления за счёт подачи его из разных пунктов с наличием порожняка выглядит так:

                                                     n         

         S Xij = a`i , где i= 1,2,...,m.                             (2.2)

                                                     j=1                                     

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

 

  m

S Xij = b`j , где j= 1,2,...,n.                                                                              (2.3)  i=1                          

Очевидно, что количество автомобилей не может быть отрицательным числом, т.е.

                               Xij > 0, при i= 1,2,...,m, j= 1,2,...,n.                                    (2.4)

Таким образом, в математической форме транспортная задача формулируется  так:

Определить значение переменных Xij минимизирующих линейную форму, выраженную (2.1),  при ограничениях, указанных в (2.2),(2.3),(2.4). Необходимо равенство общей потребности получателей и наличия груза у поставщиков или отправителей:

                                           m              n

  S b`j = S а`j                                                                                ( 2.5 )

                          i=1          j=1 

Это равенство является необходимым и достаточным условием для совместимости  уравнений (2.2) и ,(2.3).

Цель решения выражается уравнением (2.1): найти минимальный суммарный холостой пробег автомобилей. Задачу, выраженную формулами (2.1) – (2.5) принято называть задачей минимизации холостых пробегов автомобилей.

 

2.3 Метод совмещённых планов

 

Для решения задачи разработан метод совмещённых планов. С его помощью она решается в три этапа.

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

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

 

 

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

 

 

 

 

Составление матрицы условий

 

 

Составление допустимого исходного плана

 

Подсчёт числа занятых клеток в матрице (N) и сравнение с (m+n-1)

Ликвидация лишних занятых клеток

N=m+n-1

Создание недостающих занятых клеток

    N>m+n-1                                                                            N<m+n-1

 

Проверка незанятых клеток на потенциальность

Построение цепочки возможных перемещений загрузок

 

Расчёт знаков  “+”  и  “-“ по вершинам цепочки

Поиск наименьшей среди загрузок, отмеченных знаком “-“

Изменение загрузки на вершинах цепочки

 

Решение закончено: оптимальный план составлен

Потенциальных клеток нет

             Примечание [ 1]

Рисунок 2.1.-  Блок-схема алгоритма метода потенциалов.

       Теперь рассмотрим   расчёт  по  методу  совмещённых  планов.

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

Таблица 2.4. -  Матрица условий.

		Пункт назначения (образов. порожняка)
Пункт назначения	Вспом. Индек.		Б1	Б2	Б3	Б4	Б5	Б6		Б7	Б8	Потребность в перевозках
	Ui / Vi
А1			5	1	7	8	4		2	14	15
А2			5	13	8	6	3		1	7	3
А3			12	4	14	13	11		4	12	10
А4			16	7	15	15	13		5	15	12
А5			9	1	13	6	1		1	4	1
А6			3	1	5	3	8		10	3	2
Наличие порожняка
Примечание [cоставлено автором]