Минимизация холостых пробегов автотранспортного предприятия

{ 5 }

i=1 j=1

Это равенство является необходимым и достаточным условием для совместимости уравнений {2},{3}.

Цель решения выражается уравнением {1}: найти минимальный суммарный холостой пробег автомобилей. Задачу, выраженную формулами {1—5} принято называть задачей минимизации холостых пробегов автомобилей.


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

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

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

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

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


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



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


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


N>m+n-1 N

Ликвидация лишних

занятых клеток

N=m+n-1

Создание недостающих

занятых клеток



Расчёт индексов



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


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


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



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



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


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


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


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


§ 4. РАСЧЁТ ПО МЕТОДУ СОВМЕЩЁННЫХ ПЛАНОВ.


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

ТАБЛИЦА 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


Наличие порожняка












В строке записываются значения индексов Vj, а в столбце – значения индексов Ui .

Для дальнейших расчётов необходимо определить количество автомобиле-ездок, их находим по формуле :

Ze= Q/ q*,

где Q – объём перевозок;

q – грузоподъёмность автомобиля (т);

 -- коэффициент использования грузоподъёмности.

Значения q и возьмём из таблицы 3. Результаты вычисления занесём в таблицу 5.


ТАБЛИЦА 5. Расчёт ездок от объёма перевозки грузов (в тоннах).

Пункт

отправления

А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

Количество автомобиле- ездок

42

18

18

18

18

8

12

24

12

12

12

В правом верхнем углу клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами; условие bj = аi = 194 (ездки) выполняется.


ТАБЛИЦА 6. Допустимый исходный план.



Пункт назначения (образов. порожняка)


Пункт назначения

Вспом.

Индек.

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

Потребность в перевозках


Ui Vi










А1


425

1

7

8

4

2

1814

1815

78

А2


5

1813

8

6

3

1

7

3

18

А3


12

4

14

13

1811

4

12

10

18

А4


16

7

815

1215

13

5

15

12

20

А5


249

01

1213

6

01

1

4

1

36

А6


3

1

5

3

128

1210

3

2

24

Наличие порожняка


66


18

20

12

30

12

18

18

194/194


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

Планируем перевозки ближайшим из неудовлетворённых ещё потребителей, записывая соответствующие загрузки в клетки с наименьшими расстояниями. При соблюдении условий, описанных выше, удовлетворяя спрос и предложения пунктов отправления и потребления, происходит заполнение необходимых клеток; остаток по столбцу или строке сносится в клетку остатков, который впоследствии заносится в свободные не вычеркнутые клетки. При этом необходимо соблюдать условие, что количество заполненных клеток должно соответствовать числу m + n -1, где m — число пунктов отправления или погрузки; n – число пунктов погрузки.

В таблице 6 количество занятых клеток равно числу m + n -1=13; а в таблице 6 количество занятых клеток не равно этому числу 13 . Поэтому необходимо создать недостающие клетки, поставив нулевые загрузки в клетки А52 и А55.

Допустимый исходный план составлен, проверим его на оптимальность.


п.4.2. Расчёт индексов для занятых клеток.

п.4.2.1. Расчёт суммарного холостого пробега. Рассчитываем суммарный холостой пробег для допустимого исходного плана (таблица 6) с помощью формулы:

n m

Lx = Xij * lij , { 6 }

j=1 i=1

где Lx -- суммарный холостой пробег (км); Xij – количество порожняка, подаваемого между i-ым пунктом назначения, ездки; lij – расстояние от i-ого пункта отправления до j-ого пункта назначения (км).


п.4.2.2. Расчёт индексов. Следующим пунктом вычислений находим индексы для загруженных клеток :

Ui + Vj =lij Xij , { 7 }

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

Ui + Vj =lij , для Xij>0 { 8 } и Ui + Vj =lij , для Xij=0 . { 9 }

Для определения индексов используются следующие правила:

а) индексы Ui записываются во вспомогательный столбец ;

б) индексы Vj записываются во вспомогательную строку;

в) индексы правой клетки вспомогательного столбца принимаются за нуль: U1=0.

Тогда из уравнения {6} можно выразить Ui и Vj .

Далее, рассчитаем индексы для таблицы 7 допустимого исходного плана по этим правилам.


