Метод кларка райта – Оптимизация транспортной работы, связанной с грузоперевозками, методами линейного программирования

Содержание

2.2. Маршрутизация мелкопартионных перевозок (метод Кларка-Райта)

Цель: определить рациональные маршруты при доставке грузов мелкими партиями.

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

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

На каждом последующем шаге два маршрута объединяют в один. В результате объединения двух маятниковых маршрутов появляется один развозочный. Из полученных маятниковых и развозочных мар­шрутов выбирают такие два, которые после объединения обеспечивают наибольшее сокращение суммарных затрат.

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

Рассмотрим решение данной задачи на примере: имеется 8 потребителей груза, потребности завоза которых указаны в первом столбце табл. 2.1. Выделено пять автомобилей грузоподъемностью 4,5 т (ЛуАЗ-890Б) и три автомобиля грузоподъемностью 1,75 т (ГЗСА-3702).

В каждом столбце Рi (табл. 2.1) указывают рас­стояние от iго пункта до любого другого (Р

i+1, Рi+2…). Так как матрица кратчайших расстояний симметрична, то достаточно одной половины матрицы.

Таблица 2.1

Расстояния между пунктами

Потр., т

P0

0,89

10

P1

0,79

15

3

P2

0,84

20

11

8

P3

0,96

25

18

19

11

P4

1

30

2

10

15

4

P5

0,17

23

6

2

10

11

9

P6

0,61

19

8

7

5

12

6

11

P7

0,91

30

10

13

4

3

5

3

7

P8

Рассчитывают величины, характеризующие выигрыши в расстоянии, которые получают в резуль­тате объединения соответствующих маршрутов в один, и заносят их в табл. 2.2.

Таблица 2.2

Выигрыши при объединении пунктов

Потр., т

P0

0,89

10

P1

0,79

15

22

P2

0,84

20

19

27

P3

0,96

25

17

21

34

P4

1

30

38

35

35

51

P5

0,17

23

27

36

33

37

44

P6

0,61

19

21

27

34

32

43

31

P7

0,91

30

30

32

46

52

55

50

42

P8

Расчет выигрыша в расстоянии рассмотрим на примере элемента, стоящего в столбце Р4 и строке Р8. Этот элемент соответствует объединению маршрутов Р0 – Р4 – Р0 и Р0 – Р8 – Р0, в результате которого получается маршрут Р0 – Р4 – Р8 – Р0 .

В новом маршруте вместо расстояния от пункта Р4 к пункту Р

0 и от пункта Р0 к пункту Р8 (25+30=55 км) используют расстояние от пункта Р4 к пункту Р8 (3 км). Следовательно, выигрыш от объединения этих маршрутов в один составляет 55-3=52 км, что и указано в рассматриваемой клетке.

Поскольку для дальнейших расчетов необходимо знать только величины выигрышей, представляют их отдельно (см. табл. 2.2). Кроме того, присоединяют к матрице выигрышей отдельный столбец индикаторов (I) пунктов Рi. Величины, стоящие в этом столбце, принимают значения 0; 1 или 2. Индикатор строки Рi показывает, является пункт внутренним (0), первым или последним (1) в некотором развозочном маршруте, или он включается в маятниковый маршрут (2), т.е. маршрут вида Р0 – Рi– Р0.

Из табл. 2.2 видно, что наибольший выигрыш (55 км) достигается при преобразовании (объединении) маятниковых маршрутов Р0– Р

5 – Р0 и Р0 – Р8 – Р0 в развозочный Р0 – Р5 – Р8 – Р0 (табл. 2.3). Для развозочного маршрута Р0 – Р5 – Р8 – Р0 требуется автомобиль грузоподъемностью 1,91 т и более (1+0,91=1,91 т). Такой автомобиль имеется, поэтому объединение возможно.

Таблица 2.3

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

0,79

2

22

P2

0,84

2

19

27

P3

0,96

2

17

21

34

P4

1

2

38

35

35

51

P5

0,17

2

27

36

33

37

44

P6

0,61

2

21

27

34

32

43

31

P7

0,91

2

30

32

46

52

55

50

42

P8

После объединения в соответствующих строках меняют элементы первого и второго столбцов. В первых клетках обеих строк записывают число 1,91 (загрузка автомобиля на маршруте Р0– Р5 – Р8 – Р0). Индикаторы строк Р5 и Р8 примут значение 1 (вместо 2). Эти изменения в нашем примере вносят в исходную матрицу. Кроме того, необходимо следить за изменением числа свободных и занятых автомобилей различной грузоподъемности.

На следующем этапе объединяют в маршрут Р0 – Р5 – Р8 – Р4 – Р0 маршруты Р0 – Р4 – Р0 и Р0 – Р5 – Р8 – Р0. Это объединение дает наибольший теперь выигрыш – 52 км (табл. 2.4). При этом вместо двух автомобилей используют один грузоподъемностью 4,5 т (0,96+1,91=2,87 т).

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

Таблица 2.4

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

0,79

2

22

P2

0,84

2

19

27

P3

0,96

2

17

21

34

P4

1,91

1

38

35

35

51

P5

0,17

2

27

36

33

37

44

P6

0,61

2

21

27

34

32

43

31

P7

1,91

1

30

32

46

52

0

50

42

P8

Теперь максимальному выигрышу (44 км) соответствует объединение маршрутов Р0 – Р6 – Р0 и Р0 – Р5 – Р8 – Р4 – Р0 в развозочный Р0 – Р6 – Р5 – Р8 – Р4 – Р0. Объем перевозок на маршруте при этом станет 0,17+2,87= =3,04 т (табл. 2.5).

