IMPLEMENTACIÓN DE UN ALGORITMO GENÉTICO PARA LA SOLUCIÓN AL

PROBLEMA DE RUTEO DE VEHICULOS(VRP)

Vanessa Fiorella Alvarado García, Luis Ronaldo Inga Sullón, Elías Silva Jaramillo, Luis
Fernando Vilela Torres, Jimy Alexsander Yahuana Villegas, Luis David Yarleque Chininin
Escuela de Ingeniería Industrial, Departamento Académico de Investigación de Operaciones,
Investigación de Operaciones II, Universidad Nacional de Piura.
04 de septiembre de 2024

RESUMEN
El objetivo de este artículo es implementar un algoritmo genético modificado para resolver el
problema de ruteo de vehículos (VRP), utilizando como base los estudios previos del Dr. Miguel
Jiménez Carrión, detallados en su libro “Los algoritmos genéticos desde la investigación de
operaciones”. El algoritmo fue desarrollado en lenguaje Python, usando Excel como recurso de
apoyo para leer una matriz ya generada que representan las distancias entre ciudades. El VRP
es conocido por su complejidad computacional debido al gran número de restricciones que
presenta al estar compuesto por varios TSP, lo que ha motivado el desarrollo de diversos
algoritmos estocásticos. Los algoritmos genéticos, en particular, han mostrado ser una buena
aproximación para obtener soluciones factibles y, en algunos casos, óptimas para este tipo de
problemas. Se analiza el algoritmo basándonos en los siguientes parámetros: TPo (Tamaño de
la población) = 100, pC (Probabilidad de cruza) = 90%, pM (Probabilidad de mutación) = 15%.
Utilizando estos parámetros se obtuvo una solución cercana a la optima para 4 agentes
obteniendo un recorrido de 1616 y para 5 agentes obteniendo un recorrido de 1539.

Palabras Clave: Algoritmo genético, VRP, Problema de ruteo vehicular, lenguaje Python, agentes.

pág. 1
 IMPLEMENTATION OF A GENETIC ALGORITHM FOR SOLUTION TO THE VEHICLE
ROUTING PROBLEM (VRP)

ABSTRACT

The objective of this article is to implement a modified genetic algorithm to solve the vehicle
routing problem (VRP), using as a basis the previous studies of Dr. Miguel Jiménez Carrión,
detailed in his book “Genetic algorithms from operations research”. . The algorithm was
developed in Python language, using Excel as a support resource to read an already generated
matrix that represents the distances between cities. The VRP is known for its computational
complexity due to the large number of restrictions it presents as it is made up of several TSPs,
which has motivated the development of various stochastic algorithms. Genetic algorithms, in
particular, have shown to be a good approach to obtain feasible and, in some cases, optimal
solutions for this type of problems. The algorithm is analyzed based on the following
parameters: TPo (Population size) = 100, pC (Probability of crossover) = 90%, pM (Probability
of mutation) = 15%. Using these parameters, an optimal solution was obtained for 4 agents and
5 agents.

Key Words: Genetic algorithm, VRP, Vehicle routing problem, Python language, agents.

pág. 2
 1. INTRODUCCIÓN
En el campo de la investigación de operaciones hay múltiples problemas aplicativos al mundo
empresarial e industrial, uno de ellos es el problema de ruteo de vehículos por sus siglas en
inglés (VRP), la planificación de rutas para vehículos que recorren un determinado número de
ciudades es sumamente compleja puesto que presenta un gran número de posibles soluciones.
En primera instancia para dar soluciones optimas a los problemas que se presentaban día a día
eran los métodos exactos, pero a medida que la complejidad de los problemas era mayores,
surgieron métodos de exploración he implementación de algoritmos genéticos que permiten
optimizar de manera más eficiente y acercarse a la solución óptima del problema (Solarte
Martínez et al., 2015).

El VRP tiene múltiples aplicaciones en casos reales que se observa día a día, claro ejemplo es
la recolección de residuos sólidos, operación de limpieza en las calles de la ciudad; rutas de
buses de transporte público a nivel provincial e interprovincial, rutas de mantenimiento de vías,
servicios públicos, distribución de productos a minoristas etc.

2. ANTECEDENTES
El problema de ruteo de vehículos (VRP) surgió en la década de 1950 con el trabajo de Dantzig
y Ramser sobre la optimización de rutas para camiones cisterna, buscando minimizar costos de
transporte (Ni & Tang, 2023). Las principales contribuciones de Estados Unidos y China en
este campo, en el cual clasifican los modelos y algoritmos de solución del VRP en métodos
exactos, heurísticos, metaheurísticos, hiper-heurísticos y aprendizaje automático. Así mismo se
aborda la evolución histórica desde su origen con el Problema del Agente Viajero (TSP) hasta
las variantes más complejas como el VRP con restricciones de capacidad y ventanas de tiempo.
Además, describen los métodos de solución utilizados, desde algoritmos exactos hasta
metaheurísticas avanzadas, proporcionando un panorama integral de las técnicas aplicadas para
resolver este problemas logísticos esenciales (Pérez Kaligari & Guerrero Rueda, 2015).

La evolución del VRP desde su propuesta original hasta la actualidad ha permitido desarrollar
investigaciones que brindan soluciones de VRP Utilizando principios de selección natural y
evolución para resolver problemas logísticos complejos, demostrando cómo los algoritmos
genéticos pueden reducir costos y mejorar la efectividad operativa en entornos urbanos(Solarte
Martínez et al., 2015). Así mismo también se han desarrollado modelos matemáticos que
minimizan el riesgo de la ruta. Un ejemplo claro es el problema de vehículos que transportan
efectivo mediante tres conceptos clave: evitar rutas largas en los primeros tres movimientos del

pág. 3
vehículo, variar las horas de servicio en días consecutivos y no repetir arcos en días
consecutivos. Se hace uso de un algoritmo genético para resolver el problema, logrando
resultados cercanos a la solución óptima con una diferencia promedio del 1.09%. Este enfoque
es innovador en la incorporación de nuevas relaciones (Shafiekhani et al., 2024).

El modelo de ruteo de vehículos (VRP, por sus siglas en inglés: Vehicle Routing Problem) es
un problema clásico de la investigación de operaciones y la logística. Consiste en determinar
las rutas óptimas que deben seguir un conjunto de vehículos para entregar productos o servicios
a un conjunto de clientes, minimizando algún criterio, como el costo total, la distancia total
recorrida, o el tiempo total de viaje.

Para la resolución de problemas VPR, se han abordado numerosas técnicas, que podemos
clasificar en tres grandes categorías: métodos exactos, heurísticas y metaheurísticas. (Moratilla
et al., 2014)

El método de ruteo de vehículos puede dar solución a problemas como ruteo de vehículos como
alternativa de transporte: UMNG sede campus. Haciendo uso de herramientas software,
principios de programación matemática y procesos heurísticos, se hace seguimiento a una
metodología, iniciando con un proceso de recolección de información y caracterización de
variables, seguido por el diagnóstico del escenario. Posteriormente, se implementa un modelo
de ruteo hacia la sede, validado y verificado por medio de comparaciones en la simulación del
sistema real. (Enciso Caicedo et al., 2018). Otro ejemplo puede ser el ruteo de vehículos con
componentes estocásticos en demanda, tiempos de entrega y servicios para productos
perecederos. (Gonzalez-L et al., 2015).

La reducción del espacio de solución en el problema de planeamiento de redes de transmisión

se puede lograr mediante técnicas heurísticas basadas en métodos de programación lineal entera
(PLE) y programación no lineal entera (PNLE) para la identificación de variables principales.
El desempeño de estas técnicas es superior al de técnicas heurísticas convencionales que
utilizan modelos relajados que eliminan la condición entera de las variables de decisión. Sin
embargo, estas técnicas pueden conllevar un ligero aumento del tiempo computacional en
sistemas de prueba de tamaño y dificultad baja y media.(Vargas et al., 2013)

El problema del ruteo de vehículos (VRP) implica una gran complejidad matemática para
resolverlo. Esto dificulta su uso en organizaciones de tamaño pequeño y mediano, pues es
necesario que inviertan para contar con software especializado y personal capacitado. Un
algoritmo para obtener una solución factible al problema de VRP, llamado Método de Centros

pág. 4
de Masa (MCM). Este método es de fácil ejecución y su desempeño difiere poco de las
soluciones finales generadas por algoritmos comerciales. (Inge Cuc, 2013)

Los métodos de búsqueda local resuelven problemas complejos de optimización combinatoria.

El algoritmo metaheurístico basado en una búsqueda tabú granular para la solución del
problema de ruteo de vehículos (VRP) con flota heterogénea, busca determinar las rutas a ser
construidas para satisfacer las demandas de los clientes, considerando una flota de vehículos
con capacidad y costos no homogéneos. El algoritmo acepta soluciones infactibles penalizadas
por un factor dinámico que se ajusta durante la búsqueda.(Universidad del Valle et al., 2014)

En los últimos años, ha habido grandes progresos en los algoritmos y los métodos empleados
para solucionar el Problema de Ruteo de Vehículos (VRP). Convencionalmente se han
empleado técnicas heurísticas y metaheurísticas, incluido el algoritmo de Clarke-Wright,
búsquedas locales y algoritmos genéticos (Mauricio Alberto Mora Castellanos et al., 2023). A
pesar de esto, se han introducido enfoques innovadores como el uso de Cross-Docking
(González-La Rotta & Becerra-Fernández, 2017), para mejorar la eficiencia y eficacia de la
resolución de estos complejos problemas.

Asimismo, las técnicas metaheurísticas han experimentado avances significativos, impulsando

su efectividad y aplicabilidad en la resolución de VRP (Orrego Cardozo et al., 2016), dentro de
estas metodologías, el GRASP (Greedy Randomized Adaptive Search Procedure) es una técnica
ampliamente utilizada que se rige por un proceso de construcción de soluciones iniciales de
forma iterativa, haciendo uso de un enfoque avaricioso y aleatorio (Arias-Osorio & Fernando
Niño-Sáenz, 2017).

La resolución del Problema de Ruteo de Vehículos (VRP) ha evolucionado significativamente

con el desarrollo de métodos avanzados. Siendo así, otro de los estudios innovadores el cual se
aplicó la técnica del algoritmo de p-mediana para optimizar la distancia recorrida en una
empresa postal (Sánchez & Gutiérrez, 2022), superando notablemente los métodos
tradicionales. Además el que implementó el heurístico de Clarke Wright para refinar el ruteo de
vehículos en supermercados, logrando una reducción de costos operativos mediante técnicas
avanzadas de optimización (Prato Torres et al., 2015). Y el que introdujo una estrategia
innovadora al reemplazar vehículos blindados con motocicletas para el transporte de valores,
utilizando un modelo de programación lineal entera para diseñar rutas óptimas que garantizan
eficiencia y seguridad en la distribución (CASTELLANOS BALLESTEROS & SÁNCHEZ
CAIMÁN, 2015).

pág. 5
Esta investigación, realizada por Navarro Castro, Giancarlos (2021), se centra en la aplicación
de dos metaheurísticas, los Algoritmos Inspirados en Colonias de Hormigas (ACO) y
Algoritmos Genéticos (AG), para optimizar la entrega de productos en situaciones de
emergencia. El estudio utiliza datos de la ciudad de Piura para simular escenarios de entrega
bajo condiciones de emergencia. A través de la implementación de estas metaheurísticas, se
busca mejorar la eficiencia en la distribución de suministros, crucial en situaciones de crisis
donde la rapidez y precisión son vitales.

La tesis de Gerónimo Sanes, Alan Pierre (2021), aborda la optimización de la distribución de

productos y la recolección de residuos en redes logísticas urbanas mediante el uso de un modelo
de programación entera binaria y la metaheurística GRASP (Greedy Randomized Adaptive
Search Procedure). La investigación surge de la necesidad de gestionar de manera eficiente la
creciente demanda de servicios logísticos en áreas urbanas densamente pobladas.

Suarez Flores, Erika Marilú (2021), realizó un estudio sobre la aplicación de la heurística de
Clarke and Wright para optimizar el ruteo de vehículos en una empresa de transporte de
productos químicos y materiales peligrosos. Este trabajo se enfoca en mejorar la eficiencia de
las rutas, reduciendo costos y tiempo de planificación, al mismo tiempo que se asegura el
cumplimiento de las restricciones de seguridad y capacidad.

3. METODOLOGÍA
3.1. DESCRIPCIÓN DE LA IMPLEMENTACIÓN DEL ALGORITMO
GENÉTICO
El código modelo implementa un algoritmo genético para resolver problemas de ruteo de
vehículos donde un número determinado de agentes visitará 100 ciudades, cada agente saldrá
desde una misma ciudad a la cual llamaremos depósito y las ciudades de cada subconjunto debe
ser visitada una única vez. El código se ejecuta mediante los siguientes pasos: se genera una
población inicial aleatoria de posibles soluciones, donde cada individuo representa una
secuencia de ciudades a visitar. Luego, se evalúa el "fitness" de cada individuo basado en la
distancia total recorrida. A continuación, se seleccionan los mejores individuos utilizando un
método de ruleta, y se cruzan para generar una nueva población. Además, se aplica mutación
para mantener la diversidad genética. Finalmente, se reemplaza al peor individuo por el mejor
de la nueva generación, y se repite este proceso por un número determinado de generaciones
hasta encontrar la solución cercana a la óptima u óptima, teniendo en cuenta que se busca
obtener la menor distancia total que m agentes en recorren un subconjunto(k) número de
ciudades.

