Публикация Школы траблшутеров

Ближайший сосед и развороты: как сократить маршрут объезда

Время чтения: 6 мин 30 сек
18 ноября 2026 Просмотров: 12

Восемь объектов бригада объезжает за 87 километров по правилу «к ближайшему» и всего за 68 – после двух разворотов маршрута. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует быструю прокладку объезда по городу и простое, но очень сильное улучшение такого маршрута в трёх нотациях.

Ближайший сосед и развороты: как сократить маршрут объезда

Рис. 1. Схема по ГОСТ 19.701: каждый раз – в самую близкую точку

Крупный агрохолдинг решил сэкономить на программе прокладки маршрутов.

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

Сели в грузовик, развозили товар. Сначала всё шло хорошо: не успевали отдыхать после разгрузки, но к вечеру выяснилось, что последняя точка находится… на другом конце города.

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

Рисовать такой расчёт руководителю удобнее всего диаграммой Насси – Шнейдермана: вложенные циклы и развилки видны без единой стрелки.

Чем опасна жадность?

Метод ближайшего соседа – способ построить маршрут шаг за шагом: из текущей точки едут в самую близкую из непосещённых, а в конце возвращаются на базу. По ГОСТ 19.701 – цикл «Пока есть непосещённые».

Слабое место – конец дня: соседние объекты уже позади, последние переезды длинные, а обратный путь никто заранее не считал.

Бригада едет назад через весь город, тратя топливо и время.

Ближайший сосед хорош как черновик: маршрут готов за минуты, но обычно длиннее лучшего примерно на четверть – у «Кедра» на 27%, то есть на 18 километров.

Как убрать пересечения?

Улучшение 2-opt – способ выпрямить маршрут: берут два участка, убирают их и соединяют концы накрест, то есть разворачивают отрезок между ними. Если путь стал короче, замену оставляют, и так до тех пор, пока выгодных разворотов не останется.

Метод предложил Г. А. Кроус в 1958 году, а задачу коммивояжёра для 49 городов США за четыре года до того решили Данциг, Фалкерсон и Джонсон.

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

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

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

Как это выглядит на деле?

Сервисная компания «Кедр» каждый день отправляет бригаду с базы на восемь объектов: склад, цех, завод, насосную, котельную, депо, мойку и офис. По ближайшему соседу выходит 87 километров, из них 18 – последний переезд с насосной на базу.

image html

Рис. 2. Пример: две перестановки убрали пересечение и длинный возврат

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

Почему короткий путь не всегда лучший?

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

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

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

Где метод не годится?

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

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

Расчёт видит только то, что ему дали, а опыт – то, чего нет в данных. Прежде чем заменить людей алгоритмом, сравните результаты на истории.

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

Сколько стоит расчёт?

Модель: полный перебор для восьми объектов – 40’320 маршрутов, для пятнадцати – больше триллиона. Один проход 2-opt по восьми объектам проверяет 28 пар участков: три прохода вручную по 10 секунд – около 15 минут.

Какими нотациями рисовать объезд?

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

Диаграмму Насси – Шнейдермана любят руководители и методологи: вложенные циклы видны как рамки, развилка – как треугольник, стрелок нет.

image html

Рис. 3. Два вложенных цикла и две развилки без стрелок

Псевдокод предпочитают программисты и ИИ: двенадцать строк сразу переводятся в код на любом языке. Модель без подсказок прочтёт в них и вложенные циклы, и условие остановки, а программист увидит, где ускорить вычисления для сотен точек и десятков бригад.

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

image html

Рис. 4. Тот же расчёт в виде текста

Какая нотация лучше?

Лучшая нотация для маршрута объезда – диаграмма Насси – Шнейдермана: 20 баллов против 18 у псевдокода и 16 у ГОСТ. Руководитель за минуту видит, что повторяется и где принимается решение. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 5. Оценка трёх нотаций: 16, 20 и 18 баллов

Псевдокод отстал на два балла и нужен диспетчерским системам, ГОСТ – проверке построчно.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Нанесите базу и объекты на карту и постройте маршрут по ближайшему соседу.
  2. Найдите пересечения и длинные возвраты – их убирают разворотом отрезка.
  3. Проверьте окна приёма и время разгрузки, а не только километры.
  4. Сравните расчёт с маршрутами опытного диспетчера на истории поездок: если люди стабильно быстрее, ищите, чего не знает модель.

Что запомнить?

  • жадный маршрут теряет в конце дня
  • пересечение участков – верный признак лишних километров
  • два-три разворота нередко дают лучший маршрут
  • время важнее километров, когда есть окна приёма
  • маршрут объезда лучше всего рисовать диаграммой Насси – Шнейдермана.