На следующих этапах объединяют маршруты Р0 – Р2 – Р0 и Р0 – Р6 – Р5 – Р8 – Р4 – Р0 в развозочный Р0 – Р2 – Р6 – Р5 – Р8 – Р4 – Р0 (выигрыш 36 км) и Р0 – Р7 – Р0 и Р0 – Р2 – Р6 – Р5 – Р8 – Р4 – Р0 в развозочный Р0 – Р2 – Р6 – Р5 – Р8 – Р4 – Р7 – Р0 (выигрыш 32 км). В первом случае объем перевозок на маршруте составит 0,79+3,04= 3,83 т (табл. 2.6), а во втором случае – 0,61+3,83=4,44 т (табл. 2.7). Дальнейшее объединение маршрутов невозможно, так как отсутствует автомобиль грузоподъемностью более 4,5 т, поэтому маршрут Р0 – Р2 – Р6 – Р5 – Р8 – Р4 – Р7 – Р0 считают законченным и за ним закрепляют автомобиль грузоподъемностью 4,5 т.

Таблица 2.5

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

0,79

2

22

P2

0,84

2

19

27

P3

2,87

1

17

21

34

P4

2,87

1

38

35

35

51

P5

0,17

2

27

36

33

37

44

P6

0,61

2

21

27

34

32

43

31

P7

0

30

32

46

0

0

50

42

P8

Таблица 2.6

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

0,79

2

22

P2

0,84

2

19

27

P3

3,04

1

17

21

34

P4

0

38

35

35

51

P5

3,04

1

27

36

33

37

0

P6

0,61

2

21

27

34

32

43

31

P7

0

30

32

46

0

0

50

42

P8

Таблица 2.7

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

3,83

1

22

P2

0,84

2

19

27

P3

3,83

1

17

21

34

P4

0

38

35

35

51

P5

0

27

0

33

37

0

P6

0,61

2

21

27

34

32

43

31

P7

0

30

32

46

0

0

50

42

P8

На следующем этапе объединяют оставшиеся маршруты Р0 – Р1 – Р0 и Р0 – Р3 – Р0 в развозочный Р0 – Р1 – Р3 – Р0 (выигрыш 19 км). Объем перевозок на маршруте при этом станет 0,89+0,84= 1,73 т (табл. 2.8). Так как нет больше пунктов для объединения, то маршрут Р0 – Р1 – Р3 – Р0 считают законченным и за ним закрепляют автомобиль грузоподъемностью 1,75 т. Следовательно, для перевозок используют один автомобиль грузоподъемностью 4,5 т (Луаз-890Б) и один автомобиль грузоподъемностью 1,75 т (ГЗСА-3702).

Таблица 2.8

Выигрыши при объединении пунктов

Потр., т

I

0,89

2

P1

4,44

1

22

P2

0,84

2

19

27

P3

0

17

21

34

P4

0

38

35

35

51

P5

0

27

0

33

37

0

P6

4,44

1

21

27

34

0

43

31

P7

0

30

32

46

0

0

50

42

P8

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

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

В качестве исходных данных необходима матрица кратчайших расстояний между точками маршрута. Для маршрута № 1 (Р0 – Р2 – Р6 – Р5 – Р8 – Р4 – Р7 – Р0) она приведена в табл. 2.9.

В итоговой строке табл. 2.9 проставляют сумму расстояний в каждом столбце. Затем выбирают три начальных пункта, имеющих максимальные суммы в столбцах (пункты 0, 4 и 2). Они образуют кольцевой маршрут 0 – 4 – 2 – 0. В него включают следующий пункт с максимальной суммой в столбце – пункт 5. Чтобы определить, между какими пунктами его следует вставить, необходимо найти минимально возможное увеличение длины маршрута  lij, обусловленное включением пункта 5. Величину  lij находят по формуле

lkj=lki+lijlkj, (2.1)

где lki, lij, lki – расстояние между соответствующими пунктами, км;

k, j – пункты, между которыми предполагается вставка;

i – вставляемый пункт.

В данном случае пункт 5 можно вставить между парами пунктов (0,4), (4,2) и (2,0). Например, для первой пары формула (2.1) будет иметь вид l0-4=l0-5+l5-4-l0-4.

Таблица 2.9

Матрица кратчайших расстояний

Пункты

Кратчайшие расстояния между пунктами, км

P0

P2

P6

P5

P8

P4

P7

P0

15

23

30

30

25

19

P2

15

2

10

13

19

7

P6

23

2

9

3

11

11

P5

30

10

9

5

4

6

P8

30

13

3

5

3

7

P4

25

19

11

4

3

12

P7

19

7

11

6

7

12

СУММА

142

66

59

64

61

74

62

При подстановке расстояний из матрицы (табл. 2.9) получим l0-4=30+4-25=9. Для остальных двух пар l4-2=4+10-19=-5; l2-0=10+30–15=25. Минимальное значение (l4-2 =-5) определяет место вставки: пункт 5 включают в маршрут между пунктами 4 и 2. Маршрут примет вид 0-4-5-2-0. Следующее по величине значение в итоговой строке матрицы соответствует пункту 7. Его можно вставить между парами пунктов (0,4), (4,5), (5,2) и (2,0). Подсчитаем изменения длины маршрута: l0-4=l0-7+l7-4-l0-4=19+12-25=6; l4-5=12+6-4=14; l5-2=6+7-10=3; l2-0=7+19-15=11. Пункт 7 вставляют между пунктами 5 и 2. Получают маршрут 0-4-5-7-2-0.

На следующем этапе вставляют пункт 8. Производят аналогичный расчёт. Минимальное значение имеет l4-5=4. Следовательно, пункт 8 вставляют между пунктами 4 и 5 и получают маршрут 0-4-8-5-7-2-0.

В заключение вставляют пункт 6. Произведя вычисления, получают, что минимальное значение имеет l7-2=6. Поэтому пункт 6 вставляют между пунктами 7 и 2 и окончательно получают маршрут 0-4-8-5-7-6-2-0. Аналогичным образом определяют порядок объезда пунктов на маршруте №2 (Р0 – Р1 – Р3 – Р0).

studfiles.net

Метод Кларка-Райта. Оптимальное планирование маршрутов грузоперевозок

ВВЕДЕНИЕ

ПОСТАНОВКА ЗАДАЧИ

ПОДГОТОВИТЕЛЬНАЯ РАБОТА