[Link]ÓN DEL PROBLEMA

pág. 6
Según el libro (Jimenes Carrrión, M) Consiste básicamente en visitar un conjunto de N ciudades
(𝐶1 , 𝐶2 , 𝐶3 , … 𝐶𝑁 ) utilizando una flota de “m” vehículos que parten desde un único depósito.
Cada ciudad debe ser visitada exactamente una vez por uno de los vehículos, y todos deben
regresar al depósito de origen.
El problema de Ruteo de Vehículos (VRP) en este caso específico involucra 100 ciudades
(nodos), entre las cuales se tiene un conjunto de distancias asimétricas que representan el tiempo
necesario para desplazarse de una ciudad a otra. El objetivo principal es determinar el valor
óptimo de "m", es decir, el número mínimo de vehículos necesarios para cumplir con la
condición de que cada ciudad sea visitada dentro de un tiempo máximo determinado, sin que
se exceda dicho umbral. (Miguel, págs. 133-178)

La relación que hay entre una ciudad y otra está representada en una matriz asimétrica:

𝑡𝑖𝑗 → Representa la distancia que demanda trasladarse de la ciudad “i” a la

ciudad “j”
𝑡𝑗𝑖 → Representa la distancia que demanda trasladarse de la ciudad “j” a la
ciudad
“i”
Debido a la naturaleza asimétrica de las distancias (es decir, 𝑡𝑖𝑗 ≠ 𝑡𝑗𝑖 ), y la necesidad de cumplir
con restricciones de tiempo para cada ruta, el problema presenta una complejidad adicional. El
desafío radica en asignar rutas a cada vehículo de manera que, en conjunto, todos los nodos
sean visitados sin superar el tiempo máximo permitido, lo que añade un nivel significativo de
dificultad al problema.

Tabla 1: Matriz asimétrica de las distancias entre ciudades

pág. 7
 CIUDAD 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
