47695

Грузовые перевозки. Методические указания

Книга

Логистика и транспорт

Практические работы предназначены для студентов специальности "Организация перевозок и управление на транспорте (автомобильный транспорт)" и предполагают использование экономико-математических методов для решения задач организации и планирования грузовых автомобильных перевозок

Русский

2013-12-01

875 KB

25 чел.

Министерство  образования  и науки  России

ФГБОУ ВПО Национальный исследовательский

Иркутский  государственный  технический  университет

ГРУЗОВЫЕ  ПЕРЕВОЗКИ

Методические указания по выполнению практических работ

для студентов специальности 190701

"Организация перевозок и управление на транспорте"

(автомобильный транспорт)

Иркутск 2012

Грузовые перевозки. Методические указания по выполнению практических работ для студентов специальности  190701. Составил канд. техн. наук, доцент С.В. Колганов. – Иркутск,  2012.- 42 с.

Практические работы предназначены для студентов специальности "Организация перевозок и управление на транспорте (автомобильный транспорт)" и предполагают использование экономико-математических методов для решения задач организации и планирования грузовых автомобильных перевозок.

Библиогр. 5 назв. Табл. 37. Рис. 4

Рецензент канд. техн. наук, доцент О.Л. Маломыжев

Приложение

ЗАДАНИЕ ________________

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

" Грузовые перевозки "

Таблица П1 – Объемы

производства грузов

Обозначение поставщика (щебень)

Объем производ-ства, т.

А

150

Б

200

Г

160

Н

250

Таблица П2 – Объемы

потребления грузов

Обозначение потребителя (щебень)

Объем потребле-ния, т.

В

150

И

200

Л

175

Ж

90

З

145

Рисунок П1 - Транспортная сеть

Таблица П3 - Объемы производства                 Таблица П4 - Объемы потребления

Обозначение поставщика (песок)

Объем производства, т.

Обозначение потребителя (песок)

Объем

потребления, т.

Д

200

Е

250

К

50

Таблица П5 - Объемы завоза грузов в промежуточные пункты, т.

Пункт отправления, А

Пункты и объемы завоза грузов

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

2.9

0.2

0.3

0.4

0.1

0.3

0.2

0.1

0.2

0.3

0.4

0.1

0.3

Выдано студенту __________________________ группы____________________

Преподаватель ____________________________ Дата выдачи________________

42

  1.  Общие сведения

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

Перечень предлагаемых для выполнения практических работ:

  1.  Определение кратчайших расстояний между пунктами транспортной сети;
  2.  Закрепление потребителей однородного груза за поставщиками;
  3.  Маршрутизация перевозок грузов при помашинных отправках;
  4.  Решение задачи коммивояжера методом "ветвей и границ";
  5.  Разработка рациональных развозочно-сборочных маршрутов движения автомобилей;
  6.  Разработка рациональных развозочно-сборочных маршрутов движения автомобилей методом Кларка-Райта.

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

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

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

Оформление выполненных практических работ должно соответствовать действующим стандартам [5].

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

3

  1.  Методика выполнения практических работ

Практическая работа 1

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

Цель выполнения данной практической работы состоит в следующем:

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

Исходными данными для выполнения данной практической работы является транспортная сеть из индивидуального задания (рис. П1).

Для выполнения практической работы можно воспользоваться любым из известных методов, например, методом потенциалов [ 3 ]. Сущность его состоит в следующем. Потенциал одной из вершин (назовем ее исходной, например, вершины А) принимают за 0, то есть РА=0. Далее по формуле (1) определяются потенциалы всех вершин, непосредственно связанных с ней:

Рj = Рi + ℓij ,                                                      (1)

где i,j – текущие индексы соответственно исходной и непосредственно связанной с ней вершин;

Рi – потенциал исходной вершины, км;

Рj – потенциал вершины, непосредственно связанной с исходной, км;

ij – длина звена между исходной и непосредственно связанной с ней вершинами, км.

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

Рассмотрим метод потенциалов на примере рис. П1.

Примем РА= 0.

С вершиной А непосредственно связаны вершины Г, Л и Б. Их потенциалы:

РГ= РА+ℓАГ=0+6   = 6 км;

РЛ= РА+ℓАЛ=0+9  = 9 км;

РБ= РА+ℓАБ=0+10 = 10 км;

Отсюда в строке А и столбце Г табл. 1 проставляем минимальное расстояние 6, а звено АГ на рис. 1 отмечаем стрелкой. Вершину Г принимаем за исходную.

4

Литература

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

5.   СТП ИрГТУ 05-04. Система качества подготовки специалистов. Оформление курсовых и дипломных проектов. – Иркутск, 2004. – 39 с.

41

км или пункт Б с выигрышем в 20 км, однако, сделать это невозможно, поскольку автомобиль будет перегружен. Матрица выигрышей на данном этапе представлена в табл. 36.

Таблица 36 – Выигрыши после второго объединения маршрутов

Завоз, т.

I

0.2

2

Б

В

0.4

2

0

Г

0

Д

Е

0.2

2

7

11

Ж

0

З

0

И

0

К

0.4

2

7

11

18

Л

0.1

2

10

11

18

17

М

0

Н

Оставшиеся пункты включаем во второй маршрут. Максимальный выигрыш равен 18 и соответствует объединению маятниковых маршрутов А-Ж-А и А-Л-А в развозочный А-Ж-Л-А. Далее включаем пункт М с таким же выигрышем и получим маршрут А-Ж-Л-М-А длиной 36 км. Следующим включаем пункт Г с выигрышем в 11 км, а затем пункт Б с выигрышем в 10 км.