ПОШАГОВОЕ ОПИСАНИЕ АЛГОРИТМА КЛАРКА_РАЙТА

ОПИСАНИЕ ПОСЛЕДОВАТЕЛЬНОГО РЕШЕНИЯ МЕТОДОМ КЛАРКА_РАЙТА

РЕЗУЛЬТАТЫ РЕШЕНИЯ


ВВЕДЕНИЕ.
Описанный метод используется в программе “Простое формирование маршрутов. Работа с картой. Расчет оптимальных вариантов доставки”

  

В статье “Оптимизация планирования доставки грузов. Алгоритм кластеризации k-means (метод K-средних)“ было показано, КАК ПОЛУЧИТЬ ОПТИМАЛЬНЫЕ МАРШРУТЫ ДЛЯ ЗАДАННОГО КОЛИЧЕСТВА А/ТРАНСПОРТА из указанного места отгрузки, при этом грузоподъемность транспорта не принималась во внимание .
В этой статье покажем КАК УЗНАТЬ КОЛИЧЕСТВО НЕОБХОДИМОГО А/ТРАНСПОРТА С УЧЕТОМ ЕГО ГРУЗОПОДЪЕМНОСТИ ДЛЯ ФОРМИРОВАНИЯ ОПТИМАЛЬНЫХ МАРШРУТОВ.

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

Сформулированная задача известна как «задача коммивояжера». Существует множество математических методов, позволяющих найти как точное, так и приближенное решение поставленной задачи. Среди методов, дающих точное решение, наиболее известны:

  • «полный перебор»
  • «метод ветвей и границ» 

Основным недостатком данных методов является высокая временная и емкостная сложность, что важно учитывать при большом количестве пунктов. Все эффективные (сокращающие полный перебор) методы решения «задачи коммивояжера» – методы эвристические. Из них наибольшее применение нашли:

  • «метод генетических алгоритмов» 
  • «метод Кларка-Райта» 
  • «алгоритм муравьиной колонии» 
  • «метод ближайшего соседа» 
  • «метод включения ближайшего города» 
  • «метод самого дешевого включения» 

Для решения нашей задачи наиболее приемлемым методом является метод Кларка-Райта. Он относится к числу приближенных, итерационных методов и может использоваться для компьютерного решения задачи развозки. Погрешность решения не превосходит в среднем 5–10 %. Достоинствами метода являются его простота, надежность и гибкость, что позволяет учитывать целый ряд дополнительных факторов, влияющих на конечное решение задачи.

Рассмотрим на примере, как применять метод Кларка-Райта. 

ПОСТАНОВКА ЗАДАЧИ.

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

Таблица 1. Координаты и объем спроса получателей

Координаты грузового терминала (склада): x0 = 10, y0 = 15. Для доставки будет использоваться транспорт с максимальной грузовместимостью = 1500 шт.

ВОПРОС: Какое количество транспорта понадобится для развозки грузов ? Какая схема развозки будет оптимальной ?

ПОДГОТОВИТЕЛЬНАЯ РАБОТА.

Отметим эти точки в декартовой системе координат. Местоположение оптовой базы и 12 получателей, а также объем поставок каждому получателю приведены на рисунке 1. 

Рисунок 1. Расположение базы и пунктов доставки

Начальная схема маршрутов предполагает что для доставки груза каждому отдельному получателю организуется отдельный маршрут (см. рис. 2). Например, водитель загружает в кузов партию 450 шт. и везет ее в пункт 1, там разгружается, затем возвращается на базу, берет вторую партию 400 шт. и везет ее в пункт 2 и т.д. Таким образом, исходная схема развозки включает в себя только радиальные маршруты движения автомобиля, причем количество радиальных маршрутов совпадает с количеством получателей. В данном случае, схема развозки состоит из 12 радиальных маршрутов.

 

Рисунок 2. Начальная схема доставки груза

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

 Рисунок 3. Схемы доставки

На рисунке 3. отображены две схемы доставки. Схема доставки А (слева) обеспечивает доставку грузов в пункты 1 и 2 по радиальным маршрутам. В этом случае суммарный пробег автотранспорта равен:

 La = d01 + d10 + d02 + d20 = 2d01 + 2d02

Схема доставки B предполагает доставку грузов в пункты 1 и 2 по кольцевому маршруту. Тогда пробег автотранспорта составляет:

 Lв = d01 + d12 + d02

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

 S12 = La – Lв = d01 + d02 – d12

В общем случае мы имеем километровый выигрыш:

 Sij = d0i + d0j – dij

где Sij – километровый выигрыш, получаемый при объединении пунктов i и j, км; d0i, d0j – расстояние между оптовой базой и пунктами i и j соответственно, км; dij – расстояние между пунктами i и j, км. 

 Полученные значения заносятся в таблицу 2., где представлены расстояния между пунктами dij (правая верхняя часть матрицы) и километровые выигрыши Sij (левая нижняя часть матрицы).

 

Таблица 2. Матрица расстояний и километровых выигрышей

Теперь вернемся к нашему примеру. Из табл. 1 возьмем данные:

  • Пункт 0 (это база): x0 = 10, y0 = 15
  • Пункт 1: х1 = 17, у1 = 15
  • Пункт 2: х2 = 6, у2 = 15
  • Пункт 3: x3 = 13, y3 = 3
  • и т.д.

Рассчитаем расстояние d01 между пунктами 0 и 1 по формуле:

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

  • для пунктов 0 и 2: d02 = 4
  • для пунктов 0 и 3: d03 = 12,37
  • для пунктов 1 и 2: d12 = 11
  • для пунктов 1 и 3: d13 = 12,65
  • для пунктов 2 и 3: d23 = 13,89
  • и т.д

Потом для пунктов i и j получаем километровый выигрыш  Sij = d0i + d0j – dij:

  • для пунктов 1 и 2: S12 = d01 + d02 – d12 = 7 + 4 – 11 = 0
  • для пунктов 1 и 3: S13 = d01 + d03 – d13 = 7 + 12.37 – 12.65 = 6.72
  • для пунктов 2 и 3: S13 = d02 + d03 – d23 = 4 + 12.37 – 13.89 = 2.48
  • и т.д.