0 0 95 8 83 94 96 55 11 58 79 68 84 51 22 11 70 57 84 16 85 18 92 60 79 74 55 10 64 43 26 45 72 30 54 46 16 9 41 19 13 54 74 48 59 11 93 60 75 18 36 59 49 75 70 81 81 99 74 51 55 60 68 18 63 29 64 18 75 37 22 20 80 31 90 73 37 9 77 69 22 72 74 71 80 93 25 79 88 46 57 77 85 55 59 80 30 61 7 87 49
1 68 0 35 48 82 61 44 26 15 27 39 65 71 28 53 56 7 93 69 14 66 70 64 32 88 51 59 44 28 37 69 65 92 89 60 44 38 83 84 9 64 44 52 20 12 7 55 25 72 59 40 98 77 12 44 14 21 16 52 49 9 40 44 88 26 12 44 45 76 56 70 7 39 69 90 93 5 50 68 27 34 50 8 35 18 35 6 46 9 25 11 19 79 47 64 85 81 89 58 29
2 6 49 0 18 90 76 54 19 6 32 57 17 75 74 74 55 68 85 38 78 21 15 30 75 96 20 46 29 63 39 42 60 99 33 73 97 81 26 63 15 12 64 36 62 67 69 70 60 77 76 65 12 43 94 66 59 90 55 33 56 49 53 74 87 59 12 23 44 57 15 50 52 12 73 48 41 63 72 63 78 99 13 50 38 86 57 22 27 21 8 89 51 73 16 45 67 66 66 61 26
3 27 31 23 0 29 90 92 54 6 11 17 23 45 30 21 97 57 34 69 68 93 35 50 14 10 29 12 71 85 42 23 5 23 85 30 12 46 10 91 13 87 32 51 79 29 17 54 98 31 7 28 14 14 70 14 60 82 75 27 54 5 12 5 8 20 44 48 82 29 84 85 70 26 26 18 6 44 81 51 26 21 65 76 38 30 12 7 53 46 36 10 39 85 94 81 68 68 30 98 79
4 41 25 22 28 0 76 16 60 28 58 18 63 19 79 59 28 85 62 95 48 15 21 66 93 29 11 36 56 71 83 55 87 49 48 14 72 61 91 69 57 75 61 34 12 67 86 80 70 63 54 34 99 7 36 82 32 83 53 67 11 13 27 95 57 43 17 23 19 50 75 67 97 61 19 98 38 14 32 63 33 91 64 38 7 10 55 79 50 16 85 87 78 77 40 39 76 27 39 40 48
5 73 36 45 46 51 0 42 76 46 64 56 10 69 27 48 61 64 52 91 18 13 71 22 79 16 17 47 48 47 71 39 43 7 43 57 72 51 77 10 78 70 47 89 84 23 65 55 50 75 66 42 10 80 37 38 35 7 67 26 80 78 17 32 41 65 38 80 78 87 53 44 99 94 87 78 92 9 29 98 74 57 61 14 47 56 41 60 44 34 21 91 80 83 17 97 16 35 50 66 69
6 45 13 7 22 8 62 0 20 16 17 50 45 26 73 61 87 38 91 96 43 99 91 82 88 51 62 96 62 51 14 32 85 50 23 29 35 31 87 42 70 54 87 83 13 22 15 77 60 10 20 96 72 31 88 32 93 79 78 21 25 88 59 15 45 68 70 24 91 60 78 62 96 89 19 12 36 24 38 45 72 91 64 10 31 80 43 46 15 46 84 65 78 72 32 80 80 42 80 62 18
7 70 74 54 64 31 30 50 0 72 12 77 91 86 18 11 25 22 46 25 58 24 74 29 67 88 11 49 34 18 37 79 87 38 78 41 80 84 45 17 15 42 66 13 90 74 68 6 87 9 6 90 78 49 8 45 93 61 45 48 79 97 71 61 35 61 73 62 61 44 19 99 30 83 97 47 11 25 9 40 33 38 53 37 38 8 39 69 22 47 90 89 83 79 32 22 91 67 97 95 18
8 54 33 8 72 64 45 71 58 0 94 61 44 87 25 84 53 43 74 55 55 48 18 16 88 75 99 90 69 56 38 53 27 23 21 43 60 64 89 40 94 86 90 5 28 50 10 28 62 19 17 87 87 16 41 97 12 70 6 51 95 79 68 65 48 40 95 54 26 6 95 57 15 36 67 94 67 57 55 32 64 95 6 94 51 44 94 68 88 87 23 97 23 86 99 78 97 97 63 75 53
9 48 18 48 41 65 66 37 27 7 0 46 23 59 64 9 51 81 32 59 87 38 20 28 6 51 46 76 96 70 41 74 60 18 83 31 11 24 70 45 44 97 48 69 97 75 72 52 93 51 62 77 79 44 39 38 87 43 78 59 82 59 75 69 19 72 73 41 66 83 29 40 96 64 49 76 13 8 56 63 80 65 30 50 26 32 50 82 35 50 64 60 40 94 25 67 51 17 36 41 15
10 43 74 7 45 27 52 17 16 54 12 0 96 50 73 33 65 81 19 35 95 79 16 96 31 86 30 43 87 34 91 39 53 72 63 68 88 53 62 73 18 46 36 6 42 12 92 60 25 36 75 59 13 95 85 70 6 99 50 74 88 39 62 11 13 29 40 18 93 73 68 96 26 20 56 67 69 77 79 89 50 10 38 47 77 44 92 64 17 53 41 87 16 87 35 21 74 38 52 61 91
11 60 17 74 65 60 6 33 66 62 31 65 0 9 67 78 32 48 59 70 81 85 23 71 56 20 23 34 19 78 58 24 38 12 18 78 47 86 13 64 83 90 41 11 49 43 37 60 42 55 15 43 26 92 19 93 67 19 77 31 96 28 60 77 53 21 11 44 25 41 97 47 14 30 94 80 74 66 90 60 80 37 62 66 55 59 21 8 29 59 53 48 87 96 87 89 38 40 37 95 29
12 29 51 47 7 17 58 26 27 38 12 28 74 0 36 97 61 87 70 22 8 39 43 12 95 39 56 12 26 54 15 44 39 9 58 68 20 26 36 26 9 92 32 79 70 14 30 92 49 30 55 52 94 9 35 27 41 60 34 18 29 21 20 14 76 65 93 31 28 89 71 72 82 46 94 74 77 84 16 54 11 28 17 60 91 89 83 28 24 60 55 20 9 23 52 81 27 23 48 7 78
13 57 17 13 67 59 65 43 41 39 33 53 52 35 0 27 33 54 64 71 11 75 44 51 98 22 27 31 70 53 22 22 20 67 49 30 23 28 87 13 90 12 28 15 30 69 6 29 56 78 69 47 86 80 37 99 66 40 21 25 21 82 90 83 8 71 38 58 67 28 93 58 79 89 16 93 6 79 95 27 27 32 60 97 22 46 74 18 93 51 20 64 40 44 30 81 73 39 50 8 8
14 68 72 65 44 58 48 55 18 14 19 37 59 14 66 0 39 55 81 98 60 31 84 77 21 59 62 78 91 80 21 16 55 20 34 50 26 22 5 62 17 27 91 85 82 99 94 63 86 99 67 91 27 12 85 80 90 90 6 91 30 50 83 6 69 65 71 41 95 56 27 44 85 21 72 11 61 84 67 41 37 69 32 97 73 22 97 58 34 65 88 42 18 67 33 83 22 73 28 81 88
15 66 63 15 42 34 9 23 68 24 23 43 27 45 46 25 0 6 22 25 68 62 91 31 99 25 11 93 96 24 26 17 20 44 37 97 28 67 22 36 49 20 85 24 20 18 29 38 24 28 67 73 60 12 18 94 86 70 14 88 67 16 77 12 24 82 73 32 78 24 39 97 28 19 41 81 58 50 38 18 29 51 18 55 91 41 48 31 74 87 35 83 96 59 62 40 48 61 51 33 15
16 50 12 21 32 59 50 25 16 39 30 18 65 10 60 46 34 0 68 82 44 30 79 68 49 10 61 74 82 60 62 39 77 47 30 73 32 79 50 36 59 83 15 51 54 41 47 88 28 36 78 97 54 18 81 62 41 37 24 42 53 11 14 35 84 52 57 22 97 45 15 15 74 69 27 9 65 73 88 32 43 8 92 92 50 73 72 45 50 94 56 8 74 46 20 38 79 9 29 81 88
17 25 62 49 71 39 74 18 11 6 70 44 61 22 53 17 60 23 0 59 63 55 67 32 34 80 68 98 50 41 76 79 72 46 96 26 91 34 46 83 81 10 88 59 50 92 13 38 80 87 46 58 5 12 39 53 17 42 88 98 58 88 17 74 52 36 76 91 50 70 55 68 86 67 79 62 37 16 95 29 44 64 6 64 94 99 9 67 62 71 69 76 42 47 68 31 18 64 34 9 99
18 74 23 46 60 6 44 7 42 55 28 45 75 15 11 42 75 39 44 0 15 80 68 61 7 22 12 95 32 28 67 44 15 36 92 6 66 58 12 38 56 44 54 18 40 23 42 67 19 53 99 28 87 82 38 84 95 92 70 47 81 44 92 67 30 28 25 18 16 21 39 18 62 32 44 96 94 55 16 55 79 18 43 81 74 24 93 38 84 16 56 80 18 16 79 39 11 79 45 36 11
19 70 56 18 14 35 10 36 49 17 46 64 17 26 67 41 64 41 15 30 0 43 21 41 15 13 70 14 82 10 59 22 85 16 39 97 73 59 93 11 8 66 6 72 96 8 62 42 79 37 60 31 36 70 18 77 53 16 32 91 81 16 40 8 82 18 58 15 69 14 40 35 63 83 16 59 47 67 49 96 8 85 89 33 86 17 26 59 48 18 14 53 94 6 51 7 55 83 22 71 96
20 73 7 48 27 45 35 68 24 65 12 60 9 27 12 65 72 25 42 64 37 0 77 66 18 14 31 85 13 52 12 10 42 20 16 54 80 58 31 39 72 80 89 7 77 9 30 77 34 9 19 22 86 61 26 72 69 17 68 13 23 15 59 90 56 60 52 10 14 71 97 32 88 20 94 67 22 77 37 11 93 88 56 73 35 94 85 69 22 99 12 36 61 17 92 85 37 8 61 79 41
21 54 16 42 62 14 31 15 72 71 58 29 40 59 9 45 43 43 31 62 63 69 0 26 68 91 76 61 76 26 12 86 88 27 77 58 62 55 82 70 74 90 34 25 96 83 88 53 33 7 30 95 56 85 78 39 88 92 79 51 32 58 30 56 12 28 29 71 42 24 39 60 71 83 33 78 34 28 36 33 83 78 81 17 74 46 68 71 79 47 92 44 63 74 20 16 19 46 9 59 20
22 10 15 35 19 14 67 69 74 60 46 55 36 43 42 26 68 41 57 8 56 71 43 0 99 81 61 18 76 8 19 93 13 37 59 92 64 98 80 15 98 10 50 7 28 94 49 33 42 90 34 21 90 51 77 90 24 13 32 42 20 44 56 59 60 9 89 95 79 82 90 21 96 50 85 40 84 8 24 84 7 37 19 42 62 62 10 96 65 83 6 9 64 40 34 23 7 43 92 59 71
23 75 9 52 42 61 40 15 73 66 49 16 74 72 70 14 27 59 7 58 12 45 20 37 0 6 21 56 63 68 45 47 34 18 29 73 28 70 18 19 87 9 88 75 75 85 18 25 97 28 87 49 77 33 88 16 89 56 34 98 24 48 13 62 16 98 53 69 21 6 69 65 45 86 9 17 11 85 87 49 83 73 76 24 55 20 15 58 60 37 70 99 48 39 13 67 24 78 24 88 95
24 30 41 31 17 48 48 42 17 20 56 62 62 25 71 23 16 28 67 38 7 58 21 25 41 0 42 97 11 40 94 30 22 76 65 57 96 15 85 11 61 89 90 85 92 16 59 31 8 90 61 57 69 91 20 26 85 92 42 65 25 30 89 50 67 38 24 31 76 21 36 86 33 80 24 92 78 89 28 49 89 22 81 33 7 95 71 61 78 63 70 36 48 15 97 82 59 51 76 26 36
25 36 31 35 5 28 55 72 71 43 52 74 30 41 15 39 25 36 68 39 67 61 13 42 71 62 0 97 99 92 94 43 92 35 67 87 74 8 32 40 89 14 77 38 22 74 15 21 24 87 90 70 89 65 80 71 9 87 11 48 73 62 99 19 86 59 53 45 73 74 59 90 40 73 76 66 26 41 70 67 53 31 59 43 80 20 72 35 49 50 96 29 30 90 32 10 73 81 23 98 72
26 61 31 21 34 8 10 22 51 12 45 25 13 32 39 42 18 35 48 41 61 33 46 51 66 50 23 0 80 14 85 68 57 40 36 73 38 41 63 37 30 34 13 45 38 21 83 52 15 35 16 16 97 91 95 45 87 49 56 67 66 34 76 63 62 13 70 23 7 33 21 84 62 76 23 15 8 13 48 16 44 32 89 9 83 17 14 70 81 76 89 89 84 16 81 13 86 51 57 78 75
27 65 65 15 57 54 21 11 42 41 42 66 33 11 52 54 26 52 20 42 6 47 65 49 58 51 70 6 0 62 71 98 27 18 67 62 51 30 66 84 20 71 12 92 65 60 71 33 43 8 15 16 54 60 23 72 16 78 71 19 90 59 70 70 69 88 11 31 81 12 9 13 74 51 66 96 50 90 32 5 20 9 19 94 47 13 78 80 14 23 54 25 48 92 11 12 93 85 94 97 54
28 70 66 39 62 47 37 37 31 24 69 30 60 21 68 14 33 52 10 64 64 16 49 18 39 17 61 8 74 0 35 38 49 19 58 45 7 83 10 77 81 50 60 55 46 49 93 73 25 78 34 64 65 46 87 44 92 10 30 55 50 38 10 32 45 59 30 34 11 15 88 10 45 86 37 32 75 84 8 66 93 66 79 10 17 94 44 31 20 97 19 44 11 10 24 41 60 13 26 47 68
29 39 23 53 69 57 67 35 22 50 10 19 68 71 32 8 28 48 60 41 48 35 13 20 74 34 46 19 27 30 0 62 16 87 29 50 38 39 47 81 57 10 38 7 16 43 85 97 77 13 88 53 9 48 97 89 82 13 73 40 81 27 35 63 9 42 6 30 42 74 66 45 7 64 18 16 96 21 97 86 58 65 74 14 99 8 58 74 76 55 70 63 22 10 92 12 91 68 18 38 48
30 52 55 74 32 10 7 44 30 24 69 69 24 10 56 31 9 72 49 16 53 41 75 67 48 73 6 7 29 57 12 0 34 22 73 24 24 74 90 38 86 90 12 68 80 82 11 7 52 46 41 83 90 9 76 63 90 75 63 47 82 97 61 53 96 7 7 55 14 48 45 37 89 73 11 37 53 57 39 6 11 56 49 42 16 60 75 65 21 45 28 47 24 17 24 62 16 60 61 53 34
31 43 47 52 36 13 74 8 74 40 63 69 52 6 72 61 10 74 29 38 19 23 49 37 68 53 42 46 37 51 38 34 0 96 33 99 99 31 92 85 42 25 31 83 65 92 72 60 10 98 92 6 10 96 47 70 65 84 14 44 87 59 58 68 44 57 84 18 99 20 77 27 91 22 51 56 57 41 6 39 87 99 64 25 92 22 51 34 35 58 11 8 76 72 67 54 52 67 88 14 92
32 39 20 62 13 31 38 29 71 35 13 31 55 48 63 23 45 25 65 75 37 54 33 54 41 39 22 16 56 17 15 24 25 0 37 33 65 47 93 86 89 77 15 26 24 32 16 49 63 36 19 53 86 80 87 63 87 67 89 85 35 50 29 65 8 89 99 24 59 15 58 16 70 43 41 76 85 69 36 86 71 85 26 96 64 48 38 95 21 15 93 55 64 96 68 73 49 34 23 42 85
33 64 62 72 30 43 33 14 72 13 41 5 75 11 68 17 64 57 17 22 5 51 30 30 49 15 29 50 6 61 35 58 10 72 0 90 59 7 72 63 59 64 50 48 87 59 5 30 81 75 15 39 7 27 67 99 6 86 18 90 60 63 12 74 42 26 60 63 42 59 88 65 42 34 73 35 54 25 96 17 72 84 9 7 31 88 49 88 35 80 36 9 29 24 78 81 41 45 59 91 31
34 50 38 28 61 37 57 43 22 26 56 61 72 69 11 11 73 19 58 62 58 50 35 22 63 71 11 9 22 32 35 62 8 33 37 0 32 63 51 78 50 65 19 85 42 45 27 96 6 9 6 91 26 41 45 10 46 67 67 83 94 93 58 31 56 58 25 52 96 77 40 21 43 12 7 10 96 85 83 51 31 77 69 88 86 39 21 28 74 50 11 64 82 78 86 70 56 29 30 20 29
35 67 48 30 35 25 70 23 55 73 73 21 18 27 6 44 48 17 72 28 50 37 62 67 29 45 26 27 50 71 19 74 65 40 74 9 0 88 52 85 92 86 75 49 11 77 68 94 72 19 60 44 18 10 15 21 72 48 69 28 38 79 15 85 11 48 98 93 48 31 30 63 21 11 72 74 48 11 43 35 66 48 32 16 64 92 61 11 41 10 44 81 50 91 20 23 55 53 10 79 77
36 71 67 49 36 33 72 58 69 19 7 21 62 39 32 26 46 25 25 33 71 7 40 44 31 6 64 75 47 71 48 43 16 34 17 16 62 0 28 38 84 34 82 17 12 61 60 48 46 60 24 41 43 53 36 75 17 25 10 76 7 64 44 44 18 26 91 12 79 61 99 91 94 87 59 44 82 32 51 92 32 67 12 15 48 86 59 45 18 39 72 71 35 70 20 61 73 96 9 10 29
37 6 48 51 6 68 68 67 45 24 20 14 35 72 70 8 34 7 65 59 70 30 54 39 44 8 40 68 40 74 23 54 13 29 26 12 31 6 0 65 89 66 40 62 16 43 78 61 27 87 29 90 51 41 56 32 51 49 49 45 66 40 44 51 74 55 87 60 34 15 89 29 32 46 63 9 43 59 76 88 74 77 13 73 19 98 99 91 88 43 92 79 98 85 89 17 83 45 6 68 63
38 40 70 8 47 60 53 41 16 13 18 27 39 49 66 47 14 16 6 35 50 49 10 24 11 49 27 37 42 67 24 55 47 59 21 53 66 60 58 0 56 92 47 44 21 65 37 30 75 52 39 29 69 55 24 17 34 56 29 22 48 72 15 80 89 5 13 94 82 75 69 68 44 12 14 59 34 48 76 39 10 24 77 35 70 92 47 78 25 13 82 70 9 49 15 10 58 70 28 48 64
39 72 50 61 16 20 10 6 18 31 61 22 73 28 74 11 73 8 72 34 75 70 52 66 59 36 22 29 33 44 33 40 67 24 6 24 48 10 49 31 0 18 82 83 10 69 66 74 53 69 40 52 43 19 25 69 94 55 75 9 44 30 38 8 71 25 77 34 74 25 55 29 9 55 53 44 27 43 45 13 50 53 34 72 10 52 6 52 78 49 73 81 60 46 49 74 95 92 60 58 49
40 67 8 11 20 26 36 51 66 58 15 16 29 10 36 26 64 36 17 32 33 72 16 69 26 13 57 75 44 24 25 67 40 19 52 39 19 44 60 62 74 0 79 8 39 75 6 74 86 38 29 5 80 40 66 82 12 7 30 96 35 11 64 60 38 38 27 64 69 35 6 41 8 50 84 94 84 90 11 76 74 78 98 14 8 84 38 57 33 90 86 57 76 40 67 84 84 73 87 99 72
41 42 34 36 72 42 53 25 36 41 38 47 32 12 29 46 41 52 59 36 51 68 47 67 28 17 47 52 15 17 67 8 31 31 40 24 36 38 65 14 32 71 0 61 62 10 28 25 54 97 42 5 19 27 20 72 71 62 25 54 70 10 36 58 51 29 84 47 79 15 19 70 14 21 30 34 30 28 29 28 96 81 78 91 24 59 56 67 80 92 86 33 91 48 17 61 56 51 33 77 98
42 37 71 41 42 45 30 70 23 75 71 37 68 61 36 71 7 21 67 48 58 14 10 47 19 42 9 33 72 9 51 35 54 40 73 40 45 27 64 24 57 7 33 0 84 64 86 20 10 27 78 62 70 66 76 58 60 80 93 71 55 48 17 29 78 72 42 56 55 51 48 50 46 10 30 8 14 49 49 76 60 18 90 33 91 35 19 85 55 57 92 73 88 28 72 77 82 16 22 94 22
43 48 27 49 19 16 65 12 43 66 5 35 22 53 30 6 68 12 17 7 7 46 61 68 40 16 24 62 13 62 59 22 7 12 10 35 26 45 15 64 32 25 44 58 0 52 80 26 45 54 22 92 79 78 89 75 76 71 18 69 51 26 42 91 24 22 98 37 72 89 61 11 89 63 71 88 25 12 15 81 25 93 48 56 6 34 73 5 80 32 72 80 39 43 56 76 57 16 20 41 79
44 6 10 56 29 28 22 66 34 33 16 63 8 20 52 17 60 49 48 54 35 71 32 60 45 25 31 74 7 19 39 37 35 15 50 41 48 69 26 15 22 23 67 35 19 0 78 89 51 80 31 25 54 9 90 41 56 72 25 33 92 91 73 71 72 40 41 66 19 88 17 8 24 80 36 12 9 60 33 83 54 29 83 68 71 91 67 79 40 28 95 75 52 5 86 87 76 55 97 87 7
45 35 46 60 16 14 17 19 30 55 25 19 69 11 17 6 74 35 38 33 29 53 54 13 67 11 60 37 17 47 42 55 68 37 16 55 33 54 57 25 16 45 59 58 24 15 0 58 27 52 39 25 34 63 36 49 21 94 73 49 96 71 18 86 20 32 32 24 10 81 46 56 31 62 94 84 32 70 75 57 85 32 84 10 61 35 82 22 47 91 38 75 23 91 68 97 90 38 15 14 54
46 48 28 28 43 54 59 68 36 14 53 33 42 34 49 63 71 53 69 12 61 22 16 40 59 5 54 21 43 8 15 65 26 10 68 64 21 71 47 9 11 15 52 21 45 26 60 0 95 30 7 8 91 98 74 92 5 43 70 93 53 41 50 67 68 65 38 33 21 24 79 15 64 93 95 91 20 7 30 65 79 50 77 77 8 66 77 88 36 73 29 17 60 22 44 75 67 40 18 53 86
47 72 49 73 60 17 45 28 9 70 55 59 60 58 45 6 23 17 60 75 14 18 53 37 74 66 54 33 59 60 69 45 27 40 44 6 65 14 40 40 42 58 57 12 64 8 70 48 0 76 97 33 10 19 86 36 91 80 79 98 80 62 88 70 81 90 59 12 14 98 17 48 44 62 18 42 60 48 9 17 5 71 59 12 19 47 35 43 12 28 23 49 92 62 92 33 43 53 59 20 34
48 53 13 5 59 67 72 51 49 10 48 57 55 68 74 25 30 34 36 73 51 43 37 48 74 50 70 52 40 68 63 57 45 71 50 11 31 23 63 9 30 57 34 54 53 16 33 16 65 0 97 47 52 52 44 16 36 74 36 18 97 63 71 39 27 25 51 49 59 21 14 48 71 27 88 18 6 70 66 70 14 93 21 14 30 92 66 68 7 72 31 56 59 90 66 24 36 23 39 92 44
49 58 50 30 74 71 36 23 72 59 60 73 38 73 11 26 47 6 52 7 42 51 21 38 11 33 30 73 22 6 8 31 50 8 17 42 6 27 73 62 58 31 49 49 34 10 52 67 17 6 0 34 36 31 77 44 6 62 66 76 82 32 98 95 82 94 38 12 46 46 40 17 88 35 29 58 75 37 33 82 43 95 38 77 60 85 42 26 83 39 91 49 7 11 56 75 86 27 48 73 41
50 36 37 51 35 72 71 51 69 13 48 69 40 29 26 11 30 19 16 24 18 69 7 36 53 63 12 70 10 70 24 5 46 29 56 26 75 65 34 29 8 31 43 9 7 36 12 22 22 59 28 0 69 40 24 12 54 44 50 27 49 32 47 41 28 82 16 10 53 64 22 39 43 72 58 53 97 85 88 30 78 21 94 52 31 65 32 64 45 55 63 20 13 94 40 22 64 38 22 86 35
51 67 40 73 25 43 71 6 49 60 70 24 45 18 32 21 43 61 69 16 67 54 21 46 29 40 53 60 42 60 62 29 37 55 57 45 8 33 59 8 45 41 62 14 22 57 72 36 48 23 68 30 0 70 87 37 97 38 26 27 91 57 59 51 57 64 97 98 92 38 82 79 17 48 32 68 84 18 91 61 84 54 12 28 46 24 48 52 11 73 58 94 72 13 28 41 48 27 22 31 93
52 33 47 56 70 5 70 14 50 65 24 63 49 58 10 63 41 36 60 19 19 6 32 53 30 38 65 17 69 19 54 17 46 39 36 30 26 75 12 8 62 26 57 51 13 28 69 24 73 71 20 15 32 0 21 26 69 88 24 94 60 46 32 79 41 16 87 56 31 93 38 82 24 52 56 56 32 47 30 52 40 8 77 78 50 59 26 32 40 97 34 33 96 25 63 88 92 85 26 48 14
53 14 60 51 52 19 53 30 25 13 54 58 33 65 66 53 39 55 55 40 50 56 47 44 16 19 25 56 67 19 35 70 68 10 10 42 66 70 16 74 48 14 75 21 45 61 63 20 31 30 22 34 22 73 0 64 44 67 49 58 21 27 38 67 64 54 98 95 80 63 89 95 8 80 63 14 53 9 34 33 72 58 25 43 98 29 17 74 98 24 93 57 24 26 15 58 46 34 21 47 37
54 27 53 64 18 40 35 11 46 33 71 70 15 64 66 19 46 29 50 52 49 42 70 37 43 51 18 48 46 15 13 43 44 9 20 45 22 45 20 32 72 43 49 45 8 70 21 15 28 29 45 71 53 44 36 0 80 49 70 33 68 9 34 59 87 84 34 94 58 64 17 88 84 96 91 48 30 77 7 79 38 78 52 61 12 10 62 67 37 51 33 39 55 33 74 19 96 55 78 8 46
55 41 21 27 54 28 44 40 29 69 7 34 19 32 41 65 33 63 7 66 38 67 19 24 60 19 63 18 17 70 29 35 25 22 26 14 21 64 69 18 72 34 44 57 62 19 18 55 11 35 71 24 31 64 48 32 0 14 7 65 27 91 80 90 83 81 79 56 11 57 96 86 88 38 67 38 36 41 5 28 8 30 49 92 69 59 37 55 57 37 31 39 5 56 71 48 95 63 43 8 45
56 24 56 49 26 66 58 60 12 39 51 69 13 46 68 34 58 9 41 25 21 54 40 55 5 53 32 38 26 9 57 42 49 25 49 37 21 53 13 75 50 7 61 39 16 68 25 37 27 28 56 9 37 21 22 43 17 0 19 78 33 96 43 29 58 22 59 88 7 29 54 39 36 18 12 30 86 40 54 48 22 56 12 64 58 84 46 84 50 54 28 92 15 44 59 14 82 48 50 38 72
57 11 24 34 65 53 60 15 26 17 70 47 36 29 74 17 52 61 13 21 43 29 65 54 20 48 50 40 7 37 26 10 70 41 44 66 6 53 40 65 7 50 15 7 65 27 66 68 7 33 73 72 18 65 13 24 51 34 0 33 6 93 55 50 33 78 51 96 17 95 77 29 45 5 78 31 52 65 9 91 48 32 65 54 73 60 75 41 59 85 14 28 62 66 53 81 28 23 43 27 27
58 5 68 65 47 33 59 20 53 64 33 6 48 11 55 59 16 9 72 35 47 26 11 60 23 42 30 7 69 8 60 24 35 29 49 5 15 43 70 45 33 68 6 58 12 26 71 20 13 59 9 74 66 7 37 5 60 65 41 0 12 13 78 77 18 43 52 97 98 61 57 67 27 37 80 25 45 21 83 63 56 91 46 96 56 28 14 90 83 22 53 19 77 56 12 7 19 51 42 88 76
59 60 74 52 18 67 32 50 66 46 26 58 35 6 7 46 15 65 40 39 20 58 60 12 21 70 46 60 49 45 58 19 24 33 60 59 70 15 27 17 56 11 47 64 54 37 9 41 23 10 58 51 55 54 66 7 60 53 22 13 0 73 94 49 85 62 16 65 71 38 95 45 38 20 40 60 71 70 64 9 74 56 81 49 6 78 34 69 19 44 40 30 41 91 58 94 97 70 30 24 83
60 45 73 61 65 27 64 8 50 62 45 19 73 59 19 43 44 55 59 44 34 49 64 25 24 29 6 74 17 10 31 41 68 73 6 65 42 42 47 54 65 17 57 61 75 52 48 46 61 56 32 50 30 35 57 17 46 55 33 42 49 0 69 62 66 80 82 58 56 5 96 92 22 10 45 39 69 84 49 38 85 83 80 72 69 58 13 12 88 20 49 44 40 81 6 56 76 32 27 59 86
61 59 11 14 11 16 54 44 27 67 7 32 19 9 7 7 46 8 75 34 69 74 17 42 60 24 16 62 37 11 36 59 26 64 70 32 28 57 32 54 56 22 74 22 24 47 61 44 70 25 24 54 23 44 57 58 6 72 72 29 43 58 0 14 67 42 95 91 94 54 13 47 84 86 36 64 28 41 9 82 39 28 69 39 29 35 30 6 32 67 91 54 69 9 32 11 95 47 19 79 50
62 17 6 63 56 13 9 54 17 19 56 67 25 48 59 10 33 19 54 66 64 69 24 22 38 32 9 11 15 31 65 51 21 23 21 11 13 47 6 72 56 44 63 53 74 37 42 11 27 24 58 68 18 11 34 21 45 49 17 10 37 62 72 0 34 77 73 50 71 9 36 50 62 12 48 57 11 52 43 9 10 77 24 88 6 67 12 13 35 80 94 27 82 15 95 99 35 38 91 63 10
63 65 31 23 41 25 26 28 8 25 34 28 48 43 67 15 18 56 12 69 14 12 8 46 52 67 62 28 38 63 21 10 8 55 17 8 28 61 19 21 13 33 6 65 48 29 71 71 70 35 37 59 42 7 54 32 60 40 67 11 39 55 71 70 0 41 24 16 85 26 72 71 55 96 62 44 47 28 73 46 45 18 30 19 40 72 27 63 81 47 98 19 31 81 70 73 94 70 86 55 9
64 21 41 23 46 24 61 55 37 31 46 58 10 66 70 13 72 41 37 17 34 70 58 33 75 13 73 74 7 74 22 18 11 64 20 71 43 65 46 27 6 48 41 7 66 45 22 69 59 47 37 39 15 36 69 30 51 22 66 61 58 7 45 21 17 0 58 30 6 43 27 43 80 93 29 50 19 56 40 11 63 12 32 62 46 91 19 84 9 56 12 38 61 6 64 10 45 49 33 68 62
65 24 26 44 24 69 11 25 43 21 52 19 54 14 18 25 42 25 49 41 66 49 30 33 24 64 53 38 33 68 23 56 42 43 50 23 14 57 62 48 24 25 46 30 19 17 19 47 58 19 60 37 72 35 64 44 36 54 61 42 6 10 35 43 11 34 0 81 88 33 79 67 64 74 22 88 34 53 72 85 77 9 73 40 19 90 59 24 46 44 27 58 95 12 76 63 85 14 74 98 59
66 64 36 41 32 74 31 30 24 48 19 67 28 65 72 40 67 74 72 70 65 66 24 65 14 44 22 27 12 56 72 22 18 19 62 73 30 36 70 55 43 8 54 10 20 22 26 43 66 35 17 7 42 49 39 27 17 74 57 43 29 27 15 61 48 45 18 0 31 9 82 50 18 50 13 15 52 82 34 67 82 64 27 45 53 34 36 32 47 58 28 21 49 94 37 64 84 36 24 27 80
67 51 64 23 50 69 47 69 30 28 70 17 26 50 38 57 47 12 39 9 25 73 34 63 60 8 24 44 33 13 25 72 64 40 24 44 55 42 20 14 73 9 55 19 40 70 43 47 44 42 12 68 27 22 68 70 26 75 16 25 73 55 16 65 14 62 66 23 0 84 33 85 31 56 17 42 41 45 31 81 42 58 57 72 12 51 13 93 31 69 81 98 47 11 8 61 13 56 84 23 32
68 26 66 33 6 30 9 38 53 60 42 11 56 12 66 69 72 54 58 55 36 33 29 70 10 66 61 14 70 18 62 41 69 28 11 37 18 50 65 69 51 31 29 8 40 17 26 48 52 45 41 42 32 38 22 29 48 54 61 57 47 37 6 11 31 63 53 63 18 0 58 32 67 82 43 35 63 5 24 10 25 77 17 6 44 86 35 57 90 65 40 41 59 52 83 5 98 47 70 30 94
69 23 49 24 21 23 54 24 47 52 18 70 66 55 66 22 20 63 69 57 35 23 32 74 39 38 57 7 70 59 26 73 41 50 63 32 47 33 70 67 53 47 48 49 69 43 61 55 46 64 60 64 49 65 57 51 12 18 22 30 55 20 59 16 28 47 18 59 35 59 0 24 27 93 11 51 89 72 79 11 12 24 96 73 56 28 85 72 41 89 75 27 56 87 59 93 29 17 33 46 62
70 74 48 60 51 56 28 48 6 13 11 41 16 51 56 10 74 43 65 55 34 11 30 22 68 23 65 34 68 15 22 26 31 40 19 69 27 19 50 51 20 58 25 60 48 64 11 75 42 59 59 63 5 72 29 22 48 41 43 11 71 51 34 45 11 22 57 64 15 25 47 0 76 46 37 80 28 28 9 88 48 38 42 5 31 30 58 41 59 34 49 84 66 17 24 30 77 27 58 14 67
71 34 23 35 13 67 33 62 34 23 61 67 50 62 5 50 46 65 55 27 38 18 22 70 31 51 12 56 61 46 32 60 11 30 29 33 7 65 67 49 24 71 9 64 65 9 41 13 56 47 11 63 19 43 21 13 40 61 43 31 22 66 25 59 69 22 62 57 33 68 17 40 0 88 77 96 19 37 87 97 30 54 52 86 24 91 43 69 69 53 64 70 50 25 12 85 97 43 95 34 63
72 38 25 38 51 27 26 32 10 29 74 44 30 59 8 11 13 16 49 51 56 73 72 14 65 9 59 75 70 18 60 67 47 39 23 10 29 75 38 72 65 13 18 47 49 18 20 20 32 66 65 47 51 61 38 59 20 70 67 26 47 16 72 74 48 55 10 18 63 60 49 38 11 0 48 22 88 11 18 83 32 28 62 22 65 75 51 73 38 28 38 75 56 9 28 87 56 49 17 57 38
73 30 71 7 17 6 72 23 73 56 6 56 73 38 9 73 21 6 70 46 73 32 65 52 11 31 73 29 44 6 60 20 7 17 55 70 26 68 42 51 61 9 71 44 12 60 6 29 33 71 55 54 9 54 33 65 9 73 28 8 42 70 14 7 22 41 28 45 14 73 66 71 56 22 0 13 25 61 80 24 29 73 95 77 65 24 15 6 13 33 47 63 63 51 27 26 14 95 34 93 72
74 68 39 20 32 75 42 9 51 13 17 69 73 55 43 75 25 33 8 69 8 33 65 18 59 12 32 52 35 42 64 17 10 64 54 64 20 65 17 58 34 40 58 30 56 30 55 74 22 16 46 32 44 24 50 18 24 19 36 31 41 12 27 66 36 22 65 73 54 44 34 66 74 14 47 0 55 50 59 50 80 87 51 85 28 25 97 63 26 93 69 95 7 33 92 61 41 90 28 41 6
75 12 30 40 51 47 24 71 39 32 66 9 71 60 14 47 6 50 53 15 45 62 25 37 67 54 28 14 13 51 29 6 61 49 41 54 31 41 16 9 51 59 21 56 32 65 64 47 51 55 56 30 38 30 59 69 19 25 39 74 16 6 43 41 74 45 22 22 23 5 8 17 70 67 5 9 0 32 19 75 53 43 51 75 26 7 81 87 92 13 79 64 31 98 45 71 6 16 56 50 45
76 45 25 18 44 41 72 35 26 40 64 71 61 66 19 55 73 68 22 65 74 19 56 16 60 27 36 42 47 16 49 41 33 43 49 62 36 53 21 59 55 51 24 64 41 71 12 16 66 70 11 73 11 31 11 17 23 70 6 61 53 50 24 43 41 37 24 20 11 53 73 23 43 43 27 26 25 0 10 52 95 21 24 48 12 70 27 43 72 53 26 74 72 29 21 69 64 20 55 82 26
77 57 58 35 16 8 35 21 45 32 24 39 20 12 68 61 44 55 29 27 60 43 40 16 16 19 52 74 49 7 7 39 22 51 17 64 56 36 43 23 69 10 6 37 27 70 28 18 43 55 49 52 67 67 72 20 57 14 54 45 18 71 19 43 32 10 16 38 18 6 15 51 45 44 16 72 15 22 0 25 41 57 9 58 29 11 71 77 58 80 21 51 93 48 57 87 39 97 11 96 64
78 62 5 38 52 60 14 70 21 70 24 28 21 15 32 10 17 71 17 35 44 74 45 10 35 46 28 45 64 17 36 65 30 64 51 61 44 62 6 47 42 71 25 34 33 23 44 56 60 33 49 72 29 15 46 69 20 70 26 23 45 27 67 11 13 42 21 29 44 68 38 34 13 35 42 42 5 23 47 0 40 71 81 55 59 89 71 8 68 92 39 56 47 21 86 20 65 82 95 60 46
79 70 26 57 48 19 50 23 71 25 31 59 15 9 33 33 65 33 59 37 14 55 15 9 69 37 31 44 41 42 66 12 16 69 24 12 38 11 62 54 69 40 65 29 34 18 36 21 55 16 57 62 6 71 42 28 31 12 58 25 21 53 7 69 70 59 9 59 19 73 19 14 53 68 74 43 31 51 42 29 0 84 96 48 42 53 52 96 31 72 73 16 60 84 28 83 90 72 5 28 89
80 11 15 10 59 40 55 73 48 26 56 68 75 42 35 22 48 46 47 10 72 62 9 45 58 67 13 45 43 33 12 9 10 30 64 51 68 47 21 12 63 35 48 60 36 73 34 24 44 59 42 56 60 25 66 38 5 28 68 37 64 48 9 60 20 24 27 19 58 23 51 46 35 5 47 38 70 59 51 40 19 0 15 77 21 22 40 76 31 40 88 28 73 14 16 59 78 92 55 91 47
81 47 55 25 55 52 25 70 17 54 18 32 16 60 19 63 11 59 6 35 42 60 55 65 53 55 23 63 69 54 6 45 20 51 21 28 55 60 42 63 17 6 37 66 41 44 70 54 25 34 58 51 17 62 15 42 43 58 18 15 63 43 30 66 18 19 7 9 63 7 73 46 54 13 64 28 61 60 53 56 62 16 0 41 28 14 81 39 45 5 12 85 39 30 22 95 65 8 24 29 20
82 28 51 66 34 5 23 46 8 24 55 54 16 72 23 24 25 74 32 58 40 72 30 39 67 47 54 19 7 23 55 42 44 37 70 38 46 29 54 71 23 18 46 22 21 71 72 43 18 50 36 35 26 8 34 31 61 72 41 20 33 67 18 55 63 37 11 7 28 72 52 16 19 61 51 43 19 6 41 38 15 62 5 0 13 65 35 5 38 85 95 48 51 8 82 80 72 52 41 9 25
83 70 13 35 39 15 28 17 65 28 35 17 29 33 55 28 58 61 16 23 63 75 64 65 51 72 42 62 23 51 12 7 75 48 9 22 17 28 10 31 36 64 36 18 31 20 49 51 69 75 54 43 69 59 68 67 47 50 10 37 12 55 21 29 69 49 6 28 38 5 22 42 43 6 26 61 63 63 60 22 33 15 68 58 0 35 77 41 81 47 48 93 49 41 79 88 25 95 34 60 60
84 49 35 12 67 34 11 23 23 72 41 37 29 38 41 6 14 8 70 34 68 15 12 60 54 17 32 30 64 65 52 9 32 67 64 67 53 26 26 44 63 6 39 66 19 31 29 25 69 46 62 33 33 23 30 38 61 68 39 66 43 33 19 48 65 41 40 66 18 36 70 36 58 22 7 25 9 29 67 72 31 13 44 19 19 0 43 53 79 16 47 28 21 34 35 27 93 55 95 78 83
85 49 13 18 18 24 67 31 71 18 50 32 25 57 66 34 9 46 34 20 58 16 6 39 6 13 62 41 11 68 65 43 34 23 43 30 6 50 20 59 13 62 42 12 42 24 13 51 22 61 71 26 65 69 67 67 15 37 20 61 40 74 10 35 37 29 5 52 19 14 37 39 7 19 22 24 70 20 12 40 73 10 14 16 70 34 0 39 38 51 18 40 32 83 13 80 58 89 22 23 71
86 73 72 66 57 71 47 8 16 56 63 10 21 42 52 18 8 20 68 42 55 61 45 47 67 70 42 62 17 31 65 72 58 46 32 55 62 13 23 16 5 18 30 24 10 15 63 33 19 73 47 61 51 62 63 13 18 35 39 65 43 57 59 72 7 26 52 21 70 60 35 65 10 44 9 72 24 10 63 5 67 37 59 31 24 72 20 0 45 83 41 91 91 29 57 21 51 9 63 44 82
87 30 20 30 32 46 11 17 32 12 44 67 23 29 68 53 39 63 38 75 74 43 26 6 41 40 43 20 23 23 5 61 24 29 49 25 75 63 6 71 61 60 66 24 32 63 45 45 33 44 48 33 64 12 15 11 49 47 38 20 9 55 40 15 26 14 26 39 71 7 47 49 36 47 22 20 52 46 54 53 30 55 49 54 52 22 25 54 0 52 11 82 81 97 87 93 81 81 54 47 84
88 37 35 12 39 45 60 69 75 28 66 44 24 48 44 59 13 54 21 72 13 54 24 50 11 19 47 7 50 49 14 33 50 61 26 58 58 35 45 17 64 50 70 32 46 35 28 25 70 17 26 33 44 16 29 32 35 9 41 44 25 35 63 28 13 21 67 62 53 25 22 21 6 64 5 35 67 7 25 36 31 30 54 67 25 20 69 45 56 0 74 30 16 7 24 47 7 57 37 90 66
89 42 31 7 29 57 18 30 71 34 53 52 37 54 40 54 51 45 15 21 37 21 44 42 33 50 43 69 18 11 27 18 16 43 71 17 60 27 70 22 18 34 50 56 47 16 63 42 72 49 17 42 23 16 55 15 20 65 31 60 48 11 38 33 71 73 23 71 60 71 26 68 32 15 14 56 14 5 49 36 7 57 45 11 23 61 14 16 48 34 0 94 26 8 11 41 41 82 78 42 72
90 47 67 45 45 62 64 35 68 25 39 14 54 15 14 45 13 54 32 9 62 66 46 59 36 56 30 25 21 74 11 10 29 38 34 74 42 54 59 59 41 26 64 46 43 43 10 36 68 63 16 58 31 20 47 65 57 69 14 35 28 56 23 11 38 52 58 60 5 27 18 34 61 37 29 22 21 38 61 34 53 68 32 38 10 69 55 66 28 64 51 0 22 79 31 34 9 66 76 24 49
91 23 68 28 48 6 74 20 30 74 17 44 57 54 15 26 37 18 19 18 8 39 60 19 38 17 73 12 45 62 74 69 45 42 55 36 47 34 15 56 17 11 69 48 53 20 64 17 72 71 28 23 51 36 72 75 65 34 71 24 42 43 48 21 8 11 74 60 49 22 17 14 71 60 71 20 40 38 21 21 21 47 44 18 70 37 50 26 63 65 63 47 0 22 42 8 44 90 31 28 39
92 73 57 27 51 69 27 40 47 34 56 43 57 41 33 14 20 14 59 11 31 48 59 66 30 17 30 10 44 35 5 71 16 64 18 65 45 29 69 64 6 53 20 9 72 9 48 26 46 41 50 42 36 39 33 27 59 30 71 32 11 63 66 13 53 42 62 6 14 38 66 19 57 45 19 75 12 14 37 27 45 26 28 20 59 54 74 34 12 58 50 59 17 0 87 59 44 90 43 90 18
93 44 44 34 65 74 28 70 49 37 72 20 34 34 59 9 33 49 38 60 35 46 51 55 38 11 26 54 15 52 24 47 19 14 65 60 8 8 18 51 19 22 61 13 66 30 17 12 29 21 11 8 47 40 25 33 56 10 66 15 39 49 65 23 57 10 47 22 6 14 33 48 73 57 70 35 69 50 56 54 25 63 60 6 17 10 69 72 62 32 29 48 8 44 0 91 43 98 63 21 28
94 6 40 21 11 17 17 44 31 61 43 55 12 39 54 61 72 34 44 58 49 71 23 72 30 11 56 50 31 71 14 36 35 25 34 69 25 9 62 72 21 60 25 32 44 17 11 33 12 44 20 12 52 33 73 72 49 63 31 30 28 12 56 9 50 12 14 55 38 67 67 31 21 13 14 73 28 48 20 63 55 65 25 17 29 34 57 47 52 44 56 48 20 50 55 0 19 10 33 24 54
95 69 68 52 9 49 8 28 56 50 10 30 28 7 44 6 21 66 22 63 14 57 39 11 53 25 61 28 67 47 28 68 50 64 30 32 23 52 62 15 68 59 58 59 17 27 69 52 41 41 15 40 62 11 68 51 60 59 64 63 47 63 22 39 24 41 40 26 20 49 52 60 58 72 72 53 46 62 18 39 26 42 29 74 67 72 7 54 19 72 6 38 42 68 53 64 0 17 33 34 67
96 19 56 67 44 42 36 69 30 63 59 48 55 62 16 13 43 46 47 14 39 16 9 44 39 68 9 68 23 13 12 64 56 36 21 53 51 39 39 65 7 16 35 37 48 27 51 54 34 18 23 37 22 69 30 56 15 74 43 16 71 62 40 44 57 20 31 28 31 65 28 9 73 61 9 71 34 8 25 29 66 70 19 22 21 55 10 59 53 6 49 54 18 32 51 72 71 0 62 94 96
97 71 68 21 58 35 8 68 29 33 24 24 26 15 10 52 57 53 62 38 71 30 23 43 59 20 10 60 25 47 26 48 16 48 65 36 20 49 12 20 68 60 21 66 63 38 64 69 21 66 37 61 39 34 72 44 49 24 13 17 62 71 13 20 64 49 5 19 52 64 22 21 65 64 16 29 16 15 41 17 70 8 68 27 51 12 30 67 41 49 59 9 59 21 36 37 31 23 0 9 43
98 31 27 54 19 39 62 29 71 44 31 27 55 11 36 33 23 55 52 54 62 53 42 25 52 35 56 43 47 75 56 61 33 45 26 58 32 6 71 75 68 24 35 41 59 74 27 18 66 67 31 23 46 32 20 68 25 6 51 51 68 72 27 72 28 42 8 49 8 54 40 33 39 44 44 30 48 64 69 42 35 35 38 24 35 66 71 67 15 61 25 8 46 41 22 25 63 39 61 0 14
99 34 60 55 59 70 50 6 12 38 69 39 51 17 48 19 74 49 32 72 39 39 6 66 71 70 70 60 8 13 54 62 66 56 43 64 33 39 61 7 73 48 37 25 64 28 51 61 51 33 17 41 70 46 69 50 47 17 35 17 38 37 34 28 57 24 19 15 40 35 24 66 22 24 56 45 28 17 64 43 42 6 40 65 40 52 58 66 25 45 24 51 62 13 66 47 35 24 6 64 0

