Главная » Хабрахабр » Простая логистика своими руками

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В своём решении мы использовали списки смежности. В 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, которая является проекцией на сферу), где каждый более глубокий слой в два раза детальнее предыдущего.

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

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

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

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 полный перебор, иначе подключали грубую оценку в глубину.

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

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Тест: подходит ли тебе удаленка (не фриланс!)?

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

Кипр — минутка мягкого психодела

Фламинго в Ларнаке на Кипре. Поселение, кстати, по-нашему будет «Гробово», потому что «ларнака» — это саркофаг, а их тут в окрестностях нашли немало. Так город и назвали. Здесь тепло, приятно, рядом море, вокруг солнце, небо — ну как в таких ...