F谩cil log铆stica de bricolaje



Quiero compartir con ustedes la experiencia de crear un sistema log铆stico en una empresa comercial.

Un buen d铆a, cerca del 2012, el jefe estableci贸 la tarea: pensar en el problema de optimizar los costos de log铆stica de transporte de la organizaci贸n.
El principal campo de actividad de la empresa es la venta al por mayor y la entrega de productos, donde los costos de transporte ocupan una parte significativa de los costos.

La gerencia consider贸 que hab铆a llegado el momento de poner las cosas en orden para gastar dinero en combustible, y tambi茅n hab铆a sospechas de que los conductores tambi茅n estaban involucrados en la entrega "a la izquierda" entre vuelos. En las peque帽as y medianas empresas, mucho se basa en la confianza, ya que mantener a las personas bajo control no es rentable y no siempre es aconsejable. Cuando los costos aumentan y la eficiencia disminuye, solo necesita hacer algo.

Para empezar, tratamos de resolver el problema mediante m茅todos de gesti贸n: medici贸n continua del nivel de combustible, lecturas del tac贸metro, medici贸n del tiempo de entrega con acompa帽amiento personal de la carga. El efecto no fue m谩s que negatividad, sospecha y movimientos innecesarios (medir esto tambi茅n es un trabajo para alguien). Si todav铆a era posible determinar un alcance aproximado con una sola ruta, entonces con un vuelo de 25-35 establecimientos minoristas todo cambi贸 mucho, la extensi贸n fue muy grande, tanto en tiempo como en combustible.

Objetivo: enviar veh铆culos ocupados a empresas comerciales, reduciendo el kilometraje y, por lo tanto, los costos. Si es posible, evite desviarse de la ruta. El objetivo es reducir los costos con una inversi贸n m铆nima en finanzas y tiempo de implementaci贸n, por as铆 decirlo ayer. Durante las discusiones, acordaron varias alternativas:

  1. use uno de los servicios para calcular rutas y contabilizar combustible y lubricantes;
  2. poner en la flota de seguimiento / m贸dulos de seguimiento;
  3. dise帽e algo usted mismo;

Decidimos probar las tres soluciones y elegir la mejor:

1. En ese momento, no encontramos una buena soluci贸n llave en mano. O dise帽o llave en mano, pero costoso, o t贸malo como est谩 y m谩s lejos por acuerdo. He probado varios servicios en l铆nea. En general, no est谩 mal, pero b谩sicamente la dificultad era duplicar la informaci贸n del sistema de contabilidad, la cantidad de acciones para obtener el resultado (haga clic aqu铆, vaya aqu铆, actualice el directorio), todo est谩 en l铆nea (en ese momento era cr铆tico). Pero el mayor inconveniente es la dificultad de crear rutas con muchos puntos y elegir la mejor ruta. Por lo general, todo ten铆a que seleccionarse manualmente, ajustando los valores, que como resultado era largo y no siempre exitoso.

Despu茅s de un par de meses de trabajo, rechazaron esta decisi贸n.

2. Como experimento, instalaron m贸dulos de rastreo GSM en una docena de autom贸viles.
El resultado es m谩s exitoso. Siempre sabes d贸nde estaba el auto. Pero el costo es m谩s caro que la primera opci贸n. Sin embargo, despu茅s de identificar un par de casos de desviaci贸n de la ruta (un shabat del conductor, el segundo visit贸 a la dama del coraz贸n, durante las horas de trabajo), los empleados comenzaron a deshacerse intensamente de dichos dispositivos. Aunque no hab铆an aceptado con entusiasmo esta innovaci贸n antes. O el terminal de alimentaci贸n parpade贸 accidentalmente, o cuando el motor estaba siendo reparado, el dispositivo fall贸 o la electr贸nica se "sobrecalent贸" al sol. As铆 que durante tres a帽os perdimos 9 dispositivos. En general, la decisi贸n result贸 ser positiva, pero debido a las desventajas: tuve que mirar las rutas recorridas durante mucho tiempo para identificar actividades sospechosas, lo que no es muy conveniente. Una ventaja en el sistema de seguimiento fue el art铆culo al exportar la pista, que permiti贸 acumular ciertas estad铆sticas en las rutas.