Al pretender graficar la forma de las distancias entre ciudades, se adopta una figura
presentando algunas variantes que tratan en lo posible de asemejar a la realidad aumentando
restricciones a su modelamiento.

Figura 1: Ejemplo del problema de ruteamiento de vehículos VRP.

[Link]ÓN DEL MODELO MATEMÁTICO VRP

Se define como variable de decisión:

𝑋𝑖𝑗 : Re𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎 𝑣𝑖𝑠𝑖𝑡𝑎𝑟 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑗 desde 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑖 (𝑖 = 0, 1, 2, … , 99)(𝑗 =

0, 1, 2, . . . , 99)

Toma el valor de 1, "si se llega a la ciudad j desde la ciudad i; de lo contrario

toma el valor de 0"

Función Objetivo:

pág. 8
 𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 𝑀𝑖𝑛 (𝑘1 + 𝑘2 + ⋯ + 𝑘𝑚 ) 𝑦
𝑘1 𝑘1 𝑘2 𝑘2 𝑘𝑚 𝑘𝑚

𝑀𝑎𝑥 ( ∑ ∑ 𝑑𝑖𝑗𝑘1 𝑥𝑖𝑗𝑘1 , ∑ ∑ 𝑑𝑖𝑗𝑘2 𝑥𝑖𝑗𝑘2 , … , ∑ ∑ 𝑑𝑖𝑗𝑘𝑚 𝑥𝑖𝑗𝑘𝑚 ) ; 𝑑𝑖𝑗 = ∞∀𝑖