В результате получился маршрут А-Г-Ж-Л-М-Б-А с длиной 47 км и загрузкой 1.3 т.

Получившиеся маршруты сведем в табл. 37.

Таблица 37 – Маршруты, полученные методом Кларка-Райта

Маршрут движения

Загрузка, т.

Длина маршрута, км

       0.3+0.1+0.3+0.3+0.2+0.1+0.3=

1. А – В – Д – Н – К – И  – З -  Е - А

       19+ 4 + 6 + 2 +  9 +  8 + 3 + 15=

=1.6

=66

       0.4+0.2+0.4+0.1+0.2=

2. А – Г – Ж – Л – М – Б - А

      6 +  6 +  2 +  7 + 16 +10=

=1.3

=47

ИТОГО

2.9

113

Таким образом, маршруты движения автомобилей, полученные методом Кларка-Райта, оказались на 3 км длиннее, чем по кратчайшей связывающей сети (см. табл. 32), однако на 9 км короче, чем визуальным методом (см. табл. 27).

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

40

Непосредственно с ней связана только вершина Л. Ее потенциал

РГ=6

РЛГ+ℓГЛ=6+4=10 км.

Из известных к этому моменту потенциалов (РЛ=9, РБ=10 и РЛ=10) выбираем наименьший (РЛ=9), число 9 заносим в табл.1 в строку А и столбец Л, звено АЛ на рис. 1 отмечаем стрелкой. Вершину Л принимаем за исходную, с ней непосредственно связаны вершины Ж, З, М и Б (вершину Г не берем в расчет, поскольку расстояние до нее уже известно). Их потенциалы:

РЛ=9;   РЖ=9+2=11;   РЗ=9+8=17;   РМ=9+7=16;   РБ=9+12=21.

Из известных к данному моменту потенциалов (РБ=10; РЛ=10; РЖ=11; РЗ=17; РМ=16; РБ=21) выбираем минимальный РБ=10, в строку А и столбец Б проставляем 10, звено АБ отмечаем стрелкой. Вершину Б принимаем за исходную, с ней непосредственно связаны вершины М, Н и В (вершину Л не берем в расчет, поскольку до нее кратчайшее расстояние уже известно).

РБ=10;   РМ=10+16=26;   РН=10+10=20;   РВ=10+9=19.

Минимальный потенциал имеет вершина Ж (РЖ=11), ее значение заносим в табл. 1 в строку А и столбец Ж, звено ЛЖ отмечаем стрелкой на рис.1.

Таблица 1-Матрица кратчайших расстояний между пунктами транспортной сети

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

А

10

19

6

23

15

11

17

22

22

9

16

20

Б

9

16

13

18

14

17

21

12

12

16

10

В

25

4

20

23

17

21

12

21

21

10

Г

25

10

6

12

17

18

4

11

19

Д

16

20

13

17

8

21

17

6

Е

4

3

7

9

6

13

10

Ж

7

11

13

2

9

14

З

8

6

8

15

7

И

9

13

20

11

К

14

13

2

Л

7

15

М

11

Н

Таким образом, выбирая на каждом этапе минимальный потенциал, можно с абсолютной уверенностью гарантировать определение кратчайших расстояний и путей проезда от вершины А до всех остальных вершин данной транспортной сети. Расчеты повторяются до тех пор, пока все клетки в строке А табл. 1 не будут заполнены расстояниями. При этом на рис.1 у каждой вершины должна быть обозначена хотя бы одна стрелка (кроме вершины А, поскольку это исходная вершина с потенциалом РА=0).

Далее потенциал следующей вершины (например, Б) принимается за 0 и все расчеты повторяются аналогично.

5

Следует обратить внимание на то, что на данной транспортной сети нет никаких ограничений по организации дорожного движения, то есть расстояние, скажем, между пунктами А и И равно расстоянию между пунктами И и А (АИ=ℓИА). Таким образом, матрица кратчайших расстояний (см. табл. 1) будет симметрична относительно диагонали и можно заполнять только одну ее часть.

Рисунок 1-Кратчайшие пути проезда от вершины А

6

Таблица 34 – Выигрыши от объединения маятниковых маршрутов в развозочные

Завоз, т.

I

0.2

2

Б

0.3

2

20

В

0.4

2

0

0

Г

0.1

2

20

38

4

Д

0.3

2

7

14

11

22

Е

0.2

2

7

7

11

14

22

Ж

0.1

2

10

19

11

27

29

21

З

0.2

2

11

20

11

28

30

22

31

И

0.3

2

20

29

10

37

28

20

33

35

К

0.4

2

7

7

11

11

18

18

18

18

17

Л

0.1

2

10

14

11

22

18

18

18

18

25

17

М

0.3

2

20

29

7

37

25

17

30

31

40

14

25

Н

Таблица 35 – Выигрыши после первого объединения маршрутов

Завоз, т.

I

0.2

2

Б

1

20

В

0.4

2

0

0

Г

0

Д

0.3

2

7

14

11

22

Е

0.2

2

7

7

11

14

22

Ж

0.1

2

10

19

11

27

29

21

З

0.2

2

11

20

11

28

30

22

31

И

1

20

29

10

37

28

20

33

35

К

0.4

2

7

7

11

11

18

18

18

18

17

Л

0.1

2

10

14

11

22

18

18

18

18

25

17

М

1.0

0

Н

