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

Автор работы: Пользователь скрыл имя, 06 Июня 2013 в 19:23, практическая работа

Описание работы

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

Файлы: 1 файл

Гр.перев.пр.р.doc

— 381.00 Кб (Скачать файл)

      Ряд  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 с.

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