𝑖=1 𝑗=1 𝑖=1 𝑗=1 𝑖=1 𝑗=1
=𝑗

s.a

Restricciones:
𝑘1

∑ 𝑥𝑖𝑗𝑘1 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘1 (1)
𝑗=1

𝑘2

∑ 𝑥𝑖𝑗𝑘1 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘2 (2)
𝑗=1
𝑥𝑖𝑗𝑘1 = (0,1) (3)
𝐿𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑓𝑜𝑟𝑚𝑎 𝑢𝑛 𝑣𝑖𝑎𝑗𝑒 𝑟𝑒𝑑𝑜𝑛𝑑𝑜 𝑝𝑎𝑟𝑎 𝑘1 𝑐𝑖𝑢𝑑𝑎𝑑𝑒𝑠.

𝑘2

∑ 𝑥𝑖𝑗𝑘2 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘2 (4)
𝑗=1
𝑘2

∑ 𝑥𝑖𝑗𝑘2 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘2 (5)
𝑗=1
𝑥𝑖𝑗𝑘2 = (0,1) (6)
𝐿𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑓𝑜𝑟𝑚𝑎 𝑢𝑛 𝑣𝑖𝑎𝑗𝑒 𝑟𝑒𝑑𝑜𝑛𝑑𝑜 𝑝𝑎𝑟𝑎 𝑘2 𝑐𝑖𝑢𝑑𝑎𝑑𝑒𝑠.