один и получим развозочный маршрут А-В-Д-Н-К-А, его длина составляет 53 км и загрузка автомобиля 0.3 + 0.1 + 0.3 + 0.3 = 1 т. Выигрыши на данном этапе показаны в табл. 35. Здесь индикаторы строк В и К примут значения 1, строк Д и Н – 0. Поиск максимальных выигрышей следует производить в строках и столбцах, где индикаторы отличны от 0. Далее включим пункт И с выигрышем в 35 км и получим маршрут А-В-Д-Н-К-И-А, его длина – 62 км и загрузка автомобиля– 1.2 т. Следующим будет пункт З с выигрышем в 31 км, получился маршрут А-В-Д-Н-К-И-З-А с длиной 65 км и загрузкой 1.3 т. Следующим включаем пункт Е с выигрышем 29 км и получим маршрут А-В-Д-Н-К-И-З-Е-А с длиной 66 км и загрузкой 1.6 т.  Следующим можно было бы включить пункт Ж с выигрышем в 22

39

Таблица 33 – Матрица кратчайших расстояний и выигрышей

Н

М

25

11

Л

18

14

7

15

К

17

25

40

14

13

2

И

35

18

18

31

9

13

20

11

З

31

33

18

18

30

8

6

8

15

7

Ж

21

22

20

18

18

17

7

11

13

2

9

14

Е

22

29

30

28

18

18

25

4

3

7

9

6

13

10

Д

22

14

27

28

37

11

22

37

16

20

13

17

8

21

17

6

Г

4

11

11

11

11

10

11

11

7

25

10

6

12

17

18

4

11

19

В

0

38

14

7

19

20

29

7

14

29

25

4

20

23

17

21

12

21

21

10

Б

20

0

20

7

7

10

11

20

7

10

20

9

16

13

18

14

17

21

12

12

16

10

А

10

19

6

23

15

11

17

22

22

9

16

20

Завоз, т

0.2

0.3

0.4

0.1

0.3

0.2

0.1

0.2

0.3

0.4

0.1

0.3

38

Практическая работа 2

Закрепление потребителей однородного груза за поставщиками

Цель работы заключается в построении такого плана перевозок щебня, который обеспечивал бы минимальное значение транспортной работы (грузооборота).

Задача закрепления потребителей однородного груза за поставщиками заключается в построении такого плана перевозок, который обеспечит минимальное значение критерия оптимальности, которым в данном случае будет грузооборот. Исходные данные для данной практической работы представлены на рис. П1, в табл. П1 и табл. П2 Приложения. Их необходимо свести в табл. 2. Расстояния между поставщиками и потребителями проставляют в правом верхнем углу каждой клетки (из табл. 1 в практической работе 1).

Таблица 2-Исходные данные для решения задачи оптимизации закрепления потребителей за поставщиками

Поставщики

Потребители

Объем производства, т.

В

И

Л

Ж

З

VВ=

VИ=

VЛ=

VЖ=

VЗ=

А

UА=

19

22

*

9

11

17

150

Б

UБ=

**

9

21

12

14

17

200

Г

UГ=

25

17

**

4

*

6

12

160

Н

UН=

10

*

11

15

14

**

7

250

Объем потребления, т

150

200

175

90

145

760

760

Задача оптимизации закрепления потребителей однородного груза за поставщиками может быть решена любым из известных методов, например, методом МОДИ [1, 2, 3, 4]. Сущность его состоит в следующем. Вначале строится какой-либо план перевозок, который по специальным правилам проверяется на оптимальность. Если он не оптимален, то строится новый улучшенный план. Таким образом, за конечное число шагов может быть получен искомый оптимальный план.

Первоначальный (опорный) план целесообразно получить методом "двойного предпочтения" [4]. Для этого по каждой строке и по каждому столбцу отмечается

7

знаком * клетка с минимальным расстоянием. В табл.2 клетки БВ, ГЛ и НЗ имеют одновременно 2 знака **. Их загружают в первую очередь (у поставщика Б имеется 200 т., а потребителю В требуется 150 т., следовательно, в клетку БВ проставляем 150 т. и т.д.). Далее проставляем загрузку в клетки, имеющие одну отметку * (15 т. в клетку АЛ, 105 т. в клетку НИ). Оставшуюся загрузку распределяем по свободным клеткам (потребителю И оставшиеся 95 т. завезем от поставщика А и Б; потребителю Ж завезем оставшиеся 90 т. от поставщика А). Таким образом, в полученном опорном плане от всех поставщиков имеющийся груз вывезен, всем потребителям завезено все, что им требуется. При этом опорный план должен удовлетворять 2 условиям:

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

2. Число загруженных клеток должно быть равно:

m+n-1,

где m – число поставщиков;

 n – число потребителей.

Опорный план, представленный в табл. 3, обоим этим условиям удовлетворяет, однако так бывает не всегда (о том, как быть в этом случае см. ниже).

Таблица 3-Первоначальный (опорный) план для решения задачи оптимизации закрепления потребителей за поставщиками

Поставщики

Потребители

Объем производства. т.

В

И

Л

Ж

З

VВ=10

VИ=22

VЛ=9

VЖ=11

VЗ=18

А

UА=0

19

-45

22

*

15

9

90

11

+

17

150

Б

UБ= -1

**

150

9

50

21

12

14

17

200

Г

UГ= -5

25

17

**

160

4

*

6

12

160

Н

UН= -11

10

*  +

105

11

15

14

**—

145

7

250

Объем потребления, т

150

200

175

90

145

760

Подсчитаем для опорного плана значение грузооборота по формуле (3):

Р=∑∑Qij*ℓij ,                                                    (3)

где i,j – текущий индекс соответственно поставщика и потребителя;

Р   – грузооборот, ткм;

Qij – объем перевозок между i-ым поставщиком и j-ым потребителем, т;

ij   – расстояние между i-ым поставщиком и j-ым потребителем, км.

8

Практическая работа 6

