Определение кратчайших расстояний между пунктами транспортной сети

 

L_ПОР=14×16+14×4+3×18+10×4+10×4+12×4+4×2+15×8+8×9+16×4=726 км

 

   Учитывая, что  в загруженных клетках d_ij=0, определим потенциалы строк и столбцов для таблицы 6. В строке А загруженных клеток одна АИ. Отсюда потенциал столбца И равен:

                                                   V_И=ℓ_АИ – U_А= 16 – 0 = 16

Далее по загруженным  клеткам БИ и ГИ определим потенциалы:

                                                  U_Б=ℓ_БИ – V_И= 18 – 16 = 2

               U_Г=ℓ_ГИ – V_И= 9 – 16 = -5

по загруженной клетке БВ определим потенциал для столбца В:

                                                     V_В=ℓ_БВ – U_Б=4 – 2 = 2

по загруженным клетке ДВ определим потенциал для строки Д:

                                                     U_Д=ℓ_ДВ – V_В= 2 – 2 = 0

В строке Д имеем  две загруженных клетки ДЗ и ДЕ:

                                                    V_З=ℓ_ДЗ – U_Д= 15 – 0 = 15

          V_Е=ℓ_ДЕ – U_Д= 4 – 0 = 4

А потенциал столбца  К определяем по загруженной клетке БК:

                                                     V_К=ℓ_БК – U_Б=10 – 2 = 8

По загруженной клетке НК определяем потенциал строки Н:

                                                     U_Н=ℓ_НК – V_К = 9 – 8 = 1

По загруженной клетке НЛ , определяем потенциал столбца Л :

            V_Л=ℓ_НЛ – U_Н = 4 – 1 = 3

По загруженной клетке ГЖ, определим потенциал столбца  Ж:

                                                     V_Ж=ℓ_ГЖ – U_Г = 4 – (-5) = 9

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

                                                   d_АВ = 6 – 0 – 2 = 4

                                                   d_АЛ = 9 – 0 – 3 = 6

                                                   d_АЖ = 11 – 0 – 9 = 2

                                                   d_АЗ = 16 – 0 – 12 = 4

                                                   d_АЕ = 9 – 0 – 1 = 8 

                                                   d_АК = 12 – 0 – 8 = 4

                                                   d_БЛ = 7 – 2 – 3 = 2

                                                   d_БЖ = 13 – 2 – 9 = 2

                                                   d_БЗ = 21 – 2 – 12 = 7

                                                   d_БЕ = 7 – 2 – 1 = 4

                                                   d_ГВ = 13 –(- 5) – 2 = 16

                                                   d_ГЛ = 7 – (- 5) – 3 = 9

                                                   d_ГЗ = 9 – (- 5) – 13 = 2

                                                   d_ГЕ = 12 – (- 5) – 1 = 16

                                                   d_ГК = 12 – (- 5) – 8 = 9

                                                   d_НВ = 7 – 1 – 2 = 4

                                                   d_НИ = 19 – 1 – 16 = 2

                                                   d_НЖ = 14 – 1 – 9 = 4

                                                   d_НЗ = 16 – 1 – 12 = 3

                                                   d_НЕ = 17 – 1 – 1 = 15

                                                   d_ДИ = 16 – 0 – 16 = 0

                                                   d_ДЛ = 15 – 0 – 3 = 12

                                                   d_ДЖ = 10 – 0 – 9 = 7

                                                   d_ДК = 20 – 0 – 8 = 12

  По произведенным расчетам, величина  d_ij ≥ 0, следовательно, этот план принимаем за оптимальный. Таблица 6.

 

  Для составления  рациональных маршрутов перевозок  целесообразно использовать метод  «совмещенных планов». Сущность  его состоит в том, что в  одной и той же таблице совмещается план ездок с грузом (таб.4) и оптимальный план ездок без груза (таб. 6). Совмещенный план представлен в таблице 7.

 

 

 

 

 

 

 

Таблица 7. Совмещенный план ездок с грузом и ездок без груза.

Поставщики	Потребители							Число ездок от постав-щиков
	В	И	Л	Ж	З	Е	К
А		14             14						14   14
Б	14               18	3             3					4	21   21
Г		0		10               10				10   10
Н			12               12				8               8	20   20
Д	4               0				8             8	16               16	4	28   28
Число ездок к потребителям	18   18	17   17	12   12	10   10	8   8	16   16	12   12	93   93

 

 Формирование маршрутов  производится следующим образом.  Вначале выбираются маятниковые маршруты с обратным порожним пробегом. Они соответствуют клеткам из совмещенного плана, где одновременно расположены две цифры – ездки с грузом и ездки без груза. Такими клетками в табл. 7 являются:

• Клетка АИ, ей соответствует маятниковый маршрут с обратным порожним пробегом А-И-А с числом оборотов 14;
• Клетка БВ, маршрут Б-В-Б с числом оборотов 14;
• Клетка БИ, маршрут Б-И-Б с числом оборотов 3;
• Клетка ГЖ, маршрут Г-Ж-Г с числом оборотов 10;
• Клетка НЛ, маршрут Н-Л-Н с числом оборотов 12;
• Клетка НК, маршрут Н-К-Н с числом оборотов 8;
• Клетка ДВ, маршрут Д-В-Д с числом оборотов 4;
• Клетка ДЗ, маршрут Д-З-Д с числом оборотов 8;
• Клетка ДЕ, маршрут Д-Е-Д с числом оборотов 16.

 

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

 клетках, причем ездки с грузом обязательно чередуются с ездками без груза.

 

Таблица 8. Совмещенный план ездок с грузом и ездок без груза.

Поставщики	Потребители							Число ездок от постав-щиков
	В	И	Л	Ж	З	Е	К
А
Б							4	4
Г
Н
Д							4	4
Число ездок к потребителям							4   4	8   8

 

  В рассматриваемом примере один кольцевой маршрут:

Б – К – Д –  Б с числом оборотов 4. Табл.8

  Для кольцевого маршрута рассчитываем коэффициент использования пробега по формуле:

 

                                                         

 где L_гр – пробег с грузом за оборот, км;

        L_общ – общий пробег за оборот, км;

        ℓ_егij – длина ездки с грузом между i-м отправителем и j-м получателем,                       км;      

        ℓ_хij – длина ездки без грузом между i-м отправителем и j-м получателем, км.

  Для кольцевого маршрута коэффициент использования пробега равен:

                                                       

  Коэффициент равен 0,5 , значит такой кольцевой маршрут нецелесообразен, перевозки лучше осуществлять на маятниковом маршруте.

Рисунок 4. Схема 1 пример маятникового маршрута К-Д-К и схема 2 пример кольцевого маршрута А-З-Г-И-К-Е-Б-В-А.

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

Практическая  работа 5

Разработка  рациональных развозочно-сборочных маршрутов движения автомобилей

 

 

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

 

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

 

 Таблица 9. Объёмы завоза грузов в промежуточные пункты. т .

Пункт отправления. А	Пункты и объёмы завоза грузов
	Б	В	Г	Д	Е	Ж	З	И	К	Л	М	Н
2,9 тонны	0,2	0,3	0,4	0,1	0,3	0,1	0,2	0,3	0,4	0,1	0,2	0,3

 

  Для выполнения  перевозок имеется один автомобиль  грузоподъёмностью 1,7 тонны. Таким  образом, для того, чтобы вывезти  от отправителя А и завезти  всем 12 получателям 3 тонны груз, необходимо составить 2 маршрута движения  2,9/1,7 = 1,706 округляем в большую сторону( ≈ 2).

  Для начала необходимо  составить искомые маршруты движения, ориентируясь на заданную транспортную  сеть так, чтобы они имели  насколько возможно минимальную суммарную длину (т.е. визуально). Пример составленных таким образом маршрутов приведен в табл. 10.

 

Таблица 10. Развозочные маршруты движения автомобилей, составленные визуально.

Маршрут движения	Загрузка, т.	Длина маршрута, км.
0,3+0,1+0,4+0,2+0,3+0,4 1.А-Н-Л-К-З-И-Г-А 5+4+5+9+3+9+7	= 1,7	= 42
0,3+0,1+0,3+0,1+0,2+0,2 2.А-В-Д-Е-Ж-М-Б-А 6+5+4+9+20+10+2	= 1,2	= 56
ИТОГО	2,9	98

 

 Далее необходимо составить по этим же исходным данным развозочные маршруты в соответствии с методикой, изложенной в [2]. Решение задачи при этом разделяется на 2 этапа. На 1 этапе, учитывая, что маршрутов будет 2, необходимо произвести набор пунктов в маршруты, то есть определить, какие из 12 пунктов завоза будут входить в 1^ый маршрут, а какие во 2^ой .

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

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

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

 Столбец             В    Г    Д    Е   Ж    З     И    К    Л    М    Н