В продолжении темы «безтрупной» оптимизации бизнеса и эффективного планирования. В связи с недавним локдауном и переходом многих учреждений розничной торговли и общепита преимущественно на адресную доставку, этот метод оптимизации будет весьма кстати.
Речь пойдет о таком классе методов, которые, во-первых, изучают во всех экономических ВУЗах страны, во-вторых, экономят колоссальные деньги собственнику, в-третьих, за 14 лет работы экономистом, я еще ни разу не видел, чтобы кто-то применял этот инструмент на практике.
Итак, задача коммивояжёра относится к классу задач линейного программирования, так называемой, дискретной оптимизации.
Коммивояжёр (фр. commis voyageur) — разъездной сбытовой посредник, который, перемещаясь по рынку, выполняет роль простого посредника или действует по поручению своего клиента. Иногда эту задачу называют еще задачей почтальона, а в последней интерпретации TSP от англ. Traveling Salesman Problem, т.е. задачей странствующего торговца (из Википедии).
Задача коммивояжёра сводится к следующему. Существует несколько адресных пунктов, локаций или городов, которые коммивояжер, он же торговый агент, должен посетить, чтобы предложить товар потенциальному клиенту и вернуться в конце пути в исходное местоположение. Такой путь еще называют циклом Гамильтона.
Задача звучит так: в какой последовательности коммивояжёру следует посещать адресатов, чтобы охватить все места посещения как минимум один раз и при этом преодолеть самое минимальное расстояние по всему маршруту?
Конечно, можно вбить в навигатор GPS, и готово. Но если мы говорим о планировании бизнеса, скажем, в сфере службы доставки пиццы или воды в баллонах 19 л., то задача коммивояжёра поможет увидеть сумму экономии, за счет грамотной организации маршрута.
Ниши, в которых этот метод может найти достойное применение:
- службы доставки: пиццы, воды по 19 л., мебели, товаров дом;
- курьерская служба, почтовая служба;
- ЭКОСЕТИ, ТСЖ, управляющие компании – в части обслуживания пунктов сбора мусора;
- авиакомпании, транспортные компании;
- маркетинговое агентство для планирования маршрута интервьюеров и т.д.
Если Вы, уважаемый, читатель стали свидетелем использования этого метода на практике, пожалуйста, напишите в комментариях в какой фирме, в каком городе. Или Ваши мысли по поводу того, почему метод не используется. Буду премного благодарен.
Итак, с помощью решения задачи коммивояжёра мы оптимизируем расстояние с максимальным охватом. В EXCEL-таблицах решение задачи «почтальона» выглядит вот так: на рис. 1 – маршрут до оптимизации, на рис.2. после оптимизации.
Видим, что изначально маршрут вполне оптимален «на глаз». На втором рисунке маршрут после процедуры оптимизации жадным алгоритмом. Главный принцип «правильного» маршрута с замкнутым циклом – не должно быть пересечений путей.
Что не так с этим методом?
1. Неоднозначное решение. Теория утверждает, что существует единственный оптимальный путь из множества вариантов. Любой другой вариант не является оптимальным. В зависимости от условий задачи и исходных данных оптимальное решение не является единственным и точным. Каждый новый запуск процедуры решения задачи может выдать разные ответы. Полученный ответ, в частности в EXCEL, является максимально приближенным к оптимальному, но не единственным.
2. Несколько способов решения. Существует, по крайне мере, 4 известных мне способа решения этой задачи: с помощью графов «на глаз», симплекс-метод, метод ветвей и границ, жадный алгоритм. Каждый из этих методов может выдавать свою оценку оптимального расстояния. Нужно понимать, что речь идет об улучшении существующего плана, который подбирается случайно с долей здравого смысла, и только улучшается.
3. Теория заговора. Работая в авиакомпании, столкнулся с интересными явлениями. Чем больше воздушное судно находится в воздухе, тем лучше, для многих заинтересованных в этом сотрудников. Находясь в воздухе судно зарабатывает. Чем больше оно летает, чем больше расход топлива, тем выше зарплата экипажа. Зарплата экипажа зависит от количества часов летного времени. И это не единственные факторы, которые тормозят внедрение метода. А предприятие субсидируется из государственных источников. Какая там оптимизация…? Какой симплекс-метод...? Вы о чем вообще…?
4. Непредвиденные факторы. Я уверен, что решение этой задачи вшито в какое-нибудь мобильное приложение, ведь методу уже 90 лет. Но если не вшито, думаю этот вопрос к пользователям, а не к программистам. Итак, что может влиять на внедрение метода:
- дороги. Они бывают закрытыми, непрямыми, несуществующими с колдобинами. Коллеги! Все это можно откалибровать и внести поправки. Илон Маск запускал возвращаемую ступень ракеты 10 лет. Сэр Ричард Бренсон 15 лет запускал проект космических туристов. Кроме того, оптимальный маршрут - это эталон, от него можно отстраниться, понимая, что он существует.
- пути, по факту, непрямые. Скачиваете приложение для бега, шагомеры или программы для снижения веса. В них есть измеритель расстояний. Замеряете время и расстояние по пути следования. Если нужно рассчитать расстояния между городами, то открываете Яндекс.Карты, наводите на точку прибытия, копируете координаты GPS, вычисляете расстояние между пунктами, как это показано в видео к статье.
- критерий заработка курьера − не длина пути, а время. Для данного класса задач есть 3 критерия оптимизации: время, деньги, расстояния. Если курьер попадает в пробку, в тупик, в час пик - нужно фиксировать периодичность появления фактора и вносить поправки в модель. Это головная боль для курьера, но для владельца бизнеса, который балансирует на грани рентабельности это повод задуматься о следующем:
1) удлинить расстояния в матрице расстояний с поправкой на препятствие с помощью коэффициентов. Но это уже «отсебятина», которую нужно калибровать под реальность: ездить, фиксировать, сравнивать с расчетами. И так по нескольку раз с постепенными улучшениями;
2) оптимизировать стоимость перевозок. Для этого есть другой метод – решение транспортной задачи, где между пунктами отбытия и пунктами прибытия в ячейки матрицы проставляются тарифы по перевозкам.
Количество заказов для доставки выдаются курьеру не так много, чтобы он оптимизировал маршрут. С 2-3 заказов оптимизация бессмысленна, особенно для пеших/вело- курьеров. Я не могу закрыть это возражение. Могу лишь посоветовать: берите больше заказов за раз, чтобы «порожняка» было меньше.
Фактор: «30 минут - доставка или получите пиццу бесплатно!» Здесь сама концепция бизнеса выстроена так, что основные риски за несвоевременную доставку и неоплату принимает на себя курьер. Однако у владельца бизнеса всегда есть возможность оценить маршруты в радиусе 30 мин доставки от пункта выдачи заказов.
Выводы. Решение задачи коммивояжёра - это определение оптимального пути, где началом и концом пути является один и тот же адресат (цикл Гамильтона). Этот метод был создан в 30-х годах 19 века и имеет прикладное значение. Однако немногие предприниматели в нашей стране его используют, или не используют вовсе. Этому есть ряд причин и факторов. В этой статье рассмотрены эти причины и доводы в пользу внедрения метода. Ход решения задачи коммивояжёра пошагово представлен в видео к настоящей статье.
Внедряйте без потерь и процветайте!
Подписывайтесь на мой инстаграм @biznesplan_ykt
