Файл: Оптимизация процессов грузовой работы..pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 09.04.2024

Просмотров: 297

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

13, 17,

18, 19, 20. Р а сстояни я м еж -

Т а б л и ц а

38

 

 

 

 

 

 

д у точ ка м и

м нож ества

М

и

под ­

 

 

 

 

 

si

 

 

 

м нож ества 5

приведены в табл.

38.

m l

 

 

 

 

 

 

 

9

11

12

13

17

18

19

20

Затем

 

на основе найденных значе­

 

 

 

 

 

 

 

 

 

 

 

ний сц

(см. табл.

36

и

37)

состав­

9

со

11

20

27

4

14

14

3

ляем

матрицу D (табл.

39) следую ­

10

4

14

23

30

7

18

19

5

щим образом. В первой строке при­

водим

расстояния

между точками

11

11

С О

9

16

7

6

4

13

9 и 1 последовательно через точки

12

20

9

С О

7

16

9

6

22

11, 12,

13,

17,

18 и

19,

20

(под­

13

27

16

7

С О

7

15

12

29

множество S), во

второй строке —

14

17

8

8

12

12

12

5

19

расстояния между точками 10 я 2

15

9

7

14

 

 

12

 

12

через

точки

подмножества

S,

в

20

5

8

третьей

строке — между

точками

16

9

14

21

27

8

9

16

12

11

к

4 через

точки

подмножества

 

 

 

 

 

 

 

 

 

5

и т. д. Реш ив

методом целочис­

 

 

 

 

 

 

di}-

 

 

ленного программирования

матрицу D,

найдем

значения

(даны в

квадратах),

минимизирующие

линейную

форму.

П оследовательность

ра­

боты

крана

будет

тогда

такой:

1 —> 2 0 -* -9 -+ 1 -+ 2 -* -9 -+ 1 0 -+ 2 -+

^ 3 - + 1 7 - + 1 6 - + 3 - + 4 ^ 1 8 ^ 1 1 ^ 4 - + 5 ^ 1 ^ 1 5 - > 5 - + 6 - + 13-+-

 

12

 

6-^-7-*-12

 

 

13

 

7 -*- 8 -*- 19 -*- 14 -*- 8.

Учитывая,

что

кон­

тейнер

с места

6 запланировано поставить

на

занятое место

13, меняем

последовательность

работы

крана

следующим

образом:

1 -+-20-^>-9-*-

-+ 1

 

2 -* -9 -+ 1 0 -* -2 -* -3 -+ 17

16

3

 

 

4 -+

13-*-11 -*-4-+5^>-

-► 11

 

15 - > 5 -V 8 - > 19 ^ 14 -*- 8 -*- 6 -*- 14 -*- 1 2 ^ 6 ^ 7 - ^ 1 2 ^

-*-13-*-7. Общий пробег

крана по этому

варианту

312 л*.

 

 

 

 

П оследовательность

 

работы

 

 

 

 

 

 

 

 

 

 

крана,

организованной

по

прин­

Т а б л и ц а

 

39

 

 

 

 

 

ципу

перемещения

на кратчайшее

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

расстояние при

погрузке или вы г­

m i

 

 

 

 

 

h

 

 

 

рузке каждого

очередного

контей-

9

 

11

12

13

17

18

19

20

 

 

нера,

такова: 1 -

 

18-

 

11

1

 

 

 

 

 

 

 

 

 

 

- + 2 -+ 1 9 -+ 1 2 - - 2 -

 

5

- і

12-

9

С О

 

22

34

47

18

20

27

119]

- + 1 4 ^ 3 ^ 4 - 14 - 13 *- 4-

10

119]

 

23

36

49

20

22

30

20

-+ 5

 

11 -*-15 ■>5-

 

■6-і

15-

 

 

 

11

28

 

 

21

33

22

|П |

15

30

 

16 - >

6 - > 7 -■

20-

 

9 -

7 -

 

С О

 

8

9

10

 

 

8.

Общий про­

12

46

 

26

С О

1211

39

21

22

48

бег

крана

составляет

при

этом

13

56

 

36

|22|

С О

33

30

31

58

366

м.

Экономия

366 — 312

 

100 =

14

35

 

27

22

26

37

26

|23|

48

 

 

 

 

 

 

 

366

 

 

 

15

35

|25|

28

35

29

25

25

39

= 15% . Число выгружаемых контей­

16

27

 

26

34

45

|24|

16

29

30

неров

в

примере принято

равным

 

 

 

 

 

 

 

 

 

 

 

