TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
HEURÍSTICAS Y METAHEURÍSTICAS
Ante la facilidad de conocer y entender los posibles espacios de solución al abordar problemas, todo
lo encontramos reducidos a hallar un óptimo, es decir un máximo o un mínimo para dar una solución
teniendo en cuenta ciertas condiciones.
De acuerdo a ello y a ciertas condiciones de bajo rendimiento en ciertos algoritmos exactos, y al
desarrollarse métodos aproximados, se requieren técnicas precisas en un tiempo computacional breve;
aquí encontramos tales como, las heurísticas y metaheurísticas para hallar un óptimo.
Estas técnicas básicamente comprenden métodos u algoritmos para llegar a aproximaciones, o
aproximaciones exactas. Hablar de una heurística es referirse en pocas palabras, a procedimientos de
búsqueda de soluciones eficientes, siendo estas “buenas” aunque no se determinen como optimas; por
tanto, se pueden considerar características propias de este tipo de procedimientos a usarse; cuando al
problema a solucionar precisamente no se le conoce ningún método de solución exacto y aun cuando
se le conozca, su costo computacional es muy elevado. Así mismo incluye en si condiciones de difícil
modelización, volviéndolo más flexible ante un método exacto; y así entre otras características.
De este modo podríamos pensar en una heurística como una solución aproximada, aunque no de
aproximación a un problema. Así entonces se considera que en medio de esta técnica hallamos la
diferencia entre aproximada y aproximación, donde la primera se trata de obtener una buena
estimación de la solución de un problema, pero que realmente no se sabe qué tan buena es o que tan
optima puede ser; mientras que el segundo trata de obtener una solución para la que pueda demostrar
qué tan cerca está de la solución óptima, o aún ser totalmente óptima.
Ahora bien, abordar el tema desde el concepto de las metaheurísticas, encontramos que estas son
básicamente estrategias con el fin de diseñar y/o mejorar las técnicas o procedimientos heurísticos
dirigidos a obtener un rendimiento alto u óptimo. Así pues las metaheurísticas se visionan como un
marco de trabajo más global en referencia a algoritmos que pueden aplicarse a distintos problemas de
optimización o combinatorias que en este caso son muy comunes en metaheurísticas por lo que estas
se relacionan mucho con la búsqueda de soluciones de problemas de optimización combinatoria; es
decir, los procedimientos metaheurísticos son aproximados diseñados para la solución de problemas
de difícil optimización combinatoria donde las heurísticas son efectivas. Por ello hallamos
propiedades básicas en ellas, como lo son que estas siempre deben estar fundamentadas en un
principio claro y sencillo que logre una fácil comprensión de sí, ser precisa mostrándose en términos
concretos de formulación, manteniendo coherencia y proyectando eficacia; pero sin dejar de ser
utilizable en distintas variedades de problemas que a su vez se apropian de un carácter adaptable,
múltiple, robusto e interactivo permitiendo así mejorar el rendimiento del procedimiento.
Podemos entonces así decir que una heurística toma la información dependiente o visible del
problema para buscarle una solución que sea "suficientemente buena" a un problema específico,
mientras que las metaheurísticas son como patrones de diseño, ideas algorítmicas más generales que
se pueden aplicar a una amplia gama de problemas donde las anteriores no son efectivas ni llegan.
Así notamos su gran diferencia determinadas o limitadas principalmente la una de la otra en cuanto a
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
su espectro de trabajo o aplicación donde la una llega más allá de la otra en la búsqueda de una
solución más óptima que la presentada por la anterior, es decir, lo más óptima posible.
Finalmente, podemos decir que los métodos metaheurísticos se posicionan sobre los heurísticos, ya
que estos implementan una serie de instrucciones de como y donde ser aplicados, guían su diseño y
de esta manera al seguir un determinado planteamiento, surja la resolución de un problema de manera
mas eficiente conformando así un método sistemático.
CASOS DE ÉXITO EN LA PROGRAMACIÓN DE OPERACIONES
OPERACIONES EN MEDIOS DE TRANSPORTE TERRESTRE:
“Implementación de un algoritmo metaheurístico para la solución de un problema de
programación de transporte terrestre internacional”
Una empresa colombiana del sector de servicios de transporte por carretera internacional, busca la
realización de programación de operaciones entre dos países: Colombia y Venezuela, dicha empresa
tiene como objetivo el desarrollo de servicios de transporte de carga unitaria a sus clientes, lo cual no
incluye el servicio de distribución a varios destinos, solo se enfoca en el transporte desde su origen a
un único destino.
Toda compañía que preste servicios en el extranjero se ve afecta en sus procesos por la diversidad de
reglamentaciones, en este caso algunas repercusiones modifican la forma de operar del proceso y
restringen en algunos casos su operación o estandarización, algunas de estas son diferencia en el
límite de peso en las carreteras, habilitación de vehículos y tráileres, diversas modalidades de servicio,
entre otras.
Se desarrolla un VRP con diversos y nuevas particularidades, muchos de ellos marcados por las
características del proceso y otros por el tipo de manejo del mercado regional según las características
de la demanda.
Su objetivo es la generación de una programación de rutas para los vehículos y tráileres, con el cual
se efectúen todos los transportes o servicios solicitados por los diversos clientes durante un mes,
cumpliendo con todas las características y restricciones que exige el proceso y las características de
la demanda. La función objetivo busca minimizar las distancias recorridas en estado vacío de los
vehículos durante el periodo programado de operación.
La solución se realizó a través de la implementación de la metaheurística Recocido Simulado (SA,
Simulated Annealing), la cual se probó iniciando con soluciones factibles generadas por dos
algoritmos heurísticos; el primero se basa en la heurística clásica conocida como el vecino más
cercano y el segundo genera soluciones de forma aleatoria. Los resultados del Recocido Simulado
usando las soluciones generadas con el primer algoritmo, no mostraron una mejora frente a dicha
solución inicial, contrario a lo hallado con el uso de las soluciones del segundo método, donde se
alcanzó hasta cerca de un 50% de mejora.
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
“Implantación de VRP - Solver aplicando la heurística de Clarke Wright para el ruteo
del transporte terrestre en el área de distribución caso de estudio: industrias
alimentarias”
En el presente caso de estudio se muestra una empresa dedicada a la producción, venta y distribución
de productos de consumo masivo. En ella eran utilizados dos sistemas para la planificación de
transporte y facturación, para lo cual en el primero de estos no fue satisfactorio ya que el sistema no
lograba adaptar gran cantidad de la información procesada y su principal objetivo era que estos
tuviesen una adecuada planificación para poder cumplir con el despacho a los clientes. Así mismo,
fue implantado otro sistema el cual reflejo mejoría ante los primeros, pero de igual manera presentó
dificultades porque a pesar de que procesaba toda la información necesitada, traslados, devoluciones,
despachos y calculaba que ruta tomar para cada planificación, no se podía obtener como tal una ruta
óptima, y esto hacia que los conductores tomaran rutas a sus criterios, lo cual conlleva pérdida de
tiempo y costos.
Presentadas estas dificultades se requirió tener un modelo en el cual se pueda resolver las
problemáticas, por lo cual se implanta VRP-SOLVER APLICANDO LA HEURÍSTICA DE
CLARKE WRIGHT PARA EL RUTEO DEL TRANSPORTE.
La implementación del VRP Solver tuvo como objetivo la minimización de las distancias utilizadas
por una empresa distribuidora para él envió de sus productos. Para darle solución al problema en un
principio se realizan evaluaciones por los criterios de algoritmos y modelos de heurísticas, los cuales
arrojan como resultado que el modelo que se ajusta para darle solución al problema es el modelo VRP,
con la heurística de Clarke Wright y el algoritmo de Búsqueda Tabú.
El software toma como datos de entradas, la ubicación de cada cliente, de esta manera da como
resultado las rutas óptimas, con las pruebas realizadas, se logra disminuir en un 10% la distancia
total utilizada en las rutas de la empresa del caso de estudio.
OPERACIONES EN MEDIOS DE TRANSPORTE MARÍTIMO
“Estudio de calibración para la optimización de los procesos logísticos portuarios de los
accesos de buques y trenes con mercancía contenerizada”
El mercado internacional sufre de manera progresiva debido al nivel de globalización presentado
actualmente. De esta manera el comercio que se ve afectado mayormente es el marítimo, puesto que
es el menos costoso y más eficiente para transportar grandes volúmenes de mercancía.
Dada su importancia en las terminales portuarias, en esta red de transporte todas las operaciones
deben ser optimizadas con el fin de lograr una máxima productividad global.
El objetivo de este proyecto será realizar un estudio de calibración sobre un algoritmo de
optimización sobre los procesos logísticos que tienen lugar en una terminal portuaria con la llegada
de buques y trenes cargados con mercancía contenerizada. El algoritmo de optimización será un
Algoritmo Genético. Esta metaheurística tratará de minimizar el tiempo de residencia en una
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
terminal de los transportes que llegan a ella con mercancía y que deben salir de ella con mercancía
diferente de con la que entraron.
En función del tiempo de llegada dado por el algoritmo de optimización, los barcos contenedores
llegan al puerto, de igual manera que los trenes contenedores llegan a la terminal. Dado esto, todo
número de contenedor que llega por mar, debe ser igual al número de contenedores transportados por
vía terrestre. Por lo tanto, ninguno de estos al final la simulación debe quedar en el puerto.
Los parámetros variables de entrada del Algoritmo Genético que han sido estudiados y calibrados son
el número de iteraciones, el tamaño de la población, la probabilidad de mutación y la probabilidad de
cruce. A su vez fue ejecutado un modelo de simulación con arena y a partir de esto se comprueba que
dichos resultados cumplen con el modelo de algoritmos genéticos propuesto.
“Plataforma logística regional de distribución de contenedores para la eficiencia de los
buques que pasan por el puerto de corozal”
Actualmente, muchas organizaciones implementan en sus sistemas procesos donde sean controladas
sus operaciones de carga y distribución con el fin de satisfacer al cliente.
La planificación y gestión de las redes de distribución requiere de técnicas eficientes de optimización
de rutas marítimas. El sistema que está disponible afecta no solo el desarrollo del mismo, sino también
estrategias como el tamaño optimo de flota en puertos, optimización de tiempos y costos.
Dado este contexto, sabiendo que el principal negocio del canal es optimizar procesos y dar un valor
agregado al paso de los barcos, se es necesario una aplicación de modelos matemáticos eficientes
para así resolver los problemas mas complejos; Es por esto, que se plantea la siguiente problemática
¿Cómo un algoritmo genético apoya la plataforma logística regional de distribución de contenedores
para la eficiencia de los buques que pasan el puerto de Corozal?
El objetivo es minimizar los costes y tiempos asociados al transporte satisfaciendo una serie de
restricciones.
Para ser solucionado dicho problema se es implementado distintas técnicas que brindan calidad de
una solución inicial. Así, el resultado será mejor en cuanto mayor sea el tiempo de optimización. Por
lo tanto, si el algoritmo se ejecuta durante el tiempo necesario devolverá la solución óptima.
Luego de ser establecidos distintos análisis de diversos algoritmos, se evidencia el algoritmo genético
como el mas eficiente para la operación y optimización de los procesos, el cual permite adaptarse a
entornos legales, técnicos y empresariales cambiantes, pudiendo considerar una extensa variedad de
restricciones y objetivos, muchas veces ambiguos e incluso contradictorios.
OPERACIONES EN MEDIOS DE TRANSPORTES FÉRREOS
“Estudio y optimización del consumo energético del ferrocarril mediante redes neuronales y
algoritmos heurísticos”
El ferrocarril es uno de los medios de transporte con más eficiencia, pero un existe un margen mejora
para reducir su consumo energético y aumentar su sostenibilidad.
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
El objetivo de este es contribuir al conocimiento de las herramientas a emplear para el estudio del
consumo energético en el ferrocarril de ámbito urbano, partiendo del posible uso de redes neuronales
como instrumento de simulación, además llevando a cabo una comparativa sistemática de algoritmos
meta-heurísticos de optimización más usados.
Se ha desarrollado un simulador de marchas combinado con una red neuronal, la consiste en una serie
de comando que representan la salida del sistema ATO, a partir de ahí calcula el correspondiente
perfil de velocidad, tiempo de viaje y consumo energético, el simulador fue validado con datos reales
medidos en la red de metro de Valencia, con un error medio del 2,87% al estimar el tiempo y del
3,68% en la estimación de la energía.
Mediante este simulador se han calculado más de 5.800 combinaciones de comandos ATO para 32
tramos de la red de metro de Valencia (considerando ambos sentidos de circulación) y se han
calculado los frentes de Pareto reales para cada caso, con el simulador se calcularon más de 5.800
combinaciones de comandos ATO para 32 tramos de la red de metro de Valencia, además de frentes
de Pareto reales para cada caso.
A partir de aquí, se han aplicado cinco algoritmos meta-heurísticos (NSGA-II, MOPSO, SPEA-II,
MOEA-D y MOACOr) para obtener conjuntos de soluciones no-dominadas en cada uno de los 64
casos de estudio, y se ha evaluado el grado de convergencia, regularidad y diversidad de cada
conjunto de soluciones con una serie de métricas, aplicando un análisis estadístico para detectar
diferencias significativas. Se ha observado que los cinco algoritmos ofrecen resultados similares en
términos de convergencia y regularidad, pero que el algoritmo MOPSO destaca significativamente
en términos de diversidad (y, en menor medida, el algoritmo SPEA-II), siendo el algoritmo más
habitual (NSGA-II) el que peor resultados presenta en este sentido. Estos resultados pretenden
ofrecer una cierta guía para escoger algoritmos más efectivos en futuros estudios de optimización de
marchas ferroviarias.
OPERACIONES EN MEDIOS DE TRANSPORTE AÉREO
“Aplicación de recocido simulado para la optimización de procesos de aterrizaje en aeropuertos”
En los aeropuertos la capacidad es insuficiente debido a que, en los últimos años, la demanda ha
incrementado debido a que ahora en la mayoría de trabajos y ocupaciones se necesita estar viajando,
también que hemos evolucionado y cada vez somos una población más grande, con ganas de conocer
el mundo, esto conlleva a que haya atrasos en los aeropuertos, y que casi ningún vuelo sea puntual,
generando inconformidad en toda la clientela, lo que nos afecta demasiado económica y socialmente
Por lo tanto, se requiere asignar una pista de aterrizaje para que cada avión destine a cualquier
aeropuerto para un periodo de tiempo establecido
Para solucionar el problema se parte de soluciones a problemas similares; En el pasado una de ellas
es la de Pinol y Beasly que proponen un modelo de tres tipos de restricciones; tiempo de separación,
ventana de tiempo y múltiples pistas, se utilizan 2 técnicas heurísticas basada en poblaciones, la
primera es la búsqueda dispersa determinística y la segunda es la del algoritmo biológico, después de
varias pruebas como resultado se obtuvo que bajaron aproximadamente 500 aterrizajes y 5 pistas, y
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
como estas han llegado varios casos, pero se ha concluido que para la solución inicial se utilizara el
tiempo de llegada al aeropuerto de los aviones y se asigna el orden de aterrizaje por el tiempo en el
que pueden aterrizar, y así las pistas se van asignando hasta llegar al máximo y de nuevo vuelve a
comenzar por la primera, el tiempo es el mínimo siempre y cuando el avión previo ya haya aterrizado.
“Desarrollo y aplicación de un modelo de simulación discreta y una heurística de
optimización para mejorar la robustez de itinerarios de trasporte aéreo”
La industria aérea ha sido uno de los principales factores que han permitido el impulso de la
globalización en el mundo actual, pero a pesar de esto y de los altos volúmenes de ventas, las
aerolíneas obtienen bajos márgenes de utilidad como consecuencia de su alto costo fijo, el
crecimiento en el precio del petróleo, además de la volatilidad de la demanda, la cual es muy
sensible a ciclos económicos. Por lo anterior se han provocado fusiones en las aerolíneas para
reducir sus costos y a su vez aumentar la competitividad y guerra de precios.
Las aerolíneas proyectan sus itinerarios con el objetivo de maximizar sus beneficios. Para
esto se considera utilizar al máximo el tiempo disponible de sus aviones, teniendo en cuenta
eventuales disrupciones que afectan la operación, los beneficios de explotación y costos de
operación se logran localizando eficientemente tiempos los vuelos programados, de manera
de minimizar el impacto de los atrasos propagados.
La formulación general del problema las restricciones consideradas en la heurística. Se
asume como información base: Un itinerario, compuesto por el plan de vuelo y
mantenimiento de cada avión. Cada vuelo y mantenimiento posee un par origen destino y un
tiempo planificado de salida y llegada.; Un conjunto de conexiones de tripulantes y
pasajeros. Cada conexión tiene asociado un vuelo de inicio y de término;3. Tiempos mínimos
de conexión y T/A mínimos entre vuelos sucesivos de un mismo avión.;4. Desempeño
operacional simulado de itinerario base. Corresponde al promedio de minutos de atraso
reaccionario, atraso independiente y puntualidad de cada vuelo, más estadísticas de los
planes de contingencia efectuados
La heurística da como variaciones marginales en el tiempo de despegue de los vuelos, tiene
como objetivo minimizar el atraso que se da en el momento. Esto conlleva a una localización
de holguras consecuentes con el atraso del vuelo. La aplicabilidad y los cambios por la
heurística tiene su sustento en el modelo, lo cual utilizan datos de LAN Airlines y se calcula
la calidad de la metodología propuesta o aumento de puntualidad de minutos de retraso
Podemos concluir como se muestra variaciones margínale en los tiempos de despegue y el
número total de vuelos que puede mejorar el desempeño operacional de planes de
contingencias.
TRABAJO HEURISTICAS
María Movilla; Andrea Estrada; María José Tapias; Luisa Montalvo
Ingeniería industrial, Universidad Autónoma del Caribe
Barranquilla, Colombia
REFERENCIAS
▪ Suarez, O. (2013). Una aproximación a la heurística y metaheurísticas. INGE@ UAN-
Tendencias en la Ingeniería, 1(2).
▪ Pemberthy Ruiz, J. I. (2013). Implementación de un algoritmo metaheurístico para la solución
de un problema de programación de transporte terrestre internacional. Ingeniería
Administrativa.
▪ Maguiña Agurto, L. L. (2016). Implantación de VRP-Solver aplicando la heurística de Clarke
Wright para el ruteo del transporte terrestre en el área de distribución caso de estudio:
industrias alimentarias.
▪ Sánchez Molero, C. (2016). Estudio de calibración para la optimización de los procesos
logísticos portuarios de los accesos de buques y trenes con mercancía contenerizada.
▪ Moreno Ormaza, E. D., & Páez Moreno, R. F. (2017). Plataforma logística regional de
distribución de contenedores para la eficiencia de los buques que pasan por el Puerto
Corozal.
▪ Fernández, P. M. (2019). Estudio y optimización del consumo energético del ferrocarril
mediante redes neuronales y algoritmos heurísticos (Doctoral dissertation, Universitat
Politècnica de València).
▪ LÓPEZ, I. D., & MARTÍN, A. J. (2015). APLICACIÓN DE RECOCIDO SIMULADO PARA LA
OPTIMIZACIÓN DE PROCESOS DE ATERRIZAJE EN AEROPUERTOS.
▪ Cuevas Cortés, R. A. (2011). Desarrollo y aplicación de un modelo de simulación discreta y
una heurística de optimización para mejorar la robustez de itinerarios de transporte aéreo
