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

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

U₅= A₅Б₁ – V₁ = 9-5= 4; V₃ = A₅Б₃ – U₅ = 13-4= 9; U₄= A₄Б₃ – V₃ = 15-9 =6;

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

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

А₁Б₂ = u₁ + v₂ = 0-3 = -3 < ( l_1-2=1);

А₁Б₃ = u₁ + v₃ = 0+9 = 9 > ( l_1-3=7) -- 2 ;

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

А₂Б₈ = u₂ + v₈ = 16+15= 31> ( l_2-8=3)-- 28 ;

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

А₆Б₈ = u₆ + v₈ = 11+15= 26> ( l_6-8=2)-- 24 .

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

4.1.5. Оптимизация плана. Проверка допустимого плана на оптимальность заключается в соблюдении условий: {8} и {9}. Если данные условия не соблюдаются для клеток X_ij =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

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

А₁Б₂ = u₁ + v₂ = 0-1 = -1 < ( l_1-2=1); ……; А₂Б₂ = u₂ + v₂ = 0-1 = -1 < ( l_2-2=13);

А₁Б₄ = u₁ + v₄ = 0+6 = 6 < ( l_1-4=8); ……; А₂Б₇ = u₂ + v₇ = 0+6 = 6 < ( l_2-7=7);

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

А₃Б₈ = u₃ + v₈ = 5+3 = 8 < ( l_3-8=10); …..; А₄Б₈ = u₄ + v₈ = 8+3 = 11 < ( l_4-8=12);

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

А₆Б₁ = u₆ + v₁ = -3+5 = 2 ‡( l_6-8=2); ……; А₆Б₈ = u₆ + v₈ = -3+3 = 0 < ( l_6-8=2).

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

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

Пункт назначения	Б1	Б2	Б3	Б4	Б5	Б6	Б7	Б8
А1	66 425	1	12 7	8	4	2	18 14	18 15
А2	0 5	1813	8	6	3	1	7	183
А3	12	184	14	13	1811	4	12	10
А4	16	07	8815	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: А₁-Б₁-А₁ на 42 оборота и маршрут 2: А₄-Б₄-А₄ на 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	183
А3	12	184	14	13	1811	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: А₁-Б₇-А₅-Б₁-А₁ на 6 оборотов (наименьшему значению загрузки) и маршрут 4: А₄-Б₆-А₆-Б₄-А₄ на 12 оборотов. Не шедшие на образование маршрута грузовые и порожние ездки исключаются.