восьми.

При

расчете

плана

рабо-

 

 

 

 

 

 

 

 

 

 

211

Рис. 63. Схема маршрутов к задаче комми­ вояжера

ты

крана для большего

числа контейнеров (на

ЭВМ ) эффект возрастает

как

в

абсолютном, так

и в относительном выражении.

 

Оптимизация работы кранов на основе решения задачи коммивоя­

жера. В

практических

условиях работы контейнерных пунктов принцип

замкнутых маршрутов перемещения

кранов не

всегда соблюдается. При

достаточно большом фронте работ

и отсутствии специализации площадки

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

из

каждого

вагона,

причем, если в каком-либо вагоне

отсутствует хотя

бы

один

контейнер,

предназначенный для накопления

на

площадке, то

в следующем вагоне снимается

два

контейнера, когда в этом вагоне нет та ­

ких

контейнеров, снимают три

контейнера с последующего вагона, и т. д.

так, чтобы общее число освободившихся контейнеромест было равно

чис­

лу

вагонов

в

подаче.

Затем

контейнеры

сортируют как по принципу

ва ­

гон— вагон,

так

и по

принципу вагон — площадка. В

этом

случае огра­

ничение о

замкнутых

маршрутах

крана

снимается.

Задача

оптимизации

работы крана

сводится

к решению известной

задачи

коммивояжера

[27]

с учетом особенностей, характерных для контейнерной площадки:

 

 

кран

не

должен

возвращ аться

в исходную

точку;

 

 

 

 

 

в точках множеств Z и М кран может побывать не один, а два раза.

 

Разработано

достаточно

алгоритмов

для

решения

задачи

коммивоя­

ж ера, однако

ни

один

из

них практически

не

пригоден для

оператив­

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

П усть заданы точки 1 — 6 (рис. 63) и расстояние между ними. Примем за начало маршрута дви­ ж ения крана точку 1. Т ак как за ­ кончить движение можно в любой другой точке, будем рассматривать поэтапно пути к этим точкам, на­ чиная с последнего этапа (отрезка пути). Если путь оканчивается в точке 2, то в нее на последнем этапе можно попасть из точек 3, 4, 5, 6. Н а предпоследнем этапе в точку 2 можно попасть из любой точки (кро­ ме 1) через какую -нибудь третью точку. Например, из точки 3 вточку 2 можно попасть по одному из следующих путей: 3— 4—2\ 3— 5— 2\

3—6—2-, из точки 4 в точку 2: 4—3—2-, 4—5—2-, 4—6—2 и так для каждых трех точек. И з этих вариантов выберем кратчайшие маршруты между дву ­ мя точками и запомним их, например 3— 5— 2; 4— 6— 2\ 5— 4— 2; 6— 5— 2.

На более раннем этапе в точку 2 можно попасть такж е из любой точки через две другие, например из третьей: 3— 4— 5— 2; 3— 4— 6— 2; 3— 6— 4— 2\ 3—6—5— 2\ 3—5—6— 2; 3— 5— 4—2. И з точки 4 на предпоследнем этапе путь в точку 2 уж е выбран, так ж е как и из точек 5 и 6. Поэтому на данном этапе необходимо лишь к предыдущим расстояниям прибавить расстояние от точки 3 до точек 4, 5 и 6 и выбрать кратчайший маршрут. П усть это будет

маршрут 3— 4— 6— 2.

Т ак ж е поступаем и при расчете маршрутов в точку

2 из точек 4, 5 и 6.

В той ж е последовательности производятся расчеты

в предположении, что путешествие заканчивается в точках 3, 4, 5 и б.Таким образом, можно получить кратчайший путь, обходя каждую точку по од­ ному разу. Такой способ не исключает потери строго оптимального вариан­ та, особенно при большой разнице в расстояниях между точками. Однако его можно с успехом использовать для практических целей.

Рассмотрим в качестве примера задачу [27], решенную с использо­ ванием теории графов. Несимметричная матрица расстояний для точек, обозначенных на рис. 63, задана в табл. 40.

Принимая за окончание маршрута точку 1 (по условию задачи возвращ е­ ние в исходную точку обязательно), вычислим длину маршрутов из точки 2 в точку 1 через все другие точки, т. е. маршруты 2— 3— 7; 2— 4— /; 2— 5— 7; 2— 6— 7. И з них наиболее короткий маршрут 2— 3— 1, длина которого равна 36. Заносим найденную величину с индексом 3 во вторую строку

первого столбца К у

