La planificación y gestión de redes de distribución de baja demanda exige disponer de técnicas eficientes de optimización de rutas. El sistema de optimización de rutas disponible, no sólo afecta el desarrollo de operaciones sino, también las decisiones tácticas y estratégicas como el tamaño óptimo de flota, estimación de costes, políticas de publicidad y rotura de servicio, etc. Por ejemplo, es habitual la venta de paquetes turísticos que incluyen el transporte; los precios se fijan mucho antes de que la demanda de transporte sea conocida, siendo frecuentes las cancelaciones de última hora y la llegada de nuevos clientes. Si el número de pasajeros que debe ser transportado es pequeño, en comparación con la máxima capacidad de carga del vehículo óptimo a la distancia correspondiente, los beneficios o pérdidas generadas por el transporte dependen críticamente de la eficiencia del sistema de optimización de rutas. La Figura describe la influencia de la optimización de operaciones en la planificación y gestión de redes de distribución de baja demanda.
Planificación y Gestión de Redes de Distribución de Baja Demanda
George Bernard Dantzig (1914-2005), “padre de la programación lineal”
Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.
La programación matemática constituye un campo amplio de estudio que se ocupa de la teoría, aplicaciones y métodos computacionales para resolver los problemas de optimización condicionada. En estos modelos se busca el extremo de una función objetivo sometida a un conjunto de restricciones que deben cumplirse necesariamente. Las situaciones que pueden afrontarse con la programación matemática se suelen presentar en ingeniería, empresas comerciales y en ciencias sociales y físicas.
Con carácter general, un programa matemático (ver Minoux, 1986) consiste en un problema de optimización sujeto a restricciones en de la forma:
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.
Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios; si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado “óptimo de Pareto“. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.
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?”→
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”→
¿Cómo se podrían optimizar en tiempos de cálculo razonable problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otro tipo de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que es imposible hacerlo con métodos matemáticos exactos? La respuesta son los métodos aproximados, también denominados heurísticas. Este artículo divulgativo trata de ampliar otros anteriores donde ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Para más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto, una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al, 2008).
Desde los primeros años de la década de los 80, la investigación de los problemas de optimización combinatoria se centra en el diseño de estrategias generales que sirvan para guiar a las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.
Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.
Las metaheurísticas son susceptibles de agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de memoria que guíe de la exploración del espacio de elecciones posibles permite otro tipo de agrupamiento. En otras circunstancias se emplean perturbaciones de las opciones, de la topología del espacio de soluciones, o de la función objetivo. En la Figura se recoge una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), teniendo en común todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que existen en este momento muchas más técnicas de optimización, pero puede ser dicha clasificación un punto de partida para una mejor taxonomía de las mismas.
Figura. Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales (Yepes, 2002)
Las metaheurísticas empleadas en la optimización combinatoria en podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que éste concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los diferentes problemas de optimización combinatoria.
Referencias
GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)
La investigación de operaciones o investigación operativa es una rama de las matemáticas que consiste en el uso de modelos matemáticos, estadística y algoritmos con objeto de modelar y resolver problemas complejos determinando la solución óptima y permitiendo, de este modo, tomar decisiones. Frecuentemente trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede optimizar un objetivo definido, como la maximización de los beneficios o la minimización de costos.
Aunque su nacimiento como ciencia se establece durante la Segunda Guerra Mundial y debe su nombre a las operaciones militares, los verdaderos orígenes de la Investigación Operativa se remontan mucho más atrás en el tiempo, hasta el siglo XVII. Esta disciplina nació en Inglaterra durante la Segunda Guerra Mundial como estrategia para encontrar soluciones a problemas militares, para ello fue necesario crear un Grupo de Investigación de Operaciones Militares conformado por un grupo de científicos multidisciplinares. Al terminar la guerra este método fue empleado en darle solución a problemas generales como el control de inventarios, asignación de recursos, líneas de espera, entre otros. Esta técnica cumplió sus objetivos en la década de los cincuenta y sesenta, hasta su desarrollo total en la actualidad. Sin embargo su auge es debido, en su mayor parte, al gran desarrollo de la informática, gracias a la cual es posible resolver problemas en la práctica y obtener soluciones que de otra forma conllevarían un enorme tiempo de cálculo. Debido a este éxito, la Investigación Operativa se extendió a otros campos tales como la industria, física, informática, economía, estadística y probabilidad, ecología, educación, servicio social, …, siendo hoy en día utilizada prácticamente en todas las áreas. Algunos de los promotores más importantes de la filosofía y aplicación de la investigación de operaciones son C.W. Churchman, R.L. Ackoff y R. Bellman. Actualmente la Investigación Operativa incluye gran cantidad de ramas como la Programación Lineal, Programación No Lineal, Programación Dinámica, Simulación, Teoría de Colas, Teoría de Inventarios, Teoría de Grafos, etc.
Os presento ahora un vídeo, que no llega a 3 minutos de duración sobre el tema. Espero que os guste.
En este artículo traigo a colación un vídeo donde el psicólogo Barry Schwartz apunta hacia un principio central de las sociedades occidentales: la libertad de elección. Según la estimación de Schwartz, elegir no nos ha hecho más libres sino más paralizados, no más felices sino más insatisfechos.
Desconozco si estaréis de acuerdo con esta paradoja, pero es un buen punto de arranque para discutir en clase preguntas tan interesantes como: ¿por qué es tan difícil tomar una decisión?, ¿qué pasa cuando hay muchas posibilidades de elegir algo?, ¿qué relación existe entre el coste de oportunidad y la posibilidad de elegir algo? o ¿estás de acuerdo que un aumento desmesurado en la capacidad de elegir disminuye la satisfacción?
Uno de los puntos a los que me gusta llegar con estas reflexiones es a plantear a los alumnos de posgrado cómo la realidad es mucho más compleja de lo que parece y cómo la enseñanza tradicional en el campo de las ingenierías, donde un problema se enseña a solucionarlo de un modo concreto (solo una solución, que suele ser el resultado correcto en un examen), se aleja de la realidad, donde siempre existe un cúmulo de posibles soluciones, muchas de ellas válidas. El problema consiste en elegir entre todas ellas con criterio.
La optimización significa hallar el valor máximo o mínimo de una cierta función, definida en un dominio. En los problemas de decisión que generalmente se presentan en la vida empresarial existen una serie de recursos escasos (personal, presupuesto, tiempo), o de requisitos mínimos a cumplir (producción, horas de descanso), que condicionan la elección de la solución adecuada, ya sea a nivel estratégico, táctico e incluso operativo. Por lo general, el propósito perseguido al tomar una decisión consiste en llevar a cabo el plan propuesto de una manera óptima: mínimos costos o máximo beneficio.
Desgraciadamente, la complejidad de las situaciones reales es de tal magnitud que en numerosas ocasiones son inviables los métodos matemáticos de resolución exactos, de modo que los problemas de optimización planteados frecuentemente se resuelven con métodos aproximados que proporcionan soluciones factibles que sean satisfactorias.
Os dejamos aquí un pequeño vídeo para divulgar lo que significa un modelo matemático de optimización. Espero que os guste.
La