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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 ^[9], он позволил распарсить OSM карту регионов на тайловые участки по слоям приближения, точно так же как это делает 10^100 или Яндекс. Была попытка работать с картами гигантов онлайн, отрисовывая векторную карту поверх слоя браузера, но из-за лицензионных ограничений решили отказаться. В итоге создали виртуальный диск и залили туда дамп тайлов на пару десятков гигабайт, зато всё под рукой и не тормозит. Правда, примерно раз в полгода приходиться освежать, обычно это совпадает с перегрузкой карт.

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

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

Это не принципиально, если можешь пересчитать гео-координаты на плоскость проекции и обратно.
Мы выбрали 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;
//=============================================================

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

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

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

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

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

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

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

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

Автор: rebuilder

Источник ^[16]