M谩s tarde, utilizamos otro sistema de uno de los principales operadores m贸viles para comunicaciones corporativas y rastreamos la actividad de los agentes de ventas, el resultado fue similar: las tarjetas SIM se rompieron, los tel茅fonos se perdieron, se olvidaron en casa, la bater铆a se agot贸, la gente siempre encontrar铆a una salida.

3. Paralelamente a los dos primeros enfoques, decidimos inventar una bicicleta para darnos cuenta en nuestro sistema de contabilidad de la capacidad de construir rutas nosotros mismos.

Primero, trajimos todos los lugares de visita e ingresamos sus coordenadas geogr谩ficas en la base de datos. Obtuvimos las coordenadas de acuerdo con el rastreador GPS cuando visitamos, as铆 como visualmente de los mapas OSM , encontrando el lugar correcto con el mouse y copiando las coordenadas.

En la segunda etapa, fue necesario obtener mapas vectoriales de la regi贸n en un formato conveniente.
La elecci贸n recay贸 en el mismo OSM, ya que las tarjetas tienen un formato abierto. No dominamos el basurero del planeta, por lo que inicialmente cargamos los datos en pedazos en XML, a trav茅s de la exportaci贸n desde el propio OSM, y luego conectamos los territorios. M谩s tarde se encontr贸 con un proyecto GIS-LAB . Estas personas dignas durante muchos a帽os presentaron un vertedero diario de territorios, desglosados 鈥嬧媝or regi贸n. Pero todos quieren comer, el proyecto se ha estancado recientemente, y los muchachos se han mudado , y est谩n haciendo el mismo trabajo por un precio razonable.

Habiendo recibido el mapa en formato XML, extrajimos la capa responsable de las carreteras de acuerdo con la especificaci贸n . Dado que el volumen de tarjetas de varias regiones vecinas ocupaba diez gigabytes, el analizador SAX se escribi贸 en RUBY, seleccion贸 solo las etiquetas necesarias y fusion贸 las regiones vecinas en las que las actividades se llevaron a cabo en una sola estructura.

El proyecto en s铆 est谩 escrito como una DLL externa al sistema de contabilidad escrito en Pascal. La flota de dispositivos en los que se supon铆a que el sistema deb铆a funcionar era, por decirlo suavemente, obsoleta, por lo que hab铆a un l铆mite de 1 GB de RAM (s铆, tambi茅n hay empresas que utilizan esta t茅cnica, han estado trabajando durante 10 a帽os y funcionar谩n en la misma cantidad). Inicialmente, hab铆a un deseo de romper la tarjeta en pedazos y cargarla en la RAM seg煤n fuera necesario (como en los navegadores), pero fue extremadamente lenta. Como resultado, logramos componer hasta cincuenta MB razonables.

En OSM, los mapas de carreteras se representan como secciones vectoriales de la carretera con atributos adicionales. En nuestra decisi贸n, utilizamos listas de adyacencia . Donde el pico es un punto en el mapa, y los bordes son los caminos a un punto vecino. Para la optimizaci贸n, creemos que puede haber un m谩ximo de cuatro caminos (intersecci贸n) desde un v茅rtice. Si hay m谩s de 4 rutas, debe dividir el borde en dos adicionales, de modo que siempre tengamos un n煤mero fijo de bordes = 4 para cada punto del mapa. Este enfoque nos permite alinear los datos en la memoria, aunque es algo redundante.

Vale la pena se帽alar que la Tierra no es una bola (inesperadamente), sino un geoide , pero a los efectos de la cartograf铆a se simplifica a un esferoide o elipsoide .

Para nuestros prop贸sitos, encontr茅 una f贸rmula para calcular las distancias entre dos puntos en la superficie de un elipsoide, del cual no pod铆a entender el significado m谩s profundo, pero esto no nos impide usarlo.

codigo
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; 