Полученные значения заносим в таблицу 3., где представлены расстояния между пунктами dij (правая верхняя часть матрицы) и километровые выигрыши sij (левая нижняя часть матрицы):

 

Таблица 3. Расчетная матрица расстояний и километровых выигрышей

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

ПОШАГОВОЕ ОПИСАНИЕ АЛГОРИТМА КЛАРКА-РАЙТА.

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

Шаг 1.

На матрице километровых выигрышей находим ячейку (i*, j*) с максимальным километровым выигрышем Smax:

 

При этом должны соблюдаться следующие три условия:

  1. пункты i* и j* не входят в состав одного и того же маршрута;
  2. пункты i* и j* являются начальным и/или конечным пунктом тех маршрутов, в состав которых они входят;
  3. ячейка (i*, j*) не заблокирована (т.е. рассматривалась на предыдущих шагах алгоритма).

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

Шаг 2.

Маршрут, в состав которого входит пункт i*, обозначим как маршрут 1. Соответственно, маршрут, в состав которого входит пункт j*, обозначим как маршрут 2.

Введем следующие условные обозначения:

N = {1, 2, …, n} – множество получателей;

 – подмножество пунктов, входящих в состав маршрута 1;

 – подмножество пунктов, входящих в состав маршрута 2.

Очевидно, что  (согласно шагу 1, условие 1).

Рассчитаем суммарный объем поставок по маршрутам 1 и 2:


где qk – объем спроса k-го пункта, шт (см табл. 4).

Шаг 3.

Проверим на выполнение следующее условие:

где c – грузовместимость автомобиля, шт.

Если условие выполняется, то переход к шагу 4, если нет – к шагу 5.

Шаг 4.

Производим объединение маршрутов 1 и 2 в один общий кольцевой маршрут X. Будем считать, что пункт i* является конечным пунктом маршрута 1, а пункт j* – начальным пунктом маршрута 2. При объединении маршрутов 1 и 2 соблюдаем следующие условия:

  • последовательность расположения пунктов на маршруте 1 от начала и до пункта i* не меняется;
  • пункт i* связывается с пунктом j*;
  • последовательность расположения пунктов на маршруте 2 от пункта j* и до конца не меняется.

Шаг 5.

Повторяем шаги 1-4 до тех пор, пока при очередном повторении не удастся найти Smax, который удовлетворяет трем условиям из шага 1.

Шаг 6.

Рассчитываем суммарный пробег автотранспорта.

ОПИСАНИЕ ПОСЛЕДОВАТЕЛЬНОГО РЕШЕНИЯ МЕТОДОМ КЛАРКА_РАЙТА.

Весь ход последовательного решения задачи представлен в таблице 4.

 Таблица 4. Ходы и промежуточные результаты решения задачи

Графа 1 – номер итерации.

Графы 2, 3 – номера пунктов i* и j*, которые обозначают ячейку с максимальным километровым выигрышем Smax = s(i*,j*), найденную в результате просмотра матрицы километровых выигрышей (см. табл. 3).

Графа 4 – значение максимального километрового выигрыша Smax.

Графы 5, 6 и 7 – результаты проверки условий 1, 2 и 3 при выполнении шага 1. “+” – положительный результат, “–” – отрицательный результат.

Графы 8 и 9 – объем перевозок по маршруту 1, в состав которого входит пункт i* (q1), и маршруту 2, в состав которого входит пункт j* (q2).

Графа 10 – проверка на условие , где c – грузовместимость транспортного средства. “+” – положительный результат проверки условия, “–” – отрицательный результат.

Графа 11 – порядковый номер кольцевого маршрута (всего в ходе решения получено всего четыре кольцевых маршрута, см. рис. 4).

Графа 12 – структура кольцевого маршрута, образовавшегося на данной итерации.

Рисунок 4. Графическое представление оптимальной схемы доставки

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

L0 = 2*d01 + 2*d02 + … + 2*d012 = 2*7.0 + 2*4.0 + 2*12.4 + 2*5.1 + … + 2*7.3 = 195 км.

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

 

Итерация 1.

  • Объединяем два радиальных маршрута:  0-8-0 (объем доставки 200 шт.) и 0-3-0 (объем доставки 400 шт.) в общий кольцевой маршрут (под № 1) 0-8-3-0 (объем доставки 600 шт.). При этом суммарный пробег автотранспорта сокращается на 23,0 км.

Итерация 2.

  • К кольцевому маршруту № 1– 0-8-3-0 (600 шт.) присоединяем радиальный маршрут 0-5-0 (150 шт.). При этом пункт 5 присоединяем к пункту 8, в результате чего получаем новую структуру кольцевого маршрута 0-5-8-3-0 (750 шт.). Суммарный пробег автотранспорта сокращается еще на 21,4 км. 
  • Отметим важность соблюдения последовательности пунктов в кольцевом маршруте: именно 0-5-8-3-0, а не 0-5-3-8-0 или 0-8-3-5-0.
  • Если i* = 8 и j* = 5, то после объединения они должны стоять на маршруте друг за другом.

 Итерация 3.

  • Объединение пунктов 3 и 5 обеспечило бы выигрыш в 17,2 км. Но это объединение невозможно, поскольку оба пункта уже входят в состав кольцевого маршрута №1 – 0-5-8-3-0, а объединять можно пункты только из разных маршрутов. Таким образом, констатируем нарушение условия 1 и переходим к следующей итерации.

 Итерация 4.

  • К кольцевому маршруту № 1 – 0-5-8-3-0 (750 шт.) присоединяем радиальный маршрут 0-12-0 (150 шт.). При этом пункт 12 присоединяем к пункту 3, в результате чего получаем новую структуру кольцевого маршрута 0-5-8-3-12-0 (1300 шт.). Суммарный пробег автотранспорта сокращается на 14,6 км.

 Итерация 5.

  • Пункты 12 и 8 не объединяем, поскольку они уже входят в состав кольцевого маршрута 1 (нарушается условие 1).

 Итерация 6.

  • Объединяем два радиальных маршрута:  0-1-0 (450 шт.)  и 0-11-0 (475 шт.) в общий кольцевой маршрут (под № 2) 0-11-1-0 (925 шт.). При этом суммарный пробег автотранспорта сокращается на 13,4 км.

 Итерация 7.

  • Пункты 3 и 6 нельзя объединить по причине нарушения условия 2. Пункт 3 входит в состав кольцевого маршрута 1, и в этом маршруте он занимает «промежуточное» положение, то есть он связан с пунктами 8 и 12: 0-5-8-3-12-0. Радиальный маршрут 0-6-0 можно было бы присоединить к кольцевому маршруту 1 со стороны его «крайних» пунктов – 5 или 12, но к «промежуточным» пунктам 3 и 8 его присоединить нельзя.

 Итерации с 8 по 20

  • Повторяют ту же логику рассуждений, что и в предыдущих 7 итерациях. Отметим только, что на итерациях 9, 11, 12, 16 и 18 объединение не производится только по причине нарушения условия 

 Итерации с 21 по 60

  • Уже не имеют смысла, поскольку их выполнение уже не повлечет за собой изменение плана развозки.

 

