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 ​​por 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.


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).


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.