Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 1
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Integración de un SIG con modelos de cálculoy optimización de rutas de vehículos CVRP ysoftware de gestión de flotas.
Alejandro Rodríguez Villalobos
Universidad Politécnica de Valencia
http://personales.upv.es/arodrigu
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
La importancia del transporte y la gestión de flotas
El transporte de pasajeros por carretera (410.163·106
viajeros-km) representa en España el 90,5%.
Su tasa de crecimiento es de un 38,16% (superada porel transporte aéreo que crece a un ritmo del 103,9%).
El transporte por carretera es el de mayorproducción (334.081·106 toneladas-km) en
transporte interior de mercancías con un 84,2
% de las toneladas-kilómetro.
Ha ido aumentando en los últimos años acosta del transporte marítimo y por ferrocarril.
El transporte internacional de mercancías por
carretera tiene un peso importante en las
exportaciones.
Datos : 1995-2004
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
La importancia del transporte y la gestión de flotas
El transporte por carretera es uno de los sectores que másaporta a la generación de riqueza (aprox. 5,8% del Valor
Añadido Bruto Nacional de España).
Muestra un comportamiento superior al resto de los modos
de transporte (ferroviario, marítimo y aéreo) en cuanto ageneración de valor.
Presenta estabilidad en términos de crecimiento del PIB
que parece ajena a oscilaciones cíclicas de la actividad
económica general; con tasas de crecimiento un pocosuperiores a sus ramas de actividad.
Por el contrario, el sector del transporte esta integrado en su mayoría por pequeñasempresas (desigual formación de sus trabajadores).
Tejido empresarial con estructuras anticuadas en su funcionamiento y la formación no formaparte de su cultura.
El equipamiento informático del sector es escaso y su hábito de uso mínimo.
Ministerio de Fomento (2001)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
La importancia del transporte y la gestión de flotas
Interrelación logística y económica (a nivel nacional e internacional)
Dependencia del aprovisionamiento
Relación entre: el transporte, suministro, costes y PVP
El transporte: la corriente sanguínea del país y sus empresas
La logística es un factor de vital importancia
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
La cuestión es …
¿cómo optimizar el transporte?
¿cómo planificar, controlar y mejorar el suministro?
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
La respuesta es …
Las técnicas de investigación operativa relativas a la de gestión de flotas y el uso de tecnologías de la información pueden ayudar a contrarrestar los desequilibrios existentes entre la importancia del sector y su capacidad-
calidad de servicio.
A pesar del interés científico, todavía es un área virgen en muchas empresas.
Se podrían alcanzar ahorros del orden del 5% al 20%, en un área (el transporte) que representa entre el 10% y el 20% (en términos generales) del coste total de los productos
Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 2
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Antecedentes (la civilización y el comercio)
La humanidad siempre se ha planteado la cuestión de encontrar el camino más corto para desplazarse de un sitio a otro: cazar, recolectar, comerciar con sus
excedentes, trasladar sus mercancías por la ruta más segura o rápida, aprovisionar a sus metrópolis con víveres y agua, enviar mensajes y establecer
redes de comunicaciones, la intendencia de sus tropas, etc.
Ejemplos antiguos:
el transporte por el río Nilo en el antiguo
Egipto (2700 - 2250 a.C.), la gran murallachina (221 a.C. – 1368 d.C.), la ruta de la
seda (138 a.C. – s. XV d.C.), calzadasromanas (133 - 117 d.C.), caminos mayas
(600 - 800 d.C.), comercio y colonizaciónde las Américas (1492 d.C. – s. XVII),
etc.
En aquellos tiempos habría personas expertas encargadas de planificar y dirigir las operaciones logísticas y militares.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Antecedentes (la naturaleza)
Las aves en su migración, las ballenas, las tortugas marinas, y las hormigas …inspiración para nuevas heurísticas y técnicas
de resolución.
Dorigo y Gambardella, 1997.
Animales que se enfrentan al problema de rutas.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Antecedentes (literatura científica)
Los 7 puentes de Königsberg
El antecedente científico documentado másremoto es del siglo XVIII.
El matemático Leonhard Euler (1736)demostró que el esquema gráfico de los 7puentes de Königsberg no podía recorrersepartiendo de un punto cruzando cada puenteuna sola vez y volviendo al punto de partida.
Este problema y su trabajo pudo haber sido la primera aplicaciónen teoría de grafos, por lo que en su nombre, a esta idea se ledenomina ciclo o circuito Euleriano de un grafo.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Antecedentes (literatura científica)
Chinese Postman Problem – CPP: tratade encontrar la ruta cerrada más corta(circuito) visitando cada arista (al menosuna vez) de un grafo no dirigido(conectado).
Alan Goldman del NIST (National Institute of Standards andTechnology) fue el primero en acuñar el problema como delconocido y anónimo “cartero chino”, ya que originalmente fueestudiado por el matemático chino Mei Ko Kuan en 1962.
El problema del cartero chino
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Antecedentes (literatura científica)
Dantzig y Ramser (1959) describieron una aplicaciónconcerniente a la distribución de gasolina paraestaciones de servicio.
Poco después, Clarke y Wright aportaron unapropuesta de algoritmo voraz (greedy) que mejorabala anterior.
Gran interés en este tipo de problemas: por el sentido práctico de suaplicación en problemas reales, y por la gran complejidad de este tipo deproblemas.
Fértil línea de investigación y desarrollo que hacrecido mucho en los últimos años.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Elementos: La red de transporte
Calles y sentido de circulación. Grafo dirigido con pesos.
Arcos:Un sentido de circulación o ambos.
Peso: longitud en distancia el tiempo de viaje coste, etc.
Pueden depender del tipo de vehículo o delmomento en el que se recorra (tráfico).
La red de carreteras o servicioutilizada para el transporte debienes, se describe como un grafodirigido.
Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 3
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Elementos: Los clientes y su servicio
La demanda es la necesidad de un conjunto de productos que ocupanvolumen y peso en los vehículos.
La capacidad de transporte del vehículo es limitada, es usual que unmismo vehículo no pueda satisfacer la demanda de todos los clientes.
Clientes/proveedores Vehículo asociado a cliente Servicio de transporte (origen-destino) Demanda fragmentada Restricciones de horario (+tiempo de servicio) Restricción de vehículo en la red (centro urbano)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Elementos: Los almacenes o depósitos
Los productos a transportar y los vehículos, suelen estar localizados en losdepósitos (almacenes, centros de tránsito, muelles o cocheras).
Es habitual que las rutas den comienzo y/o finalicen en dichos depósitos.Excepción: el viaje debe finalizar donde pernocta o finaliza la jornada el conductor.
Varios almacenes o depósitos Características: cap. máx., horario, flota, etc. Flota conocida o incógnita Espacio y tiempo de preparación Limitación de uso (congestión de muelles)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Elementos: La flota de vehículos
Es el medio de transporte. Se define por unconjunto de atributos (capacidad de cargaen peso, volumen, costes asociados,disponibilidad, prioridad de uso, etc.)
Varios productos o uno sólo Compartimentos Costes fijos de utilización Coste variable (tiempo, distancia, etc.) Flota homogénea/heterogénea Núm. Vehículos conocido/incógnita Limitación legislativa: descanso, relevo conductores, velocidad máx., de paso. Equilibrado de cargas de trabajo
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Elementos: Las rutas
Un vehículo para cada ruta Un vehículo que participa en varias rutas
Los problemas de rutas de vehículos - VRP tratan por tanto dedeterminar la ruta/s para cada uno de los vehículos de la flotacumpliendo con todo el conjunto de restricciones e intentandoalcanzar los objetivos propuestos.
La función objetivo:
min. los costes fijos min. los costes totales min. el número de vehículos min. el tiempo total de transporte min. la distancia total recorrida min. las esperas máx. el beneficio de la operación máx. la función de utilidad del cliente
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Modelos básicos de VRP
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Proyecto Rutas: objetivos y estructura
Solver
ERPGIS
DepósitosFlota de vehículosClientes y proveedoresVentanas horariasServicios y órdenesCostesObjetivos…
VRP-XML
Geo-localización (geocoding)Red de transporteTráficoCálculo de itinerarios (min. path)
Representación de rutasSeguimiento (tracking)
Modelado y resolución CVRP
• HC (Hamiltonian Cycle)• HP (Hamiltonian Path)
• TSP (viajante de comercio)• m-TSP (m-viajantes)• CVRP (Capacited VRP)• OVRP (Open CVRP)• DCVRP (Distance Constrained VRP)• VRPTW (VRP with Time Windows)…
Información y restricciones
Grafo reducido
Informes y documentación
Objetivos: facilitar la resolución de problemas reales de flotas de vehículoscapacitados CVRP, el cálculo de rutas y su gestión.
Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 4
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Proyecto Rutas: interfaz
Integración Logística
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Proyecto Rutas: desarrollo
Programado en Visual Studio .net
20.112 líneas de código fuente
Su estructura es modular, flexible y escalable
Es compatible con Windows Vista
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Complejidad computacional (tipos de problema)
camino mínimo ruta
Variables continuas Variables discretas
POLINOMIAL NO-POLINOMIAL (NP)
Programación lineal Programación entera
ÓPTIMO FACTIBLE
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Complejidad computacional (modelado)
Modelo de programación lineal entera mixta (MILP)
para el problema del viajante de comercio (TSP)
Función objetivo: minimizar distancia total
Cada nodo se visita una vez; condiciones de continuidad.
Variables de decisión binarias
Tucker: evita la formación de subrutas
Las variables de decisión introducidas por las condiciones deTucker son reales y no tienen límites ni superior ni inferior. Lapropuesta de Tucker genera n2 restricciones, mientras queotras en la literatura pueden llegar a generar 2n. Sin embargo,desde un punto de vista computacional, este modelo aunquemás compacto es menos eficiente.
2 subrutas 1 ruta
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
/* PROBLEMA DEL VIAJANTE DE COMERCIO */
/* Objective function */
min: +1.2 x_0_1 +x_0_2 +1.4 x_0_3 +3 x_0_4 +0.6 x_0_5 +2.4 x_0_6 +0.6 x_0_7 +1.2 x_0_8 +1.2 x_0_9 +2 x_0_10
+2.3 x_0_11 +2.2 x_0_12 +1.7 x_0_13 +1.5 x_0_14 +2.1 x_0_15 +2.8 x_0_16 +0.9 x_0_17 +0.5 x_0_18 +0.8 x_1_0
+1.8 x_1_2 +1.9 x_1_3 +3 x_1_4 +x_1_5 +2.5 x_1_6 +x_1_7 +0.7 x_1_8 +0.5 x_1_9 +2.1 x_1_10 +2.7 x_1_11
+3.2 x_1_12 +0.9 x_1_13 +1.4 x_1_14 +2.2 x_1_15 +2.9 x_1_16 +x_1_17 +1.3 x_1_18 +x_2_0 +1.9 x_2_1 +0.4 x_2_3
+5 x_2_4 +0.8 x_2_5 +4.4 x_2_6 +1.3 x_2_7 +2.1 x_2_8 +1.7 x_2_9 +4 x_2_10 +3 x_2_11 +2.9 x_2_12 +2.2 x_2_13
+3.5 x_2_14 +4.1 x_2_15 +4.8 x_2_16 +2.9 x_2_17 +2.5 x_2_18 +1.7 x_3_0 +2.6 x_3_1 +0.7 x_3_2 +5.7 x_3_4
+1.5 x_3_5 +5.1 x_3_6 +1.9 x_3_7 +2.7 x_3_8 +2.3 x_3_9 +4.7 x_3_10 +3.7 x_3_11 +3.6 x_3_12 +2.8 x_3_13
+4.2 x_3_14 +4.8 x_3_15 +5.5 x_3_16 +3.6 x_3_17 +3.2 x_3_18 +2.7 x_4_0 +2.5 x_4_1 +3.8 x_4_2 +4.1 x_4_3
+3 x_4_5 +0.2 x_4_6 +2.7 x_4_7 +2.2 x_4_8 +2.4 x_4_9 +2.5 x_4_10 +3.2 x_4_11 +3.7 x_4_12 +1.8 x_4_13
+1.4 x_4_14 +0.6 x_4_15 +0.2 x_4_16 +2.4 x_4_17 +3.4 x_4_18 +0.2 x_5_0 +1.4 x_5_1 +0.9 x_5_2 +1.3 x_5_3
+3.2 x_5_4 +2.6 x_5_6 +0.3 x_5_7 +1.4 x_5_8 +0.7 x_5_9 +2.2 x_5_10 +2.4 x_5_11 +2.2 x_5_12 +1.9 x_5_13
+1.7 x_5_14 +2.3 x_5_15 +3 x_5_16 +1.1 x_5_17 +0.7 x_5_18 +2.5 x_6_0 +2.2 x_6_1 +3.5 x_6_2 +3.9 x_6_3
+0.5 x_6_4 +2.7 x_6_5 +2.5 x_6_7 +1.9 x_6_8 +2.2 x_6_9 +2.3 x_6_10 +3 x_6_11 +3.5 x_6_12 +1.6 x_6_13
+1.1 x_6_14 +0.6 x_6_15 +0.2 x_6_16 +2.2 x_6_17 +3.1 x_6_18 +0.2 x_7_0 +1.4 x_7_1 +1.3 x_7_2 +1.6 x_7_3
+3.1 x_7_4 +0.3 x_7_5 +2.6 x_7_6 +1.3 x_7_8 +0.4 x_7_9 +2.1 x_7_10 +2.5 x_7_11 +2.4 x_7_12 +1.8 x_7_13
+1.6 x_7_14 +2.2 x_7_15 +2.9 x_7_16 +1.1 x_7_17 +0.7 x_7_18 +x_8_0 +0.7 x_8_1 +2.1 x_8_2 +2.4 x_8_3
+2.3 x_8_4 +1.3 x_8_5 +1.8 x_8_6 +x_8_7 +0.7 x_8_9 +1.3 x_8_10 +2 x_8_11 +2.5 x_8_12 +0.1 x_8_13 +0.7 x_8_14
+1.5 x_8_15 +2.1 x_8_16 +0.6 x_8_17 +2.2 x_8_18 +0.5 x_9_0 +x_9_1 +1.5 x_9_2 +1.8 x_9_3 +2.7 x_9_4 +0.6 x_9_5
+2.2 x_9_6 +0.3 x_9_7 +0.9 x_9_8 +1.7 x_9_10 +2.4 x_9_11 +2.9 x_9_12 +1.4 x_9_13 +1.2 x_9_14 +1.9 x_9_15
+2.5 x_9_16 +0.7 x_9_17 +0.8 x_9_18 +2 x_10_0 +1.8 x_10_1 +2.2 x_10_2 +2.6 x_10_3 +2.4 x_10_4 +1.8 x_10_5
+1.9 x_10_6 +1.8 x_10_7 +1.5 x_10_8 +1.8 x_10_9 +1.1 x_10_11 +1.6 x_10_12 +1.1 x_10_13 +0.9 x_10_14
+1.5 x_10_15 +2.2 x_10_16 +1.1 x_10_17 +1.2 x_10_18 +2.9 x_11_0 +2.6 x_11_1 +2.9 x_11_2 +3.2 x_11_3
+3.4 x_11_4 +2.5 x_11_5 +2.8 x_11_6 +2.4 x_11_7 +2.4 x_11_8 +2.6 x_11_9 +1.1 x_11_10 +0.5 x_11_12 +2.1 x_11_13
+1.9 x_11_14 +2.5 x_11_15 +3.2 x_11_16 +2.3 x_11_17 +1.9 x_11_18 +3 x_12_0 +2.8 x_12_1 +3.1 x_12_2 +3.4 x_12_3
+3.5 x_12_4 +2.7 x_12_5 +3 x_12_6 +2.6 x_12_7 +2.6 x_12_8 +2.7 x_12_9 +1.2 x_12_10 +0.2 x_12_11 +2.3 x_12_13
+2.1 x_12_14 +2.7 x_12_15 +3.4 x_12_16 +2.2 x_12_17 +2.1 x_12_18 +0.9 x_13_0 +0.7 x_13_1 +1.9 x_13_2
+2.3 x_13_3 +2.2 x_13_4 +1.1 x_13_5 +1.6 x_13_6 +0.9 x_13_7 +0.3 x_13_8 +0.6 x_13_9 +1.2 x_13_10 +1.9 x_13_11
+2.4 x_13_12 +0.6 x_13_14 +1.3 x_13_15 +1.8 x_13_16 +0.6 x_13_17 +1.4 x_13_18 +1.4 x_14_0 +1.1 x_14_1
+2.4 x_14_2 +2.7 x_14_3 +2.1 x_14_4 +1.6 x_14_5 +1.6 x_14_6 +1.4 x_14_7 +0.8 x_14_8 +1.1 x_14_9 +1.2 x_14_10
+1.9 x_14_11 +2.3 x_14_12 +0.5 x_14_13 +1.3 x_14_15 +2 x_14_16 +1.1 x_14_17 +2 x_14_18 +2.4 x_15_0 +2.1 x_15_1
+3.4 x_15_2 +3.7 x_15_3 +0.9 x_15_4 +2.6 x_15_5 +0.7 x_15_6 +2.4 x_15_7 +1.8 x_15_8 +2.1 x_15_9 +2.2 x_15_10
+2.9 x_15_11 +3.3 x_15_12 +1.5 x_15_13 +x_15_14 +0.8 x_15_16 +2.1 x_15_17 +3 x_15_18 +2.6 x_16_0 +2.4 x_16_1
+3.7 x_16_2 +4 x_16_3 +0.6 x_16_4 +2.9 x_16_5 +0.4 x_16_6 +2.6 x_16_7 +2.1 x_16_8 +2.3 x_16_9 +2.4 x_16_10
+3.1 x_16_11 +3.6 x_16_12 +1.7 x_16_13 +1.3 x_16_14 +x_16_15 +2.4 x_16_17 +3.3 x_16_18 +0.8 x_17_0 +0.6 x_17_1
+1.9 x_17_2 +2.2 x_17_3 +2.6 x_17_4 +1.1 x_17_5 +2 x_17_6 +0.8 x_17_7 +0.3 x_17_8 +0.5 x_17_9 +1.6 x_17_10
+2.3 x_17_11 +2.8 x_17_12 +0.4 x_17_13 +1.1 x_17_14 +1.7 x_17_15 +2.4 x_17_16 +1.3 x_17_18 +x_18_0 +0.7 x_18_1
+2 x_18_2 +2.3 x_18_3 +2.5 x_18_4 +1.2 x_18_5 +1.9 x_18_6 +x_18_7 +0.7 x_18_8 +0.7 x_18_9 +1.5 x_18_10
+2.2 x_18_11 +2.7 x_18_12 +1.2 x_18_13 +x_18_14 +1.6 x_18_15 +2.3 x_18_16 +0.4 x_18_17;
/* Constraints */
r1: +x_1_0 +x_2_0 +x_3_0 +x_4_0 +x_5_0 +x_6_0 +x_7_0 +x_8_0 +x_9_0 +x_10_0 +x_11_0 +x_12_0 +x_13_0 +x_14_0
+x_15_0 +x_16_0 +x_17_0 +x_18_0 = 1;
r2: +x_0_1 +x_0_2 +x_0_3 +x_0_4 +x_0_5 +x_0_6 +x_0_7 +x_0_8 +x_0_9 +x_0_10 +x_0_11 +x_0_12 +x_0_13 +x_0_14
+x_0_15 +x_0_16 +x_0_17 +x_0_18 = 1;
r3: +x_0_1 +x_2_1 +x_3_1 +x_4_1 +x_5_1 +x_6_1 +x_7_1 +x_8_1 +x_9_1 +x_10_1 +x_11_1 +x_12_1 +x_13_1 +x_14_1
+x_15_1 +x_16_1 +x_17_1 +x_18_1 = 1;
r4: +x_1_0 +x_1_2 +x_1_3 +x_1_4 +x_1_5 +x_1_6 +x_1_7 +x_1_8 +x_1_9 +x_1_10 +x_1_11 +x_1_12 +x_1_13 +x_1_14
+x_1_15 +x_1_16 +x_1_17 +x_1_18 = 1;
r5: +x_0_2 +x_1_2 +x_3_2 +x_4_2 +x_5_2 +x_6_2 +x_7_2 r39: +19 x_1_0 +u1 -u0 <= 18;
r40: +19 x_1_2 +u1 -u2 <= 18;
r41: +19 x_1_3 +u1 -u3 <= 18;
r42: +19 x_1_4 +u1 -u4 <= 18;
r43: +19 x_1_5 +u1 -u5 <= 18;
r44: +19 x_1_6 +u1 -u6 <= 18;
r45: +19 x_1_7 +u1 -u7 <= 18;
r46: +19 x_1_8 +u1 -u8 <= 18;
r47: +19 x_1_9 +u1 -u9 <= 18;
r48: +19 x_1_10 +u1 -u10 <= 18;
r49: +19 x_1_11 +u1 -u11 <= 18;
r50: +19 x_1_12 +u1 -u12 <= 18;
r51: +19 x_1_13 +u1 -u13 <= 18;
r52: +19 x_1_14 +u1 -u14 <= 18;
r53: +19 x_1_15 +u1 -u15 <= 18;
r54: +19 x_1_16 +u1 -u16 <= 18;
r55: +19 x_1_17 +u1 -u17 <= 18;
r56: +19 x_1_18 +u1 -u18 <= 18;
r373: +x_0_10 <= 1;
r374: +x_0_11 <= 1;
r375: +x_0_12 <= 1;
r376: +x_0_13 <= 1;
r377: +x_0_14 <= 1;
r378: +x_0_15 <= 1;
r379: +x_0_16 <= 1;
r380: +x_0_17 <= 1;
r381: +x_0_18 <= 1;
/* Integer definitions */
int
x_0_1,x_0_2,x_0_3,x_0_4,x_0_5,x_0_6,x_0_7,x_0_8,x_0_9,x_0_10,x_0_11,x_0_12,x_0_13,x_0_14,x_0_15,x_0_16,x_0_17,x_0_18,x_1_0,x_1_2,x_1_3,x_1_4,x_1_5,x_1_6,x_1_7,x_1_8,x_1_9,x_1_10,x_1_11,x_1_12,x_1_13,x_1_14,x_1_15,x_1_16,x_1_17,x_1_18,x_2_0,x_2_1,x_2_3,x_2_4,x_2_5,x_2_6,x_2_7,x_2_8,
x_2_9,x_2_10,x_2_11,x_2_12,x_2_13,x_2_14,x_2_15,x_2_16,x_2_17,x_2_18,x_3_0,x_3_1,x_3_2,x_3_4,x_3_5,x_3_6,x_3_7,x_3_8,x_3_9,x_3_10,x_3_11,x_3_12,x_3_13,x_3_14,x_3_15,x_3_16,x_3_17,x_3_18,x_4_0,x_4_1,x_4_2,x_4_3,x_4_5,x_4_6,x_4_7,x_4_8,x_4_9,x_4_10,x_4_11,x_4_12,x_4_13,x_4_14,x_4_15,
x_4_16,x_4_17,x_4_18,x_5_0,x_5_1,x_5_2,x_5_3,x_5_4,x_5_6,x_5_7,x_5_8,x_5_9,x_5_10,x_5_11,x_5_12,x_5_13,x_5_14,x_5_15,x_5_16,x_5_17,x_5_18,x_6_0,x_6_1,x_6_2,x_6_3,x_6_4,x_6_5,x_6_7,x_6_8,x_6_9,x_6_10,x_6_11,x_6_12,x_6_13,x_6_14,x_6_15,x_6_16,x_6_17,x_6_18,x_7_0,x_7_1,x_7_2,x_7_3,x_7
_4,x_7_5,x_7_6,x_7_8,x_7_9,x_7_10,x_7_11,x_7_12,x_7_13,x_7_14,x_7_15,x_7_16,x_7_17,x_7_18,x_8_0,x_8_1,x_8_2,x_8_3,x_8_4,x_8_5,x_8_6,x_8_7,x_8_9,x_8_10,x_8_11,x_8_12,x_8_13,x_8_14,x_8_15,x_8_16,x_8_17,x_8_18,x_9_0,x_9_1,x_9_2,x_9_3,x_9_4,x_9_5,x_9_6,x_9_7,x_9_8,x_9_10,x_9_11,x_9_12,
x_9_13,x_9_14,x_9_15,x_9_16,x_9_17,x_9_18,x_10_0,x_10_1,x_10_2,x_10_3,x_10_4,x_10_5,x_10_6,x_10_7,x_10_8,x_10_9,x_10_11,x_10_12,x_10_13,x_10_14,x_10_15,x_10_16,x_10_17,x_10_18,x_11_0,x_11_1,x_11_2,x_11_3,x_11_4,x_11_5,x_11_6,x_11_7,x_11_8,x_11_9,x_11_10,x_11_12,x_11_13,x_11_14,x_11
_15,x_11_16,x_11_17,x_11_18,x_12_0,x_12_1,x_12_2,x_12_3,x_12_4,x_12_5,x_12_6,x_12_7,x_12_8,x_12_9,x_12_10,x_12_11,x_12_13,x_12_14,x_12_15,x_12_16,x_12_17,x_12_18,x_13_0,x_13_1,x_13_2,x_13_3,x_13_4,x_13_5,x_13_6,x_13_7,x_13_8,x_13_9,x_13_10,x_13_11,x_13_12,x_13_14,x_13_15,x_13_16,x_
13_17,x_13_18,x_14_0,x_14_1,x_14_2,x_14_3,x_14_4,x_14_5,x_14_6,x_14_7,x_14_8,x_14_9,x_14_10,x_14_11,x_14_12,x_14_13,x_14_15,x_14_16,x_14_17,x_14_18,x_15_0,x_15_1,x_15_2,x_15_3,x_15_4,x_15_5,x_15_6,x_15_7,x_15_8,x_15_9,x_15_10,x_15_11,x_15_12,x_15_13,x_15_14,x_15_16,x_15_17,x_15_18,
x_16_0,x_16_1,x_16_2,x_16_3,x_16_4,x_16_5,x_16_6,x_16_7,x_16_8,x_16_9,x_16_10,x_16_11,x_16_12,x_16_13,x_16_14,x_16_15,x_16_17,x_16_18,x_17_0,x_17_1,x_17_2,x_17_3,x_17_4,x_17_5,x_17_6,x_17_7,x_17_8,x_17_9,x_17_10,x_17_11,x_17_12,x_17_13,x_17_14,x_17_15,x_17_16,x_17_18,x_18_0,x_18_1,
x_18_2,x_18_3,x_18_4,x_18_5,x_18_6,x_18_7,x_18_8,x_18_9,x_18_10,x_18_11,x_18_12,x_18_13,x_18_14,x_18_15,x_18_16,x_18_17;
Complejidad computacional (modelado)
Ejemplo: 19 nodos (clientes)
Matriz 19x19 = 361 (diagonal 19 ceros)
Sujeto a 1084 restricciones
18 pantallas para poder ver el modelo completo
Función objetivo con 342 variables de decisión binarias
+18 variables reales (Tucker)
121.645.100.408.832.000 posibles soluciones (>120.000 billones)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Problemas de optimización combinatoria
Técnicas de resolución:
Aproximación algorítmica
Enumeración
Búsqueda local (Branch & Bound)
Programación dinámica
Meta-Heurísticas:
• Búsqueda tabú
• Algoritmos genéticos
• Algoritmo de hormigas
Soluciones buenas en un tiempo razonable
probablemente no-optimas
Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 5
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Software Rutas: pantalla del solver MILP
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Ventanas horarias - VRPTW
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Seguimiento de vehículos (vehicle tracking)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Interfaz abierto
.gpx
.kml
.itn
.ov2
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Conclusiones
El software integra un conjunto de funciones que facilita el cálculo, lagestión y la interacción con elementos de la cadena logística(proveedores y clientes, vehículos, otros sistemas: ERP-CRM, etc.):
Localización de clientes, centros de tránsito y almacenes (geocoding, waypoints) Selección optimizada de vehículos (flota propia vs. subcontratada) Definición de zonas de distribución
Planificación de rutas de reparto y aprovisionamiento Cálculo y gestión de distancias, tiempos y costes de transporte Definición y análisis de ventanas horarias de entrega o recogida
Seguimiento de vehículos (GPS tracking) Intercambiar información sobre localizaciones e itinerarios con su navegador GPS
Generación de mapas, mejora de la documentación logística Exportar información sobre localizaciones e itinerarios para otro softwarecartográfico (Google Earth, OziExplorer, GPS Visualizer, CompeGPS, Google Maps, GPS
TrackMaker, etc.)
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Conclusiones
En este proyecto de acción-investigación se está validando el desarrollo mediantela resolución de problemas reales en empresa.
Gran aceptación de la herramienta y bondad de los primeros resultados en lasempresas piloto (transporte internacional, distribución farmacéutica, vending,sector agro-alimentario).
Un 69,23% de las empresas consiguieron mejoras económicas en sus procesosde transporte del orden del 15-30% respecto a su situación inicial.
Integración de un SIG con modelos de cálculo y
optimización de rutas de vehículos CVRP y software de
gestión de flotas.
Alejandro Rodríguez Villalobos 6
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Conclusiones
Es fácil hablar de optimización pero muy difícil alcanzar el óptimo.
La optimización del transporte debe entenderse como un proceso demejora continua.
Es necesario un análisis de la problemática particular, la definición deobjetivos y restricciones, así como la estrategia de resolución.
El éxito del transporte depende de otras decisiones y áreas de la empresa.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Conclusiones
En la actualidad el proyecto de investigación y desarrollo sigue en activo:
Programando nuevos modelos MILP para otros problemas VRP yheurísticas para casos concretos.
Se actualiza el solver de optimización con nuevas mejoras.
Mejoras y ampliación en el módulo de generación de informes y análisisde las soluciones.
Abriendo el proceso de validación y financiación a nuevas empresas-piloto.
Alejandro Rodríguez Villalobos http://personales.upv.es/arodrigu/rutas
Gracias por su atención!
Alejandro Rodríguez Villalobos
Universidad Politécnica de Valencia
http://personales.upv.es/arodrigu