Суммарный километровый выигрыш за 20 итераций составляет: 

S = 23,0 + 21,4 + 14,6 + 13,4 + 8,8 + 8,3 + 7,9 + 7,8 = 105,3 км 

 а общий пробег автотранспорта, соответственно:  

L1 = L0 – S = 195 –105,3 = 89,7 км

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

, где Li – протяженность i-го маршрута, км; r – количество маршрутов.

 Рассмотрим, например, кольцевой маршрут 0-5-8-3-12-0. Протяженность маршрута определяется по формуле (см. табл. 4):

L1 = d0,12 + d12,3 + d3,8 + d8,5 + d5,0 = 7,3 + 5,1 + 4,1 + 5,4 + 12,0 = 33,9 км.

 Аналогично рассчитываем протяженность остальных маршрутов.

РЕЗУЛЬТАТЫ РЕШЕНИЯ.

Результаты решения задачисведены в таблицу:

 

1c-e.ru

Использование передовых методов составления маршрутов перевозок грузов пищевой промышленности

Введение

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

В связи с этим рассмотрим применение эвристических методов решения задачи развоза продукции. Среди известных методов широко применяется метод Кларка-Райта [1], построенный на экономии при объединении маятниковых маршрутов в развозочные. Однако данный метод имеет ряд существенных недостатков, среди которых можно выделить нечеткий выбор транспортного средства при формировании маршрута, неправильное построение порядка объезда пунктов на маршруте, приводящее к увеличению общего пробега подвижного состава, возможность зацикливания (отсутствие конечного результата) при решении задачи на ЭВМ.

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

Дальнейшим развитием метода Кларка-Райта стал эвристический способ решения задачи развозки на основе обобщенной задачи назначения, разработанный Фишером и Якумаром [2].

Рассмотрим данный алгоритм подробнее. В нем вводятся следующие обозначения: n — число пунктов сети, отправитель (склад) имеет номер n; p — число неоднородных транспортных средств различной грузоподъемности; Qk — грузоподъемность автомобиля с номером k; qi — заявка на перевозку от потребителя с номером i; ||cij||— матрица стоимости переезда между смежными пунктами транспортной сети G = (V,E).

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

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

Чтобы ликвидировать этот недостаток был предложен эвристический алгоритм Коскосидиса и Пауэлла [3], в котором выбор начального пункта для маршрута может изменяться в процессе действия алгоритма.

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

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

Сократить пробег и, соответственно, снизить транспортные расходы по поставке продукции можно с использованием метода раздельной (дробной) доставки [4]. При этом методе партия поставки одному потребителю делится на несколько завозов, и за счет этого наблюдается лучшая «упаковка» продукцией транспортного средства, сокращаются пробег и транспортные расходы.

Решение задачи. Рассмотрим применение этого метода на следующем примере. Осуществляется обслуживание одного кластера (группы) потребителей хлебопекарной промышленности, состоящей из 15 пунктов. Продукция доставляется в картонных ящиках. Для доставки используются ящики различной формы и массы. Средняя масса одного ящика составляет8 кг. Перевозка продукции осуществляется автомобилями различной грузоподъемности (вместимости), максимальная загрузка которых в пересчете на картонные ящики составляет 150, 170 и 200 ящиков (физических единиц).

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

Таблица 1

Исходные данные для маршрутизации методом раздельной доставки

 

Варианты поставок

Потребители

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Объем поставки в ящиках

Автомобиль с максимальной загрузкой в 150 ящиков

Вариант 1

87

115

90

100

57

36

73

60

100

90

54

63

55

77

75

Вариант 2

78

7

31

37

106

40

77

84

130

68

14

45

96

35

120

Автомобиль с максимальной загрузкой в 170 ящиков

Вариант 1

87

22

20

86

12

14

73

21

20

90

26

23

32

77

98

Вариант 2

87

44

120

86

57

36

73

60

20

90

54

33

32

77

98

Вариант 3

87

115

90

86

57

36

73

60

100

90

54

63

55

77

75

Вариант 4

87

115

90

100

57

36

73

60

100

90

54

63

55

77

75

Автомобиль с максимальной загрузкой в 200 ящиков

Вариант 1

87

22

20

86

12

14

73

21

20

90

26

23

32

77

98

                                                           

Для сравнения был взят эвристический алгоритм Кларка-Райта с последующим уточнением порядка объезда пунктов методом сумм. Применение метода раздельной доставки дает эффект на сокращении пробега и транспортных расходов при обслуживании потребителей. Результаты сравнительных расчетов по пробегу автомобилей комплексным методом Кларка-Райта и методом раздельной доставки показаны в табл. 2.

Таблица 2

Сравнение методов Кларка-Райта и раздельной доставки

 

Варианты