𝑘𝑚

∑ 𝑥𝑖𝑗𝑘𝑚 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘𝑚 (𝑚 − 2)
𝑗=1
𝑘𝑚

∑ 𝑥𝑖𝑗𝑘𝑚 = 1 , 𝑖 = 1, 2 , 3, … , 𝑘𝑚 (𝑚 − 1)
𝑗=1
𝑥𝑖𝑗𝑘𝑚 = (0,1) (𝑚)
𝐿𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑓𝑜𝑟𝑚𝑎 𝑢𝑛 𝑣𝑖𝑎𝑗𝑒 𝑟𝑒𝑑𝑜𝑛𝑑𝑜 𝑝𝑎𝑟𝑎 𝑘𝑚 𝑐𝑖𝑢𝑑𝑎𝑑𝑒𝑠

* Cómo resolver este modelo matemático si la F.O es una función de funciones, se recurrirá a
otros métodos de solución.

Donde: 𝑛 = 𝑘1 + 𝑘2 + ⋯ + 𝑘𝑚 ; y el número de ciudades en cada subconjunto 𝑘𝑚 puede

variar; sin embargo, en este análisis, se busca que la cantidad de ciudades en cada subconjunto

pág. 9
 sea lo más equilibrada posible. Además, cada subconjunto de ciudades es mutuamente
excluyente, es decir, no comparten ninguna ciudad entre sí (Miguel, págs. 133-178).

4. DISEÑO Y CONSTRUCCIÓN DEL ALGORITMO GENETICO

Diseño del cromosoma

El cromosoma contiene todas las ciudades a visitar, en las que se incluye un depósito como una
ciudad. El cromosoma agrupa las ciudades en subconjuntos, de modo que parezca que está
realizando un TSP. Dado que es una matriz de 100 nodos, comenzará simulando 4 agentes, por
lo que el numero de ciudades en cada subconjunto será de alrededor de 25 (25c – 25c – 25c –
24c).

AGENTE 1 AGENTE 2 AGENTE 3 AGENTE 4

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
0 64 54 77 3 52 50 21 82 39 85 98 46 26 94 11 86 92 87 22 31 51 81 96 18 80 28 91 56 72 13 2 65 35 88 70 63 33 14 7 53 4 67 10 9 76 83 5 32 30 45 95 38 17 55 34 25 66 8 68 23 24 27 41 6 1 89 75 84 15 79 61 49 48 74 37 20 42 69 78 62 58 47 19 44 99 97 66 71 29 73 43 16 57 59 12 90 40 60 93 0

Tal como se aprecia en el siguiente cromosoma para que 4 agentes realicen el mínimo recorrido
a las 99 ciudades, las tres primeros recorrerán 25 ciudades y el cuarto agente recorrerá 24,
despues de haber generado la población para cada agente, será tratado cada uno como un TSP
individual mediante el algoritmo genético con un tamaño de población de 100 individuos y
1000 ejecusiones, se obtiene una solución cercana a la obtima para cada agente que se muestra
a continuación.
Los recorridos de cada agente son:
La mejor distribución con 4 agente(s) y 25 ciudades agrupadas es:
Recorrido del agente 1: [0, 64, 54, 77, 3, 52, 50, 21, 82, 39, 85, 98, 46, 26, 94, 11, 86, 92, 87,
22, 31, 51, 81, 96, 18, 80, 0] – Recorrido para el agente 1: 392.00
Recorrido del agente 2: [0, 28, 91, 56, 72, 13, 2, 65, 35, 88, 70, 63, 33, 14, 7, 53, 4, 67, 10, 9,
76, 83, 5, 32, 30, 45, 0] - Recorrido para el agente 2: 447.00
Recorrido del agente 3: [0, 95, 38, 17, 55, 34, 25, 36, 8, 68, 23, 24, 27, 41, 6, 1, 89, 75, 84, 15,
79, 61, 49, 48, 74, 37, 0] - Recorrido para el agente 3: 370.00
Recorrido del agente 4: [0, 20, 42, 69, 78, 62, 58, 47, 19, 44, 99, 97, 66, 71, 29, 73, 43, 16, 57,
59, 12, 90, 40, 60, 93, 0] - Recorrido para el agente 4: 407.00
Recorrido total de los agentes: 1616.00
Fitness:0.0006188118811881188

La mejor distribución con 5 agente(s) y 20 ciudades agrupadas es:

Recorrido del agente 1: [0, 39, 36, 59, 47, 16, 96, 51, 6, 45, 91, 40, 35, 4, 20, 48, 8, 55, 9, 23,
25, 0] - Recorrido para el agente 1: 316.00

pág. 10
 Recorrido del agente 2: [0, 7, 75, 15, 46, 83, 17, 34, 14, 30, 87, 37, 24, 57, 72, 74, 22, 79, 97,
10, 94, 0] - Recorrido para el agente 2: 328.00
Recorrido del agente 3: [0, 85, 61, 86, 43, 31, 19, 28, 77, 41, 68, 82, 52, 90, 12, 32, 70, 63, 58,
26, 67, 0] - Recorrido para el agente 3: 290.00
Recorrido del agente 4: [0, 2, 93, 69, 80, 66, 27, 78, 62, 5, 95, 89, 76, 13, 1, 88, 49, 18, 84, 73,
64, 0] - Recorrido: 335.00
Recorrido del agente 5: [0, 38, 21, 29, 42, 99, 92, 33, 81, 53, 71, 3, 60, 54, 98, 56, 50, 44, 11,
65, 0] - Recorrido para el agente 4: 270.00
Recorrido total para los 4 agentes: 1539.00
Fitness:0.000649772579597141

FUNCIÓN DE CALIDAD FITNESS

La evaluación para el mejor cromosoma se evalúa para cada subconjunto de ciudades que se
agrupan, es decir para cada TSP. En cualquier caso, el Fitness para cada individuo esta dado
1
de la siguiente manera 𝐹 = 𝑑𝑢𝑟𝑎𝑐𝑖ó𝑛

La calidad del cromosoma para cuando se realiza la evaluación para que 4

vehículos recorran las 99 ciudades desde un mismo punto de inicio está
dada por 𝐷𝑢𝑟𝑎𝑐𝑖ó𝑛 = 𝑀𝑎𝑥(392, 447, 370, 407) = 447 puesto que tiene
el tiempo máximo en que todos los agentes han terminado el recorrido por
1
lo tanto 𝐹 = 447 = 0.002237136465, así sucesivamente para cuando se
avalúa para 5 ciudades tal como se muestra en la siguiente tabla.

a b c d e F RT
0, 64, 54, 77, 3, 52, 50, 21, 82, 39, 85, 98, 46, 26, 94, 11, 86, 92,
87, 22, 31, 51, 81, 96, 18, 80, 0
392
0, 28, 91, 56, 72, 13, 2, 65, 35, 88, 70, 63, 33, 14, 7, 53, 4, 67, 10,
447
9, 76, 83, 5, 32, 30, 45, 0
25 4 447 0.002237 1616
370
0, 95, 38, 17, 55, 34, 25, 36, 8, 68, 23, 24, 27, 41, 6, 1, 89, 75, 84,
15, 79, 61, 49, 48, 74, 37, 0
407
0, 20, 42, 69, 78, 62, 58, 47, 19, 44, 99, 97, 66, 71, 29, 73, 43, 16,
57, 59, 12, 90, 40, 60, 93, 0
0, 39, 36, 59, 47, 16, 96, 51, 6, 45, 91, 40, 35, 4, 20, 48, 8, 55, 9, 316
23, 25, 0

0, 7, 75, 15, 46, 83, 17, 34, 14, 30, 87, 37, 24, 57, 72, 74, 22, 79, 328
97, 10, 94, 0 335 0.002985 1539
20 5
0, 85, 61, 86, 43, 31, 19, 28, 77, 41, 68, 82, 52, 90, 12, 32, 70, 63, 290
58, 26, 67, 0

pág. 11
 0, 2, 93, 69, 80, 66, 27, 78, 62, 5, 95, 89, 76, 13, 1, 88, 49, 18, 84, 335
73, 64, 0
0, 38, 21, 29, 42, 99, 92, 33, 81, 53, 71, 3, 60, 54, 98, 56, 50, 44, 270
11, 65, 0
a = número de ciudades agrupadas d = distancia de viaje en
km
b = número de agentes e = distancia máxima de
recorrido
c = recorrido o viajes de los agentes f = F= calidad de lindividuo
RT= recorrido total

Distancia total para cuando todos los 4 agentes hayan terminado de recorrer las 99 ciudades
en total y regresar a el punto de partida es 1616.
Distancia total para cuando todos los 5 agentes hayan terminado de recorrer las 99 ciudades
en total y regresar a el punto de partida es 1539.
PARÁMETROS
Los parámetros de los operadores genéticos que en las pruebas y durante la calibración del
algoritmo han demostrado un buen comportamiento fueron: porcentaje de cruza 90%,
porcentaje de mutación 15%, tamaño de la población de 100 individuos, así mismo se necesitó
1000 generaciones.
SELECCIÓN
Permite transmitir y conservar las características de las soluciones que se consideran valiosas a
lo largo de las generaciones, siendo el principal medio de esta transmisión aquellos individuos
mejor adaptados (mejor Fitness) tengan más probabilidades de reproducirse.
Mecanismo de Selección por Ruleta
En nuestro caso particular hemos empleado este método en la implementación del AG, aquí la
probabilidad que tiene un individuo de reproducirse es proporcional a su valor de la función de
evaluación, es decir, a su adaptación. Se eligió este, ya que es un método sencillo, pero al
aumentar el tamaño de la población el tiempo de ejecución se incrementa; su complejidad es
del orden O(n²).
CRUZA
Permite a los individuos seleccionados en la etapa anterior, tener descendencia y se espera que
estos hijos sean mejores que los padres.
Cruce por emparejamiento parcial
Los pasos a seguir son:
Elegir aleatoriamente dos puntos de cruce.
• Intercambiar las dos subcadenas comprendidas entre dichos
puntos en los hijos que se generan.
• Para los valores que faltan en los hijos se copian los valores de

pág. 12
los padres:
o Si un valor no está en la subcadena intercambiada se copia
igual.
o Si está en la subcadena intercambiada, entonces se
substituye por el valor que tenga dicha subcadena en su par
opuesto.

A
1 2 3 4 5 6 7 8
Padre 1 1 3 6 4 2 5 8 7

Padre 2 2 7 8 3 1 5 4 6

B
1 2 3 4 5 6 7 8
Hijo 1 2 4 6 4 2 5 8 7

Hijo 2 1 7 8 3 1 5 3 6

Probabilidad de Pc = 0.5 0.7 0.9

cruza

MUTACIÓN
Esta etapa consiste en la alteración genética en la estructura del cromosoma de un individuo,
incorporando este fenómeno natural de manera artificial dentro del AG.
Mutación con representación de orden con números enteros:
4 3 1 5 7 6 2 4 7 1 5 3 6 2

Mutación por Inverción

4 3 1 5 7 6 2 4 7 5 1 3 6 2

Para el desarrollo del AG se ha empleado este tipo, utilizando los siguientes datos.
Probabilidad de Pm = 0.15
mutación

pág. 13
Corrección de ruta: Asegura que cada cromosoma es válido, eliminando duplicados y garantizando
que todas las ciudades son visitadas.
Verificación de unicidad: Garantiza que cada individuo en la población es único, generando nuevos si
se detectan duplicados.

5. DISCUSIONES Y RESULTADOS
Comportamiento del Algoritmo: El algoritmo implementado es un algoritmo genético multi-
agente que se encarga de encontrar soluciones óptimas o cercanas a lo óptimo para el problema
de ruteo de vehículos (VRP). El VRP es un problema complejo de optimización combinatoria,
donde el objetivo es minimizar el tiempo total de recorrido o la distancia que los vehículos
deben cubrir al visitar un conjunto de ciudades, partiendo y terminando en un punto de depósito
o bodega.
El algoritmo fue implementado en Python, aprovechando las bibliotecas NumPy para
operaciones numéricas eficientes y Pandas para la manipulación de datos. Python es un lenguaje
adecuado para la investigación científica debido a su legibilidad y la disponibilidad de
bibliotecas robustas para la manipulación de datos y la implementación de algoritmos
complejos.
Instancia del Problema: El problema se probó utilizando una matriz de distancias contenida
en el archivo [Link]. Esta matriz representa las distancias entre un conjunto de ciudades
que deben ser visitadas por los vehículos. La instancia del problema también incluye parámetros
como el tamaño de la población, el número de generaciones, la tasa de mutación, el número de
agentes (vehículos), y la ciudad de inicio.
Distancia total para cuando todos los 4 agentes hayan terminado de recorrer las 99 ciudades en
total y regresar a el punto de partida es = 1616 y con respecto a la distancia total para cuando
todos los 5 agentes hayan terminado de recorrer las 99 ciudades en total y regresar a el punto
de partida es = 1539 observando que si se decide recorrer las ciudades con 5 Agentes se estaría
minimizando 77 km, cabe recalcar que se puede mejorar este trabajo realizando mayor número
de ejecuciones donde optimice mejor el algoritmo y obteniendo el valor optimo.