Разработка рациональных развозочно-сборочных маршрутов движения автомобилей методом Кларка-Райта

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

Таким образом, в этой практической работе цель та же самая, что и в практической работе 5, только использовать необходимо метод Кларка-Райта. Исходные данные соответственно те же самые.

Метод Кларка-Райта в отличие от использовавшегося в практической работе 5 предусматривает совместное решение задач набора пунктов в маршруты и определения последовательности их объезда. Суть метода состоит в следующем. Вначале составляется план, состоящий из маятниковых маршрутов, на каждом из которых предполагается обслуживать только одного потребителя, то есть в нашем случае необходимо составить 12 заведомо неэффективных маршрутов:

А-Б-А,  А-В-А,  А-Г-А,  А-Д-А,  А-Е-А,  А-Ж-А,  А-З-А,  А-И-А,  А-К-А,  А-Л-А, А-М-А, А-Н-А.

Далее каждые два маятниковых маршрута последовательно объединяют в один развозочный, включающий два потребителя, например, из маятниковых маршрутов А-Б-А и А-В-А получается один развозочный А-Б-В-А. Разумеется, длина получившегося развозочного маршрута будет меньше, чем суммарная длина маятниковых (в крайнем случае, равна). В нашем случае суммарная длина маятниковых маршрутов равна (10 + 10) + (19 + 19) = 58 км, а развозочного (10 + 9 + 19) = 38 км. Разница составляет 20 км и называется выигрыш (численно выигрыш равен разнице между сэкономленными звеньями Б-А и А-В и дополнительным звеном Б-В, то есть 10 + 19 – 9 = 20 км). Указанным образом определим величины выигрышей для всех возможных комбинаций и приведем их в табл. 33 в правом столбце (в левом столбце указаны кратчайшие расстояния между пунктами из табл.1). Для дальнейших расчетов необходимы только выигрыши, они представлены в табл. 34. Кроме того, к этой таблице присоединен столбец индикаторов I, которые принимают значения: 2 – маршрут маятниковый типа А-Б-А; 1 – пункт первый или последний (исключая исходный пункт А) в некотором развозочном маршруте; 0 – пункт внутренний.

Построение развозочных маршрутов необходимо начинать с выбора наибольшего выигрыша. В табл. 34 наибольший выигрыш в 40 км соответствует объединению двух маятниковых маршрутов А-К-А и А-Н-А в один развозочный А-Н-К-А. Следующий выигрыш в 38 км соответствует объединению маршрутов А-В-А и А-Д-А в развозочный А-В-Д-А. Следующий выигрыш в 37 км соответствует объединению А-Д-А и А-К-А, однако пункты Д и К уже входят в предыдущие развозочные  маршруты,  поэтому  оба  этих  развозочных  маршрута  объединим  в

37

первый, включаем в него оставшийся пункт Л (сумма 21).

  1.  А-Л-Ж-Е-Г-А, приращение длины 0 км;
  2.  А-Ж-Л-Е-Г-А, приращение длины 4 км;
  3.  А-Ж-Е-Л-Г-А, приращение длины 0 км;
  4.  А-Ж-Е-Г-Л-А, приращение длины 7 км.

В первом и третьем вариантах приращение пробега равно 0, поэтому можно выбрать любой из них, например первый.

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

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

Оба маршрута с уточненным порядком объезда пунктов сведем в табл. 32.

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

Маршрут движения

Загрузка, т.

Длина маршрута, км

      0.2+0.3+0.1+0.3+0.3+0.2+0.1+0.1=

1. А - Б -  В -  Д -  Н -  К -  И -  З -  М - А

    10 +9 + 4 +   6 + 2 +  9 +  8 +15 +16=

=1.7

=79

       0.4+0.2+0.3+0.4=

2. А – Л –Ж – Е – Г - А

      9 + 2 +  4 +10 +6 =

=1.2

=31

ИТОГО

2.9

110

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

36

Р = 45*22+15*9+90*11+150*9+50*21+160*4+105*11+145*7 = 7325 ткм

Для проверки на оптимальность по методу МОДИ определим вспомогательные величины ui (для строк) и vj (для столбцов), называемые потенциалами. Для этого потенциал одного из поставщиков (например, А) примем равным 0. Тогда все оставшиеся потенциалы определим по формуле (4)

dij  =  ℓij  -  ui  -  vj.                                            (4)

Учитывая, что в загруженных клетках dij = 0, определим потенциалы строк и столбцов для табл. 3. В строке А загруженных клеток три: АИ, АЛ и АЖ. Отсюда потенциалы столбцов И, Л и Ж равны:

uА=0;  vИ=ℓАИ-uА=22-0=22;

 vЛ=ℓАЛ-uА=  9-0=  9;

 vЖ=ℓАЖ-uА=11-0=11.

Далее по загруженной клетке БИ определим потенциал строки Б:

uБ=ℓБИ-vИ=21-22= -1;

по загруженной клетке НИ потенциал строки Н:

uН=ℓНИ-vИ=11-22= -11;

по загруженной клетке ГЛ потенциал строки Г:

  uГ=ℓГЛ-vЛ=4-9= -5;

по загруженной клетке БВ потенциал столбца В:

  vВ=ℓБВ-uБ=9-(-1)=10;

по загруженной клетке НЗ потенциал столбца З:

  vЗ=ℓНЗ-uН=7-(-11)=18.

