Оптимизация трассировки КПМ

Рассмотрена ранее упрощенная имитационная математическая модель предполагает равномерное распределение узлов МПЗ вдоль круга КПМ, при котором задача трассировки КПМ имеет единственное решение.

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

С ростом потоков посылок раньше или позже возникает необходимость использования дополнительных КПМ, трассировки которых могут повторять или отличаться от трассировок основных КПМ.

При использовании нескольких КПМ с збигаючимы трассировки суммарный показатель , так или иначе распределяясь между этими КПМ, остается неизменным.

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

, В результате чего для передачи потока выбирается путь

(при избирается любой из этих путей).

Согласно такому выбору, значение при использовании односторонних и двусторонних КПМ соответственно составляют

Пример расположения 24 узлов МПЗ в узлах прямоугольной решетки 4x6

Рисунок 4.22 - Пример расположения 24 узлов МПЗ в узлах прямоугольной решетки 4x6

в частности, при единичных межузельных потоках и единичных расстояниях между соседними узлами в трассировке КПМ,

например, при М - 24 , , то есть при переходе от односторонних КПМ в двусторонних показатель ΤΚΜΣ уменьшается в 6624/3456 = 2,10 раза.

На рис. 4.22 приведен пример расположения 24 узлов МПЗ в узлах прямоугольной решетки размером 4 × 6. Принята нумерация узлов слева - направо и сверху - вниз.

На рис. 4.23 приведены 7 вариантов трассировки КПМ в решетке 4 × 6.

Варианты трассировки КПМ в решетке 4 × 6

Рисунок 4.23 - Варианты трассировки КПМ в решетке 4 × 6

В табл. 4.23 приведены формализованное представление прямых и обратных КПМ в решетке 4 × 6. Направление от узла 1 вправо (по часовой стрелке) считается направлением прямого КПМ, а направление вниз (против часовой стрелки) - направлением обратного КПМ.

Таблица 4.23 - Формализованное представление прямых и обратных КПМ в решетке 4 × 6

КПМ

трассировки КПМ

Е-образный прямой

1

2

3

4

8

7

6

10

11

12

16

15

14

18

19

20

24

23

22

21

17

13

9

5

1

Е-образный обратный

1

5

9

13

17

21

22

23

24

20

19

18

14

15

16

12

11

10

6

7

8

4

3

2

1

Ж-образный прямой

1

2

3

4

8

7

11

12

16

15

19

20

24

23

22

21

17

18

14

13

9

10

6

5

1

Ж-образный обратный

1

5

6

10

9

13

14

18

17

21

22

23

24

20

19

15

16

12

11

7

8

4

3

2

1

Н-образный прямой

1

2

6

10

11

7

3

4

8

12

16

20

24

23

19

15

14

18

22

21

17

13

9

5

1

Н-образный обратный

1

5

9

13

17

21

22

18

14

15

19

23

24

20

16

12

8

4

3

7

11

10

6

2

1

П-образный прямой

1

2

3

4

8

12

16

20

24

23

19

15

11

7

6

10

14

18

22

21

17

13

9

5

1

П-образный обратный

1

5

9

13

17

21

22

18

14

10

6

7

11

15

19

23

24

20

16

12

8

4

3

2

1

С-образный прямой

1

2

3

4

8

12

11

7

6

10

14

18

19

15

16

20

24

23

22

21

17

13

9

5

1

С-образный обратный

1

5

9

13

17

21

22

24

23

20

16

15

19

18

14

10

6

7

11

12

8

4

3

2

1

В-образный прямой

1

2

6

10

11

7

3

4

8

12

16

20

24

23

22

21

17

18

19

15

14

13

9

5

1

В-образный обратный

1

5

9

13

14

15

19

18

17

21

22

23

24

20

16

12

8

4

3

7

11

10

6

2

1

Х-образный прямой

1

2

6

7

3

4

8

12

11

15

16

20

24

23

19

18

22

21

17

13

14

10

9

5

1

Х-образный обратный

1

5

9

10

14

13

17

21

22

18

19

23

24

20

16

15

11

12

8

4

3

7

6

2

1

Принимая во внимание, что суммарная протяженность каждого КПМ равен 24, при расстоянии между узлами сети и и j по трассе прямого КПМ, равной , для передачи потока выбирается прямой КПМ, если , и обратный КПМ, если . В связи с этим в дальнейшем направление КПМ не указывается.

В табл. 4.24 приведены значения расстояний от узла 13 до остальных узлов МПЗ и соответствующих им ТКМ в решетке 4 × 6 при использовании для передачи потоков Е, Ж, Η, П, С, В, Х-образных КПМ и их сочетаний по 2.

Как следует из табл. 4.24, при использовании одного двустороннего КПМ его трассировки не имеет значения, поскольку при любом трассировке показатель равен 144.

При использовании двух двусторонних КПМ минимальное значение показателя , равное 100, достигается при сочетании С и В- подобных трассировок КПМ.

Подчеркнем, что сокращения показателя со 144 до 100, то есть в 1,441 раза, обеспечивается за счет комбинационного эффекта, возникающего из "воздуха", то есть не требует каких-либо дополнительных затрат для своей реализации. Однако, отсюда не следует, что сочетание С и В-подобных трассировок КПМ обеспечивает минимум суммарного показателя ТКМΣ в МПЗ, поскольку - только одна из его 24 составляющих.