Комплексный метод Кларка-Райта

Метод раздельной

доставки

Выигрыш, %

Общий пробег автомобилей по маршрутам, км

Автомобиль с максимальной загрузкой в 150 ящиков

Вариант 1

174,29

154,82

11,17%

Вариант 2

123,29

130,89

-6,17%

Автомобиль с максимальной загрузкой в 170 ящиков

Вариант 1

103,93

90,51

12,91%

Вариант 2

120,04

112,76

6,07%

Вариант 3

157,44

131,20

16,66%

Вариант 4

161,37

148,84

7,76%

Автомобиль с максимальной загрузкой в 200 ящиков

Вариант 1

87,28

81,77

6,31%

Результаты, приведенные в табл. 2, показывают неоспоримое превосходство применения метода раздельной доставки при проектировании маршрутов, кроме 2 варианта при использовании автомобиля с загрузкой в 150 ящиков. Выигрыш от сокращения пробега автомобилей изменяется от 6% до 13% и в среднем по всем вариантам с учетом отрицательного эффекта составляет примерно 7%.

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

При проектировании маршрутов перевозок методом раздельной доставки изменяется конфигурация объезда пунктов. Пример порядка объезда пунктов для комплексного метода Кларка-Райта и метода раздельной доставки для 3 варианта при использовании автомобиля с загрузкой в 170 ящиков отражен на рисунках 1 и 2 соответственно.

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

Рис.1. Конфигурация маршрутов, полученных комплексным методом Кларка-Райта для 3 варианта при использовании автомобиля с загрузкой в 170 ящиков

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

 

Рассмотрим другой пример порядка объезда пунктов для комплексного метода Кларка-Райта и метода раздельной доставки для 2 варианта при использовании автомобиля с загрузкой в 170 ящиков. Полученные маршруты отражены на рисунках 3 и 4 соответственно.

Рис.3. Конфигурация маршрутов, полученных комплексным методом Кларка-Райта для 2 варианта при использовании автомобиля с загрузкой в 170 ящиков

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

 

На рис. 4 также изменяются маршруты доставки по сравнению с рис. 3. Дополнительно происходит деление партии поставки в 10-й пункт на 2 завоза, т.е. пункт 10 обслуживается двумя маршрутами: 0-11-12-10-0 и 0-1-5-10-0. За счет таких действий сокращается пробег автомобилей и повышается степень загрузки подвижного состава, но необходимо учесть в графике работы автомобилей эти два завоза в пункт 10 и согласовать время приема продукции с потребителем 10.

 

Выводы

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

creativeconomy.ru

2.Оптимизация транспортной работы в excel

Чтобы минимизировать транспортные расходы, используем функцию « Поиск решения » в Excel.

Ограничения по заказам ( по ввозу), ограничения по запасам ( по вывозу), ограничение по плановым объёмам ( план не может быть отрицательным).

Рисунок 1. Поиск оптимального решения

.

Рисунок 2. Поиск решения

Рисунок 3. Поиск решения

Рисунок 4. Результат решения

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

3. Планирование развозочных маршрутов методом кларка-райта

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

же одновременно автомобиль развозит и собирает мелкие партии грузов, то маршрут называют сборно – развозочным.

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

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

Для решения задач маршрутизации перевозок мелкопартийных грузов существует 2 группы методов:

– получение точных результатов

– получение приблизительных результатов.

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

Идея метода Кларка-Райта заключается в том, что маятниковые маршруты, исходящие из одного пункта ГО, попарно группируются в кольцевые маршруты по принципу получения на каждом максимальных «выигрыша» от этого объединения.

«Выигрыш» от объединения пунктов i и j маршрутов определяется по формуле, гдеli,o—кратчайшее расстояние от пункта i до ГО, lo,j— кратчайшее расстояние от ГО до j пункта, li,j— кратчайшее расстояние от пункта i до пункта j.

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

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

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

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

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

Пример заполнения таблицы «выигрышей»:

f 1-2=7+11-4=11, f 1-6=7+8-4=11,

f 1-3=7+15-7=15, f 1-7=7+9-2=14,

f 1-4=7+7-5=9, f 1-8=7+5-7=5,

f 1-5=7+14-7=14, f 1-9=7+9-2=14,

f 1-10=7+5-3=9.

Таблица «выигрышей»

Таблица № 7

объём груза

ГП

А2

А3

А4

Б1

Б2

Б3

Б4

Б5

Б6

Б7

9

А2

14

15

9

14

11

14

5

14

9

8

А3

14

18

11

21

11

18

7

16

8

7

А4

15

18

7

21

16

14

3

12

5

5

Б1

9

11

7

10

6

11

10

13

2

3

Б2

14

21

21

10

13

19

8

17

8

5

Б3

11

11

16

6

13

11

2

11

5

8

Б4

14

18

14

11

19

11

7

16

8

8

Б5

5

7

3

10

8

2

7

9

1

6

Б6

14

16

12

13

17

11

16

9

8

4

Б7

9

8

5

2

8

5

8

1

8

Выбираем наибольшее значение из таблицы «выигрышей», равное 14 из ячеек Б2Б45. Потребность в грузе этих ГП Б2=3 пакета, А4=15 пакетов. У Б2 вывоз составит 3 пакета, у А4- 7 пакетов, так как грузоподъёмность автомобиля равна 10 пакетам. Получим:

М1: ГО- Б2-А4-ГО (3+7)

М2: ГО-А3-Б4-ГО (6+4)

М3: ГО-Б4-Б6-ГО (4+6)

М4: ГО-А2-Б3-ГО (5+5)

М5: ГО-А2-А3-Б7- ГО (4+2+4)

М6: ГО-Б1-Б5-ГО (5+5)

М7:ГО-Б5-ГО (3)

Суммарный пробег по маятниковому маршруту составляет

Lм=7+11+15+7+14+8+9+5+9+4=178 км

Суммарный пробег по сформированным кольцевым маршрутам составляет 144 км. Пробег автомобилей сократился на 34 км.

studfiles.net

