Построение минимальной последовательности поворотов посылок

На рис. 5.16 приведены возможные позиции расположения меток на посылках (показаны позиции меток на передней, верхней и правой гранях параллелепипеда).

Возможные позиции расположения меток на посылках

Рисунок 5.16 - Возможные позиции расположения меток на посылках

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

Первая цифра указывает умер грани:

1 - передняя,

2 - верхняя,

3 - задняя,

4 - нижняя,

5 - левая,

6 - правая.

Вторая цифра указывает номер позиции на грани:

1 - нижняя левая,

2 - верхняя левая,

3 - верхняя правая,

4 - нижняя правая.

На рис. 5.17 приведены граф G (24,72), который отвечает любым возможным поворотам посылки при расположении меток на позициях рис. 5.16.

Ребра графа соответствуют поворотам - X , X, - Y , Y, -Z, Z на ± 90 ° вокруг осей координат Х в У, Z (повороты Х 9 В, Z на 90 ° по часовой стрелке, повороты -X, - Y , -Z на - 90 ° против часовой стрелки).

В табл. 5.14 приведены матрицу переходов между позициями посылки при ее повороте на ± 90 ° вокруг осей координат X, Y, Z.

Таблица 5.14 - Матрица переходов между позициями посылки

первоначальная позиция

Следующая позиция

- X

X

- Y

Y

-Z

Z

11

41

21

14

12

61

51

12

42

22

11

13

62

52

13

43

23

12

14

63

53

14

44

24

13

11

64

54

21

11

31

54

62

24

22

22

12

32

51

63

21

23

23

13

33

52

64

22

24

24

14

34

53

61

23

21

31

21

41

32

34

53

63

32

22

42

33

31

54

64

33

23

43

34

32

51

61

34

24

44

31

33

52

62

41

31

11

64

52

42

44

42

32

12

61

53

43

41

43

33

13

62

54

44

42

44

34

14

63

51

41

43

51

52

54

44

22

11

33

52

53

51

41

23

12

34

53

54

52

42

24

13

31

54

51

53

43

21

14

32

61

64

62

24

42

33

11

62

61

63

21

43

34

12

63

62

64

22

44

31

13

64

63

61

23

41

32

14

Граф возможных поворотов посылки

Рисунок 5.17 - Граф возможных поворотов посылки

Будем считать позицию 11 позиции считывания ПИ, следовательно, при начальном расположении меток на других позициях они должны быть переведены на позицию 11.

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

Рельеф графа приведен в табл. 5.15.

Таблица 5.15 - Рельеф графа посылки

Вес текущей вершины

Текущая вершина

очередная вершина

-X

X

-Y

Y

-Z

Z

3

23

13

33

52

64

22

24

3

32

22

42

33

СО

54

64

3

34

24

44

31

33

52

62

3

43

33

13

62

54

44

42

3

53

54

52

42

24

13

31

3

63

62

64

22

44

31

13

2

13

12

14

2

22

12

51

21

2

2

24

14

61

21

31

21

41

2

33

51

61

2

42

12

61

41

2

44

14

51

41

2

52

51

41

12

2

54

51

21

14

2

2

62

61

21

12

64

61

41

14

1

12

11

1

14

11

1

21

11

1

41

11

1

51

11

1

61

11

0

11

Из рис. 5.17 табл. 5.15 следует, что с позиций 12, 14, 21, 41, 51, 61 можно перейти на позиции 11 за один поворот посылки; с позиций 13, 22, 24, 31, 33, 42, 44, 52, 54, 62, 64 - по два поворота посылки; с позиций 23, 32, 34, 43, 53, 63 - по три поворота посылки, следовательно минимальное значение среднего количества поворотов посылки, которую можно достичь при размещении 24 устройств для поиска меток на всех 24 позициях составляет

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

Например, кратчайший путь от вершины 23 (вес 3) до вершины 11 (вес 0) может быть сформирован следующим образом:

- От вершины 23 (вес 3) возможны переходы к вершинам 13 (- X , 33 ( X ), 52 (- Y ), 64 (П, 22 (-Z), 24 (Z) (вес 2) выбираем 24 ( Z)

- От вершины 24 (вес 2) возможны переходы к вершинам 14 (- X , 41 ( X ) (вес 1) выбираем 14 (- X )

- От вершины 14 (вес 1) возможен переход только к вершине 11 ( Y ) (вес 0).

Таким образом, возможно кратчайший путь от вершины 23 до вершины 11 мас вид: 23, 24, 14, 11 (Ζ - X , Y ).

Из рис. 5.16 и табл. 5.14 можно построить полные перечни последовательностей поворотов от произвольных позиций в позиции 11.

Так, полный перечень содержит 16 последовательностей поворотов от позиции 23 до позиции 11:

23-13-12-11 (повороты Х, - Y , )

23-13-14-11 (повороты - Х , Y , Υ )

23-22-12-11 (повороты -Ζ, -X У);

23-22-21-11 (повороты -Ζ, -Ζ, -. X )

23-22-51 - 11 (повороты -Ζ - Y , -Ζ)

23-24-14-11 (повороты Ζ - X , Υ )

23-24-21-11 (повороты Z, Z - X )

23-24-61 - 11 (повороты Ζ, Y , Ζ)

23-33-51 11 (повороты Х , -Ζ, -Ζ)

23-33-61- 11 (повороты X , Z, Z)

23-52-12-11 (повороты - Y , -Ζ - Y )

23-52-41- 11 (повороты - Y - Y , X )

23-52-51-11 (повороты - Y , X, -Z)

23-64-14-11 (повороты Y , Ζ, В)

23-64-41-11 (повороты Y , Y , X )

23-64-61-11 (повороты Y , Ζ).

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

В табл. 5.16 приведены рельеф графа в условиях запрета поворотов посылки вокруг оси Ζ.

Таблица 5.16 - Рельеф графа посылки в условиях запрета поворотов вокруг оси Ζ

Вес текущей вершины

Текущая вершина

очередная вершина

- X

X

Υ

1

2

3

4

5

6

4

33

23

43

34

32

3

23

13

52

64

3

32

22

42

31

3

34

24

44

31

3

43

13

62

54

3

51

52

54

44

22

3

53

54

52

42

24

3

61

64

62

24

42

3

63

62

64

22

44

2

13

12

14

2

22

12

2

24

14

2

СО

21

41

2

42

12

2

44

14

2

52

41

2

54

21

2

62

21

2

64

41

1

12

11

1

14

11

1

21

11

1

41

II

0

11

В условиях запрета поворотов посылки вокруг оси Z кратчайший путь от вершины 23 (вес 3) до вершины 11 (вес 0) может быть сформирован следующим образом:

- От вершины 23 (вес 3) возможны переходы к вершинам 13 (- X ), 52 (- Y ), 64 (В) (вес 2) выбираем 64 ( Y )

- От вершины 64 (вес 2) возможен переход только к вершине 41 ( Y ) (вес 1);

- От вершины 41 (вес 1) возможен переход только к вершине 11 ( X ) (вес 0).

Таким образом, возможно кратчайший путь от вершины 23 до вершины 11 в условиях запрета поворотов посылки вокруг оси Z имеет вид: 23, 64, 41, 11 ( Y , Y , X ).

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

Дальнейшее увеличение количества устройств для поиска меток не приводит к уменьшению среднего количества поворотов, поскольку полученное при значение совпадает с минимальным значением при

Следует подчеркнуть, что минимальное значение при заданном значении к в общем случае достигается при некоторых неминимально значений и Так, если разместить к = 12 устройств для поиска меток на позициях 11, 12, 13, 14, 31, 32, 33, 34, 51, 53, 61, 63, то метки будут найдены или непосредственно на указанных позициях, или на остальных позиций после одного поворота посылки вокруг оси X в любом направлении, следовательно и имеет минимальное значение, а - некоторое неминимально значения. при этом

Таким образом, в то время, как в ранее приведенном расположении устройств для поиска меток было получено

В табл. 5.17 приведена зависимость среднего количества поворотов посылки от значения количества устройств для поиска меток k.

Таблица 5.17 - Зависимость среднего количества поворотов посылки от количества устройств для поиска меток

1

2

3

4

5

6

7

8

9

10

11

12

11,5

6,00

4,43

3,25

2,71

2,50

2,33

2,25

2,17

2,08

2,00

1,92

С табл. 5.17 следует, что применение более 6-8 устройств для поиска меток нецелесообразно, поскольку не приводит к сколько-нибудь заметному уменьшению среднего количества поворотов посылки.

На рис. 5.18 приведен алгоритм управления автоматическим поворотом посылок.

Алгоритм управления автоматическим поворотом посылки

Рисунок 5.18 - Алгоритм управления автоматическим поворотом посылки

Алгоритм содержит 2k + 7 блоков ( k - количество устройств для поиска меток).

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

В блоках 2, 3, ..., k + 1 (всего к блоков) выполняются проверки обнаружения меток устройствами . Если "Нет" - переход к следующим блоков, если

"Да" -до соответствующего блока

В блоке k + 2 выполняется проверка завершения поворотов посылки на первом этапе. Если "Нет" - переход к следующему блока, если "Да" - к блоку

В блоке k + 3 выполняется управления очередным поворотом посылки на первом этапе.

В блоке k + 4 формируется ответ "Метки не найдены". В этом случае посылка направляется на ручное обработки.

В блоках k + 5, k + 5 ..., 2 k + 4 (всего к блоков) выполняется ввод последовательностей поворотов на втором этапе от позиции расположения соответствующего устройства для поиска меток позиции 11. В случае управления

поворотами с помощью специализированного устройства последовательности поворота не вводятся, а хранятся в постоянном запоминающем устройстве.

В блоке + 5 выполняется проверка завершения поворотов посылки на втором этапе. Если "Нет" - переход к следующему блока, если "Да" - к блоку

В блоке 2k + 6 выполняется управления очередным поворотом посылки на втором этапе.

В блоке 2k + 7 формируется ответ "Индекс на позиции считывания". В этом случае выполняется считывание индекса и его распознавания.

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

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

Содержание