Оптово-торговым и транспортным кампаниям

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

 

Метод Кларка-Райта был разработан двумя британскими учеными Г. Кларком (G. Clarke) и Дж.В. Райтом (J.W. Right). Несмотря на давность разработки (метод опубликован в 1963 г.), он до сих пор остается самым популярным методом для решения данной задачи, о чем свидетельствует практика его применения.

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

Рассмотрим метод Кларка-Райта на примере. За основу возьмем исходные данные из таблицы 1.

Таблица 1. Исходные данные

i

xi

yi

qi

i

xi

yi

qi

1

17

15

450

7

4

14

250

2

6

15

400

8

17

2

200

3

13

3

400

9

12

22

450

4

9

20

200

10

6

12

300

5

19

7

150

11

19

17

475

6

8

8

450

12

12

8

550

где xi, yi – координаты iго получателя, qi – объем спроса iго получателя, шт.

 

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

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

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

 Рисунок 1. АСУ:Оптимальные пути по методу Кларка-Райта, карта 1

   Рисунок 1.

 

Рисунок 2. АСУ:Оптимальные пути по методу Кларка-Райта.

Рисунок 2.

 

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

Используя Метод Кларка-Райта суммарный километровый выигрыш составляет:

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

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

L1 = L0S = 195 –105,3 = 89,7 км

Графически оптимальная схема развозки представлена на рисунке 3. Как видно, оптимальная схема развозки включает в себя четыре кольцевых маршрута (вместо первоначальных 12 радиальных маршрутов). Результаты расчетов сведены в таблицу 2:

 Рисунок 3. АСУ:Оптимальные пути по методу Кларка-Райта, карта 2

Рисунок 3.

 

Таблица 2

Результат решения задачи развозки

 

№ п/п

Маршрут

Объем поставки, шт

Пробег, км

1

0-12-3-8-5-0

1300

33,9

2

0-1-11-0

925

19,0

3

0-9-4-0

650

16,0

4

0-2-7-10-6-0

1400

20,8

Итого

4275

89,7

Заказать разработку.

Добавить комментарий

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