лаба без таблицы Таня

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра “Организация перевозок, управление и безопасность на транспорте”

ЛАБОРАТОРНАЯ РАБОТА № 4

Формирование развозочных маршрутов методом Кларка-Райта

Выполнил:

ст-т гр. АТ 34-1

Т.А. Халюкова

Проверил:

В.П. Горячев

Красноярск 2006

Лабораторная работа №4

Формирование развозочных маршрутов методом Кларка-Райта

Цель: научиться формировать развозочные маршруты методом Кларка-Райта.

Оборудование: таблица транспортной сети, таблица кратчайших расстояний, калькулятор.

Исходные данные: объемы спроса получателей q1=225, q2=525, q3=675, q4=500, q5=575, q6=450, q7=275, q8=300, q9=275, q10=500, q11=425, q12=225, qн=1500.

Ход работы:

1. Используя данные первой лабораторной работы из схемы транспортной сети формируем ее фрагмент, состоящий из 12 пунктов и склада.

2. Используя данные второй лабораторной работы составляем таблицу расстояний между пунктами и складом.

3. Для каждой комбинации радиальных маршрутов рассчитывается выгода от объединения их в кольцевой маршрут.

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

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

6. Чертим образовавшиеся маршруты.

7. Рассчитываем общий выйгрыш.

8. Записываем вывод о проделанной работе.

Вывод

Метод Кларка-Райта – метод решения задачи развозки мелкопартионных грузов из распределенного центра множеству получателей, расположенных в районе развозки. Достоинствами этого метода являются: простота, надежность, гибкость. Суть метода заключается в том, чтобы, отталкиваясь от исходной схемы развозки, по шагам перейти к оптимальной схеме развозки с кольцевыми маршрутами. Тем самым мы можем рассчитать километровый выйгрыш.

studfiles.net

Сборник методических указаний к практическим занятиям, страница 12

Для простоты считается, что при погрузке затрачивается 4 мин на 1 т грузоподъемности автомобиля, а на разгрузку требуется 10 мин независимо от грузоподъемности конкретного автомобиля. Норматив технической скорости при движении с грузом и без груза принять одинаковым и равным 41 и 37 км/ч (соответственно для автомобилей грузоподъемностью менее 10 т и для автомобилей г/п 10 и более тонн).

В отчете необходимо привести граф дорожной сети, оптимальный план закрепления клиентуры за АТП, потребное количество автомобилей по маркам и их маршруты на графе (одинаковые маршруты показывать не нужно), пробег с грузом, порожний пробег и нулевой пробег по каждому маршруту и в сумме для всех автомобилей. Значение критерия эффективности вида (13).

Таблица 5

Марка
автомобиля

Грузоподъемность, т

Количество, шт.

Постоянные расходы, Аi, руб/сут.

Переменные расходы, Вi, руб/сут.

Зарплата водителя, руб/сут

Камаз-5511

10,0

8

300

400

200

Зил-ММЗ-4502

6,0

7

110

200

70

Краз-256Б1

12,5

4

250

300

230

Камаз-55111

13

10

350

420

250

Маз-5551

8,5

6

150

200

100

Каз-4540-01

5,5

8

100

170

65

Урал-5557

7,0

12

120

200

80

Маз-5549

8,0

5

200

270

90

Камаз-55102

7,0

7

170

250

110

Примечание. Приведенные в трех последних колонках таблицы постоянные и переменные составляющие эксплуатационных расходов и суточная зарплата водителя являются ориентировочными.

Рис. 1. Граф дорожной сети

Защита отчета на следующем занятии

Практическое занятие № 6

(4 часа)

Оптимизация мелкопартионных перевозок методом Кларка-Райта

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

Теоретические сведения

Метод разработан английскими математиками Кларком и Райтом в начале пятидесятых годов. Он позволяет найти приближенное решение задачи маршрутизации перевозок, осуществляемых мелкими партиями, в общем случае парком автомобилей различной грузоподъемности.

Вначале строится план, состоящий только из маятниковых маршрутов

А – В1 – А

А – В2 – А

…………

А – Вi– А

………

А – Вj– А

………

А – Вn– А,

где А – обозначает центральный склад;

Вi – обозначает потребителя с номером  i   (i=1, 2, …, n)

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

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

 Центральный пункт дорожной сети (имеет номер 0, а в табл. 1 обозначен буквой А) является складом, базой, промышленным районом и т.д. В случае развозки из него грузов в пункты В1, В2, …, Вn нужно доставить грузы Q1, Q2, …, Qn соответственно. Можно решать и обратную задачу сбора грузов Q1, Q2, …, Qn в соответствующих пунктах В1, В2, …, Вnи доставки их в пункт А.

Кратчайшие расстояния (стоимости, время) между пунктами

Таблица 1

vunivere.ru

2.2 Проектирование развозочной транспортной системы

2.2.1. Маршрутизация методом Кларка-Райта

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

Особенности мелкопартионных перевозок:

– значительные затраты времени на передачу грузов и погрузочно-разгрузочные работы, часто большие, чем на движение;

– низкие техническая и эксплуатационная скорости на маршрутах, проходящих, как правило, по загруженным магистралям в густозаселенных местах;

– высокие требования к качеству перевозок: гарантия своевременной доставки (“точно в срок”), сохранность грузов;

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

Задачи планирования мелкопартионных перевозок относят к классу задач дискретной оптимизации, так как теоретически возможно перебрать все варианты решений и выбрать лучший из них. Однако, если учесть, что задача объезда 10 пунктов на маршруте будет иметь более 3,5 млн решений, естественно, такой подход к решению задачи нереален.

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

Один из таких способов, разработанный английскими специалистами Кларком и Райтом и поэтому известный как метод Кларка – Райта, применяется для решения задач мелкопартионных перевозок с одним отправителем или получателем. В данном методе используется метод функций “выгоды”.

“Выгода” появляется от объединения двух маятниковых маршрутов в один кольцевой в случае, если соблюдается условие (рис. 2.)

Δl= l1+l2l12>0. (2.13)