Теперь рассчитаем значение параметра dij для всех свободных клеток:

  dАВ =19-0-10      = 9;

  dАЗ =17-0-18      =-1;

  dБЛ =12-(-1)-9    = 4;

  dБЖ=14-(-1)-11  = 4;

  dЗБ =17-(-1)-18  = 0;

  dГВ =25-(-5)-10  =20;

  dГИ =17-(-5)-22  = 0;

  dГЖ =6-(-5)-11   = 0;

  dГЗ  =12-(-5)-18  = -1;

  dНВ =10-(-11)-10=11;

  dНЛ =15-(-11)-9  =17;

  dНЖ=14-(-11)-11=14.

В двух клетках (АЗ и ГЗ) величина dij принимает значение меньше 0 (выде-лены курсивом). Значит, этот план не оптимален. Перемещение загрузки в эти клетки уменьшит значение грузооборота. Из нескольких клеток с отрицательными значениями dij выбирают такую, в которой оно самое минимальное.

Для перемещения загрузки необходимо составить специальный контур, все вершины  которого  лежат в  загруженных клетках, кроме одной,  в которой dij ‹ 0 (в табл.3 показан жирной линией).  В табл. 3 контур построен для клетки АЗ следу-

9

ющим образом: из клетки АЗ линия контура движется вниз до загруженной клетки НЗ, отсюда до загруженной клетки НИ, затем до АИ и наконец, контур замыкается в клетке АЗ. В углах контура проставим попеременно знаки "+" и "—", начиная с клетки АЗ. В клетки АЗ и НИ (где стоят знаки "+") нужно добавить загрузку, а из клеток НЗ и АИ (где стоят знаки "—") – отнять. Объем перемещаемой по контуру загрузки равен наименьшей цифре, стоящей в углах НЗ и АИ (откуда загрузку отнимаем). Это 45 т. Новый план перевозок после перемещения загрузки по этому контуру представлен в табл 4. Если среди клеток контура со знаком "—" окажется 2 (или более) с одинаковыми минимальными загрузками, то из плана исключается только одна из них с большим расстоянием, а вместо других оставляют условную нулевую загрузку, чтобы не допустить вырождения плана.

Таблица 4- Улучшенный план закрепления потребителей за поставщиками

Поставщики

Потребители

Объем производства. т.

В

И

Л

Ж

З

VВ=9

VИ=21

VЛ=9

VЖ=11

VЗ=17

А

UА=0

19

22

*

15

9

90

11

45

17

150

Б

UБ=0

**

150

9

50

21

12

14

17

200

Г

UГ= -5

25

17

**

160

4

*

6

12

160

Н

UН= -10

10

*

150

11

15

14

**

100

7

250

Объем потребления, т

150

200

175

90

145

760

Для плана перевозок из табл. 4 произведем расчет потенциалов ui и vj, а также значений dij для всех свободных клеток. Результаты расчетов свидетельствуют, что величина dij нигде не принимает значение меньше 0, следовательно, это оптимальный план. Грузооборот для оптимального плана равен:

Р = 15*9+90*11+45*17+150*9+50*21+160*4+150*11+100*7 = 7280 ткм.

На заключительном этапе корреспонденции из оптимального плана необходимо перенести на схему транспортной сети (рис. 2). Лучше это сделать разными цветами. В конце работы необходимо сделать вывод.

В случае, если первоначальный (опорный) план не удовлетворяет 2 условию, определить все потенциалы ui и vj невозможно. Недостающее количество клеток загружают нулевыми загрузками. Нулевые загрузки целесообразно размещать в незанятых клетках, расположенных на пересечении строки (столбца), для которой потенциал определен, со столбцом (строкой), для которого потенциал неизвестен. Из всех этих клеток выбирается такая, в которой стоит наименьшее расстояние (поскольку задача решается на минимум грузооборота).

10

Наиболее целесообразен 5 вариант, где приращение равно 3 км, его берем за основу и включаем пункт К (сумма 84).

  1.  А-К-Б-В-Д-И-З-М-А, приращение длины 24 км;
  2.  А-Б-К-В-Д-И-З-М-А, приращение длины 15 км;
  3.  А-Б-В-К-Д-И-З-М-А, приращение длины 16 км;
  4.  А-Б-В-Д-К-И-З-М-А, приращение длины 0 км;
  5.  А-Б-В-Д-И-К-З-М-А, приращение длины 7 км;
  6.  А-Б-В-Д-И-З-К-М-А, приращение длины 4 км;
  7.  А-Б-В-Д-И-З-М-К-А, приращение длины 19 км.

Наиболее целесообразен 4 вариант, где приращение равно 0 км, его берем за основу и включаем последний оставшийся пункт Н (сумма 77).

  1.  А-Н-Б-В-Д-К-И-З-М-А, приращение длины 20 км;
  2.  А-Б-Н-В-Д-К-И-З-М-А, приращение длины 11 км;
  3.  А-Б-В-Н-Д-К-И-З-М-А, приращение длины 12 км;
  4.  А-Б-В-Д-Н-К-И-З-М-А, приращение длины 0 км;
  5.  А-Б-В-Д-К-Н-И-З-М-А, приращение длины 4 км;
  6.  А-Б-В-Д-К-И-Н-З-М-А, приращение длины 10 км;
  7.  А-Б-В-Д-К-И-З-Н-М-А, приращение длины 3 км;
  8.  А-Б-В-Д-К-И-З-М-Н-А, приращение длины 15 км.

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

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

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

А

Е

Ж

Л

Г

А

15

11

9

6

Е

15

4

6

10

Ж

11

4

2

6

Л

9

6

2

4

Г

6

10

6

4

Сумма

41

35

23

21

26

Исходный маршрут А-Е-Г-А, его длина 31 км, в него включаем пункт Ж с суммой 23 км.

  1.  А-Ж-Е-Г-А, приращение длины 0 км;
  2.  А-Е-Ж-Г-А, приращение длины 0 км;
  3.  А-Е-Г-Ж-А, приращение длины 11 км.

