3.1 Формирование маршрутов по максимуму коэффициента пробега

Для начала составим таблицу 3.2 под названием "Маятниковые маршруты с обратным холостым пробегом". При этом будем опираться на таблицу 1.2.

Таблица 3.2 Маятниковые маршруты с обратным холостым пробегом

Для того чтобы оптимизировать работу транспорта на маятниковых маршрутах с обратным холостым пробегом составим план перевозок по разнице объемов перевозок из таблицы 1.2 опираясь на таблицу 3.2 в итоге чего получится исходный план перевозки грузов, которые остались, который показан в таблице 3.3.

Суммируя по строкам в таблице 3.3, получаем суммарный запас груза, полученные результаты заносятся в соответствующие ячейки по строкам и столбцам.

Таблица 3.3 Исходный план перевозки грузов, которые остались или исходный план потребности в пустых автомобилях

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

Таблица 3.4 Исходный план возврата пустых автомобилей

Таблица 3.5 Метод северо-западного угла

С = 22*290+25*90+18*230+15*90+18*110+24*110+17*290+23*50+28*330 = 6380+2250+4140+1350+1980+2640+4930+1150+9240 = 34060

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

Таблица 3.6 Метод наименьшего элемента

С = 22*290+18*320+29*310+10*90+17*200+0*7+17*110+23*250+20*28 = 6380+5760+8990+900+3400+1870+5750+560 = 33610

Таблица 3.7 Метод двойного предпочт ения

C = 27*30+30*250+38*330+13*230+18*80+90*10+17*200+12*60+7*320 = 810+7500+12540+2990+1440+900+3400+720+2240 = 32540

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

Таблица 3.8 Первый этап оптимизации (метод двойного предпочтения)

С = 27*30+30*250+38*330+13*230+18*80+90*10+17*200+12*60+7*320 = 810+7500+12540+2990+1440+900+3400+720+2240 = 32540

U₃=0,

V₆=10-0=10,

V₉=17-0=17,

U₁=30-17=13,

V₈=27-13=14,

U₂=18-14=4,

V₅=12-4=8,

U₄=12-8=4,

V₇=7-4=3,

V₁₀=38-13=25.

Таблица 3.9 Второй этап оптимизации (метод двойного предпочтения)

С = 13*290+30*27+30*250+38*330+18*20+900+17*200+7*320+17*60 = 3770+7500+12540+360+900+3400+2240+1020 = 32540

V₇=0,

U₄=7-0=7,

V₈=17-7=10,

U₁=27-10=17,

U₂=18-10=8,

V₅=13-8=5,

V₉=30-17=13,

V₁₀=38-17=21,

U₃=17-13=4,

V₆=10-4=6.

Так как, потенциалы всех незагруженных клеток меньше расстояний в этих клетках, то есть U+V<C и проведённая оптимизация не показала никаких изменений в значении целевой функции, это означает, что план возвращения пустых автомобилей , полученный методом двойного предпочтения, является оптимальным.

Оптимизируем исходный план возвращения пустых автомобилей, полученный методом наименьшего элемента. Изобразим первый этап оптимизации в таблице 3.10.

Таблица 3.10 Первый этап оптимизации (метод наименьшего элемента)

С = 22*290+18*320+29*310+10*90+17*200+0*7+17*110+23*250+20*28 = 6380+5760+8990+900+3400+1870+5750+560 = 33610

V₇=0,

U₄=7,

V₈=17-7=10,

V₉=23-7,

U₁=18-0=18,

V₁₀=28-7,

U₂=29-21=8,

U₃=17-16=1,

V₆=10-1=9,

V₅=22-18=4.

Таблица 3.11 Второй этап оптимизации (метод наименьшего элемента)

С = 22*290+70*18+30*250+29*310+90*10+17*200+250*7+17*110+20*28 = 6380+1260+7500+8990+900+3400+1750+1870+560 = 32610

V₇=0,

U₁=18-0=18,

U₄=7-0=7,

V₉=30-18=12,

V₈=17-7=10,

V₁₀=28-7=21,

U₂=29-21=8,

U₃=17-12=5,

V₆=10-5=5,

V₅=22-18=4.

Таблица 3.12 Третий этап оптимизации (метод наименьшего элемента)

C = 22*290+18*50+30*250+20*38+29*310+900+17*200+270*7+17*110 = 6380+900+7500+760+8990+900+3400+1870 = 32590

V₇=0,

U₁=18,

U₄=7,

V₅=22-18=4,

V₉=30-18=12,

V₁₀=38-18=12,

U₂=29-20=9,

U₃=17-12=5,

V₆=10-5=5,

V₈=17-7=10.

Таблица 3.13 Четвёртый этап оптимизации (метод наименьшего элемента)

C = 22*290+27*50+30*250+20*38+29*310+900+3400+7*320+17*60 = 6380+1350+7500+760+8990+900+3400+2240+1020 = 32540

