Складно не помітити, як сильно за останні два роки змінилася доставка товарів. Заходи, вжиті для стримування пандемії, змусили багатьох вперше повністю покластися на онлайн-замовлення. Ринок онлайн-продажів різко виріс, і компанії досить швидко підлаштувалися під нові умови, налагодили доставку і навіть стали пропонувати додаткові послуги на кшталт «залишити замовлення біля дверей». У нас сформувалися нові звички і нові очікування від доставки: вона повинна бути швидкою і комфортною. А бізнес зрозумів, що в сучасному світі потрібно вміти швидко підлаштовуватися під зміни і планувати різні сценарії.
Самою, напевно, вражаючою послугою сьогодні є експрес-доставка з дарксторів - наприклад, з Яндекс.Лавки. Отримавши ваше замовлення, збирач даркстора формує його і передає кур'єру. Даркстори розташовані так, що до будь-якої точки в радіусі обслуговування (близько 1-2 км) можна дістатися в термін від 10 хвилини.
Але важливо забезпечити безперебійне постачання дарксторів товарами. З раннього ранку від розподільних центрів до дарксторів їдуть сотні машин. Щоб вони вийшли на дороги, логісти розраховують необхідну кількість машин на наступний день, їх характеристики, розподіляють товари по машинах, будують маршрути. Результат планування, наприклад, може виглядати так:
Завтра необхідно задіяти n «газелей» вантажопідйомністю 3,5 т, n1 машин-холодильників і n2 машин вантажопідйомністю 5 т
При побудові маршрутів доводиться стикатися з різними обмеженнями і особливостями. Наприклад, житлові зони не можуть приймати п'ятитонні вантажівки - туди можна відправити тільки менш габаритні машини. Звичайно, для цього у логістів повинні бути відомості про всі подібні правила.
Крім особливостей складів, Яндекс.Лавці доводиться враховувати особливі умови перевезення товарів. Для позначення специфічних характеристик товарам, точкам доставки і машинам присвоюються теги. Наприклад, якщо товар повинен їхати в машині з холодильним обладнанням, то в логістичній системі він відзначається тегом «холод». Цим же тегом позначаються і самі машини-холодильники.
Разом з водіями, які доставляють товари в даркстори, на вулиці міста, що прокидається, виїжджають тисячі їхніх колег, які постачають звичайні магазини, склади і пункти видачі замовлень, розвозять замовлення і посилки безпосередньо по клієнтах або ж забирають їх, щоб повернути на склад або в сортувальний центр.
Великі магазини, що доставляють безпосередньо покупцям, виконують десятки тисяч замовлень на день. Всі ці замовлення потрібно розподілити по машинах, враховуючи їх місткість і наявність необхідного обладнання, принципи і межі завантаження кур'єрів, їх перерви на відпочинок, обіцяні клієнтам інтервали доставки, сервісний час у клієнта на додаткові послуги на зразок примірки і установки обладнання. Таких обмежень безліч
Основу цієї піраміди параметрів становить дорожня ситуація і затори зокрема. Можна дуже акуратно, з урахуванням всіх операційних умов спланувати маршрути, але без інформації про затори доставка вчасно буде неможлива. Ми стикаємося з заторами, коли запускаємо навігатор або замовляємо таксі, але для логістів, які планують маршрути кур'єрів, важливі затори в прогнозі на день вперед або навіть більше.
У Яндекс.Маршрутизації розповідають, що для точного прогнозу часу прибуття кур'єра потрібно розуміти, якими з великою ймовірністю будуть затори в певному часовому зрізі конкретного дня на кожному дорожньому сегменті.
Причому спланувати оптимальний маршрут недостатньо. Для забезпечення якості доставки логісти моніторять виконання замовлень у реальному часі. Так можна бачити місце розташування машин, точно прогнозувати постачання товарів у ритейл-мережі, бути на зв'язку з кур'єрами. Якщо ж станеться непередбачена ситуація, логісти, які використовують сучасні системи, можуть швидко перерозподіляти товари по інших кур'єрах або перенести доставку - залежно від ситуації і правил компанії.
Моніторинг якості доставки до Яндекс.Маршрутизації
Є і ще один важливий аспект, про який ми, покупці, не замислюємося, але який має величезне значення для деяких компаній і їх кур'єрів - це зміна обсягів продажів через сезон або період розпродажів або ковидних обмежень у сфері торгівлі. У середньому в пікові періоди кількість замовлень зростає на 20-30%. Для великої компанії, яка виконує по кілька тисяч або десятків тисяч на день, це сотні і тисячі додаткових замовлень. І ось тут компаніям доводиться вирішувати питання управління логістикою за різних умов. Одні на піках наймають додаткових кур'єрів (аутсорс), інші, у яких попит зростає не настільки сильно, розраховують кількість кур'єрів так, щоб максимально навантажувати їх у пікові періоди і тримати середнє навантаження протягом решти року.
Все це відбувається за лаштунками: в кабінетах логістів, в офісах компаній і на складах, в телефонах кур'єрів. Щоб скласти маршрут, потрібно об'єднати сотні тисяч точок кінцевої доставки і різні необхідні для неї параметри, а це мільйони можливих комбінацій. Перебрати ці варіанти вручну і вибрати оптимальний, та ще й врахувати всі параметри, не вийде. Адже вирішувати доводиться, по суті, одне з найзнаменитіших оптимізаційних завдань - завдання комівояжера.
Завдання комівояжера в сучасному прочитанні
Постановка завдання комівояжера, або бродячого торговця, дуже проста: потрібно об'їхати деяку кількість пунктів і повернутися у вихідний максимально «дешевим» чином. «Ціну» переїзду з одного пункту в інший можна визначати і через довжину маршруту, і через час в дорозі, і через оплату проїзду, якщо дорога платна. Головне, потрібно проїхати оптимальним способом.
Як ви можете собі уявити, задачку з п'ятьма пунктами цілком можна вирішити ручним перебором. Проблема в тому, що з кожною новою точкою перебирати доведеться в рази більше варіантів. Так, додавання шостої точки збільшує кількість варіантів в шість разів, сьомий - ще в сім разів. Знаючі математику, звичайно, здогадалися, що для n точок буде n! варіантів комбінацій. І це все без урахування дорожньої ситуації і безлічі обмежень і вимог, які пред'являє до доставки сучасне місто. До того ж класичне завдання комівояжера будує маршрут для однієї людини, а рітейл сьогодні повинен будувати їх для десятків і сотень кур'єрів. І тут в гру вступають сили математики, обчислювальні потужності і величезна кількість даних. Звичайно, вручну виконати всі ці розрахунки і знайти оптимальний маршрут неможливо - логісту необхідна допомога алгоритмів.
Алгоритм Дейкстри і завдання маршрутизації транспорту (VRP)
Найвідоміший (і того заслуговує!) алгоритм пошуку найкоротшого шляху між точками (з певними обмеженнями) - це алгоритм Дейкстри. Його винайшов у 1959 році нідерландський вчений Едсгер Вібе Дейкстра, який отримав у 1972 році премію Тьюрінга, по суті, «нобелівку» з інформатики, за свій внесок у розвиток мов програмування і численні наукові статті, в тому числі з теорії графів. Саме графом найпростіше представити завдання доставки.
Адреси клієнтів і склади стають вершинами графа, а шляхи між ними - ребрами, які, звичайно, мають свою «ціну», будь то довжина маршруту або час у дорозі. Алгоритм «пробігає» по вершинах, перевіряючи всі шляхи до них і визначаючи мінімальні з них. Так, якщо шлях в точку по прямій «коштує» 10 одиниць, а через іншу точку 2 + 5 = 7, то алгоритм відкине перший варіант і в результаті видасть вам вартість 7! (Якщо, звичайно, не знайдеться якийсь ще більш «дешевий» шлях - можливо, через іншу адресу або через кілька інших адрес.)
Як розповідав сам Дейкстра, він розробив цей алгоритм всього за 20 хвилин під час походу по магазинах зі своєю нареченою. Дейкстра задумався, як знайти найкоротший шлях між двох міст і, коли вони зупинилися випити по чашечці кави, склав алгоритм в голові, без паперу і олівця.
Через три роки вийшла публікація. Весь опис проблеми і алгоритму вмістився на трьох сторінках. Алгоритм має свої обмеження. Зокрема, він не працює з негативними «цінами» доріг і може довго шукати найкоротший шлях до віддаленої точки, так як для його обчислення алгоритм «біжить» з точки А по всіх напрямках, поки один з них не призведе до зустрічі з цільовою точкою Б. Тим не менш саме його модифікації використовуються в багатьох картах.
Доставка товарів - це не тільки завдання пошуку найкоротших маршрутів, адже потрібно враховувати і сам товар. Так народилося завдання маршрутизації транспорту, яка лежить на перетині завдання комівояжера і завдання про упаковку рюкзака (як запхати якомога більше «цінних» речей, якщо місце обмежене). У реальному житті набагато більше параметрів, ніж проста «ціна» дороги, але, як не крути, саме з неї все і починається.
Почнемо з вирішення проблеми прогнозування заторів. Чим більше даних, тим краще буде прогноз. Де взяти достатньо даних? Наприклад, Яндексу допомагає, з одного боку, великий досвід у картографії, а з іншого - дані сервісів (наприклад, користувачів навігатора), які можуть використовуватися і в завданні маршрутизації комерційного транспорту. Для точного прогнозу заторів наступного дня Яндекс.Маршрутизація аналізує історичні дані на всіх ділянках маршруту.