Простая логистика своими руками



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

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

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

    Для начала пробовали решить проблему управленческими методами: постоянное измерение уровня топлива, показаний тахометра, измерение времени на доставку при личном сопровождении груза. Эффект был около ничего, кроме негатива, подозрений и лишних движений (измерять это тоже для кого-то работа). Если при одиночном маршруте ещё можно было определить примерные рамки, то при рейсе из 25-35 торговых объектов всё очень сильно менялось, разброс был очень большим, как по времени, так и по топливу.

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

    1. использовать один из сервисов для расчёта маршрутов и учёта ГСМ;
    2. поставить на автопарк модули трекинга/отслеживания положения;
    3. спроектировать что-то самим;

    Решили попробовать все три решения и выбрать наилучшее:

    1. Хорошее готовое решение на тот момент мы не нашли. Либо проектирование под ключ, но дорого, либо берите как есть и дальше по договорённости. Попробовали несколько онлайн сервисов. В целом не плохо, но в основном сложность сводилось к дублированию информации из учётной системы, количеству действий для получения результата (нажми здесь, перейди сюда, обнови справочник), всё онлайн (на тот момент это было критично). Но самый большой недостаток — это сложность в составление маршрутов с множеством точек и выбор лучшего маршрута. Обычно всё приходилось подбирать вручную, подгоняя значения, что долго и не всегда удачно в результате.

    После пары месяцев работы отказались от такого решения.

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

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

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

    Для начала завели все места посещения и внесли их гео-координаты в БД. Получали координаты по данным GPS трекера при посещении, а также визуально по картам OSM, находя нужное место мышью и копируя координаты.

    На втором этапе нужно было получить векторные карты региона в удобном формате.
    Выбор пал на тот же OSM, так как карты имеют открытый формат. Парсить дамп планеты мы не осилили, поэтому изначально выгружали данные кусками в XML, через экспорт из самого OSM, а затем соединяли территории. Позднее натолкнулись на проект GIS-LAB. Эти достойные люди на протяжении многих лет выкладывали ежедневный дамп территорий, разбитый по регионам. Но кушать хочется всем, проект в последнее время заглох, а ребята переехали, и делают ту же работу за вполне вменяемую цену.

    Получив карту в формате XML мы извлекли слой отвечающий за дороги согласно спецификации. Так как объём карт нескольких соседних регионов занимал десяток гигабайт, был написан SAX парсер на RUBY, он выбирал только нужные теги и объединял соседние регионы, в которых осуществлялась деятельность в единую структуру.

    Сам проект написан как внешняя DLL к учётной системе написанная на Pascal. Парк устройств, на которых должна была работать система, был мягко говоря устаревшим, поэтому было ограничение в 1 ГБ ОЗУ (Да, есть ещё компании, которые используют такую технику, 10 лет работает, проработает ещё столько же). Изначально было желание разбить карту на куски и грузить в ОЗУ по мере необходимости (как на навигаторах), но это было крайне медленно. В итоге удалось скомпоновать до разумной полусотни МБ.

    В OSM карты дорог представлены в виде векторных участков дорожного полотна с дополнительными атрибутами. В своём решении мы использовали списки смежности. Где вершина — это точка на карте, а рёбра — это пути к соседней точке. Для оптимизации мы считаем, что из одной вершины может быть максимум четыре пути (перекрёсток). Если путей больше 4, то нужно разбить ребро на два дополнительных, так у нас всегда для каждой точки карты будет фиксированное количество рёбер = 4. Такой подход позволяет производить выравнивание данных в памяти, хотя несколько избыточен.

    Стоит отметить, что Земля представляет собой, не шар (неожиданно), а геоид, но для целей картографии упрощают до сфероида или эллипсоида.

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

    код
    function distance(StartLong:Single; StartLat:Single; EndLong:Single; EndLat:Single) : Single;
    const
    D2R: Double = 0.017453;         // Degrees to Radians Conversion
    E2: Double = 0.006739496742337; // Square of eccentricity of ellipsoid
    var
    fPhimean: Double;                 // Mean latitude
    fdLambda: Double;                 // Longitude difference
    fAlpha: Double;                   // Bearing
    fRho: Double;                     // Meridional radius of curvature
    fNu: Double;                      // Transverse radius of curvature
    fR: Double;                       // Radius of spherical earth
    fz: Double;                       // Angular distance at centre of spheroid
    begin
    fdLambda := (StartLong - EndLong) * D2R;
    fPhimean := ((StartLat + EndLat) / 2.0) * D2R;
    fRho := (6378137.0 * (1 - E2)) / Power(1 - E2 * (Power(Sin(fPhimean),2)), 1.5);
    fNu := 6378137.0 / (Sqrt(1 - E2 * (Sin(fPhimean) * Sin(fPhimean))));
    fz := Sqrt(Power(Sin((StartLat - EndLat) * D2R/2.0),2) + Cos(EndLat*D2R) * Cos(StartLat*D2R) * Power(Sin(fdLambda/2.0),2));
    fz := 2 * ArcSin(fz);
    fAlpha := ArcSin(Cos(EndLat * D2R) * Sin(fdLambda) * 1 / Sin(fz));
    fR := (fRho * fNu) / ((fRho * Power(Sin(fAlpha),2)) + (fNu * Power(Cos(fAlpha),2)));
    distance := fz * fR;            // 1 единица 1 метр
    end;
    


    После создания базы дорог был необходим визуальный слой для отображения окружающего пространства. Тут помог проект maperitive, он позволил распарсить OSM карту регионов на тайловые участки по слоям приближения, точно так же как это делает 10^100 или Яндекс. Была попытка работать с картами гигантов онлайн, отрисовывая векторную карту поверх слоя браузера, но из-за лицензионных ограничений решили отказаться. В итоге создали виртуальный диск и залили туда дамп тайлов на пару десятков гигабайт, зато всё под рукой и не тормозит. Правда, примерно раз в полгода приходиться освежать, обычно это совпадает с перегрузкой карт.



    Для совмещения тайловой картинки и векторной карты нужно знать, что тайлы, Google, OpenStreetMap, Bing, Yahoo представлены в проекции Меркатора (точнее WEB MERCATOR, которая является проекцией на сферу), где каждый более глубокий слой в два раза детальнее предыдущего.



    Яндекс.Карты используют проекцию Меркатора эллипсоида.

    Это не принципиально, если можешь пересчитать гео-координаты на плоскость проекции и обратно.

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

    2^17 * 256 =33554432 (256 — размер ребра тайла в пикселях).

    код
    Const     
    size  =33554432; // размер карты на уровне детализации 17 в пикселях;
    center=16777216; // задаёт x и y координаты центра карты в пикселях;
    EXCT=0.081819790992; // коэффициент отклонение земли от сферы к эллипсу
    map_type=true; // тип проекции: истина – сфероид иначе эллипсоид 
    //=============================================================
    // Пересчёт долготы на плоскость
    function TO_X(X:Single):Integer;  
    begin
    TO_X := floor(center+size*(x/360)); // Координата X точки находящейся на долготе Lon;
    end;
    //=============================================================
    // Пересчёт широты на плоскость
    function TO_Y(Y:Single):Integer;  
    var ls:single;
    begin
    ls:=sin(Y*Pi/180);               // Cинус широты;
    if map_type then	 
     TO_Y := floor(center-atanh(ls)*(size/(2*Pi))) // Координата Y точки находящейся на долготе Lat для сферы
    else
     TO_Y := floor(center-(atanh(ls) - EXCT * atanh(EXCT * ls))*(size/(2*Pi))); // Координата Y точки находящейся на долготе Lat для эллипсоида;
    end;
    //=============================================================
    // Обратный пересчёт координаты пикселя в долготу
    function TO_LON(X:Single):Single;
    begin
    TO_LON := (X - center) * 360 / size;
    end;
    //=============================================================
    // Обратный пересчёт координаты пикселя в широту
    function TO_LAT(Y:Single):Single;
    var g:Double;
    begin
    if map_type then
     // Для сферы
     TO_LAT:= (180 / Pi)* (2 * ArcTan(exp((center - y) * 2 * Pi / size)) - Pi / 2) 
    else
    begin
     // Для эллипсоида
     g := (PI/2) - 2 * ArcTan(1 / Exp((20037508.342789 - (y*64) / 53.5865938) / 6378137)); 
     TO_LAT:=  180 / Pi * (g + 0.00335655146887969 * Sin(2 * g) + 0.00000657187271079536 * Sin(4 * g) + 0.00000001764564338702 * Sin(6 * g) + 0.00000000005328478445 * Sin(8 * g));
    end;
    end;
    //=============================================================
    


    Теперь, когда у нас есть базовые инструменты, мы можем приступить непосредственно к задаче создания оптимального маршрута. Соединяем торговые объекты с ближайшим ребром в графе дорог, а затем запускаем поиск кратчайшего пути. Для этого используем разновидность алгоритма Дейкстры для разряженной его вариации последовательно для каждого пункта посещения. На выходе получаем матрицу смежности, размера (N+1)*(N+1) с бесконечностью на главной диагонали (запрет кольца), где N-количество точек посещения без учёта точки выезда.

    Полученная матрица хранит минимальные расстояния по дорогам между всеми торговыми объектами, что является классической задачей коммивояжера. Так как алгоритмическая сложность такой задачи зашкаливает, мы использовали для решения метод ветвей и границ. При n <15 полный перебор, иначе подключали грубую оценку в глубину. Вариант конечно не идеальный, но вполне рабочий.

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

    Решение работает в организации порядка 7 лет, вполне успешно, хотя и не без недостатков, как в точности, так и в удобстве. Результаты вполне соотносятся с данными GPS-трекинга автомобилей. По моей оценке, внедрение логистики позволило сэкономить 10-12% выделяемых средств на топливо. Программа была спроектирована, запущена и сопровождалась всего одним человеком – Вашим покорным слугой.

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



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

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

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

    Подробнее
    Реклама

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

      0
      off не очень понятно какая цель этого «Параллельно с первыми двумя подходами решили реализовать в своей учётной системе возможность строить маршруты самостоятельно». Маршруты выгружались на навигаторы водителям?
        +3
        На основе маршрута формируется путевой лист. Денежные средства на топливо выделяются согласно ему же, зная средний расход топлива для конкретного автомобиля. Ведь всегда можно взять больше денег на дорогу и проехать больше чем нужно, но не для целей компании.
          0
          Я правильно понимаю, что в этом варианте местоположение автомобилей не отслеживается?
            0
            Да Вы правы, положение отслеживается выборочно, только если есть подозрения. Отдельного человека для проверок не выделили, установка устройств не сплошная, экономим.
            +1
            Я решал подобные задачи в компании, которая развозит питьевую воду примерно в 2006 году, уже тогда были абсолютно недорогие качественные решения для решения задачи коммивояжера по конкретной местности с учетом скорости движения от класса дорог. И маршруты строились хорошо. Почему я считаю, что хорошо? Потому что мы ставили черные ящики, которые писали координаты и по возвращению на базу производили обмен по радиоканалу. Анализ планового и фактического маршрута показал высокое качество планировнаия и расчета маршрута и километража. Есть ещё бытовой лайф-бизнес-хак — используйте маштны на газу, его слить труднее. И главное, расчет зарплаты был заточен на качество доставки — недоставка сильно влияла на зарплату, а исполнение плана давало хороший зароботок. При этом важно, что водители-экспедиторы давали очень качественную обратную связь и их мнение реально учитывалось. И ещё лайф-бизнес-хак, надо разбивать область доставки на зоны с коэффициентами за сложность-удаленность. Плюс органнизовать удобную загрузку(по времени, например), выбрать подходящие транспортные средства и т.д. Вот реальные задачи АйТи в среднем бизнесе)))
              0
              Есть ещё бытовой лайф-бизнес-хак — используйте маштны на газу, его слить труднее.
              Сложно «продать» на заправке и не залить себе в бак?
                0
                Ну бензин слить и продать легче, не так ли? Бензин более ликвидный, я считаю.
                  +1
                  Ничего сливать не нужно, приехал на заправку, отдал деньги, а тебе в замен чек. Если карточка — заправил в другую машину, забрал наличку. Не нужно ничего сливать в канистры и палиться, а потом бегай продавай. Не каждый захочет покупать непонятно что в канистре. Но то что сливать проще — это легко сказано, газ вообще не получится «слить».
              0
              Деньги на топливо выделяются? Прямо водителю? А может заправку организовать по договору?
                0
                Карта та же наличка только позже. Смысл един, выкатываешь много больше установленного, повод проверить, тогда и треки не помешают.
                0
                Хм, то есть, на сколько я понял, каждый день могут быть разные маршруты? Если нет, то как раз трекинг позволяет нарисовать геозоны, при выезде за которые идет сообщение в системе/смс/на почту.
                Пробег по путевому и по данным GPS сверяются?
                Также можно ставить датчик топлива, крайне полезно для грузовых автомобилей.
                При построении маршрута учитываются пробки?
                Нет разногласий у водителей касательно маршрута движения? Ибо основной аргумент — там пробка, я лучше знаю как ехать, лучше поехать вокруг, чем стоять в пробке.
                А исходники в закрытом доступе?
                  0
                  Маршруты очень разные, обычно водитель прикрепляется за направление, доставка по мере заказов.
                  Пробки отдельно не учитываются, входят в усреднение, если только нет конкретной проблемы вроде крупной аварии или ремонта дороги.
                  Водители иногда не согласны, выбирают свой маршрут, но он обычно не сильно расходится с заявленным, ведь дополнительных средств не выделят.
                  Зато как рада бухгалтерия, им для отчётности только подпись на рейсовом нужна, и чеки.
                  Исходники собственность компании.
                    0
                    То есть, пробеги с одометра никто не смотрит и уровень топлива тоже никого не интересует?
                      0
                      Почему же, смотрят, но не после каждого рейса, а примерно раз в неделю. Ну или если есть подозрения. Это же коммерческое предприятие для лишних действий свободных людей нет.
                        0
                        Знаю случаи, когда просто после установки устройств пробеги упали на 30% по всему автопарку. А если брать отдельно инкасаторскую службу, то все 50-60%. А если еще заглянуть в бак (с учетом того, что нормы могут быть выше факта), то в целом, затраты на ГСМ могут упасть на 30-40%. Считайте.
                          0
                          Знаю случаи когда такая экономия выходила боком. Смотря какая зп, конечно, но я рассматриваю этот бензин и пробег как некий бонус водителю за аккуратное вождение.
                            0
                            Ну да, есть разные степени контроля. Когда нет систем — счастливы водители, шины проходят нужные километры и они списываются, ТО проходят чаще, что можно и масло не менять, запчасти тоже иногда можно у себя оставлять, ибо старые как новые. То в таком случае з/п — это лишь малая часть того, где можно найти себе. Как я говорил выше — считайте. Если «дешевле» не платить з/п и делать расчет на левые доходы, то да — такие системы противопоказаны.
                              0
                              Запчасти меняются по фактическому пробегу на одометре, периодичность определяется производителем авто. Авто обслуживается в сервисе или механиком предприятия. Водитель никак не имеет отношения к обслуживанию.
                              Бензин и пробег конечно должен контролироваться, но не метр-в-метр. А не больше какой-то нормы. Экономия топлива пойдет в плюс самому водителю за аккуратное вождение. Он материально заинтересован в экономии бензина, значит будет выбирать маршруты без пробок, будет выбирать экономные режимы движения, а это значит и меньший износ шин и автомобиля. Он ведь не будет стартовать с пробуксовкой? Это и его же деньги в трубу вылетят?
                              0
                              Водители и воспринимали это как бонус. Но иногда такая бонусация выходила до половины ЗП. Зачем плодить тёмные схемы, если можно повысить ЗП, поощряя аккуратное вождение. Замечено, что разные люди на одном маршруте на одном и том же авто по-разному ездят, разница до 20% по топливу.
                                0
                                Ключевое «если можно повысить ЗП». С белой ЗП надо платить налоги. Поэтому в определенных случаях может быть выгоден «материальный» бонус.
                    0
                    То случайно клемма питания слетела, то при ремонте двигателя устройство из строя вышло, то электроника на солнце «перегрелась». Так за три года мы потеряли 9 устройств.

                    Если честно вы сами виноваты. Приведение в порядок трудового контракта решает многие проблемы (это уже из нашего опыта). Убытки причиненные из за разгильдяйства сотрудника, должны быть им-же компенсированы.
                      +1
                      Бывает достаточно трудно доказать что тот или иной человек виноват. А штрафовать просто за то что на твоей машине поломка…, хотя некоторых наказывали.
                      0
                      Оффтоп: компания Тандер (ака сеть Магнит)?
                        0
                        Увы нет. Мы мелкий региональный игрок, но очень приятно когда тебя сравнивают с такими китами.

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

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