6. CONCLUSIONES
 El algoritmo divide el problema en rutas para varios agentes. Cada agente tiene la
responsabilidad de visitar un subconjunto de ciudades, comenzando y terminando en
una ciudad de inicio (depósito). Esto simula escenarios reales en los que varias unidades
de transporte deben operar simultáneamente para maximizar la eficiencia.
 La solución generada por el algoritmo puede evaluarse en función del tiempo total de
recorrido de los agentes, el cual se minimiza. El valor de "fitness" calculado es
inversamente proporcional al tiempo total, por lo que una mayor aptitud indica una
solución más eficiente.
Al final de la ejecución, el algoritmo proporciona no solo las rutas individuales para
cada agente, sino también la duración del recorrido para cada uno, permitiendo un
análisis detallado del rendimiento.
 El algoritmo es adaptable a diferentes tamaños de problemas, ajustando dinámicamente
parámetros como el tamaño de la población y el número de generaciones en función del

pág. 14
 número de ciudades y agentes. Esto lo hace aplicable tanto a problemas pequeños como
a instancias más grandes y complejas del VRP.
 El uso de un Algoritmo Genético permite la exploración de una amplia variedad de
posibles soluciones (rutas), favoreciendo la evolución de soluciones cada vez mejores a
lo largo de múltiples generaciones. Este enfoque es adecuado para problemas complejos
como el VRP, donde las soluciones óptimas no son evidentes y deben ser descubiertas
mediante técnicas de búsqueda exploratoria.

7. REFERENCIAS BIBLIOGRÁFICAS

Arias-Osorio, J., & Fernando Niño-Sáenz, A. (2017). Un Algoritmo GRASP híbrido para el 2eCVRP.

Dyna, 84(202), 16-16-25. Academic Search Ultimate.

[Link]

CASTELLANOS BALLESTEROS, K. N. I., & SÁNCHEZ CAIMÁN, P. J. (2015). Diseño de un modelo de redes

para el ruteo de vehículos de carga liviana para la distribución de valores. Revista Épsilon, 25,

139-139-155. Academic Search Ultimate.

Enciso Caicedo, M. A., Arteaga Sarmiento, W., & Guarín Cortés, N. L. (2018). MODELO DE RUTEO DE

VEHÍCULOS COMO ALTERNATIVA DE TRANSPORTE, ESTUDIO DE CASO: UMNG SEDE CAMPUS.

Revista Politécnica, 14(27), 45-56. [Link]

Gonzalez-L, E. C., Adarme-Jaimes, W., & Orjuela-Castro, J. A. (2015). Modelo matemático estocástico

para el problema de ruteo de vehículos en la recolección de productos perecederos. Dyna,

82(189), 199-206.

González-La Rotta, E. C., & Becerra-Fernández, M. (2017). Plataformas de intercambio con ruteo de

vehículos. Una revisión delestado del arte. Dyna, 84(200), 271-271-280. Academic Search

Ultimate. [Link]

Inge Cuc, R. I. (2013). Alternativa Heurística MCM para Problemas de Ruteo de Vehículos. 9.

Mauricio Alberto Mora Castellanos, Cristopher Alberto Tinajero Naranjo, & Mayra Ximena Cevallos

Andrade. (2023). Propuesta metodológica para el diseño de flotas de transporte desde el

enfoque del problema de ruteo de vehículos. Revista Eruditus, 4(2), 59-59-77. Directory of

Open Access Journals. [Link]

pág. 15
Moratilla, A., Fernández, E., & Sánchez, J. J. (2014). Optimización de problemas reales VRP-complejos

mediante Algoritmos Genéticos. CISTI (Iberian Conference on Information Systems &

Technologies / Conferência Ibérica de Sistemas e Tecnologias de Informação) Proceedings, 2,

236-241.

Ni, Q., & Tang, Y. (2023). A Bibliometric Visualized Analysis and Classification of Vehicle Routing

Problem Research. Sustainability (2071-1050), 15(9), 7394-7394-7430. Food Science Source.

[Link]

Orrego Cardozo, J. P., Ospina Toro, D., & Toro Ocampo, E. M. (2016). Solución al Problema de Ruteo de

Vehículos con Capacidad Limitada (CVRP) usando una técnica metaheurística. Scientia et

Technica, 21(3), 225-225-233. Academic Search Ultimate.

[Link]

Pérez Kaligari, E., & Guerrero Rueda, W. J. (2015). MÉTODOS DE OPTIMIZACIÓN PARA EL PROBLEMA

DE RUTEO DE VEHÍCULOS CON INVENTARIOS Y VENTANAS DE TIEMPO DURAS. Revista

Ingeniería Industrial, 14(3), 31-31-49. Academic Search Ultimate.

Prato Torres, R., Suero Pérez, D. F., & Guzmán Ávila, O. J. (2015). Ruteo de Vehículos desde un Centro

de Distribución a una Línea de Supermercados en Barranquilla, Colombia. Revista Ingeniare,

18, 11-11-21. Applied Science & Technology Source Ultimate. [Link]

2458/ingeniare.18.533

Sánchez, D. E., & Gutiérrez, E. (2022). Aplicación de la p-mediana y ruteo de vehículos para la

reducción de distancias en una empresa de servicio postal. Información Tecnológica, 33(1),

121-121-130. Food Science Source. [Link]

Shafiekhani, M., Komijan, A. R., & Javanshir, H. (2024). Optimizing the Routing Problem in the Vehicle

Carrying Cash Considering the Route Risk (Case Study of Bank Shahr). Journal of Applied

Research on Industrial Engineering, 11(2), 143-143-154. Applied Science & Technology Source

Ultimate. [Link]

pág. 16
Solarte Martínez, G. R., Castillo Sanz, A. G., & Gahona, G. R. (2015). Optimization of a vehicular

routing using simple genetic chu-beasley algorithm. Tecnura, 19(44), 93-93-108. Fuente

Académica Plus. [Link]

Universidad del Valle, Puenayán, D. E., Londoño, J. C., Universidad del Valle, Escobar, J. W., Pontificia

Universidad Javeriana Cali, Linfati, R., & Universidad del Bío-Bío. (2014). Un algoritmo basado

en búsqueda tabú granular para la solución de un problema de ruteo de vehículos

considerando flota heterogénea. Revista Ingenierías Universidad de Medellín, 13(25), 81-98.

[Link]

Vargas, L. M. E., Zuluaga, A. H. E., Gutiérrez, J. N. M., & Gómez, D. (2013). Identificación de variables

principales en el planeamiento de redes de transmisión usando técnicas heurísticas basadas

en PLE y PNLE. 18(1).

Arias-Osorio, J., & Fernando Niño-Sáenz, A. (2017). Un Algoritmo GRASP híbrido para el

2eCVRP. Dyna, 84(202), 16-16-25. Academic Search Ultimate.

[Link]

CASTELLANOS BALLESTEROS, K. N. I., & SÁNCHEZ CAIMÁN, P. J. (2015). Diseño

de un modelo de redes para el ruteo de vehículos de carga liviana para la distribución

de valores. Revista Épsilon, 25, 139-139-155. Academic Search Ultimate.

Enciso Caicedo, M. A., Arteaga Sarmiento, W., & Guarín Cortés, N. L. (2018). MODELO DE

RUTEO DE VEHÍCULOS COMO ALTERNATIVA DE TRANSPORTE, ESTUDIO

DE CASO: UMNG SEDE CAMPUS. Revista Politécnica, 14(27), 45-56.

[Link]

Gonzalez-L, E. C., Adarme-Jaimes, W., & Orjuela-Castro, J. A. (2015). Modelo matemático

estocástico para el problema de ruteo de vehículos en la recolección de productos

perecederos. Dyna, 82(189), 199-206.

pág. 17
González-La Rotta, E. C., & Becerra-Fernández, M. (2017). Plataformas de intercambio con

ruteo de vehículos. Una revisión delestado del arte. Dyna, 84(200), 271-271-280.

Academic Search Ultimate. [Link]

Inge Cuc, R. I. (2013). Alternativa Heurística MCM para Problemas de Ruteo de Vehículos.

9.

Mauricio Alberto Mora Castellanos, Cristopher Alberto Tinajero Naranjo, & Mayra Ximena

Cevallos Andrade. (2023). Propuesta metodológica para el diseño de flotas de

transporte desde el enfoque del problema de ruteo de vehículos. Revista Eruditus,

4(2), 59-59-77. Directory of Open Access Journals.

[Link]

Moratilla, A., Fernández, E., & Sánchez, J. J. (2014). Optimización de problemas reales VRP-

complejos mediante Algoritmos Genéticos. CISTI (Iberian Conference on Information

Systems & Technologies / Conferência Ibérica de Sistemas e Tecnologias de

Informação) Proceedings, 2, 236-241.

Ni, Q., & Tang, Y. (2023). A Bibliometric Visualized Analysis and Classification of Vehicle

Routing Problem Research. Sustainability (2071-1050), 15(9), 7394-7394-7430. Food

Science Source. [Link]

Orrego Cardozo, J. P., Ospina Toro, D., & Toro Ocampo, E. M. (2016). Solución al Problema

de Ruteo de Vehículos con Capacidad Limitada (CVRP) usando una técnica

metaheurística. Scientia et Technica, 21(3), 225-225-233. Academic Search Ultimate.

[Link]

Pérez Kaligari, E., & Guerrero Rueda, W. J. (2015). MÉTODOS DE OPTIMIZACIÓN PARA

EL PROBLEMA DE RUTEO DE VEHÍCULOS CON INVENTARIOS Y

VENTANAS DE TIEMPO DURAS. Revista Ingeniería Industrial, 14(3), 31-31-49.

Academic Search Ultimate.

pág. 18
Prato Torres, R., Suero Pérez, D. F., & Guzmán Ávila, O. J. (2015). Ruteo de Vehículos desde

un Centro de Distribución a una Línea de Supermercados en Barranquilla, Colombia.

Revista Ingeniare, 18, 11-11-21. Applied Science & Technology Source Ultimate.

[Link]

Sánchez, D. E., & Gutiérrez, E. (2022). Aplicación de la p-mediana y ruteo de vehículos para

la reducción de distancias en una empresa de servicio postal. Información

Tecnológica, 33(1), 121-121-130. Food Science Source.

[Link]

Shafiekhani, M., Komijan, A. R., & Javanshir, H. (2024). Optimizing the Routing Problem in

the Vehicle Carrying Cash Considering the Route Risk (Case Study of Bank Shahr).

Journal of Applied Research on Industrial Engineering, 11(2), 143-143-154. Applied

Science & Technology Source Ultimate.

[Link]

Solarte Martínez, G. R., Castillo Sanz, A. G., & Gahona, G. R. (2015). Optimization of a

vehicular routing using simple genetic chu-beasley algorithm. Tecnura, 19(44), 93-93-

108. Fuente Académica Plus.

[Link]

Universidad del Valle, Puenayán, D. E., Londoño, J. C., Universidad del Valle, Escobar, J. W.,

Pontificia Universidad Javeriana Cali, Linfati, R., & Universidad del Bío-Bío. (2014).

Un algoritmo basado en búsqueda tabú granular para la solución de un problema de

ruteo de vehículos considerando flota heterogénea. Revista Ingenierías Universidad de

Medellín, 13(25), 81-98. [Link]

Vargas, L. M. E., Zuluaga, A. H. E., Gutiérrez, J. N. M., & Gómez, D. (2013). Identificación

de variables principales en el planeamiento de redes de transmisión usando técnicas

heurísticas basadas en PLE y PNLE. 18(1).

pág. 19
Miguel, J. C. (s.f.). Algoritmos Genéticos desde la investigación de operaciones. Piura: Editorial

académica española.

8. ANEXOS