табл. 41

(столбцы

К у ,

К 2, •••> К п — этапы

расчетов).

Затем аналогичные

расчеты

делаем

для

маршрутов 3— 2— 7;

3— 4— 7;

3— 5— 7; 3— 6— 1. И з них минимальный маршрут 3— 5— 7 с общей длиной, равной 17. Эту величину с индексом 5 заносим в третью строку столбца К у Аналогично рассчитываем маршруты из точек 4, 5 и 6 и минимальные рас­ стояния заносим соответственно в четвертую, пятую и шестую строки пер­ вого столбца.

На втором этапе расчетов вычисляем маршруты на один рейс длиннее предыдущих, учитывая, что маршруты, включающие два последних рей­

са, уж е

найдены. Т ак, маршруты через точку

2 следующие:

2— 3— 5— 1 и

2— 5— 6— 1. Кратчайший из них маршрут 2 —

3— 5— 7

с расстоянием,

рав­

ным 38.

Величину эту с индексом 3 заносим во

 

вторую

строку

столбца

К 2-

Маршруты через точку 3 следующие: 3— 4—2— 7; 3— 5— 6— 7 и 3— 6— 2— 7,

минимальный

из

них

3— 6— 2

— 7

равен 12,

и эту величину

с

индексом 6

заносим

в третью

строку столбца

К 2-

 

 

 

 

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

все

строки столб­

цов К у — К у .

На последнем этапе расчетов

(столбец

К 5) к рассчитанным

в столбце К 4 длинам

маршрутов добавляем

расстояние отточки

1 до точек

начала

маршрутов,

которые

обозначены

соответствующими

индексами.

213

Т а б л и ц а

40

 

 

 

 

Номер

1

 

 

4

5

6

точки

2

 

1

с о

27

43

16

30

26

 

 

 

 

 

 

2

7

О О

16

16

30

25

3

20

13

С О

35

5

0

4

21

16

25

О О

18

18

5

12

46

27

48

С О

5

в

23

5

5

9

5

О О

Т а б л и ц а

41

 

 

 

 

Номер

 

Этап расчета

 

 

Номер

точии

н,

н 3

Нз

Кд

н

точки

5

I—

-

-

-

-

 

*— 1

 

 

2

3 6 з

3 8 ,

4 7 ,

-

-

2

3

1 7 ,

1 2 ,

Н И З * I 7 0 -

-

3

 

4

2 3 г

3 0 ,

3 5 ,

 

-

4

 

 

 

 

 

 

5

2 8 , Н і Н Н

3 9 з

-

-

5

L _ L _

 

1 2 2 з

4 3 3

-

-

6

 

 

 

 

 

 

 

 

 

 

 

Т а б л и ц а

42

 

 

 

 

Номер

1

2

3

4

5

6

точки

1

С О

7

20

21

12

23

2

7

О О

13

16

46

5

3

20

13

О О

25

27

5

4

21

16

25

С О

48

9

5

12

46

27

48

ОО

5

6

23

5

5

9

5

О О

И з этих величин выбираем мини­ мальную, которая и является мини­ мальным общим замкнутым марш ­ рутом. В данном случае минималь­ ная длина маршрута равна 63 и, следуя в обратном направлении в соответствии с обозначенными ин­ дексами (см. стрелки в табл. 41), найдем оптимальный маршрут: 1—

4— 3— 5— 6— 2— 1.

Следует

отме­

тить,

что этот результат такой ж е,

как

и полученный

точным

мето­

дом [27].

Если матрица расстояний сим­ метрична, что соответствует реаль­ ным условиям работы кранов на контейнерных площ адках, алгоритм расчетов существенно упрощается и формализуется. Процедура вы ­ числений сводится к последователь­ ному сложению столбцов матрицы расстояний. Возьмем для примера следующую матрицу расстояний (табл. 42), полученную из несим­ метричной матрицы (табл. 41). И с­ пользуем такж е условие о том, что кран не должен возвращ аться в исходную точку. Тогда мы можем условно рассматривать последнюю как конец маршрута и, исходя из этого предположения, вести расче­ ты, а затем, поскольку матрица расстояний симметрична, перепи­ сать маршрут в обратном порядке.

Процедура вычислений выпол­ няется следующим образом. Скла­ дываем члены первого столбца с соответствующими членами второго и наименьшую сумму с индексом, соответствующим строкам сложен­ ных членов, заносим во вторую строку столбца Кі табл. 43. Анало­ гично складываем члены первого

214

Смотрите также файлы