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

      Ряд  1           6    7    11   9   11   16   16   12    9    12    5

 Строка            А    А    А   А   А    А    А     А    А    А    А

 

Из чисел этого ряда найдем наименьшее (2), соответствующее ему звено А-Б занесем в табл11. сравним соответствующие числа ряда 1 и строки Б табл.1. Из каждой сопоставляемой пары выберем наименьшее, получим ряд II.

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

     Ряд II     4    7     9     7   11   16   16   10    7   10

 Строка      Б  А    Б    Б     А    А    А    Б     Б    Б

 

  Наименьше число 3 соответствует звену Б-Н, заносим его в табл.11. Сравним числа строки Н с числами ряда II, и получим ряд III.

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

    Ряд III       4   7     9     7     11  16  16   9            7

 Строка         Б    А    Б     Б     А    А    А    Н            Н

     

Наименьшее число 4 соответствует звену Н-Л, занесем его в табл.11. Сравним числа строки Л с числами ряда III, получим ряд IV.

 

 

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

    Ряд IV              7     9     7     11    14   16    5     7

 Строка                А    Б     Б     А     Л     А    Л    Н

 

Наименьшее число 4 соответствует  звену Б-В, занесем его в табл.11. Сравним числа строки В с числами ряда IV, получим ряд V.

 

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

    Ряд V         7     5             11   14   16    5     7                              

 Строка          А    В             А    Л     А    Л    Н

 

Наименьшее число 3 соответствует звену В-Е, занесем его в табл.11. Сравним числа строки Е с числами ряда V, получим ряд VI.

Столбец          Г    Д    Ж     З     И    К    М

    Ряд VI         7            9     14   15    5     7

 Строка           А           Е     Е     Е    Л     Н

 

Наименьшее число 4 соответствует  звену Е-Д, занесем его в табл.11. Сравним числа строки Д с числами ряда VI, получим ряд VII.

Столбец         Г     Ж     З     И     К    М

    РядVII         7     9     14    15            7

 Строка           А     Е     Е      Е            Н

 

Наименьшее число 5 соответствует звену Л-К, занесем его в табл.11. Сравним числа строки К с числами ряда IIV, получим ряд VIII.

Столбец          Г     Ж     З      И    

  РядVIII      7      9      9     12

 Строка           А     Е      К     К

 

Наименьшее число 6 соответствует  звену К-М, занесем его в табл.11. Сравним числа строки М с числами ряда VIII, получим ряд IХ.

Столбец                 Ж    З     И

   Ряд IХ                9     9    12

 Строка                   Е    К     К

 

Наименьшее число 7 соответствует  звену А-Г, занесем его в табл.11. Сравним числа строки Г с числами ряда IХ, получим ряд Х.

 

 

Столбец         Ж    З     И

   Ряд Х                   9     9

 Строка                   Г     Г

 

Наименьшее число 4 соответствует  звену Г-Ж, занесем его в табл.11. Сравним числа строки Ж с числами ряда Х, получим ряд ХI.

 

Столбец                  И

   Ряд ХI                  6 

 Строка                   Ж  

 

                                                                                             

Наименьшее число 5 соответствует звену Ж-З, занесем его в табл.11. Сравним числа строки З с числами ряда ХI, получим ряд ХII.

Столбец               

   Ряд ХII              

 Строка             

 

 

Таблица 11. Звенья кратчайшей связывающей сети.

Порядковый номер звена	Звено	Длина звена, км	Порядковый номер звена	Звено	Длина звена, км
1	А - Б	2	7	Л - К	5
2	Б - Н	3	8	К - М	6
3	Н - Л	4	9	А - Г	7
4	Б - В	4	10	Г - Ж	4
5	В - Е	3	11	Ж - З	5
6	Е - Д	4	12	З - И	3

 

Рисунок 5. Кратчайшая связывающая сеть.

 

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

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

 

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

  Для решения этой  задачи можно применить метод  «ветвей и границ», использованный  для решения задачи коммивояжера.

  Рассмотрим метод «суммирования по столбцам», который также можно использовать для оптимизации последовательности объезда пунктов развозочного маршрута при симметричной матрице расстояний. Составим матрицу расстояний для 1^го маршрута и подсчитаем сумму расстояний по каждому столбцу.

 

Таблица 13. Матрица расстояний и суммы столбцов для 1^го маршрута.

	А	В	Е	Д	И	З	Ж	Г
А		6	9	11	16	16	11	7
В	6		3	5	21	20	12	13
Е	9	3		4	15	14	9	12
Д	11	5	4		16	15	10	8
И	16	21	15	16		3	6	9
З	16	20	14	15	3		5	9
Ж	11	12	9	10	6	5		4
Г	7	13	12	8	9	9	4
Сумма	76	80	65	69	86	82	57	62

 

  Составление маршрута  начинается с выбора трех пунктов  с наибольшей суммой. В таблице 13 это В, И и З. Они образуют исходный маршрут, в который должны быть включены все оставшиеся пункты по мере убывания суммарного расстояния . Отсюда исходный маршрут:

   И – З – В – И , его длина 44 км.

 В него включаем  пункт А (сумма расстояний равна 76) таким образом, чтобы приращение длины исходного маршрута было минимальным:

1. И-А-З-В-И, приращение длины 29 км;
2. И-З-А-В-И, приращение длины 2 км;
3. И-З-В-А-И, приращение длины 1 км.                                                     