Принимая во внимание, что

для окончательного выбора оптимальной пары (тройки, четверки и т.д.) КПМ следует выбрать ту пару (тройку, четверку и т.д.) КПМ, которой соответствует минимальное значение суммарного показателя . Это значит, что расчеты, подобные приведенным в табл. 4.24, необходимо повторить для всех 24 узлов сети. Опуская эти простые, но громоздкие выкладки, отметим лишь, что оптимальной парой среди рассмотренных двусторонних КПМ является сочетание КПМ П и В-образными трассировки, что позволяет уменьшить суммарный показатель с 3456 до 2520, то есть в 1,37 раза.

Таблица 4.24 - Значения расстояний от узла 13 до остальных узлов МПЗ и соответствующих им ТКМ в решетке 4 × 6 при использовании для передачи потоков р ij ( j = 2, 3, ..., 24) Е, Ж, Η, П, С , В, Х-образных КПМ и их сочетаний по 2

КПМ

узлы назначения

ткм

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

Е-образный

3

4

5

6

2

9

8

7

1

10

11

12

-

9

10

11

1

8

7

6

2

3

4

5

144

Ж-образный

5

6

7

8

4

3

10

9

1

2

11

12

.

-1

10

11

3

2

9

8

4

5

б

7

144

Н-образный

3

4

9

10

2

5

8

11

1

б

7

12

-

5

б

11

1

4

7

10

2

3

8

9

144

П-образный

3

4

5

б

2

7

8

7

1

6

9

8

-

5

10

9

1

4

11

10

2

3

12

11

144

С-образный

3 и

4

5

б

2

11

10

7

1

12

9

8

-

11

8

7

1

10

9

6

2

3

4

5

144

В-образный

3

4

9

10

2

5

8

11

1

6

7

12

-

1

2

11

5

4

13

10

6

7

8

9

144

Х-образный

5

6

9

10

4

7

8

11

3

2

11

12

-

1

10

9

1

4

5

8

2

3

б

7

144

Е + Ж-образный!

3

4

5

6

2

3

8

7

1

2

11

12

-

1

10

11

1

2

7

6

2

3

4

5

116

Е + Н-образный И

3

4

5

6

2

5

8

7

1

б

7

12

-

5

6

11

1

4

7

6

2

3

4

5

120

Е + П-образный И

1 Марта

4

5

6

2

7

8

7

1

б

9

8

-

5

10

9

1

4

И 7

б

2

3

4

5

122

Е + С-образный 1

3

4

5

6

2

9

8

7

1

10

9

8

-

9

8

7

1

8

7

б

2

3

4

5

132

Е + В-подюний И

3

4

5

6 и

2

5

8

7

1

6

7

12

-

1

2

11

1

4

1 из

6

2

3

4

5

108

Е + Х-образный 1

3

4

5

1 июня

2

7

8

7

1

2

11

12

-

1

10

9

1

4

5

б

2

3

4

5

118

Ж + Н-образный и

и 3

4

7

8

2

3

8

9

1

2

7

12

-

1

б

11

1

2

7

8

2

3

6

7

Ж + П-образный 1

3

4

5

6

2

3

8

7

1

2

9

8

-

1

10

9

1

2

9

8

2

3

б

7

Ж + С-образный

3

4

5

6

2

3

10

7

1

2

9

8

-

1

8

7

1

2

9

6

2

3

4

5

Ж + В-образный

3

4

7

8

2

3

8

9

п

2

7

12

-

1

2

11

3

2

3

8

4

5

б

7

Ж + Х-образный

5

6

7

8

4

3

8

9

и

2

11

12

-

1

10

9

1

2

5

8

2

3

6

7

Н-П-образный

3

4

5

6

2

5

8

7

!

6

7

8

-

5

6

9

1

4

7

10

2

3

8

9

126

Н + С-образный

3

4

5

6

2

5

8

7

1

6

7

8

-

5

б

7

1

4

7

б

2

3

4

5

112

Н + В-образный

3

4

9

10

2

3

8

и

1

6

7

12

.

1

2.

11

1

4

3

10

2

3

8

9

132

Н + Х-образный

3

4

9

10

2

5

8

ги

1

2

7

12

-

1

6

9

1

4

5

8

2

3

6

7

126

П + С-образный

3

4

5

б

2

7

8

7

1

6

9

8

-

5

8

7

1

4

9

6

2

3

4

5

120

П + У-образный

3

4

5

6

2

5

8

7

1

6

7

8

-

1

2

9

1

4

3

10

2

3

8

9

114

П + Х-образный

3

4

5

6

2

7

8

7

1

2

9

8

-

1

10

9

1

4

5

8

2

3

6

7

118

С + В-образный

3

4

5

6

2

5

8

7

1

6

7

8

-

1

2

7

1

4

3

6

2

3

4

5

100

С + Х-подибиий

3

4

5

6

2

7

8

7

1

2

9

8

-

1

8

7

1

4

5

б

2

3

4

5

108

В + Х-образный

3

1 Апреля

9

10

2

5

8

11

1

2

7

12

-

1

2

9

1

4

3

8

2

3

6

7

120

При цитировании материалов в рефератах, курсовых, дипломных работах правильно указывайте источник цитирования, для удобства можете скопировать из поля ниже:

Поделиться материалом

Содержание