Алгоритм Кларка-Райта

Алгоритм Кларка-Райта (также известный как алгоритм экономии или метод «сбережений») — это эвристический метод решения задачи маршрутизации транспорта (Vehicle Routing Problem, VRP), предназначенный для построения приближённого к оптимальному набора маршрутов для парка транспортных средств, обслуживающих заданное множество клиентов из одного или нескольких депо. Алгоритм был предложен в 1964 году американскими исследователями Джеффри Кларком и Джоном Райтом и до сих пор остаётся одной из наиболее широко применяемых базовых эвристик в транспортной логистике.

История

Задача маршрутизации транспорта в её классической формулировке (CVRP — Capacitated VRP) была впервые описана в 1959 году Джорджем Данцигом и Джоном Рамзером. К началу 1960-х годов стало очевидно, что точные методы решения (например, методы целочисленного линейного программирования) неспособны эффективно обрабатывать задачи с десятками и сотнями клиентов из-за экспоненциального роста вычислительной сложности. В 1964 году Джеффри Кларк и Джон Райт, работавшие в компании «Arthur D. Little», опубликовали статью «Scheduling of Vehicles from a Central Depot to a Number of Delivery Points», в которой предложили простой и интуитивно понятный эвристический алгоритм, основанный на идее последовательного объединения маршрутов с максимальной экономией пробега. Алгоритм быстро завоевал популярность в промышленности и академических кругах, став стандартным инструментом для начального этапа решения VRP.

Описание алгоритма

Алгоритм Кларка-Райта относится к классу конструктивных эвристик: он строит решение постепенно, начиная с тривиального набора маршрутов и последовательно улучшая его путём слияния отдельных маршрутов. Основная идея заключается в расчёте «экономии» (saving) от объединения двух клиентов в один маршрут вместо обслуживания их отдельными рейсами.

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

Для работы алгоритма необходимы:

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

Этапы

1. Начальное решение: строится тривиальный набор маршрутов, в котором каждый клиент обслуживается отдельным рейсом от депо и обратно. Таким образом, для N клиентов получается N маршрутов вида (депо → клиент i → депо).

1. Расчёт экономии: для каждой пары клиентов (i, j) вычисляется значение экономии S(i, j) по формуле:

S(i, j) = d(депо, i) + d(депо, j) — d(i, j), где d(A, B) — расстояние между точками A и B. Экономия показывает, насколько уменьшится общий пробег, если вместо двух отдельных рейсов (депо → i → депо и депо → j → депо) выполнить один маршрут (депо → i → j → депо). Чем больше значение S(i, j), тем выгоднее объединить этих клиентов.

1. Сортировка: все пары (i, j) сортируются по убыванию значения экономии. Получается список кандидатов на объединение.

1. Итеративное объединение: алгоритм последовательно просматривает отсортированный список. Для каждой пары проверяется:

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

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

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

Модификации

Существует несколько вариантов алгоритма, различающихся порядком обработки пар и правилами объединения:

• Параллельная версия: на каждом шаге рассматривается несколько пар с наибольшей экономией, и объединения выполняются одновременно, если они не конфликтуют.
• Последовательная версия: объединения выполняются строго по одному, начиная с пары с максимальной экономией, после чего список пересчитывается.
• Версия с учётом ограничений по времени: вводится дополнительное ограничение на максимальное время в пути или время работы водителя.

Применение

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

• Планирование доставки товаров: оптимизация маршрутов для курьерских служб, сетей розничной торговли, дистрибьюторов продуктов питания.
• Сбор и вывоз отходов: построение маршрутов для мусоровозов.
• Обслуживание клиентов: маршрутизация для полевых сервисных бригад (ремонт, установка оборудования).
• Школьные автобусы: планирование маршрутов для подвоза учащихся.
• Почтовые и логистические службы: «Почта России», «СберЛогистика» и другие операторы используют подобные алгоритмы в своих системах оптимизации.

Преимущества и недостатки

Преимущества

• Простота реализации: алгоритм легко программируется и не требует сложных математических вычислений.
• Быстродействие: для N клиентов вычислительная сложность составляет O(N² log N) (из-за сортировки пар), что позволяет обрабатывать задачи с сотнями и тысячами точек.
• Интуитивная понятность: логика объединения маршрутов по принципу максимальной экономии расстояния легко объяснима менеджерам и диспетчерам.
• Хорошее качество начального решения: в большинстве случаев алгоритм даёт решение, близкое к оптимальному (обычно в пределах 10–15 % от глобального оптимума).

Недостатки

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

Критика и развитие

Несмотря на широкое распространение, алгоритм Кларка-Райта подвергался критике за то, что в некоторых случаях он может строить маршруты, пересекающие друг друга, что увеличивает общий пробег. Для устранения этого недостатка были предложены модификации, такие как алгоритм «сбережений с перекрёстным обменом» (savings with exchange) и гибридные методы, сочетающие алгоритм Кларка-Райта с методами локального поиска (например, 2-opt, 3-opt). В современных системах маршрутизации алгоритм часто используется как один из этапов в составе более сложных решателей, таких как OR-Tools (Google), LKH (Lin-Kernighan Helsgaun) или коммерческие пакеты (например, «Логистика: Планирование маршрутов» от российской компании «1С-Рарус»).

Источники

• Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581.
• Laporte, G. (1992). The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358.
• Toth, P., & Vigo, D. (Eds.). (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM.
• Lysgaard, J. (1997). Clarke & Wright's Savings Algorithm. Department of Management Science and Logistics, Aarhus School of Business.