Первый  и  второй варианты равнозначны, выбираем любой из них, например,

35

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

А

Б

В

Д

Н

К

З

И

М

А

10

19

23

20

22

17

22

16

Б

10

9

13

10

12

17

21

16

В

19

9

4

10

12

17

21

21

Д

23

13

4

6

8

13

17

17

Н

20

10

10

6

2

7

11

11

К

22

12

12

8

2

6

9

13

З

17

17

17

13

7

6

8

15

И

22

21

21

17

11

9

8

20

М

16

16

21

17

11

13

15

20

Сумма

149

108

113

101

77

84

100

129

129

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

А-И-М-А, его длина 58 км.

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

  1.  А-В-И-М-А, приращение длины 18 км;
  2.  А-И-В-М-А, приращение длины 22 км;
  3.  А-И-М-В-А, приращение длины 24 км.

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

Следующим включаем пункт Б (сумма 108).

  1.  А-Б-В-И-М-А, приращение длины 0 км;
  2.  А-В-Б-И-М-А, приращение длины 20 км;
  3.  А-В-И-Б-М-А, приращение длины 17 км;
  4.  А-В-И-М-Б-А, приращение длины 10 км.

Выгоден 1 вариант, его берем за основу и включаем пункт Д (сумма 101).

  1.  А-Д-Б-В-И-М-А, приращение длины 26 км;
  2.  А-Б-Д-В-И-М-А, приращение длины 8 км;
  3.  А-Б-В-Д-И-М-А, приращение длины 0 км;
  4.  А-Б-В-И-Д-М-А, приращение длины 14 км;
  5.  А-Б-В-И-М-Д-А, приращение длины 24 км.

В данном случае наиболее целесообразен 3 вариант, где приращение длины маршрута равно 0, его берем за основу и включаем пункт З (сумма 100).

  1.  А-З-Б-В-Д-И-М-А, приращение длины 24 км;
  2.  А-Б-З-В-Д-И-М-А, приращение длины 25 км;
  3.  А-Б-В-З-Д-И-М-А, приращение длины 26 км;
  4.  А-Б-В-Д-З-И-М-А, приращение длины 4 км;
  5.  А-Б-В-Д-И-З-М-А, приращение длины 3 км;
  6.  А-Б-В-Д-И-М-З-А, приращение длины 16 км.

34

При наличии циклов и (или) когда загруженных клеток больше, чем n+m-1, то одну из клеток необходимо сделать незагруженной. Для этого строят один из возможных контуров и нумеруют его углы (по ходу часовой стрелки). Затем определяют сумму расстояний перевозки для клеток, в которых лежат углы контура с четными и нечетными номерами. Из числа клеток с наибольшей суммой расстояний перевозок выявляется клетка с наименьшим значением объема перевозок. Значение объема перевозок в выявленной клетке вычитается из объемов загрузки клеток с наибольшей суммой расстояний перевозок и прибавляется к объемам загрузки каждой из клеток, для которых сумма расстояний меньше.

Рисунок 2 -  Транспортные связи, соответствующие

оптимальному плану

11

Практическая работа 3

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

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

Исходными данными для практической работы являются:

  •  оптимальный план закрепления потребителей щебня за поставщиками, полученный в практической работе 2;
  •  объемы производства и потребления песка из табл. П3 и табл. П4 индивидуального задания.

Оптимальный план закрепления потребителей щебня за поставщиками дополняется поставщиками и потребителями песка. Полученная табл. 5 является планом перевозок щебня и песка.

Таблица 5 - План перевозок щебня и песка

Постав-щики

Потребители

Объем производства, т.

В

И

Л

Ж

З

Е

А

19

22

15

9

90

11

45

17

15

150

Б

150

9

50

21

12

14

17

18

200

Г

25

17

160

4

6

12

10

160

Н

10

150

11

15

14

100

7

10

250

Д

4

17

21

23

13

200

16

200

К

12

9

14

13

6

50

9

50

Объем потребления, т

150

200

175

90

145

250

1010

По заданию преподавателя или самим студентом (для заочников) выбирается марка автомобиля-самосвала и определяется количество ездок с грузом по формуле:

Qij

nегij = ——— ,                                                      (5)

q γij

12

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

Таблица 29–Развозочные маршруты движения автомобилей,

полученные по кратчайшей связывающей сети

Маршрут движения

Загрузка, т.

Длина маршрута, км

      0.2+0.3+0.1+0.3+0.3+0.1+0.2+0.1=

1. А- Б – В – Д – Н -   К -  З -  И  - М - А

     10+ 9+  4  + 6 + 2  +   6 + 8 + 20 + 16=

=1.7

=81

       0.3+0.2+0.4+0.4=

2. А - Е -  Ж – Л -  Г - А

     15 + 4 + 2 +   4 + 6=

=1.2

=31

ИТОГО

2.9

112

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

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

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

33

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

Столбец

Б

В

Д

И

М

Ряд VIII

10

10

6

7

7

Строка

А

Н

Н

Е

Л

Наименьшее число 6 соответствует звену Н-Д, его занесем в табл. 28. Сравним числа строки Д с числами ряда VIII, получим ряд IX.

Столбец

Б

В

И

М

Ряд IX

10

4

7

7

Строка

А

Д

Е

Л

Наименьшее число 4 соответствует звену Д-В, его занесем в табл. 28. Сравним числа строки В с числами ряда IX, получим ряд X.

Столбец

Б

И

М

Ряд X

9

7

7

Строка

В

Е

Л

Наименьшее число 7 соответствует звеньям Е-И и Л-М, любое из них (например, Е-И) занесем в табл. 28. Сравним числа строки И с числами ряда X, получим ряд XI.

