Optimización de rutas mediante la búsqueda en entornos variables y aceptación por umbrales estocásticos

Búsqueda local mejorada por el criterio de aceptación por umbrales

RESUMEN

La ponencia presenta un procedimiento de resolución aproximada en la optimización económica de rutas de reparto con flotas de vehículos heterogéneas y horarios de servicio flexibles VRPHESTW basado en la búsqueda probabilista en entornos variables y en la aceptación por umbrales estocásticos. Se ha ensayado en un problema concreto la eficacia de la búsqueda con múltiples operadores, así como la ventaja del empleo de la aceptación por umbrales. Sin embargo, la introducción de ruidos estocásticos gaussianos en los umbrales no ha representado una mejora significativa del procedimiento.

 

Referencia:

MEDINA, J.R.; YEPES, V. (2004). Optimización de rutas mediante la búsqueda en entornos variables y aceptación por umbrales estocásticos, en Larrodé, E. y Castejón, L. (Eds.): Infraestructuras de Transporte y Logística como Motor de Desarrollo de las Regiones EuropeasActas del VI Congreso de Ingeniería del Transporte. Vol. 4, pp. 1985-1992. Zaragoza, 23-25 de junio. ISBN (Vol. 4): 84-609-1364-3.

Descargar (PDF, 254KB)

Algoritmo del solterón aplicado a la optimización de rutas con flotas heterogéneas VRPHESTW

Me ha parecido interesante rescatar una pequeña publicación, que ya tiene 10 años, donde se aplicaba un algoritmo de optimización heurística curioso: Old Bachelor Acceptance, o “algoritmo del solterón“. En este caso, aplicado a la optimización de redes de transporte con flotas heterogéneas. Resulta curioso ver cómo determinados comportamientos sociales (colonias de hormigas), principios naturales (teoría de la evolución) o recreaciones de nuestro cerebro (redes neuronales) son capaces de resolver problemas complejos de optimización.

Espero que os sea de interés.

GDE Error: Error al recuperar el fichero. Si es necesario, desactiva la comprobación de errores (404:Not Found)

¿Por qué son tan complicados los problemas de distribución física?

Aspecto de diversas soluciones al problema de rutas
Aspecto de diversas soluciones al problema de rutas

Los problemas de distribución física consisten básicamente en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías. Los clientes se localizan en puntos o arcos y a su vez pueden presentar horarios de servicio determinados; el problema consiste en establecer secuencias de clientes y programar los horarios de los vehículos de manera óptima. Los problemas reales de transporte son extraordinariamente variados. Yepes (2002) propone una clasificación que contiene un mínimo de 8,8·109 combinaciones posibles de modelos de distribución. Si alguien fuese capaz de describir en un segundo cada uno de ellos, tardaría cerca de 280 años en enunciarlos todos. La investigación científica se ha centrado, por tanto, en un grupo muy reducido de modelos teóricos que además tienden a simplificar excesivamente los problemas reales. Son típicos problemas de optimización matemática combinatoria. Continue reading “¿Por qué son tan complicados los problemas de distribución física?”

Optimización económica de redes de transporte

Trascendencia del transporte

La trascendencia económica del sector del transporte genera costos sociales y medioambientales de gran envergadura. Esta actividad supone aproximadamente un sexto del Producto Interno Bruto (PIB) de los países industrializados (ver Yepes, 2002). Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del PIB de Estados Unidos en 1978, constituyendo más del 45% de todos los costos logísticos de las organizaciones. En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector en el valor añadido bruto del año 1997 se situó en un 4.6%. En cuanto al empleo, 613,400 personas se encontraban ocupadas en el año 1999 en el sector de transportes en España, lo cual representa el 3.69% de la población activa. La distribución física representa para las empresas entre la sexta y la cuarta parte de las ventas y entre uno y dos tercios del total de los costos logísticos (Ballou, 1991). Continue reading “Optimización económica de redes de transporte”