1. import random
2. import numpy as np
3. import pandas as pd
4. import os
5. class AlgoritmoGeneticoMultiAgente:
6. def __init__(self, matriz_distancias, tamano_poblacion, generaciones,
tasa_mutacion, ciudad_inicio, num_agentes, p_c):
7. self.matriz_distancias = matriz_distancias
8. self.num_ciudades = matriz_distancias.shape[0]
9. self.tamano_poblacion = tamano_poblacion
10. [Link] = generaciones
11. self.tasa_mutacion = tasa_mutacion
12. self.ciudad_inicio = ciudad_inicio
13. self.num_agentes = num_agentes
14. self.p_c = p_c
15. [Link] = self.inicializar_poblacion()
16. self.poblacion_total=[]
17.
18. #Generar como población inicial el conjunto de cromosomas que contienen todas
las ciudades en orden aleatorio
19. #y que comienza y termina con la ciudad de "bodega"
20. def inicializar_poblacion(self):
21. poblacion = []
22. for _ in range(self.tamano_poblacion):
23. cromosoma = [Link](range(self.num_ciudades), self.num_ciudades)
24. if self.ciudad_inicio in cromosoma:
25. [Link](self.ciudad_inicio) # Remover la ciudad de inicio si está
presente
26. [Link](cromosoma)
27. return poblacion
28.
29. def fitness(self, cromosoma):
30. if len(cromosoma) != (self.num_ciudades - 1):
31. raise ValueError(f"El cromosoma debe tener una longitud igual al número de
ciudades menos uno. Longitud encontrada: {len(cromosoma)}")
32.
33. # Dividir el cromosoma en rutas para cada agente
34. chunk_size = len(cromosoma) // self.num_agentes
35. remainder = len(cromosoma) % self.num_agentes
36. rutas_agentes = []
37. current_index = 0
38.

pág. 20
39. for i in range(self.num_agentes):
40. extra = 1 if i < remainder else 0
41. rutas_agentes.append(cromosoma[current_index:current_index + chunk_size +
extra])
42. current_index += chunk_size + extra
43.
44. # Asegurar que cada ruta comience y termine con la ciudad de inicio
45. for idx in range(self.num_agentes):
46. if rutas_agentes[idx][0] != self.ciudad_inicio:
47. rutas_agentes[idx].insert(0, self.ciudad_inicio)
48. if rutas_agentes[idx][-1] != self.ciudad_inicio:
49. rutas_agentes[idx].append(self.ciudad_inicio)
50.
51. # Calcular la distancia recorrida por cada agente
52. duraciones = []
53. for idx in range(self.num_agentes):
54. recorrido =
sum(self.matriz_distancias[rutas_agentes[idx][j]][rutas_agentes[idx][j + 1]] for j in
range(len(rutas_agentes[idx]) - 1))
55. [Link](recorrido)
56.
57. tiempo_maximo = sum(duraciones)
58. return 1 / tiempo_maximo if tiempo_maximo > 0 else float('inf')
59.
60. def seleccion_ruleta(self):
61. total_aptitud = sum([Link](ind) for ind in [Link])
62. mejores = []
63. for _ in range(2):
64. ruleta_valor = [Link](0, total_aptitud)
65. suma_parcial = 0
66. for individuo in [Link]:
67. suma_parcial += [Link](individuo)
68. if suma_parcial >= ruleta_valor:
69. [Link](individuo)
70. break
71. return mejores
72.
73. def cruza(self, padres):
74. hijos = []
75. for i in range(0, len(padres), 2):
76. if i + 1 < len(padres) and [Link]() <= self.p_c:
77. if self.num_ciudades > 3:
78. cr1, cr2 = sorted([Link](range(1, self.num_ciudades - 1), 2))
79. else:
80. cr1, cr2 = 1, 2
81. hijo1, hijo2 = padres[i][:], padres[i + 1][:]
82.
83. # Intercambio de genes
84. hijo1[cr1:cr2], hijo2[cr1:cr2] = padres[i + 1][cr1:cr2], padres[i][cr1:cr2]
85.
86. # Resolver duplicados en hijo1

pág. 21
87. for k in range(len(hijo1)):
88. if k < cr1 or k >= cr2:
89. max_attempts = 100
90. attempts = 0
91. while hijo1[k] in hijo1[cr1:cr2] and attempts < max_attempts:
92. available_genes = [gene for gene in padres[i + 1] if gene not in
hijo1]
93. if not available_genes:
94. break
95. hijo1[k] = available_genes[0]
96. attempts += 1
97.
98. # Resolver duplicados en hijo2
99. for k in range(len(hijo2)):
100. if k < cr1 or k >= cr2:
101. max_attempts = 100
102. attempts = 0
103. while hijo2[k] in hijo2[cr1:cr2] and attempts < max_attempts:
104. available_genes = [gene for gene in padres[i] if gene not in
hijo2]
105. if not available_genes:
106. break
107. hijo2[k] = available_genes[0]
108. attempts += 1
109.
110. [Link]([hijo1, hijo2])
111. else:
112. if i + 1 < len(padres):
113. [Link]([padres[i], padres[i + 1]])
114. else:
115. [Link](padres[i])
116.
117. return self.corregir_ruta(hijos, 1)
118.
119. def mutacion(self, poblacion):
120. for i in range(len(poblacion)):
121. if [Link]() < self.tasa_mutacion:
122. if self.num_ciudades > 3:
123. p1, p2 = sorted([Link](range(1, self.num_ciudades - 1),
2))
124. else:
125. p1, p2 = 1, 2
126. if [Link]() > 0.5:
127. poblacion[i][p1], poblacion[i][p2] = poblacion[i][p2],
poblacion[i][p1]
128. else:
129. poblacion[i][p1:p2 + 1] = reversed(poblacion[i][p1:p2 + 1])
130. return self.corregir_ruta(poblacion, 1)
131.
132. def mejor(self):
133. return max([Link], key=[Link])

pág. 22
134.
135. def remplaza_peor_con_mejor(self):
136. mejores_individuos = sorted([Link], key=[Link],
reverse=True)
137. num_elite = max(1, int(0.1 * self.tamano_poblacion)) #Orden de
menor a mayor según el fitness
138. [Link] = sorted([Link], key=[Link])
139. [Link][:num_elite] = mejores_individuos[:num_elite]
140.
141. def corregir_ruta(self, rutas, a):
142. rutas_corregidas = []
143.
144. if a == 1:
145. # 'rutas' es una lista de listas
146. for ruta in rutas:
147. ciudades_vistas = set()
148. ruta_corregida = []
149. for ciudad in ruta:
150. if ciudad not in ciudades_vistas:
151. ruta_corregida.append(ciudad)
152. ciudades_vistas.add(ciudad)
153. # Completar la ruta con las ciudades faltantes excluyendo la ciudad
inicial
154. ciudades_faltantes = set(range(self.num_ciudades)) -
ciudades_vistas
155. ciudades_faltantes.discard(self.ciudad_inicio) # Asegurar que la
ciudad de inicio no se repita
156. ruta_corregida.extend(ciudades_faltantes)
157. rutas_corregidas.append(ruta_corregida)
158. return rutas_corregidas
159. else:
160. # 'rutas' es una única lista
161. ciudades_vistas = set()
162. ruta_corregida = []
163. for ciudad in rutas:
164. if ciudad not in ciudades_vistas:
165. ruta_corregida.append(ciudad)
166. ciudades_vistas.add(ciudad)
167. # Completar la ruta con las ciudades faltantes excluyendo la ciudad
inicial
168. ciudades_faltantes = set(range(self.num_ciudades)) - ciudades_vistas
169. ciudades_faltantes.discard(self.ciudad_inicio) # Asegurar que la
ciudad de inicio no se repita
170. ruta_corregida.extend(ciudades_faltantes)
171. return ruta_corregida
172.
173. def verificar_poblacion_unica(self):
174. """
175. Verifica que todas las rutas en la población sean únicas.
176. Si encuentra duplicados, los reemplaza con nuevas rutas generadas
aleatoriamente.

pág. 23
177. """
178. rutas_unicas = []
179. rutas_duplicadas = []
180.
181. for ruta in [Link]:
182. if ruta in rutas_unicas or ruta in self.poblacion_total:
183. rutas_duplicadas.append(ruta)
184. else:
185. rutas_unicas.append(ruta)
186.
187. # Si se encontraron duplicados, reemplázalos
188. while rutas_duplicadas:
189. ruta_nueva = [Link](range(self.num_ciudades),
self.num_ciudades)
190. ruta_nueva.remove(self.ciudad_inicio)
191.
192. # Asegúrate de que la nueva ruta también sea única
193. if ruta_nueva not in rutas_unicas and ruta_nueva not in
self.poblacion_total:
194. rutas_duplicadas.pop()
195. rutas_unicas.append(ruta_nueva)
196. self.poblacion_total.append(ruta_nueva)
197.
198. # Actualizar la población con las rutas únicas
199. [Link] = rutas_unicas
200.
201. def ejecutar(self):
202. self.verificar_poblacion_unica()
203. Mejor=[[] for _ in range([Link])]
204. for generacion in range([Link]):
205. [Link]('cls')
206. print(f"Cargando: {100*generacion/[Link]}%")
207. nueva_poblacion = []
208.
209. # Asegurar que cada cromosoma en la población sea válido
210. for individuo in [Link]:
211. if len(individuo) != self.num_ciudades - 1:
212. raise ValueError("Cada cromosoma debe tener una longitud igual
al número de ciudades menos uno.")
213. if self.ciudad_inicio in individuo:
214. raise ValueError("Ningún cromosoma debe contener la ciudad de
inicio.")
215.
216. # Añadir el mejor individuo de la generación anterior
217. nueva_poblacion.append([Link]())
218.
219. while len(nueva_poblacion) < self.tamano_poblacion:
220. padres = self.seleccion_ruleta()
221. hijos = [Link](padres)
222. hijos = [Link](hijos)
223. nueva_poblacion.extend(hijos)

pág. 24
224.
225. [Link] = nueva_poblacion[:self.tamano_poblacion]
226. self.verificar_poblacion_unica()
227. mejor_individuo = [Link]()
228. self.remplaza_peor_con_mejor()
229. Mejor[generacion]=mejor_individuo
230.
231. mejor_solucion = max(Mejor, key=[Link])
232.
233. # Verificar y agrupar el mejor individuo en rutas para cada agente
234. if len(mejor_solucion) != (self.num_ciudades - 1):
235. raise ValueError("El mejor individuo debe tener una longitud igual al
número de ciudades menos uno.")
236.
237. # Dividir la mejor solución en rutas de agentes
238. chunk_size = len(mejor_solucion) // self.num_agentes
239. remainder = len(mejor_solucion) % self.num_agentes
240. mejor_sol_ag = [[] for _ in range(self.num_agentes)]
241. current_index = 0
242.
243. for i in range(self.num_agentes):
244. extra = 1 if i < remainder else 0
245. mejor_sol_ag[i] = mejor_solucion[current_index:current_index +
chunk_size + extra]
246. current_index += chunk_size + extra
247.
248. # Asegurar que cada ruta comience y termine con la ciudad de inicio
249. for idx in range(self.num_agentes):
250. if mejor_sol_ag[idx][0] != self.ciudad_inicio:
251. mejor_sol_ag[idx].insert(0, self.ciudad_inicio)
252. if mejor_sol_ag[idx][-1] != self.ciudad_inicio:
253. mejor_sol_ag[idx].append(self.ciudad_inicio)
254.
255. # Calcular la distancia recorrida por cada agente
256. duraciones = []
257. for idx in range(self.num_agentes):
258. recorrido = 0
259. for j in range(len(mejor_sol_ag[idx]) - 1):
260. recorrido +=
self.matriz_distancias[mejor_sol_ag[idx][j]][mejor_sol_ag[idx][j + 1]]
261. [Link](recorrido)
262.
263. tiempo_maximo = sum(duraciones)
264. return mejor_sol_ag, duraciones, tiempo_maximo
265.
266. def leer_matriz_desde_excel(ruta_archivo, hoja):
267. try:
268. df = pd.read_excel(ruta_archivo, sheet_name=hoja, header=None)
269. return df.to_numpy()
270. except Exception as e:
271. print(f"Error al leer el archivo: {e}")

pág. 25
272. raise
273.
274. def seleccionar_ciudades(matriz, ciudades):
275. ciudades = [ciudad - 1 for ciudad in ciudades]
276. return matriz[np.ix_(ciudades, ciudades)]
277.
278. # Código para interactuar con el usuario y ejecutar el algoritmo
279. usar_hoja = str(input("¿Desea usar la Hoja1(100 ciudades), Hoja2 (11
ciudades) u Hoja3 (sin matriz definida)? (Hoja1/Hoja2/Hoja3): ").strip())
280. ruta_excel = "[Link]"
281. matriz_distancias = leer_matriz_desde_excel(ruta_excel, usar_hoja)
282. ciudades_seleccionadas = range(0,len(matriz_distancias))
283.
284. ciudad_inicio = int(input("Ingrese la ciudad donde desea iniciar el ruteo:
").strip())
285.
286. num_agentes = int(input("Ingrese el número de agentes que recorrerán las
ciudades: ").strip())
287. num_ciudades = matriz_distancias.shape[0]
288. tamano_poblacion = max(20,num_ciudades)
289. generaciones = max(100,num_ciudades*5)
290.
291. tasa_mutacion = 0.15
292. p_c = 0.9
293. age=1
294.
295. ag = AlgoritmoGeneticoMultiAgente(matriz_distancias, tamano_poblacion,
generaciones, tasa_mutacion, ciudad_inicio, num_agentes, p_c)
296. mejor_rutas, duraciones, tiempo_maximo = [Link]()
297. age=num_agentes
298. print(f"La mejor distribución con {age} agente(s) y {num_ciudades//age}
ciudades agrupadas es:")
299. for i, ruta in enumerate(mejor_rutas):
300. ciu=[]
301. for j in ruta:
302. [Link](ciudades_seleccionadas[j])
303. if i < len(duraciones):
304. print(f"Recorrido del agente {i + 1}: {ciu} - Recorrido:
{duraciones[i]:.2f}")
305. else:
306. print(f"Error: No se encontró una duración para el agente {i + 1}")
307. print(f"Recorrido total de los agentes: {tiempo_maximo:.2f}")
308. print(f"Fitness:{1/tiempo_maximo}")
309. print("--------------------------------------------------------------------------------------
----")

pág. 26