Таким образом, пункт  А включаем в исходный маршрут между В и И.

Следующим включаем пункт  Д (сумма 69)

1. И-Д-З-В-А-И, приращение длины 28 км;
2. И-З-Д-В-А-И, приращение длины 0 км;
3. И-З-В-Д-А-И, приращение длины 10 км;
4. И-З-В-А-Д-И, приращение длины 11 км.

  Таким образом, пункт Д включаем в исходный маршрут между пунктами З и В.

   Следующим включаем пункт Е (сумма 65)

1. И-Е-З-Д-В-А-И, приращение длины 27 км;
2. И-З-Е-Д-В-А-И, приращение длины 3 км;
3. И-З-Д-Е-В-А-И, приращение длины 2 км;
4. И-З-Д-В-Е-А-И, приращение длины 6 км;
5. И-З-Д-В-А-Е-И, приращение длины 8 км

Выгоден вариант 3, берем его за основу и включаем в маршрут между пунктами Д и В, следующим включаем пункт Г (сумма 62).

1. И-Г-З-Д-Е-В-А-И, приращение длины 15 км;
2. И-З-Г-Д-Е-В-А-И, приращение длины 2 км;
3. И-З-Д-Г-Е-В-А-И, приращение длины 16 км;
4. И-З-Д-Е-Г-В-А-И, приращение длины 22 км;
5. И-З-Д-Е-В-Г-А-И, приращение длины 14 км;
6. И-З-Д-Е-В-А-Г-И, приращение длины 0 км.

Наиболее целесообразен 6 вариант, где приращение равно 0. Это и будет окончательный маршрут. Заметим, что он стал длиннее выбранного по кратчайшей связывающей сети на 6км., значит необходимо оставить первоначальный маршрут.

  Определим последовательность объезда пунктов во 2^ом маршруте таким же образом. Матрица кратчайших расстояний и сумма столбцов представлены в таблице 14.

 

Таблица 14. Матрица расстояний и суммы столбцов для 2^го маршрута.

	А	Г	З	И	К	Ж	Д
А		8	13	17	22	19	7
Г	8		5	9	14	13	9
З	13	5		4	9	8	14
И	17	9	4		6	12	18
К	22	14	9	6		10	22
Ж	19	13	8	12	10		12
Д	7	9	14	18	22	12
Сумма	86	58	53	66	83	74	82

 

  Исходный маршрут  А-К-М-А, его длина 31 км., в него  включаем пункт Л с суммой 35.

1. А-Л-К-М-А, приращение длины 1 км;
2. А-К-Л-М-А, приращение длины 7 км;
3. А-К-М-Л-А, приращение длины 5 км.

Пункт Л включаем в маршрут между пунктами А и К и включаем в него пункт Б с суммой 32.                                                                                         

1. А-Б-Л-К-М-А, приращение длины 0 км;
2. А-Л-Б-К-М-А, приращение длины 12 км;
3. А-Л-К-Б-М-А, приращение длины 14 км;
4. А-Л-К-М-Б-А, приращение длины 0 км;

Пункт Б включаем в маршрут между пунктами А и Л, его длина составит 32 км. В него включаем пункт Н с суммой 28.

1. А-Н-Б-Л-К-М-А, приращение длины 6 км;
2. А-Б-Н-Л-К-М-А, приращение длины 0 км;
3. А-Б-Л-Н-К-М-А, приращение длины 8 км;
4. А-Б-Л-К-Н-М-А, приращение длины 20 км;
5. А-Б-Л-К-М-Н-А, приращение длины 0 км.

  Длина маршрута не изменилась, изменился лишь порядок объезда пунктов таблица 12.

  Следует заметить, что при использовании метода  « суммирования по столбцам  »  наибольшая сумма не всегда  соответствует пункту А. Алгоритм  при этом не изменяется, получившийся  маршрут перезаписывается, начиная  с пункта А.

 

Таблица 13. Маршруты с уточненным порядком объезда пунктов.

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

 

 

 

 

 

Рисунок 6. Развозочные маршруты, составленные с использованием кратчайшей сети и оптимизированные методом «суммирования по столбцам».

 

  Вывод: Таким образом, использование кратчайшей связывающей сети (для набора пунктов в маршруты) и метода « суммирования по столбцам  »  (для уточнения последовательности их объезда) позволило получить развозочные маршруты на 25км. короче, чем без их использования.

 

 

 

 

 

 

ЛИТЕРАТУРА:

 

 

1. Ванчукевич В.Ф., Седюкевич В.Н., Холупов В.С. Грузовые автомобильные перевозки. – Минск: Высшая школа, 1989.- 272с.
2. Воркут А.И. Грузовые автомобильные перевозки. – Издание 2-е переработанное и доп. – Киев: Выш. Шк. Головное изд-во, 1986. – 447 с.
3. Кожин А.П., Мезенцев В.Н. Математические методы в планировании и управлении грузовыми автомобильными перевозками. – М.: Транспорт, 1994. 287 с.
4. Геронимус Б.Л., Царфин А.В. Экономико-математические методы в планировании и управлении на автомобильном транспорте,-М.: Транпорт, 1988.- 196 с.
5. СТП ИрГТУ 05-99. Система качества подготовки специалистов. Оформление курсовых и дипломных проектов. – Иркутск, 1999. – 39 с.
6. Колганов С.В. Грузовые перевозки. Методические указания по выполнению практических работ для студентов специальности 190701. – Иркутск, 2012.- 42 с.