V₇=0,

U₄=7,

V₈=17-7=10,

U₁=27-10=17,

V₅=22-17=13,

V₉=30-17=13,

V₁₀=38-17=21,

U₂=29-21=8,

U₃=17-13=4,

V₆=10-4=6.

Так как потенциалы всех незагруженных клеток меньше расстояний в этих клетках, то есть U+V<C.Это означает, что план возвращения пустых автомобилей является оптимальным. В клетках: 2-5, 2-8, 4-5, 4-10 сумма потенциалов U и V равна нулю. А если выполняется такое условие, то существует как минимум ещё один оптимальный план, для которого общее расстояние плана перевозок остаётся прежним, поскольку C_ij - (U_i + V_j) = 0.

Значение целевой функции при оптимальном плане , полученном с помощью метода наименьшего элемента, как видим, остаётся таким же, как и при расчёте плана методом двойного предпочтения и составляет 32540 т-км.

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

На основании таблицы 3.13 составим оптимизированную таблицу 3.14 маятниковых маршрутов с обратным холостым пробегом.

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

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

Строим совмещённую матрицу оптимального плана возврата порожних автомобилей (табл. 3.13) с исходным планом перевозки грузов, которые остались (табл. 3.3) в таблице 3.15.

Таблица 3.15 Совмещённая матрица

В совмещенной матрице размещены два типа цифр:

- объем оставшихся грузов - подчеркнутые цифры;

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

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

На данном примере клетка 1-5 с двумя цифрами. Груз от поставщика 1 будет доставляться потребителю 5 в количестве 290 т на расстояние 22 км, а после разгрузки пустые автомобили снова возвращаются в пункт погрузки 1, пока не будет перевезено всё количество груза. Шифр этого маршрута 15-22 км. Из таблицы 3.15 следует исключить объемы перевозок на маятниковых маршрутах с обратным порожним пробегом, в результате чего получится таблица 3.16.

Таблица 3.16 Совмещенная матрица, построение контура первого кольцевого маршрута 3-8-4-9-3

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

Построение первого кольцевого маршрута показано в таблице 3.16. Шифр маршрута будет иметь вид: 38493. Количество перевезённого груза: от поставщика 3 потребителю 8 - 60 т; от поставщика 4 потребителю 9 - 60 т; всего равно 120 т. Коэффициент использования пробега: в = (23+23):(23+17+23+17) = 0,57.

Построение контура второго кольцевого маршрута показано в таблице 3.17.

Таблица 3.17 Построение контура второго кольцевого маршрута 1-7-4-10-1

Шифр этого маршрута - 174101. Коэффициент использования пробега: в = (18+28):(18+38+28+7) = 46:91=0,51. Количество перевезённого груза - 20+20=40 т.

Построение контура третьего кольцевого маршрута показано в таблице 3.18.

Таблица 3.18 Построение контура третьего кольцевого маршрута 1-7-4-9-3-8-1

Шифр этого маршрута - 174931. Коэффициент использования пробега: в = (18+23+23):(18+7+23+17+23+27) = 64:115 = 0,55. Количество перевезённого груза: 3*50 = 150 т.

Построение контура четвёртого кольцевого маршрута показано в таблице 3.19.

Таблица 3.19 Построение контура четвёртого кольцевого маршрута 3-10-2-6-3

Шифр маршрута - 31063. Коэффициент использования пробега: в = (30+24):(30+29+24+10) = 54:93 = 0,58. Количество перевезённого груза: 90+90 = 180 т.

Построение контура пятого кольцевого маршрута показано в таблице 3.20.

Таблица 3.20 Построение контура пятого кольцевого маршрута 2-9-3-10-2

Шифр пятого кольцевого маршрута - 293102. Коэффициент использования пробега: в = (24+30):(24+17+30+29) = 0,54. Количество перевезённого груза: 90+90=180 т.

Построение контура шестого кольцевого маршрута показано в таблице 3.21.

Таблица 3.21 Построение контура шестого кольцевого маршрута 1-9-4-7-1

Шифр этого маршрута - 19471. Коэффициент использования пробега: в = (18+23):(18+30+23+7) = 41:78 = 0,52. Количество перевезённого груза: 120+120=240 т.

Построение контура седьмого кольцевого маршрута показано в таблице 3.22.

Таблица 3.22 Построение контура седьмого кольцевого маршрута 1-7-4-10-2-9-1

Шифр маршрута - 17410291. Коэффициент использования пробега: в = (18+28+24):(18+7+28+29+24+30) = 70:136 = 0,51. Количество перевезённого груза: 3* 130 = 390 т. Для того чтобы получить общую картину использования пробега автомобилей составим таблицу 3.23, непосредственно в которой посчитаем коэффициенты использования пробега по каждому из кольцевых маршрутов и общий коэффициент использования пробега по всем кольцевым маршрутам в целом.

Таблица 3.23

Расчёт коэффициентов использования пробега

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