Столбец

Б

М

Ряд XI

9

7

Строка

В

Л

Наименьшее число 7 соответствует звену Л-М, его занесем в табл. 28 Последний XII ряд:

Столбец

Б

Ряд XII

9

Строка

В

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

Порядковый номер звена

Звено

Длина звена, км

Порядковый номер звена

Звено

Длина звена, км

1

А-Г

6

7

К-Н

2

2

Г-Л

4

8

Н-Д

6

3

Л-Ж

2

9

Д-В

4

4

Ж-Е

4

10

Е.И

7

5

Е-З

3

11

Л-М

7

6

З-К

6

12

В-Б

9

Кратчайшая связывающая сеть представлена на рис. 5.

При наборе пунктов в маршруты по кратчайшей связывающей сети процесс необходимо начинать от пункта, наиболее удаленного от отправителя. Результаты набора пунктов в маршруты по кратчайшей связывающей сети (с попыткой одновременно определить последовательность их объезда) приведены в табл. 29.

32

где nегij - количество ездок с грузом между i-ым поставщиком и j-ым потребителем;

  q – грузоподъемность автомобиля-самосвала, т;

 γij – коэффициент использования грузоподъемности при перевозке грузов между i-ым поставщиком и j-ым потребителем.

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

Таблица 6- План ездок с грузом при перевозке щебня и песка

Постав-щики

Потребители

Число ездок от постав-щиков

В

И

Л

Ж

З

Е

А

19

22

3

9

18

11

9

17

15

30

Б

30

9

10

21

12

14

17

18

40

Г

25

17

32

4

6

12

10

32

Н

10

30

11

15

14

20

7

10

50

Д

4

17

21

23

13

40

16

40

К

12

9

14

13

6

10

9

10

Число ездок к потребителям

30

40

35

18

29

50

202

Учитывая, что количество автомобилей с грузом, убывающих от каждого поставщика, должно обязательно равняться количеству порожних автомобилей, прибывающих к нему (так же как и количество автомобилей с грузом, прибывающих к каждому потребителю, должно обязательно равняться количеству порожних автомобилей, убывающих от него), можно составить оптимальный план ездок без груза (порожних). Для этого исходные данные должны быть сведены в табл. 7. Методика получения оптимального плана изложена в практической работе 2. С использованием метода МОДИ получен оптимальный план ездок без груза (план возврата порожних автомобилей), который представлен в табл. 8.

Для составления рациональных маршрутов перевозок целесообразно использовать метод "совмещенных планов". Сущность его состоит в том, что в одной и той же таблице совмещается и план ездок с грузом (табл. 6) и оптимальный  план  ездок без груза  (табл. 8).   Совмещенный  план  представлен  в

13

Таблица 7- Первоначальный (опорный) план ездок без груза

Постав-щики

Потребители

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

В

И

Л

Ж

З

Е

VВ=3

VИ=16

VЛ=9

VЖ=11

VЗ=12

VЕ=15

А

UА=0

19

22

*

3

9

11

17

27

15

30

Б

UБ=3

*

9

21

12

18

14

17

22

18

40

Г

UГ=-5

25

17

**

32

4

*

6

12

10

32

Н

UН=-5

10

31

11

15

14

*

19

7

10

50

Д

UД=1

**

30

4

9

17

21

23

13

1

16

40

К

UК=-6

12

*

9

14

13

**

10

6

*

9

10

Число ездок к потребителям

30

40

35

18

29

50

202

LПОР=3*9+27*15+18*14+22*18+32*4+31*11+19*7+30*4+9*17+1*16+10*6=2031 км

Таблица -8 Оптимальный план ездок без груза

Постав-щики

Потребители

Число ездок от постав-щиков

В

И

Л

Ж

З

Е

VВ=3

VИ=16

VЛ=9

VЖ=11

VЗ=

VЕ=15

А

UА=0

19

22

9

11

17

30

15

30

Б

UБ=3

9

21

3

12

18

14

17

19

18

40

Г

UГ=-5

25

17

32

4

6

12

10

32

Н

UН=-5

10

21

11

15

14

29

7

10

50

Д

UД=1

30

4

9

17

21

23

13

1

16

40

К

UК=-7

12

10

9

14

13

6

9

10

Число ездок к потребителям

30

40

35

18

29

50

202

LПОР=30*15+3*12+18*14+19*18+32*4+21*11+29*7+30*4+9*17+1*16+10*9=2021

табл. 9. Здесь в правом нижнем углу клеток жирным шрифтом записаны ездки с грузом, а в левом верхнем углу курсивом – ездки без груза (для обозначения ездок лучше использовать различные цвета, например, синим – ездки с грузом, а красным – ездки без груза).

14

соединяются дважды. Следовательно, кратчайшая связывающая сеть, соединяющая n пунктов, имеет (n-1) звеньев.

Построение кратчайшей связывающей сети необходимо начать с первой точки (пункта отправления А). Выпишем из табл. 12 первую строку (строку А), при этом сверху обозначим столбцы, а снизу – строки.

Столбец

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

Н

Ряд I

10

19

6

23

15

11

17

22

22

9

16

20

Строка

А

А

А

А

А

А

А

А

А

А

А

А

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

Столбец

Б

В

Д

Е

Ж

З

И

К

Л

М

Н

Ряд II

10

19

23

10

6

12

17

18

4

11

19

Строка

А

А

А

Г

Г

Г

Г

Г

Г

Г

Г

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

Столбец

Б

В

Д

Е

Ж

З

И

К

М

Н

Ряд III

10

19

21

6

2

8

