el caso de la panificadora
introducción
Panificadora Corbi S.L es una empresa familiar que se crea en 1961 en la
localidad de Cocentaina, donde inicialmente sólo se comercializaba pan, y que
curiosamente repartía el hijo del fundador en un triciclo. En 1975 se crea la
primera panadería Corbi en la calle Perú de la localidad de Alcoi. En 1982 se
crea una planta panificadora en la calle Carrascar por la necesidad de
industrializar la fabricación del pan y de este modo poder abastecer la demanda
de las panaderías existentes y beneficiarse de una producción a mayor escala. En
la planta de panadería se procesan diferentes clases de productos de panadería,
tales como empacados, panes frescos y panes crocantes entre otros; además de los
diferentes productos de pastelería entre los cuales existen varios tipos de
tortas y hojaldrados. En 1991 se decide ampliar la planta de panadería con el
fin de especializar la producción en 2 plantas, una de panadería y otra de
pastelería. Dos años más tarde se hace la primera gran inversión en maquinaria
para automatizar la producción de panadería con la compra de un horno túnel,
posteriormente se realizó otra inversión considerable en cámaras de maduración
automática. En 1996 y debido al incremento de la demanda, se adquiere otro horno
y otra cámara. En 1998 se unifica la gestión administrativa de la planta de
panadería y la de pastelería.
En la actualidad, la empresa cuya gerencia asume la nieta del fundador, cuenta con un gran reconocimiento en la elaboración de sus productos y con 19 panaderías en toda la ciudad de Alcoi; no se descarta la expansión a otras localidades.
el problema del reparto
Diariamente la empresa debe suministrar desde la planta
central la demanda de todas sus panaderías de la ciudad. El problema consiste en
hallar una ruta de reparto de modo que, partiendo de la central, se visiten
todas las panaderías una sola vez en un recorrido único que termine de vuelta en
la central panadera.
Este problema se identifica como un problema de reparto clásico o 'problema del viajante de comercio' (TSP - Traveling Salesman Problem). Este tipo de problemas son de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece exponencialmente con el número de nodos del grafo (panaderías en este caso), y rápidamente sobrepasa las capacidades de cálculo de los ordenadores más potentes. En el caso que aquí se presenta n=19 el número de posibles soluciones es aproximadamente de 3,2012E+15 (3.200 billones de soluciones). Se trata por tanto de encontrar dentro de ese conjunto la mejor solución posible (solución óptima) o una solución factible lo suficientemente buena (si no se dispone de tiempo y recursos suficientes).
Además de la complejidad computacional de este problema, debemos enmarcar su resolución en su contexto real. Es decir, en este caso para su resolución será necesaria información sobre la localización geográfica de la central y las panaderías, las distribución y sentido de circulación de las calles de la ciudad (red de tránsito), los caminos mínimos entre pares de nodos (según una función tiempo, distancia o coste), etc. Esta información está sujeta a la dinámica de la ordenación urbana y del tránsito (cambia periódicamente), y puede ser enriquecida con mayor información o mayor nivel de detalle como por ejemplo: información sobre el tráfico, las obras o calles cortadas, etc.
Todo ello quiere decir que para el correcto modelado y resolución del problema según la teoría de grafos y las técnicas de programación lineal entera mixta (MILP), será necesario contar con un sistema de información geográfica que permita geo-referenciar las correctas localizaciones de las panaderías, calcular los caminos mínimos entre pares, y poder analizar y representar la solución final al problema planteado.
información de partida
La información de partida suministrada por la empresa es la localización de su central panificadora y del resto de panaderías en la ciudad de Alcoi. En la tabla de la izquierda se puede ver la dirección postal de la central y de las otras 18 panaderías.
| Panadería | Dirección | Num. | CP | Localidad | Latitud | Longitud | ||
| 0 | Central | Pza. Evarist Botella | 6 | 3802 | Alcoi | 38,694832 | -0,484622 | |
| 1 | Azorin | Azorin | 11 | 3803 | Alcoi | 38,700412 | -0,4858 | |
| 2 | Banyeres | Banyeres | 2 | 3802 | Alcoi | 38,69079 | -0,493934 | |
| 3 | Carrascar | Carrascar | 22 | 3802 | Alcoi | 38,68856 | -0,494581 | |
| 4 | Cocentaina | Cocentaina | 6 | 3804 | Alcoi | 38,707436 | -0,464974 | |
| 5 | Gregori | Gregori Casasempere Juan | 46 | 3802 | Alcoi | 38,694286 | -0,486535 | |
| 6 | Hispanitat | Avd. Hispanitat | 31 | 3804 | Alcoi | 38,707713 | -0,467357 | |
| 7 | Ibi | Ibi | 55 | 3802 | Alcoi | 38,696331 | -0,485867 | |
| 8 | Isabel | Isabel la católica | 37 | 3803 | Alcoi | 38,701846 | -0,481412 | |
| 9 | Espi | Mestre Espí | 26 | 3802 | Alcoi | 38,698293 | -0,485015 | |
| 10 | Torregrossa | Mossèn Torregrosa | 21 | 3801 | Alcoi | 38,697963 | -0,47446 | |
| 11 | Goncal | Músic Gonçal Blanes | 2 | 3801 | Alcoi | 38,690693 | -0,47538 | |
| 12 | Carbonell | Músic Josep Carbonell | 12 | 3801 | Alcoi | 38,689476 | -0,474449 | |
| 13 | Entenza28 | Na Saurina d'Entença | 28 | 3803 | Alcoi | 38,701096 | -0,480373 | |
| 14 | Entenza99 | Na Saurina d'Entença | 99 | 3803 | Alcoi | 38,704108 | -0,476875 | |
| 15 | Poveda | Pare Poveda | 7 | 3804 | Alcoi | 38,70466 | -0,46993 | |
| 16 | Eloi | Sant Eloi | 3 | 3804 | Alcoi | 38,70842 | -0,466423 | |
| 17 | Isidre | Sant Isidre | 19 | 3803 | Alcoi | 38,700183 | -0,480929 | |
| 18 | Alçamora | Alçamora | 35 | 3802 | Alcoi | 38,697334 | -0,481477 |
Gracias a la presente herramienta de gestión de flotas y cálculo de rutas con conexión a un sistema de información geográfica, es posible geo-referencias dichas localizaciones. Este proceso transforma la información suministrada por la dirección postal en un conjunto de datos de latitud y longitud geográfica (ver tabla anterior a la derecha). Gracias a esto último se puede ubicar sobre el mapa y con precisión todas las localizaciones (haga clic para ampliar la siguiente imagen).
proceso de modelado y resolución
A partir de la información anterior, ya es posible comenzar el proceso de resolución. En primer lugar se realizará el cálculo de los caminos mínimos. En este caso estarán cuantificados en distancia (km) siguiendo la ruta más rápida, aunque podrían haberse calculado en otra variable (tiempo, coste, multi-variable, etc.) o bien en distancia (km) pero siguiendo la ruta más corta.
La siguiente imagen muestra un ejemplo de camino mínimo entre un par de localizaciones (Carrascar --> Cocentaina = 5.7 km por la ruta más rápida):
Este camino mínimo vendrá expresado por su itinerario:
Inicio en Carrascar (0) km
Salga en Carrer del Carrascar (S-O) -- (0.1) km
Gire a la DERECHA (N-O) por Carrer de Sotarroni -- (0.2) km
Gire a la DERECHA (E) por CV-795 [Carretera de Banyeres] -- (0.7) km
Permanezca RECTO por CV-795 [Carrer d'Oliver] -- (0.5) km
Gire a la DERECHA (S) por Carrer de Santa Rosa -- (0.2) km
Permanezca RECTO por Pont de Fernando Reig -- (0.3) km
Permanezca a la IZQUIERDA por c. local(s) hacia N-340 / Valencia -- (0.1) km
Tuerza a la IZQUIERDA (N) por Carrer d'Alacant -- (0.6) km
Gire a la IZQUIERDA (O) por Carrer dels Alçamora -- (0.7) km
C. cambia de nombre a Avinguda de l'Alameda -- (0.8) km
C. cambia de nombre a Avinguda de Juan Gil Albert -- (1) km
Gire a la DERECHA (S-E) por Carrer de l'Arquebisque Domènech -- (0.4) km
Gire a la DERECHA (S-O) por Carrer de Cocentaina -- (0.1) km
Llegada al destino en Carrer Cocentaina.
Una vez realizado el proceso de cálculo de todos los caminos mínimos (361 caminos en este caso), el resultado es una matriz cuadrada (no simétrica) como la que se muestra a continuación (haga clic sobre ella para obtener los datos en modo texto). Hay que recordar que cada celda de dicha matriz tiene asociado un camino como el que se ha mostrado anteriormente.
Tal y como muestra la siguiente imagen, con toda esta información anterior, se construye el grafo completo .graphml (que se puede abrir y editar con el software Grafos)
En este caso, este problema se aborda a través del modelo que sigue y su resolverá mediante Programación Lineal Entera Mixta, aunque también podría haberse abordado con otras técnicas de resolución heurísticas o meta-heurísticas.
Se trata de un repartidor que debe visitar n panaderías para suministrar sus productos. Cada par de localizaciones esta comunicada con una distancia definida mediante cij. El problema es por tanto, decidir el recorrido que comenzando por la central panificadora, que pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida (coste o tiempo).
Sea xij una variable binaria que indica si el repartidor utilizará el arco (camino mínimo) de la ciudad i a la j en su recorrido solución. A continuación se muestra el modelo completo del problema:
Analizando las restricciones, se puede observar que sólo debe haber un arco de llegada a un nodo, y que igualmente tan sólo debe haber un arco de salida. Con esto se garantiza que cada nodo es visitado sólo una única vez.
Sin embargo, con estas restricciones y la condición binaria de las variables xij, no es suficiente para garantizar que las soluciones factibles son recorridos. Es posible por tanto, que aparezca una solución formada por subrutas (no conectadas entre sí) y que cumplan las restricciones anteriormente comentadas.
Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Tucker y que se muestra en la ilustración superior del modelo. Las variables de decisión introducidas por las condiciones de Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera n2 restricciones, mientras que otras en la literatura pueden llegar a generar 2n. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente.
Si lo desea, puede descargarse el modelo MILP completo de este problema en formato estándar .lp y también en .mps. (modelo de 308 variables de decisión y 1084 restricciones).
Dicho modelo es enviado al solver MILP, donde tras un período de tiempo definido por el usuario el proceso finalizará mostrando la mejor solución factible encontrada hasta el momento. Si se dispone de tiempo suficiente (o de una buena estrategia de resolución), el modelo podría acabar encontrando la solución óptima al problema, como ha sido en este caso.
análisis de la solución final
La interpretación de la solución final muestra la ruta completa de reparto a realizar. En la siguiente tabla se muestra dicha ruta formada por conjuntos de pares de localizaciones origen-destino. La solución mostrada es óptima. Y la distancia total del recorrido son 14,2 km (siguiendo los caminos mínimos más rápidos valorados en distancia).
| Origen | Destino | Distancia (km) |
| Central | Banyeres | 1,0 |
| Banyeres | Carrascar | 0,4 |
| Carrascar | Gregori | 1,5 |
| Gregori | Alçamora | 0,7 |
| Alçamora | Isidre | 0,4 |
| Isidre | Isabel | 0,3 |
| Isabel | Entenza28 | 0,1 |
| Entenza28 | Goncal | 1,9 |
| Goncal | Carbonell | 0,5 |
| Carbonell | Torregrossa | 1,2 |
| Torregrossa | Poveda | 1,5 |
| Poveda | Cocentaina | 0,9 |
| Cocentaina | Hispanitat | 0,2 |
| Hispanitat | Eloi | 0,2 |
| Eloi | Entenza99 | 1,3 |
| Entenza99 | Azorin | 1,1 |
| Azorin | Espi | 0,5 |
| Espi | Ibi | 0,3 |
| Ibi | Central | 0,2 |
Si desplegamos esta solución sobre el sistema de información geográfica obtendremos el recorrido que muestra la siguiente imagen que comienza en la central y parte hacia la primera panadería en dirección oeste (haga clic para ampliar).
Esta misma solución se puede representar de un modo más simplificado sin mostrar el recorrido por las calles (haga clic en la siguiente imagen para ampliar). Este tipo de representación aunque es irreal facilita la interpretación de la solución.
El itinerario resultante, también podría ser exportado al conocido Google Earth, para poder ser analizado en un entorno tridimensional, tal y como muestra la siguiente imagen. Si lo desea puede descargarse los ficheros (.kml) para ser representados en Google Earth (corbi_panaderias.kml, corbi_ruta.kml).
Este mismo itinerario podría ser exportado también al navegador GPS del repartidor (TomTom Navigator), o bien al formato estándar GPX - GPS exchange format para ser representado y analizado con su software cartográfico (p.e. OziExplorer, GPS Visualizer, GPS TrackMaker, CompeGPS, etc.).
Esta solución representa un ahorro en distancia del 35'18% sobre el planteamiento original de la empresa (esto es un ahorro equivalente casi a la distancia recorrida en uno de cada 3 días de reparto). La solución a este problema ha sido valorada en distancia (según los caminos más rápidos), pero podría haberse resuelto y valorado igualmente en términos económicos (€ ahorrados por año) o bien en tiempo de reparto (horas-hombre ahorradas al año). Aunque el resultado final hubiera podido ser diferente, el proceso aquí mostrado para su modelado y resolución sería el mismo. Hay que subrayar que unos pocos km o minutos ahorrados al día pueden significar un gran ahorro al final del año, este ahorro se puede utilizar para liberar o mejorar la eficiencia de los recursos, o bien para amortizar inversiones y rentabilizar acciones de mejora.
La información detallada de la solución podría ser analizada en otros términos o bajo otros escenarios (tráfico, obras, flota de vehículos, etc.). Una vez validada, la ruta solución podría ser volcada a dispositivos de navegación GPS de los vehículos. Periódicamente, y según cambien las condiciones del entorno (red de transporte) o de la demanda, se podría volver a calcular y analizar la nueva ruta solución.
Con este pequeño ejemplo, se ha querido mostrar la utilidad y facilidad de uso de una herramienta de este tipo. El problema aquí mostrado es el más sencillo de todos los posibles ya que no contempla una flota de vehículos, ni restricciones de capacidad de los mismos, ventanas horarias de reparto, etc. Con la herramienta aquí mostrada también se puede resolver problemas de características más complejas.
Fuente: A. Rodríguez
Nota: Este caso ha sido redactado gracias a la información suministrada por la empresa Panificadora Corbi S.L y está basado en una práctica realizada por los alumnos: Damián Costa Soler, Essagui Elmostafa y Alberto López Calvet (Mayo 2006). Los resultados aquí mostrados mejoran los de la práctica anterior.