ТАБЛИЦА 7. Допустимый исходный план ( предварительный вариант).



Пункт назначения (образов. порожняка)


Пункт назначения

Вспом.

Индек.

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

Потребность в перевозках


Ui Vi

5

-3

9

9

-3

-1

14

15


А1

0

425

1

72

81

4

2

1814

1815

78

А2

16

516

1813

817

619

310

114

723

+ 328

18

А3

14

127

47

149

1310

1811

49

1216

1019

18

А4

6

16

7

815

1215

13

5

155

129

20

А5

4

249

01

1213

67

01

12

419

18

36

А6

11

313

17

515

313

128

1210

322

224

24

Наличие порожняка


66


18

20

12

30

12

18

18

194/194


V1= A1Б1 – U1 = 5-0= 5; V7 = A1Б7 – U1 = 14-0=14; V8 = A1Б8 – U1= 15-0 =15

……………………….. ………………………….. …………………………

U5= A5Б1 – V1 = 9-5= 4; V3 = A5Б3 – U5 = 13-4= 9; U4= A4Б3 – V3 = 15-9 =6;

После расчёта индексов проверяем незанятые клетки на потенциальность.

п.4.2.3. Определение потенциальных клеток. Незанятые клетки, для которых получилось, что Ui + Vj >lij – называются потенциальными. Проверяем незанятые клетки на потенциальность. Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов.

А1Б2 = u1 + v2 = 0-3 = -3 < ( l1-2=1);

А1Б3 = u1 + v3 = 0+9 = 9 > ( l­1-3­=7) -- 2 ;

....................................................................;

А2Б8 = u2 + v8 = 16+15= 31> ( l2-8=3)-- 28 ;

.....................................................................;

А6Б8 = u6 + v8 = 11+15= 26> ( l6-8=2)-- 24 .

По данным вычислений построим таблицу 7.


4.1.5. Оптимизация плана. Проверка допустимого плана на оптимальность заключается в соблюдении условий: {8} и {9}. Если данные условия не соблюдаются для клеток Xij =0, то значение потенциала отрицательно, что и определяет потенциальную клетку. Следует скорректировать допустимый план. Корректировка плана состоит в перемещении в потенциальную клетку с наименьшим по модулю потенциалом какую-нибудь загрузку. Перемещение производится при условии сохранения количества “+” и “-“ по строке и столбцу. Производя перемещение, следует повторить процесс определения потенциала до тех пор, пока условия {8} и {9} не будут соблюдены. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.

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

Цепочку возможных перемещений определяют: для потенциальной клетки с наибольшим значением потенциала строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна из её вершин находилась в данной клетке, а все остальные вершины в занятых клетках. Знаком “+” отмечают в цепочке её нечётные вершины, считая вершину в клетке с наибольшим потенциалом, а знаком “-“ – чётные вершины. Наименьшая загрузка в вершинах 18 ездок, уменьшая загрузку в вершинах со знаком “-“ и увеличивая её в вершинах со знаком “+” получают улучшенный план. Дальнейшие расчёты по его оптимизации производятся аналогично. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.

В результате всех вычислений имеем конечный оптимальный план возврата порожняка в таблице 8.


ТАБЛИЦА 8. Оптимальный план возврата порожняка.



Пункт назначения (образов. порожняка)


Пункт назначения

Вспом.

Индек.

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

Потребность в перевозках


Ui / Vi

5

-1

7

6

3

-3

6

3


А1

0

665

1

127

8

4

2

14

15

78

А2

0

05

13

8

6

3

1

7

183

18

А3

5

12

184

14

13

11

4

12

10

18

А4

8

16

07

815

15

13

125

15

12

20

А5

-2

9

1

13

6

301

1

64

01

36

А6

-3

3

1

5

123

8

10

123

2

24

Наличие порожняка


66


18

20

12

30

12

18

18

194/194

После составления оптимального плана возврата порожняка произведём проверку клеток на потенциальность. Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов.

А1Б2 = u1 + v2 = 0-1 = -1 < ( l1-2=1); ……; А2Б2 = u2 + v2 = 0-1 = -1 < ( l2-2=13);

А1Б4 = u1 + v4 = 0+6 = 6 < ( l­1-4­=8); ……; А2Б7 = u2 + v7 = 0+6 = 6 < ( l2-7=7);