Despu茅s de crear la base del camino, se necesitaba una capa visual para mostrar el 谩rea circundante. El proyecto maperitivo ayud贸 aqu铆 , nos permiti贸 analizar el mapa OSM de regiones en secciones de mosaico por capas de aproximaci贸n, como 10 ^ 100 o Yandex. Hubo un intento de trabajar con los mapas de gigantes en l铆nea, representando un mapa vectorial en la parte superior de la capa del navegador, pero debido a las restricciones de licencia, decidieron rechazarlo. Como resultado, creamos un disco virtual y subimos un volcado de mosaicos a un par de decenas de gigabytes, pero todo est谩 a la mano y no se ralentiza. Es cierto que aproximadamente una vez cada seis meses tiene que actualizar, generalmente esto coincide con la sobrecarga de tarjetas.



Para combinar la imagen de mosaico y el mapa vectorial, debe saber que los mosaicos, Google, OpenStreetMap, Bing, Yahoo est谩n representados en la proyecci贸n de Mercator (m谩s precisamente WEB MERCATOR , que es la proyecci贸n en la esfera), donde cada capa m谩s profunda es dos veces m谩s detallada que la anterior.



Yandex.Maps utiliza la proyecci贸n del elipsoide de Mercator.

No importa si puede volver a calcular las coordenadas geogr谩ficas en el plano de proyecci贸n y viceversa.

Seleccionamos el nivel de detalle 17 como m谩ximo. M谩s cerca no tiene sentido debido a un aumento en el almacenamiento de la cantidad de mosaicos (cada nivel es 4 veces m谩s grande que el anterior), as铆 como su bajo contenido de informaci贸n.

2 ^ 17 * 256 = 33554432 (256 es el tama帽o del borde del mosaico en p铆xeles).

codigo
 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; //============================================================= 


Ahora que tenemos las herramientas b谩sicas, podemos proceder directamente a la tarea de crear la ruta 贸ptima. Conectamos los centros comerciales con el borde m谩s cercano en el gr谩fico de carreteras y luego iniciamos la b煤squeda del camino m谩s corto. Para hacer esto, utilizamos una variaci贸n del algoritmo de Dijkstra para su variaci贸n descargada secuencialmente para cada punto de visita. En la salida, obtenemos una matriz de adyacencia de tama帽o (N + 1) * (N + 1) con infinito en la diagonal principal (prohibici贸n de anillo), donde N es el n煤mero de puntos de visita sin tener en cuenta el punto de salida.

La matriz resultante almacena la distancia m铆nima a lo largo de las carreteras entre todas las tiendas, lo cual es un problema cl谩sico de vendedor ambulante . Dado que la complejidad algor铆tmica de un problema de este tipo es exagerada, utilizamos el m茅todo de ramificaci贸n y uni贸n para resolverlo. Para n <15, es exhaustivo; de lo contrario, una estimaci贸n aproximada est谩 conectada en profundidad. La opci贸n ciertamente no es ideal, pero funciona bastante.

Como resultado, obtuvimos una ruta cercana a la distancia 贸ptima con una estimaci贸n en km. Si es necesario, el operador puede cambiar manualmente la ruta a favor de la prioridad de los puntos individuales.

La soluci贸n ha estado funcionando en la organizaci贸n durante aproximadamente 7 a帽os, con bastante 茅xito, aunque no sin fallas, tanto en precisi贸n como en conveniencia. Los resultados son consistentes con los datos de rastreo de veh铆culos GPS. En mi opini贸n, la introducci贸n de la log铆stica permiti贸 ahorrar del 10 al 12% de los fondos asignados para combustible. El programa fue dise帽ado, lanzado y acompa帽ado por una sola persona: su humilde servidor.

Mi liderazgo conservador no est谩 ansioso por "brillar", as铆 que sugiero un ejemplo ficticio de la ruta para llamar la atenci贸n.



Sin visualizaci贸n, el c谩lculo es muchas veces m谩s r谩pido, y dentro de un acuerdo, casi al instante.

Despu茅s de tantos a帽os, a veces le da ganas de entrar en el c贸digo y copiarlo con nueva experiencia en una plataforma nueva y m谩s moderna, pero hasta ahora no hay viabilidad econ贸mica.

Eso es todo lo que quer铆a decirte, espero que haya sido interesante.
Pido disculpas si no fui precisa en alguna parte.

Source: https://habr.com/ru/post/437280/


All Articles