Значит, если есть маршруты, которые можно объединять в соответствии с получаемой при этом “выгодой”, то в случае объединения маршрутов с наибольшей “выгодой” можно рассчитывать, что решение будет близко к оптимальному.

В1

В2

В1

В2

Рис.2.1. Эффект “выгоды” от объединения маятниковых

маршрутов в кольцевой маршрут

ООО “ТД Акватория” осуществляет доставку воды со своего склада в магазины, склады и юридическим лицам. Развоз воды осуществляется тарно упаковками по 30 л.

Таблица 2.9.

Исходные данные

Номер получателя

Наименование получателя

0

Липецкая обл., г. Елец, ул. Александровская 16

1

ООО «Аква-Блюз»

2

ООО «Тандем»

3

Магазин «Красные зори», с. Красное

4

ООО «Смак»

5

ООО «Эридан»

6

ООО «Регион-продукт»

7

Дом Быта

8

ООО «Виктория»

9

ООО «Регион-продукт»

10

ООО «Предприятие «Управляющая компания»

11

ЗАО «Липецкнефтепродукт», с. Бабарыкино

Объемы завоза грузов, расстояния от грузоотправителя до получателей и между ними представлены в табл. 3.2. Для перевозки может быть использован подвижной состав грузоподъемностью 1 и 1,5 т. Перевозки необходимо выполнить для 11 пунктов.

В случае объединения маршрутов, например первого (0-1-0) и второго (0-2-0), возможный эффект Δl = 20 + 21-1= 40 км.

Эффект от объединения всех маршрутов попарно занесем в табл.2.9.

Таблица 2.9.

Матрица кратчайших расстояний

Ввоз, л

0

160

8

1

370

45

42

2

210

44

42

54

3

132

4

7

48

40

4

478

5

4

42

39

2

5

471

2

6

48

52

5

6

6

139

4

5

47

38

1

2

4

7

181

7

6

40

40

4

3

8

4

8

684

8

5

40

41

4

3

8

5

1

9

139

42

49

83

55

43

53

40

43

55

56

10

166

43

50

84

56

44

54

41

44

56

57

1

11

Таблица 2.10.

Матрица выигрышей

Ввоз, л

160

1

370

11

2

210

10

35

3

132

5

0

8

4

478

9

8

10

7

5

471

4

-1

-6

1

1

6

139

7

2

10

7

7

2

7

181

9

12

11

7

9

1

7

8

684

11

13

11

8

10

2

7

14

9

139

1

4

31

3

-6

4

3

-6

-6

10

166

1

4

31

3

-6

4

3

-6

-6

84

11

Анализируя матрицу выигрышей, приходим к заключению, что максимальную выгоду, равную 84, можно получить, объединяя маршруты 0-10-0 и 0-11-0. При объединении первой пары маршрутов (0-10-0 и 0-11-0) суммарное количество груза по ввозу 139+ 166 = 305 л.

На данный маршрут (0-10-11-0) можем назначить автомобиль грузоподъемностью 1000 кг или 1500 кг, но следует помнить, что он при этом недогружен (1000 – 305 = 695 кг или 1500 – 305 = 1195 л). Количество ввозимого груза проставляем в соответствующих столбцах напротив пунктов 10 и 11, (табл. 2.11).

Таблица 2.11.

Объединение маршрутов 0-3-0 и 0-4-0

Ввоз, кг

1

2

3

4

5

6

7

8

9

305

1

4

31

3

-6

4

3

-6

-6

10

305

1

4

31

3

-6

4

3

-6

-6

84

11

Далее рассмотрим возможность объединения маршрута 0-3-0 с полученным 0-10-11-0, так как в этом случае “выгода” будет максимальной (выгода от объединения маршрутов 0-3-0 и 0-11-0 равна 31). Для объединенного маршрута (0-3-10-11-0) ввоз составит 305 + 210 = 515 л (табл. 2.12).

Таблица 2.12.

Объединение маршрутов 0-3-4-0 и 0-1-0.

Ввоз, кг

1

2

515

10

35

3

4

5

6

7

8

9

515

1

4

31

3

-6

4

3

-6

-6

10

515

1

4

31

3

-6

4

3

-6

-6

84

11

При последующем рассмотрении матрицы выигрышей можно объединить маршруты 0-6-0 и 0-3-10-11-0. Для объединенного маршрута ввоз составит 210+471+139+166=986л. Присваиваем данному маршруту №1.

Ищем следующую наибольшую выгоду по матрице выигрышей (табл. 2.12), она равна 13, т.е. при объединении маятниковых маршрутов 0-2-0 и 0-9-0 в один кольцевой выигрыш составит 13 км. Далее присоединяем маршруты 0-8-0 и 0-1-0. Получаем маршрут 0-1-2-8-9-0. Объем ввоза составит 160+370+181+684=1395 л. Присваиваем маршруту №2.

Маршрут №3 получаем при объединении маршрутов 0-4-0, 0-5-0 и 0-7-0 в маршрут 0-4-5-7-0. Объем ввоза равен 132+478+181 = 791 кг.

Окончательный вариант объединения маршрутов представлен в табл. 2.13.

Таким образом, получены 2 маршрута организации перевозок:

маршрут №1: 0-3-6-10-11, объем ввоза равен 986л;

маршрут №2: 0-2-9-8-1-0. Объем ввоза составит 1395л;

маршрут №3: 0-4-5-7-0. Объем ввоза составил 749л.

Таблица 2.13.

Матрица объединенных маршрутов

Ввоз, кг

Маршрут

1395

2

1

1395

2

11

2

986

1

10

35

3

749

3

5

0

8

4

749

3

9

8

10

7

5

986

1

4

-1

-6

1

1

6

749

3

7

2

10

7

7

2

7

1395

2

9

12

11

7

9

1

7

8

1395

2

11

13

11

8

10

2

7

14

9

986

1

1

4

31

3

-6

4

3

-6

-6

10

986

1

1

4

31

3

-6

4

3

-6

-6

84

11

studfiles.net