.........................................................; ……; .…………………………………;

А3Б8 = u3 + v8 = 5+3 = 8 < ( l3-8=10); …..; А4Б8 = u4 + v8 = 8+3 = 11 < ( l4-8=12);

.........................................................; ….…; .…………………………………..;

А6Б1 = u6 + v1 = -3+5 = 2 ‡ ( l6-8=2); ……; А6Б8 = u6 + v8 = -3+3 = 0 < ( l6-8=2).


п.4.3. Составление матрицы совмещённых планов. Матрица совмещённых планов составляется после окончания разработки оптимального плана возврата порожняка. В таблицу 9 подставляются груженые ездки из таблицы 5. С целью лучшей наглядности изображения данные выполняются разными цветами.


ТАБЛИЦА 9. Матрица совмещенных планов.

Пункт назначения

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

А1

66 42 5

1

12 7

8

4

2

18 14

18 15

А2

0 5

1813

8

6

3

1

7

18 3

А3

12

184

14

13

18 11

4

12

10

А4

16

07

8 815

12 15

13

125

15

12

А5

24 9

1

12 13

6

301

1

64

01

А6

3

1

5

123

12 8

12 10

123

2


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

Следующим этапом идёт расчёт маятниковых и кольцевых маршрутов. Маятниковые маршруты определяются в таблице 9 клетками с двойной загрузкой и рассчитываются по наименьшей загрузке. Таких клеток в матрице две: маршрут 1: А111 на 42 оборота и маршрут 2: А444 на 8 оборотов. После их образования происходит расчёт кольцевых маршрутов.

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


ТАБЛИЦА 10. Таблица образования двухзвенных кольцевых маршрутов.

Пункт назначения

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

А1

24 5

1

12 7

8

4

2

18 14

18 15

А2

5

1813

8

6

3

1

7

18 3

А3

12

184

14

13

18 11

4

12

10

А4

16

7

15

12 15

13

12 5

15

12

А5

24 9

1

12 13

6

30 1

1

6 4

1

А6

3

1

5

12 3

12 8

12 10

12 3

2


Маршрут 3: А17511 на 6 оборотов (наименьшему значению загрузки) и маршрут 4: А46644 на 12 оборотов. Не шедшие на образование маршрута грузовые и порожние ездки исключаются.

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

ТАБЛИЦА 11. Таблица образования трёхзвенного маршрута.


Пункт назначения

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

А1

18 5

1

12 7

8

4

2

12 14

18 15

А2

5

1813

8

6

3

1

7

18 3

А3

12

18 4

14

13

18 11

4

12

10

А4

16

7

15

15

13

5

15

12

А5

18 9

1

12 13

6

30 1

1

4

1

А6

3

1

5

3

12 8

10

12 3

2


Маршрут 5: А1765531 на 12 оборотов.


ТАБЛИЦА 12. Таблица образования четырёхзвенного маршрута.

Пункт назначения

Б1

Б2

Б3

Б4

Б5

Б6

Б7

Б8

А1

18 5

1

7

8

4

2

14

18 15

А2

5

18 13

8

6

3

1

7

18 3

А3

12

18 4

14

13

18 11

4

12

10

А4

16

7

15

15

13

5

15

12

А5

18 9

1

13

6

18 1

1

4

1

А6

3

1

5

3

8

10

3

2

Маршрут 6: А182235511 на 18 оборотов.

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


§ 5. ПРИКРЕПЛЕНИЕ ОБРАЗОВАННЫХ МАРШРУТОВ К АТП.


После расчётов и образования всех типов маршрутов производится прикрепление полученных маршрутов к автотранспортному предприятию, при этом решаются две основные задачи:

  • определяется пункт погрузки, с которого следует начинать работу по кольцевым маршрутам;

  • выбирается автотранспортное предприятие, техника которого будет выполнять данные маршруты.

Рекомендуется выбирать первый пункт погрузки и АПТ на кольцевом маршруте так, чтобы получить наименьший нулевой пробег автомобиля. Критерием правильности выбора первого пункта назначения служит прирост порожнего пробега. Меньший прирост порожнего пробега соответствует наилучшему варианту выполнения маршрута.

Прирост порожнего пробега вычисляется по формуле:

lk ij = lk i +