company_banner

Яндекс.Маршрутизация: как мы окунулись в логистику и решили поменять будущее

    Этот текст возник благодаря появившейся в Яндексе забаве random coffee — система назначает встречу двум случайным сотрудникам, если они указали, что хотят участвовать в таких встречах. Мои собеседники находили рассказ о том, чем я занимаюсь, интересным, и вот у меня дошли руки предложить его более широкой аудитории.

    До Хабра я выступил с гостевой лекцией на факультете компьютерных наук Вышки и Яндекса — рассказал студентам ФКН ровно то же самое, о чем сейчас расскажу вам (в конце поста есть видео). А именно — как путешествия с водителями, развозящими заказы из интернет-магазинов, убедили нашу команду делать новый сервис про логистику. Надеюсь, у меня получится передать вам мои ощущения от этой сферы: я поездил в «Газели» и «Ларгусе», послушал жалобы сотрудников на придирчивую «тетку из Ногинска» и стал свидетелем того, как заказ из трех самокатов для трех детей превратился в драму. А в конце поговорим про технологии.

    Часть 1. Как все начиналось


    Несколько лет назад, гуляя по офису в раздумьях о том, не пора ли мне поменять что-то в жизни, я практически случайно столкнулся в коридоре с коллегой, которого сильно уважал по одному из прошлых проектов. Оказалось, он перешел во внутренний стартап, и они как раз ищут аналитика. Так я очутился в подразделении под названием B2BGeo. Эта небольшая на тот момент группа должна была делать какие-то штуки для компаний на базе геосервисов Яндекса — только никто не знал, какие именно. Исторически сотрудники геосервисов делают десктопные Яндекс.Карты, мобильные приложения Карт, Навигатора и Метро. Также в это подразделение входит внушительная инфраструктура: разработка движка маршрутизации, картографическая служба, распознавание дорожных знаков, извлечение данных из спутниковых снимков и многое другое. И веб-карты, и Яндекс.Навигатор — приложения, предназначенные для массового пользователя. Из сервисов для компаний у нас был только набор картографических API: JS-виджет карт для сайтов, MapKit для приложений и REST API построения маршрутов.

    Так что команде B2BGeo, прежде чем начать продавать продукты для компаний, предстояло эти продукты придумать. Некоторое время мы потратили на исследование рынка и создание прототипов. Прототипы были интересные, например карта качества сотового сигнала внутри зданий. Тогда сотовые операторы не использовали те огромные объемы данных, которые у них есть, измеряли качество в основном на улицах и довольно примитивным образом. Другой пример прототипа — универсальный кастомизируемый роутер с машинным обучением. Кстати, здесь и далее под роутером и маршрутизатором имеется в виду не сетевое оборудование, а программа построения маршрутов.

    Одни прототипы не взлетели, другими бы не заинтересовалось достаточное количество компаний. Нужно было нечто более масштабное. В перспективе — переворачивающее мир и открывающее новые горизонты, а для начала приносящее значительную пользу за счет геотехнологий. Мы провели стратегическую сессию: уехали из офиса и два дня брейнштормили. По итогам сессии определили отрасль, где есть для нас достаточные перспективы. Наш выбор пал на логистику.

    В России масса коммерческого транспорта, множество транспортных и курьерских компаний что-то куда-то возят. И все они, скорее всего, составляют свои маршруты либо вручную, либо с помощью программ, которые наверняка не очень хорошо работают, потому что не учитывают пробки. А у нас за спиной был целый Яндекс c большим количеством железа, пробочными данными, которые есть лишь у небольшого числа компаний (редкий пример — Google), и хорошими программистами. Компетенции в этой сфере редки и ценны: Uber в какой-то момент выкупил целую картографическую команду.

    Воодушевленные этой перспективой, мы договорились с одним из агрегаторов доставки (компанией, которая развозит заказы разных интернет-магазинов), чтобы они дали нам посмотреть изнутри на их работу, «погрузиться в индустрию». Участники нашей небольшой команды поездили с курьерами, развозящими заказы, и посидели рядом с логистом, который планирует маршруты.

    Часть 2. Погружение в индустрию


    8 утра, одна из промзон за Третьим транспортным кольцом, где находится склад и офис агрегатора. Небольшое помещение, напоминает отделение почты: угол огорожен конторкой, внутри — компьютеры логистов, телефоны, принтеры. Засаленные стулья и компьютерные кресла с потрескавшимся дермантином. Коробка с дешевыми китайскими телефонами, на каждый наклеена бумажка с номером — их раздают водителям. Вдоль стен простенькие диванчики-банкетки, у выхода стенд с распечатками: правила перевозки, какие-то внутренние инструкции, таблица штрафов — например, за недоставленный заказ с водителя снимут 200-300 рублей. У агрегатора есть еще и нормальный офис, где за красивыми столами сидят директор, менеджеры и бухгалтерия, но ключевые для нас события происходят именно в этой маленькой комнате.



    Водители курят на улице, но там прохладно, большинство стоят внутри, поэтому в помещении тесно и душно. Мат-перемат в три этажа, многие по-утреннему хмуры, кто-то хочет получить свою пачку накладных и уйти загружаться, у кого-то заминка, он недоволен. Обстановка напряженная, логистов двое, и они в мыле. Нам говорят, что это обычный день, просто утром, во время выезда на маршруты, всегда запарка. Ночью, когда шло планирование, тоже была запарка, где-то через часок напряжение спадет, и логист сможет отдохнуть.

    Нескольким водителям говорят, что «с вами поедет Яндекс». Они удивлены и не особо довольны — непонятно, с чего им такое счастье и не поставили ли нас за ними следить. Мы, офисные салаги IT-работники с рюкзачками, здорово контрастируем с этим хмурыми мужиками.

    Мне досталась «Газель», в ней водитель и экспедитор, я сажусь третьим с рюкзаком в обнимку и стараюсь не занимать слишком много места. Заказы уже погружены в кузов, стартуем.



    Позже я узнал, что обычно предшествует выезду автомобилей на маршрут.

    Допустим, сегодня среда, вы заказываете холодильник на небольшом сайте, который вы нашли на Яндекс.Маркете, у этого магазина лучшая цена и приемлемые отзывы. Доставка возможна только в пятницу, вас это устраивает. Сайт на самом деле является всего лишь витриной, у совсем мелких сайтов менеджер, подтвердивший заказ, вообще может быть единственным сотрудником. Ваш холодильник находится где-нибудь на складе под Подольском вместе с другими холодильниками той же фирмы (собственного склада у мелкого магазина нет — по сути, продажа идет со склада производителя). Менеджер бронирует этот холодильник и отправляет заказ агрегатору доставки. В течение среды агрегатор собирает заказы и в четверг отправляет большой грузовик в Подольск за вашим и другими холодильниками, заказанными в других магазинах. Все это приезжает на арендуемый агрегатором склад в московской промзоне.

    Вечером в четверг, когда все товары, которые предстоит доставить в пятницу, собраны на складе, за работу садятся логисты. К 4-5 утра они должны распределить заказы по машинам, складские работники разложат товары в кучки, каждой машине своя кучка — нужно оставить им запас времени на эту работу. Кучку загрузят в машину, и она поедет радовать заказчиков.




    Для распределения заказов по машинам логист использует специально купленную программу. Она интегрируется с 1С: Предприятием, в нее загружаются данные о машинах (допустимый вес и объем груза, стоимость дня работы) и о товарах (вес, объем, адрес и интервал доставки, контакты покупателя, комментарии). Часть машин принадлежит агрегатору, у этого были «каблучки» (Lada Largus) и «Газельки» (Газель/Ford Transit/Hyundai Porter). Также были наемные курьеры на личном автотранспорте, обычно на легковушках-универсалах (мы видели Ford Focus, Mitsubishi Pajero и даже какой-то старый Lexus).

    Программа написана хорошими программистами, она умеет разбрасывать грузы по машинам и строить оптимальный (по времени или пробегу) маршрут объезда заказов, учитывая кучу параметров. Но логист этой функциональностью никак не пользуется. Зато он активно использует визуализацию заказов на карте. Программа позволяет нарисовать на карте многоугольники-области и выводить статистику грузов и маршрутов внутри этих областей. Логисты разбили всю Москву и Подмосковье до «Большой бетонки» (трасса А108) на зоны примерно такого вида:



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

    В каждой такой зоне работают определенные водители, которые обычно хорошо с ней знакомы, знают дороги, особенности трафика, знают, где стоят гаишники, какие ограничения и знаки есть для грузовиков. Логист, в свою очередь, знает, сколько заказов может развезти экипаж. Более опытным он дает под 30 заказов, а тем, кто начал работать недавно, — 20-25 заказов. Он смотрит, сколько заказов попало в определенную зону, и если их слишком много, то перебрасывает в соседнюю. Или добавляет из соседней: скажем, с некоторыми водителями логист дружит и отдает им «легкие» заказы, которые, скорее всего, будут по дороге. А нелюбимому водителю может насолить. Например, подбросить заказ для клиента, про которого заранее известно, что он придирчив, потребует доставки строго в обозначенное время, распечатает все товары, будет их долго осматривать. Кроме того, логист может просто дать водителю меньше заказов: за каждый заказ водитель получает 200 рублей, он заинтересован в том, чтобы их было побольше.

    Возможность планирования маршрутов в программе игнорируется совершенно. Эта возможность в такой системе и не имеет смысла: если логист скажет водителю, как ему надо объезжать заказы, водитель ему ответит: «Вы там в офисе сидите, а я этот район как свои пять пальцев». Так что логист лишь назначает заказы на машину, задание водителю формулируется в виде кучки на складе и стопки распечатанных накладных.

    Итак, возвращаемся в «Газель». Наш район — шоссе Энтузиастов и дальше в сторону Ногинска, до МКАДа будет около 15 заказов, там я сойду. Водитель выезжает на Третье транспортное кольцо, в это время экспедитор берет пачку накладных и перекладывает их в правильном порядке. Правильный порядок такой:

    — Сначала мы поедем по шоссе Энтузиастов в сторону МКАДа и возьмем все заказы, которые справа. Слева не всегда берем, могут быть пробки при пересечении шоссе, лучше их вечером взять. Потом уедем в область, там развезем. Вечером поедем обратно и развезем оставшееся.
    — А вот, к примеру, первый заказ в стопке — с пожеланием «после 14 часов»? Оставите его на вечер?
    — Можно и на вечер, но лучше попробуем договориться, чтобы отдать сейчас.

    Процесс «договаривания» был продемонстрирован немедленно. В 9:30 экспедитор позвонил по телефону заказа «после 14 часов»:

    — Здравствуйте, доставка, мы уже в вашем районе, сможете заказ принять?.. Мы после вашего района поедем в область, и сюда уже до вечера не вернемся. Может быть, вернемся после девяти, а может быть, совсем задержимся в области, тут дело непредсказуемое, возможно, придется на другой день доставку переносить… Хорошо, тогда через 15 минут подъедем.

    Вот тут-то я и понял, откуда берутся курьеры, которые говорят: «Здравствуйте, я уже у вас!» — и совершенно игнорируют мои комментарии и интервал доставки!

    Коллеги, которые поехали в других машинах, рассказывали, что у кого-то водитель или экспедитор честно звонил клиенту за час до доставки. Мои же были не очень общительны, звонили минут за пятнадцать, проговаривали комментарии клиентов вслух. Простые пожелания («не звоните в домофон, ребенок спит») учитывались, но все, что влияло на маршрут, обычно игнорировалось. Перекладывая накладные, экспедитор выудил заказ, который требовалось отвезти в поселок в нескольких километрах от Ногинска.

    — О, снова эта тетка. Помнишь, у нее был заказ, потом возврат по браку? Теперь новый заказ.
    — Ага, опять стиралку поднимать. Еще интересная такая: «просьба доставить с 12 до 16». Как она себе это представляет?
    — Да вообще, они не понимают, что пишут. Я так считаю: если ты в Ногинске своем заказываешь стиральную машину, так сиди себе и жди спокойно, пока ее привезут. Или договорись как-то с соседями, или с работы отпросись. Мы же не можем каждый день в ее этот Ногинск ездить.

    Около МКАДа я сошел, а водитель повел «Газель» дальше по Горьковскому шоссе. На самом деле, они неплохие ребята, и, несмотря на бухтение в адрес клиентов (оно составляло не менее двух третей всех разговоров), скорее всего, успели бы доставить стиралку до 16. Просто если бы не успели, то даже не побеспокоились бы.

    Вторая моя поездка состоялась на машине поменьше: грузовой «Ларгус» ездил по СЗАО. Грузы были мелкие, никаких холодильников, поэтому водитель был один. Дядька попался общительный, мы с ним о многом поговорили. Он сказал, что вообще он мастер спорта по борьбе, работает тренером, но сейчас все глухо, поэтому подрабатывает курьером. Деньги небольшие, но прибавка приятная: за день получается порядка 2 тысяч. Доставлять заказы несложно, работает, когда хочет. Конечно, есть нюансы: попадаются неприятные клиенты, питаться приходится в машине припасенными бутербродами, постоянная спешка, даже в туалет не сходишь, приходится у клиентов проситься. Но в целом он вполне благополучен, для него это скорее развлечение.

    Забавно: коллегам, особенно девушкам, сотрудники служб доставки тоже рассказывали истории, что «Курьерка не основная работа, а чисто для души», «Вообще я обычно на бэхе езжу» и т. п.

    Помню, в районе Рублевки или Крылатского состоялся у нас такой разговор:

    — Как-то в Сити привозил заказ, там у них в небоскребе апартаменты, коридоры все в мраморе, захожу в квартиру — ковры, картины в золотых рамах, шубы какие-то висят, чего только нет. Заказ на 5800, так он сдачу 200 рублей попросил, прикинь?!
    — Так, может, у него шубы и картины именно из-за того, что он даже 200 рублей экономит.

    После моих слов водитель крепко задумался. А еще через час мы приехали в Щукино и я «все понял» про этот бизнес.

    В очередной накладной ручкой была сделана пометка, что с заказом не все в порядке: из трех купленных детских самокатов общей стоимостью 20 тысяч рублей в машине лежали только два. Водитель позвонил логисту. Оказалось, что женщина сделала заказ на три самоката в понедельник, но вчера, в среду, третий самокат по ошибке положили не в ту машину. А это была машина частника, он вечером почему-то не вернулся на склад, как делают «штатные» водители, и самокат по-прежнему ездит вместе с ним. Мы могли бы попробовать его перехватить, но он сегодня ездит по своим делам, пересечься не получается. В следующий раз он будет работать завтра (в пятницу), но это не точно. Гарантированно воссоединить все три самоката и отвезти их разом можно будет только в субботу.

    Вооружившись этой информацией, водитель позвонил клиенту. Там оказалась очень недовольная женщина. Она сказала: в субботу в 10 утра у них семейный праздник, где трем ее детям хотели подарить самокаты. Поэтому они ей нужны строго в количестве трех штук, на частичный выкуп она не согласна и вообще не понимает, как так можно — она сделала заказ в понедельник, а теперь мы, магазин самокатов, так ее подставляем. Доставка в субботу в неопределенное время ее не устраивает категорически. Завтра она дома до обеда, если не можете сегодня или завтра утром, то она отменяет заказ и проклинает магазин до третьего колена (и ее можно понять).

    Часть 3. Локальный минимум


    Магазин покупает услугу доставки заказов у курьерской компании. За недоставленные самокаты он оштрафует курьерскую компанию на 500 рублей. Компания оштрафует своего кладовщика и водителя, который не привез самокат обратно вовремя, на 200-300 рублей. Расстроенная женщина отдаст свои 20 тысяч более расторопному магазину, а этому влепит одну звезду на Яндекс.Маркете. Магазин может оказывать самый лучший сервис, но «последняя миля» осуществляется хмурыми мужиками на «Газелях» и «Ларгусах». Если они будут нехорошо себя вести с клиентами, магазин никак не сможет на это повлиять.

    В то же время магазин обычно ищет минимальную по стоимости доставку — в том смысле, что если платить водителям еще меньше, то они пойдут работать таксистами или куда-то еще. Водители оптимизируют свой дневной заработок — надо развозить побольше заказов и не быть оштрафованным. Если составить глобальную функцию стоимости, которая описывает систему в целом, то это состояние функции наверняка будет соответствовать ее локальному минимуму, «потенциальной яме».



    В этой яме явно есть большие, системные проблемы. Во-первых, самая сложная работа отдана в руки самого неквалифицированного сотрудника: водитель и машиной управляет, и маршрут планирует, и с клиентом общается. А еще возит деньги. У него появляются дополнительные навыки и специализации — например, умение развезти 30 заказов за день в определенном районе. Получается, компания должна обучать неопытных водителей, а опытных не терять, потому что их (к несчастью для компании) сложно заменить.

    Во-вторых, процесс доставки совершенно непредсказуем. Клиент не знает, во сколько к нему приедут. Клиенту обычно предлагают широкие окна доставки — четыре, шесть часов или больше. Это создает для него большие неудобства: не всегда можно шесть часов сидеть на одном месте. И даже в эти окна водители не всегда могут попасть. Возможность сделать более узкие окна, удобные покупателям (два часа, а лучше час), есть только у крупных компаний, которые смогли оттолкнуться посильнее и выпрыгнуть из потенциальной ямы в более оптимальное состояние. Речь идет о фирмах с собственной доставкой и курьерами. «Свои» курьеры пригодились бы всем компаниям: так можно контролировать качество их работы и даже делать какой-нибудь upsale (когда курьер предлагает человеку что-то докупить к заказу). Но держать штат курьеров очень дорого — только самые крупные фирмы вроде WildBerries или Lamoda могут себе такое позволить.

    В-третьих, логисты постоянно читерят. В порядке вещей считаются такие трюки, как перегруз машин и нарушение смен водителей (вместо 8 часов они работают по 10-12). «Ничего страшного — если не влезет по объему, то он положит лишнее в кабину» — даже такое бывает. За это положены штрафы, особенно за перегруз фур: к самому штрафу (от ста тысяч рублей с компании) добавят возмещение ущерба дорожному полотну. Оно считается умножением коэффициента перегруза на расстояние и легко может достигать сотен тысяч рублей. Владельцы автопарков рады бы ездить без нарушений. Но предположим, у логиста есть выбор:

    — «Впихнуть лишний паллет, немножко превысив»
    — «Добавить лишнюю машину, увеличить затраты, зато без нарушений»
    — «Посидеть еще полчаса и составить план как следует»

    Часто он выбирает первое.

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

    Часть 4. MVRP и пробки


    Ниже будут технические подробности нашего продукта, поэтому начнем с определения. MVRP — это multiple vehicle routing problem, то есть задача, в которой нужно оптимально объехать несколько локаций, обладая автопарком из нескольких автомобилей. Мы используем терминологию, в которой аналогичная задача для одной машины называется SVRP (single VRP). От классической задачи коммивояжера (TSP, travelling salesman problem) она отличается наличием окон доставки. Единой терминологии, кажется, нет: в статье в Википедии решаемые нами задачи называются сложной аббревиатурой VRPPDTW (VRP с режимом pickup-and-delivery и окнами доставки).

    Программы, решающие подобные задачи, традиционно называются «солверами». Для универсальности надо в солвер поместить еще кучу опций и ограничений:

    Примеры дополнительных опций
    — Вес и объем заказов, вместимость автомобилей.
    — Сервисное время заказов (например, время вручения), время загрузки автомобиля.
    — Совместимость заказов с машинами и друг с другом (мясо и молочку надо возить в холодильнике, но не в одном и том же одновременно).
    — У разных авто разная стоимость эксплуатации. Кроме того, обычно автопарк состоит из наемных и собственных машин компании: свои обходятся дешевле, поэтому их надо грузить по полной.
    — Нужно соблюдать восьмичасовые смены у водителей.
    — Маршруты бывают многодневными.
    — Если несколько заказов нужно везти в одну локацию (например, запланировано несколько доставок в один бизнес-центр), то иногда их можно обрабатывать одновременно: курьер садится на диван в холле и звонит сразу всем клиентам. Тогда время на обработку заказов становится меньше, чем число заказов * время на заказ.
    — Иногда возникает требование к «кучности» маршрута, пусть и в ущерб общей оптимальности. Кучный маршрут гораздо лучше реагирует на изменения в отдельных заказах, он не ломается, если кто-то попросил перенести доставку на час раньше или позже.
    — Требование сбалансированности маршрутов: лучше, когда все водители выполняют примерно равный объем работы.

    Есть несколько видов алгоритмов, которые могут использоваться в солверах. Например, есть большая группа универсальных опенсорсных и платных constraint-солверов (Google OR-Tools, OptaPlanner, Choco-solver). Внутри каждого из них строится функционал, который оптимизируется с учетом требуемых ограничений. Такие солверы обычно умеют решать целую пачку задач: VRP-задачи, составление расписаний, оптимальное распределение ресурсов в облаке.

    Также есть много коммерческих решений, заточенных именно под MVRP-задачи и готовых к интеграции с системами управления предприятием. В России известны VeeRoute, Maxoptra, Антор.

    Солвер Яндекс.Маршрутизации использует комбинацию алгоритма симуляции отжига и генетического алгоритма. Мы не знаем, что используют конкуренты, но, скорее всего, что-то похожее. По нашим измерениям, на VRP-задачах constraint-солверы очень сильно проигрывают коммерческим солверам.


    Решение TSP-задачи объезда штатов в Америке

    Сразу оговорюсь: тема решения MVRP-задачи настолько велика, что в статье мы не будем подробно ее касаться, а лучше напишем отдельную статью.

    Основные входные данные для солвера — матрица расстояний между точками, участвующими в планировании (точки заказов плюс одно или несколько депо). На самом деле это не одна матрица, а две: по километражу и по времени проезда. Именно за счет этих матриц делается оптимизация. Как уже говорилось, у Яндекса, в отличие от разработчиков остальных коммерческих решений, есть информация о пробках. То есть для нас матрица не постоянна, а меняется во времени, и мы учитываем это в солвере. Насколько нам известно, так в мире никто не делает: даже зная всё о пробках, сложно построить набор матриц расстояний с разумной дискретизацией (достаточной для того, чтобы итоговые маршруты получались хорошими). Дело в том, что число ячеек матрицы растет квадратично от числа заказов.

    Предположим, мы решаем VRP-задачу по развозу 10 000 заказов при помощи парка из 500 машин. Тогда у нас получатся две огромные матрицы, меняющиеся во времени. Одно их скачивание по сети займет немало времени, а ведь их содержимое нужно сначала посчитать. Если делать это недостаточно эффективно, нам потребуется подождать пару часов, пока матрицы построятся и скачаются, и только потом можно будет запускать солвер. Здесь нам помогает алгоритм Дейкстры: вычисление больших матриц расстояний можно реализовать за почти линейное (от размера матрицы) время. Но и об этом наша команда расскажет в отдельной статье в ближайшие недели.

    Итак, мы построили умный солвер, распараллелили его на кучу машин, сделали роутер со сверхбыстрыми матрицами расстояний, которые учитывают пробки, а также придумали, как эти матрицы в солвер засунуть. В итоге получили возможность за 15 минут решать задачи по объезду 3000 локаций. Результат на карте:



    Часть 5. Результаты и трудности внедрения


    Можно сравнить наши маршруты и маршруты, построенные логистами, которые планируют поездки вручную или (иногда) в полуавтоматическом режиме с использованием программ-конкурентов. В типичном случае наше решение позволяет обыгрывать логистов в среднем на 20% с небольшим в оптимальности маршрута. При этом время до получения готового маршрута гораздо ниже — 15 минут вместо нескольких часов. В прекрасном будущем логист должен превратиться из нервного измотанного человека, раскидывающего заказы по машинам посреди ночи, в респектабельного члена общества. Он будет пользоваться нашим автоматическим планированием и изредка поправлять руками единичные краевые случаи.

    Наиболее гладко внедрение проходило, когда клиенты покупали наше решение в момент открытия своей службы доставки. Но большинство наших клиентов — не новички. У них уже есть внедренное решение для логистики, и чем крупнее клиент, тем сильнее оно обросло всевозможными особенностями процессов именно этой компании, да и просто костылями. Их разработкой и поддержкой занимается своя или наемная IT-служба. Есть мнение, что крупные фирмы (даже если преимущества нашего продукта для них очевидны) могут внедрить Маршрутизацию только вместе с крупным обновлением IT-инфраструктуры. А это обычно случается раз в несколько лет. В мае 2018 года наш новорожденный сервис был анонсирован на конференции YaC 2018 в партнерстве с ИКЕА. Спустя полгода началось внедрение, мы стали обмениваться данными, а спустя год на отраслевой конференции по логистике руководитель проектов в ИКЕА рассказал о результатах.

    Результаты оказались позитивными, но немного неожиданными для нас. Например, информирование клиентов повысило их удовлетворенность и существенно снизило число обращений в кол-центр (раньше, ничего не зная о судьбе купленного дивана, люди нервничали и начинали звонить).

    Или другой пример — с нефтяниками.
    Однажды Маршрутизацией заинтересовались нефтяники, развозящие бензин по заправкам с нефтеперерабатывающего завода. Заправки могут находиться на значительном удалении от завода, на каждой из них несколько видов топлива. Нужно, чтобы заправка «не просыхала» — то есть чтобы топливо всегда было в наличии. Цистерна бензовоза состоит из нескольких отсеков, в каждый можно залить свой вид топлива, но заливать и сливать можно только отсек целиком, иначе жидкость «бултыхается» и опрокидывает бензовоз (если интересно, на YouTube есть несколько видео того, как это происходит). Слив идет с хвоста, бывают цистерны с правым и левым сливом (а также универсальные, на обе стороны), и на заправках тоже иногда можно подъехать только с определенной стороны, то есть бензовозы и заправки бывают несовместимы. Вишенка на торте: для бензовозов существует свой дорожный граф — им разрешено передвигаться только по определенным дорогам, заявки на маршруты одобряются в ГИБДД, которое смотрит, чтобы маршрут не проходил рядом со школой и т. п. Пока мы не можем сделать поддержку такого большого объема специфичных фич.

    То есть оказалось, что наша изначальная установка не совсем верна. Мы-то думали, что будем продавать эффективный объезд точек, а оказалось, что компаниям нужны разные продукты, влияющие на разные показатели, а не только и не столько на эффективность. К счастью, вместе с основным технологическим продуктом мы поставляем еще несколько.

    Небольшие компании лучше преодолевают трудности интеграции, но могут столкнуться с человеческим фактором. Очень трудно убедить водителя следовать запланированному маршруту и держать включенным телефон с трекинговым приложением. Это чем-то напоминает истории про крестьян XIX века, ломавших механизированные косилки и плуги. Всё, конечно, не так печально, но сопротивление прогрессу присутствует.

    Заключение


    За короткое время нам удалось выстроить продукт, который, как мы надеемся, перевернет всю логистику в стране (или хотя бы сильно на нее повлияет). В нас верят наши действующие клиенты и Яндекс. Последнее тоже немаловажно: да, внутреннему стартапу живется спокойнее, чем стартапу за пределами компании, но и нам нужно показывать результат.

    Мы начинали с акцентом на крупные компании, в наших дальнейших планах — снижать порог входа в сервис. Поиграться с решением SVRP-задач можно прямо на Яндекс.Картах: при добавлении в маршрут четвертой точки появляется кнопка «Оптимизировать», которая вызывает наш солвер.



    Видео этого же рассказа для студентов ФКН в Вышке:


    Всем оптимальных маршрутов!
    Яндекс
    Как мы делаем Яндекс

    Комментарии 17

      0
      Логичный вопрос — кто ваши «конкуренты»? Из моего не очень богатого опыта приходит на ум название ArcGIS, например. У которого как раз есть REST API, в том числе включающий задачи VRP.

      С чем конкретно уже сравнивали, если сравнивали?
        +1
        Sygic Routing API ИМХО
        Не знаем как работает по России. Проверим в ближайшее время.
        Я.Маршрутизацию тоже потестим, если дадут обещанный триал.
          0
          Да, вопрос «как работает» хороший. Карты ведь тоже свои… не факт что самые точные. Не факт, что геокодирование работает (Зеленоград кстати, отличный пример).
            +1
            если дадут обещанный триал

            триал идет в данный момент и до середины апреля, 3 месяца бесплатно новым подключившимся компаниям
            не знаю, уместно ли тут оставлять ссылку, могу отправить в личку, если интересно
              0
              Все кто мог тут уже оставили свои контакты, так что возможно и уместно.
              Триал я получил у тех кто его и обещал.
              С нашими расчетами, проверенными опытным путем расстояния совпадают.
              Сама тема маршрутизации немного пока не наша, может просто не дорасли и специфика другая.
              В вашу копилку www.avtodispetcher.ru/api — пользуемся для расчета расстояний. Качество приемлемое.

              И чтобы два раза не бегать вопрос к мы (компания BIA-Technologies)
              А вот раз уж вы взялись хвалиться.
              У вас на сайте раздел Тарифы лежит или это секретная информация.
              И как вы через Яндекс API считаете грузовой контур.
              Например сейчас много трасс закрыто на просушку.
            0
            В России известны VeeRoute, Maxoptra, Антор

            вот это те, с кем мы конкурируем за контракты
              0
              Очень напомнило ключевой проект, разрабатываемый в моей компании.
              А запрос от «нефтянников» был не из Газпром-Нефти, случайно?
              Если да — могу (т.к. нашёл эту информацию в открытых источниках, и ничего не рассекречиваю) сказать, что мы (компания BIA-Technologies) его взяли.
              Есть слухи, что и другие нефтенники хотят купить у нас этот продукт, но пока это только слухи
                0
                А запрос от «нефтянников» был не из Газпром-Нефти, случайно?

                не могу сказать ) у нас есть несколько публично известных партнерств, но это, кажется, не из их числа

                BIA-Technologies

                Прикольно, если я правильно понял, вы сделали свой ati.su, теперь пилите маршрутизацию в каком-то виде.
                Даже грузовой навигатор есть! А откуда карты брали, если не секрет?
                  +1
                  Исторически, мы делали всю «внутрянку» Деловых линий (когда-то даже были частью этой компании, потом нас отделили).
                  Про технические детали грузового навигатора, к сожалению, не в курсе.

                  На моих глазах делается проект «логистика автодоставки», помогающий рулить «газельками и каблучками». Там тоже есть разделение городов на зоны, учёт пробок и всякое такое. Геокодирование и учёт пробок мы делаем через ваше API (куплена лицензия). Вывод сгенерированных маршрутов для логиста — вроде как, тоже, для водителя — не знаю.

                  Движение межтерминальных фур сейчас построено по принципу «логист разбросал груз, водитель поехал».

                  В проекте для Газпром-Нефти точные маршруты тоже не строятся, только порядок посещения пунктов (стоянка, нефтезавод, АЗС) исходя из введённого заказчиком взвешенного графа, сколько в среднем занимает любое перемещение. А типы топлива, совместимость АЗС и бензовозов и вот это всё — учтено.
            +4

            Ждём последующих статей с обещанными техническими деталями и прочим хардкором (это всё же хабр, не забывайте).

              0
              По маршрутизации понятно, но мне кажется здесь есть еще чисто технический лайфхак по загрузке. На загрузку каждой машины из припасенной для нее кучки явно уходит минут 15, а то и больше. И наверняка из-за этого выстраивается очередь на загрузку. Чего бы не сделать как в авиации — на каждый размер машинки сделать свой поддон, весь груз упаковывать на него и закидывать этот поддон на машинку вилочным погрузчиком?
                +1
                Чего бы не сделать как в авиации — на каждый размер машинки сделать свой поддон, весь груз упаковывать на него и закидывать этот поддон на машинку вилочным погрузчиком?
                В авиации стандартизация по размерам — чуть больше чем в 100% современных конструкций планеров. В отличие от автотехники, где только европаллет — единственный стандарт. Остальные типы паллет не стандартизированы. К тому же что-то запихивать вилочным погрузчиком в размеры Газели и меньше — не самое лучшее решение) Минимум 5 раз видел вывалившийся набок из Газели погрузчик. То о чем Вы говорите делается такой штукой.

                А вообще тема складской логистики — отдельное искусство. Склад начинает проектироваться от потока товаров (частота и объем движения SKU, массогабаритные характеристики SKU и еще пара сотен параметров). И если экономика говорит, что так выгоднее, то вся автоматизация и механизация идет лесом и авто грузится руками без паллет покоробочно. Как тот склад готовой табачной продукции JTI, где я когда-то работал аналитиком складских бизнес-процессов.
                +2
                Попробовал солвер на карте, думал, может когда-то пригодится для личных нужд, но не понял как зафиксировать последнюю точку.
                Без этого польза существенно меньше.
                  0
                  Странно, ведь в посте как раз про «вернулся на склад» присутвует.
                    0

                    Нет, к сожалению, все верно. Речь про веб-карты, туда выкатили сильно урезанную функциональность, поэтому сейчас оно не для всех сценариев подходит. Возможно, в будущем что-то поменяем/улучшим.

                  0
                  Было бы интересно если бы вы выложили матрицу и точки для 3000 локаций, ваше решение, чтобы посмотреть бенчмарк (мы тоже занимаемся VRP задачами)
                    0
                    можно попробовать, ответил в личку

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

                  Самое читаемое