Метод Кларка – Райта

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

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

Рассмотрим метод Кларка – Райта на примере.

Пример 3. Из исходного пункта, в котором располагается грузовой терминал, необходимо доставить грузы 12 получателям. Координаты исходного пункта: x0 = 10, y0 = 15. Грузовместимость транспортного средства 1500 шт. Координаты и объем спроса получателей представлены в Таблице 3, где xi, yi – координаты i-го получателя, qi – объем спроса i-го получателя, шт.

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

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

На Рисунке 8 указана и исходная схема развозки грузов. Согласно исходной схеме для доставки груза каждому отдельному получателю организуется отдельный маршрут.

Например, водитель загружает в кузов партию 450 шт. и везет ее в пункт 1, там разгружает, затем возвращается на базу, берет вторую партию 400 шт. и везет ее в пункт 2 и т. д.

В данном случае, схема развозки состоит из 12 радиальных маршрутов.

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

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

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

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

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