Función de evaluación y penalizaciones en algoritmos genéticos aplicados a la optimización de rutas
En un algoritmo genético, no basta con generar muchas soluciones posibles. También es necesario saber comparar unas soluciones con otras. Para ello se utiliza una función de evaluación, también conocida como función de aptitud o función fitness. Esta función permite medir la calidad de cada individuo de la población y determinar qué soluciones tienen más posibilidades de sobrevivir, reproducirse y transmitir sus características a las siguientes generaciones.
En un algoritmo genético, no basta con generar muchas soluciones posibles. También es necesario saber comparar unas soluciones con otras.
Para ello se utiliza una función de evaluación, también conocida como función de aptitud o función fitness. Esta función permite medir la calidad de cada individuo de la población y determinar qué soluciones tienen más posibilidades de sobrevivir, reproducirse y transmitir sus características a las siguientes generaciones.
En el contexto de la optimización de rutas, la función de evaluación es uno de los elementos más importantes del sistema. Su diseño determina qué entiende el algoritmo por una buena planificación.
Una solución puede parecer buena porque reduce kilómetros, pero ser inviable porque incumple horarios. Otra puede cumplir todas las ventanas horarias, pero utilizar demasiados vehículos. Una tercera puede ser barata en distancia, pero generar jornadas desequilibradas o excesivas para determinados conductores.
Por este motivo, en problemas logísticos reales, la función de evaluación debe ser capaz de integrar muchos criterios diferentes.
Qué es la función de evaluación
La función de evaluación es el mecanismo que asigna una puntuación a cada solución candidata.
En un problema de rutas, una solución puede estar formada por el conjunto de vehículos utilizados, los pedidos asignados a cada uno de ellos y el orden en que se visitan los diferentes puntos.
La función de evaluación analiza esa solución y calcula su calidad según los objetivos del problema.
Estos objetivos pueden incluir, entre otros:
Reducir la distancia total recorrida.
Reducir el tiempo total de conducción.
Minimizar el coste operativo.
Utilizar el menor número posible de vehículos.
Cumplir las ventanas horarias de los clientes.
Evitar retrasos.
Aprovechar correctamente la capacidad de los vehículos.
Equilibrar la carga de trabajo entre rutas.
Reducir tiempos muertos.
Evitar pedidos no asignados.
La dificultad está en que todos estos criterios no siempre apuntan en la misma dirección.
Por ejemplo, reducir el número de vehículos puede hacer que algunas rutas sean más largas. Minimizar kilómetros puede provocar incumplimientos horarios. Repartir mejor el trabajo entre vehículos puede aumentar ligeramente el coste total, pero mejorar la viabilidad operativa.
Por eso, la función de evaluación debe representar correctamente las prioridades reales del negocio.
Evaluar no es solo medir distancia
Uno de los errores habituales al abordar la optimización de rutas es pensar que el objetivo principal consiste únicamente en recorrer menos kilómetros.
Aunque la distancia es un factor importante, no suele ser suficiente para definir la calidad de una planificación logística.
En una operación real, una ruta debe poder ejecutarse. Debe respetar horarios, capacidades, tiempos de servicio, restricciones de acceso, descansos, costes laborales y limitaciones propias de cada vehículo o conductor.
Una ruta muy corta puede ser inútil si llega tarde a un cliente importante. Una ruta aparentemente barata puede no ser aceptable si obliga a superar la jornada máxima. Una solución con pocos vehículos puede no ser viable si provoca sobrecargas o incumplimientos.
Por este motivo, la función de evaluación debe ir más allá del cálculo de distancia. Debe valorar la solución desde un punto de vista operativo.
Criterios habituales en la evaluación de rutas
La función de evaluación puede construirse combinando diferentes componentes.
Uno de los criterios más habituales es la distancia total recorrida. Reducir kilómetros suele implicar un menor consumo de combustible, menos desgaste de vehículos y menor coste operativo.
Otro criterio importante es el tiempo total de trabajo. En muchas empresas, el coste no depende únicamente de los kilómetros, sino también de las horas dedicadas por los conductores y vehículos.
También puede considerarse el número de vehículos utilizados. En determinados escenarios, reducir un vehículo puede suponer un ahorro muy relevante, incluso si la distancia total recorrida aumenta ligeramente.
Las ventanas horarias son otro elemento crítico. Muchos clientes solo pueden recibir mercancía en determinados intervalos de tiempo. Incumplir estas ventanas puede generar esperas, rechazos, penalizaciones o pérdida de calidad de servicio.
La capacidad de los vehículos también debe formar parte de la evaluación. Una solución que asigna más carga de la permitida a un vehículo no puede considerarse válida, aunque sea eficiente en distancia.
Además, pueden existir restricciones específicas: productos incompatibles, vehículos con requisitos especiales, zonas de acceso limitado, horarios de carga, conductores concretos, bases de salida y retorno, pausas obligatorias o prioridades comerciales.
Todos estos factores deben traducirse de alguna forma en la puntuación final de cada solución.
Penalizaciones
En los algoritmos genéticos aplicados a rutas, las penalizaciones permiten tratar las soluciones que incumplen alguna condición del problema.
Una penalización es un coste adicional que se añade a una solución cuando esta presenta un incumplimiento.
Por ejemplo, si una ruta llega tarde a un cliente, se puede añadir una penalización proporcional al retraso. Si un vehículo supera su capacidad, se puede añadir una penalización por exceso de carga. Si un pedido queda sin asignar, la penalización puede ser muy alta para indicar que se trata de una solución poco aceptable.
Las penalizaciones permiten que el algoritmo no descarte necesariamente todas las soluciones imperfectas desde el primer momento.
Esto es importante porque, durante el proceso evolutivo, algunas soluciones inicialmente malas pueden contener partes útiles. Un individuo puede incumplir una restricción, pero incluir una buena secuencia de visitas o una asignación interesante de determinados pedidos.
Si el algoritmo eliminara de forma inmediata cualquier solución con un pequeño incumplimiento, podría perder material genético valioso para futuras generaciones.
Las penalizaciones permiten graduar la gravedad de los errores y guiar la búsqueda hacia soluciones cada vez mejores.
Penalizaciones duras y penalizaciones suaves
No todas las restricciones tienen la misma importancia.
Algunas restricciones son absolutamente obligatorias. Por ejemplo, un vehículo no puede transportar una mercancía para la que no está autorizado, o no puede superar una limitación legal de jornada. Este tipo de restricciones suelen tratarse como restricciones duras.
Otras restricciones pueden ser preferentes, pero no necesariamente invalidantes. Por ejemplo, puede ser deseable equilibrar la carga de trabajo entre vehículos, reducir esperas o evitar pequeñas desviaciones respecto a una hora preferida. Estas restricciones suelen tratarse como restricciones suaves.
Las restricciones duras requieren penalizaciones muy elevadas o mecanismos de reparación que impidan que la solución final las incumpla.
Las restricciones suaves, en cambio, pueden influir en la calidad de la solución sin invalidarla completamente.
Este equilibrio es fundamental. Si todas las restricciones se tratan como absolutas, el algoritmo puede tener dificultades para encontrar soluciones factibles. Si todas se tratan como flexibles, el resultado puede ser operativo en apariencia, pero poco útil en la práctica.
Peso de cada criterio
Una de las decisiones más delicadas al diseñar una función de evaluación es determinar el peso de cada criterio.
No todas las empresas tienen las mismas prioridades. Para una empresa puede ser esencial minimizar el número de vehículos. Para otra, el factor más importante puede ser cumplir estrictamente los horarios de entrega. En otros casos, puede interesar equilibrar rutas para evitar jornadas excesivamente largas.
La función de evaluación debe reflejar estas prioridades.
Por ejemplo, una función sencilla podría combinar distancia, tiempo y penalizaciones de la siguiente forma:
Coste total = coste por kilómetros + coste por tiempo + penalizaciones
Sin embargo, en problemas reales, esta fórmula puede ampliarse mucho más. Se pueden añadir costes fijos por vehículo, costes variables, penalizaciones por retraso, penalizaciones por exceso de capacidad, penalizaciones por pedidos no asignados o bonificaciones por cumplir determinados objetivos.
El diseño de estos pesos no es una tarea trivial. Si una penalización es demasiado baja, el algoritmo puede aceptar soluciones que incumplen restricciones importantes. Si es demasiado alta, puede bloquear la exploración y hacer que el algoritmo se concentre demasiado pronto en una zona limitada del espacio de búsqueda.
Soluciones factibles y soluciones de calidad
En optimización de rutas es importante distinguir entre una solución factible y una solución de calidad.
Una solución factible es aquella que cumple las restricciones mínimas del problema.
Una solución de calidad, además de ser factible, optimiza los objetivos definidos: reduce costes, mejora tiempos, aprovecha recursos y genera rutas ejecutables de forma eficiente.
El algoritmo genético debe avanzar en dos direcciones al mismo tiempo.
Por un lado, debe acercarse a la factibilidad, reduciendo incumplimientos y eliminando soluciones inviables.
Por otro lado, debe mejorar la calidad de las soluciones factibles, buscando planificaciones cada vez más eficientes.
Las penalizaciones ayudan especialmente en la primera parte. Los criterios de coste y optimización ayudan en la segunda.
El papel de la función de evaluación en la selección
La función de evaluación no solo mide la calidad de una solución. También influye directamente en la selección de los individuos que participarán en la siguiente generación.
Los individuos mejor evaluados tienen más probabilidades de ser seleccionados para cruzarse y generar descendencia.
Esto significa que la función de evaluación actúa como el entorno en la evolución biológica. Define qué individuos están mejor adaptados y cuáles tienen menos posibilidades de sobrevivir.
Si la función de evaluación está mal diseñada, el algoritmo evolucionará en la dirección equivocada.
Por ejemplo, si se valora demasiado la reducción de kilómetros y poco el cumplimiento horario, el sistema tenderá a generar rutas cortas, pero poco realistas. Si se penaliza en exceso cualquier desviación, el algoritmo puede volverse demasiado conservador y perder capacidad de exploración.
La calidad de la evaluación determina la calidad de la evolución.
Evaluación multicriterio
Muchos problemas de optimización de rutas son problemas multicriterio.
Esto significa que no existe un único objetivo, sino varios objetivos que deben equilibrarse.
Algunos de estos objetivos pueden ser contradictorios entre sí.
Reducir kilómetros puede entrar en conflicto con reducir tiempos.
Reducir vehículos puede entrar en conflicto con cumplir horarios.
Equilibrar rutas puede entrar en conflicto con minimizar el coste total.
Maximizar la ocupación de los vehículos puede entrar en conflicto con mantener flexibilidad operativa.
En estos casos, la función de evaluación debe transformar todos esos objetivos en una puntuación comparable.
Una forma habitual de hacerlo es combinar los distintos criterios mediante pesos. Otra posibilidad es trabajar con jerarquías de objetivos, dando prioridad absoluta a unos criterios sobre otros.
También pueden aplicarse enfoques en los que el algoritmo no busca una única solución óptima, sino un conjunto de soluciones alternativas con diferentes equilibrios entre coste, tiempo y calidad de servicio.
En entornos reales, esta visión es especialmente útil, porque la mejor solución matemática no siempre es la mejor decisión operativa.
Penalizaciones dinámicas
En algunos casos, las penalizaciones pueden variar durante la ejecución del algoritmo.
Al inicio del proceso evolutivo puede ser útil permitir cierto grado de incumplimiento para explorar zonas amplias del espacio de búsqueda. A medida que avanzan las generaciones, las penalizaciones pueden endurecerse para forzar la convergencia hacia soluciones factibles.
Este enfoque permite combinar exploración y refinamiento.
Durante las primeras generaciones, el algoritmo puede experimentar con asignaciones y secuencias diversas. En las fases finales, se da más importancia al cumplimiento estricto de las restricciones.
Las penalizaciones dinámicas son especialmente interesantes en problemas complejos, donde encontrar soluciones factibles desde el principio puede ser difícil.
Reparación de soluciones
Las penalizaciones no son la única forma de tratar incumplimientos.
Otra estrategia consiste en reparar las soluciones antes o después de evaluarlas.
Por ejemplo, si un pedido aparece duplicado en dos rutas, se puede eliminar de una de ellas. Si un pedido queda sin asignar, se puede intentar insertar en la ruta más adecuada. Si un vehículo supera su capacidad, se pueden mover algunos pedidos a otros vehículos.
Estos mecanismos de reparación pueden mejorar la eficiencia del algoritmo, ya que reducen el número de soluciones claramente inválidas.
Sin embargo, también deben diseñarse con cuidado. Una reparación demasiado agresiva puede alterar excesivamente la solución original y reducir la diversidad genética. Una reparación demasiado débil puede no corregir los problemas relevantes.
En la práctica, suele utilizarse una combinación de penalizaciones y reparaciones.
La importancia de evaluar rápido
En un algoritmo genético se evalúan muchas soluciones durante muchas generaciones.
Por este motivo, la función de evaluación debe ser precisa, pero también eficiente.
Si evaluar una solución es demasiado lento, el algoritmo completo se vuelve poco práctico. Esto es especialmente importante en problemas de rutas con muchos pedidos y muchos vehículos, donde cada individuo puede representar una planificación compleja.
La eficiencia de la evaluación depende de muchos factores: cómo se calculan las distancias, cómo se comprueban las ventanas horarias, cómo se acumulan los tiempos de servicio, cómo se detectan incumplimientos y cómo se actualizan los costes cuando se modifica una ruta.
Una buena implementación debe evitar recalcular desde cero todo lo que no ha cambiado. En muchos casos, pequeñas modificaciones locales en una ruta pueden evaluarse de forma incremental.
Esta eficiencia permite explorar más soluciones en menos tiempo y mejorar la calidad final de la optimización.
Función de evaluación y realidad operativa
La función de evaluación debe representar la realidad de la operación logística.
Esto significa que no debe limitarse a un modelo teórico simplificado, sino incorporar las condiciones que realmente afectan a la planificación diaria.
Por ejemplo, puede ser necesario considerar tiempos de carga y descarga, horarios de almacén, restricciones de circulación, clientes prioritarios, zonas geográficas, descansos, costes diferenciados por vehículo o condiciones específicas de determinados pedidos.
Cuanto mejor refleje la función de evaluación la realidad operativa, más útiles serán las soluciones generadas por el algoritmo.
En cambio, si la función de evaluación ignora elementos importantes, el sistema puede encontrar soluciones aparentemente óptimas, pero difíciles o imposibles de ejecutar.
Conclusión
La función de evaluación es el criterio que guía la evolución de un algoritmo genético.
En la optimización de rutas, esta función debe valorar muchos aspectos al mismo tiempo: distancia, tiempo, coste, vehículos utilizados, ventanas horarias, capacidad, equilibrio de rutas y cumplimiento de restricciones.
Las penalizaciones permiten incorporar incumplimientos y restricciones dentro del proceso evolutivo, guiando al algoritmo hacia soluciones factibles y de mayor calidad.
Diseñar correctamente esta función es tan importante como definir la representación de las soluciones o los operadores genéticos. Una buena función de evaluación permite que el algoritmo no solo encuentre rutas más cortas, sino planificaciones logísticas realmente útiles, viables y adaptadas a las necesidades de cada operación.
La experiencia acumulada por Evolution Algorithms permite que el motor de optimización de LOGISPLAN aplique estos criterios de evaluación a problemas logísticos reales, complejos y con múltiples restricciones operativas.