13

14

7

15

Строка

А

А

Л

Л

Л

Л

Л

Л

Л

Л

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

Столбец

Б

В

Д

Е

З

И

К

М

Н

Ряд IV

10

19

20

4

7

11

13

7

14

Строка

А

А

Ж

Ж

Ж

Ж

Ж

Л

Ж

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

Столбец

Б

В

Д

З

И

К

М

Н

Ряд V

10

19

16

3

7

9

7

10

Строка

А

А

Е

Е

Е

Е

Л

Е

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

Столбец

Б

В

Д

И

К

М

Н

Ряд VI

10

17

7

6

7

7

Строка

А

З

З

Е

З

Л

З

Наименьшее число 6 соответствует звену З-К, его занесем в табл. 28. Сравним числа строки К с числами ряда VI, получим ряд VII.

Столбец

Б

В

Д

И

М

Н

Ряд VII

10

12

8

7

7

2

Строка

А

К

К

Е

Л

К

31

Практическая работа 5

Разработка рациональных развозочно-сборочных маршрутов движения автомобилей

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

В качестве исходных данных необходимо использовать транспортную сеть, матрицу кратчайших расстояний (см. табл. 1) и объемы завоза грузов потребителям из табл. П5 задания. Для выполнения перевозок имеется один автомобиль грузоподъемностью 1.7 тонны. Таким образом, для того, чтобы вывезти от отправителя А и завезти всем 12 получателям (Б, В, Г,…, Н) 2.9 тонны груза, необходимо составить 2 маршрута движения (2.9:1.7≈2, округляем, естественно, в большую сторону).

Для начала необходимо составить искомые маршруты движения, ориентируясь на заданную транспортную сеть так, чтобы они имели насколько возможно минимальную суммарную длину (т.е. визуально). Пример составленных таким образом маршрутов приведен в табл. 27.

Таблица 27–Развозочные маршруты движения автомобилей,

составленные визуально

Маршрут движения

Загрузка, т.

Длина маршрута, км

      0.4+0.4+0.2+0.3+0.1+0.1+0.2 =

1. А –Г – Л – Ж –  Е – З – М  – Б - А

      6 + 4 + 2 +  4 +  3 +15 + 16 +10 =

=1.7

=60

     0.3+0.1+0.3+0.3+0.2   =

2. А - В-Д – Н –  К  - И - А

     19+4+ 6 +  2 +  9 + 22=

=1.2

=62

ИТОГО

2.9

122

Далее необходимо составить по этим же исходным данным развозочные маршруты в соответствии с методикой, изложенной в [ 2 ]. Решение задачи при этом разделяется на 2 этапа. На 1 этапе, учитывая, что маршрутов будет 2, необходимо произвести набор пунктов в маршруты, то есть определить, какие из 12 пунктов завоза будут входить в 1ый маршрут, а какие во 2ой. Для этого используется кратчайшая связывающая сеть. На 2 этапе необходимо определить последовательность объезда пунктов в каждом из маршрутов. Для этого могут быть использованы методы "ветвей и границ" или "суммирования по столбцам".

Разработку кратчайшей связывающей сети покажем на примере рис. П1 и табл. 12. Кратчайшая связывающая сеть представляет собой сеть улиц (дорог), имеющих наименьшую длину, соединяющих несколько пунктов. Существует простой алгоритм нахождения кратчайшей связывающей сети. Прежде всего, находят на транспортной сети звено наименьшей длины. На каждом следующем шаге добавляют звено самой малой длины, при присоединении которого к уже выбранным  звеньям  замкнутого  пути  (контура)  не образуется,  то есть звенья не

30

Таблица 9- Совмещенный план ездок с грузом и ездок без груза

Постав-щики

Потребители

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

В

И

Л

Ж

З

Е

А

3

18

9

30

30

30

Б

30

10

3

18

19

40

40

Г

32

32

32

32

Н

21

29

50

30

20

50

Д

30

9

1

40

40

40

К

10

10

10

10

Число ездок к потребителям

30

40

35

18

29

50

202

30

40

35

18

29

50

202

Формирование маршрутов производится следующим образом. Вначале выбираются маятниковые маршруты с обратным порожним пробегом. Они соответствуют клеткам из совмещенного плана, где одновременно расположены 2 цифры – ездки с грузом и ездки без груза. Такими клетками в табл. 9 являются:

  •  клетка ГЛ, ей соответствует маятниковый маршрут с обратным порожним пробегом Г-Л-Г с числом оборотов 32;
  •  клетка НИ, маршрут Н-И-Н с числом оборотов 21;
  •  клетка НЗ, маршрут Н-З-Н с числом оборотов 20;
  •  клетка ДЕ, маршрут Д-Е-Д с числом оборотов 1.

Далее совмещенный план переписывается заново уже без маятниковых маршрутов (табл. 10). Из него выбираются кольцевые маршруты. Для этого в совмещенном плане составляются сначала 4-х, затем 6-ти, 8-ми и т.д. угольные контуры. Все вершины этих контуров лежат в загруженных клетках, причем ездки с грузом (цифры, выделенные жирным шрифтом) обязательно чередуются с ездками без груза (цифры, выделенные курсивом). В рассматриваемом примере кольцевыми будут маршруты:

1. Б-В-Д-Е-Б с числом оборотов 19 (контур показан жирной линией);

2. Н-И-Д-Е-А-З-Н с числом оборотов 9 (контур показан тонкой линией);

15

Таблица 10- Совмещенный план ездок с грузом и ездок без груза

Постав-щики

Потребители

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

В

И

Л

Ж

З

Е

А

3

18

9

30

30

30

Б

30

10

3

18

19

40