PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA OPTIMIZACIÓN DE RUTAS EN LA DISTRIBUCIÓN DE PRODUCTOS DE BELLEZA Tesis para optar el Título de Ingeniero Industrial, que presenta el bachiller: JAROL JERENS LUGO ORÉ ASESOR: Walter Silva Sotillo Lima, junio de 2012 RESUMEN El presente estudio a través de 5 capítulos, demuestra que la aplicación de algoritmos en un caso real tal como las rutas de distribución de productos de belleza, para las zonas de San Juan de Miraflores y Villa María del Triunfo, es posible debido a que se obtiene una óptima distribución de las rutas para ambas zonas. En el primer capítulo se definió los algoritmos a utilizar tales como: Algoritmo de Ahorros, Algoritmo de Pétalos y el Algoritmo de Inserción para cada algoritmo se analizó ambas zonas a excepción de la zona de San Juan De Miraflores ya que para esta zona el algoritmo de Inserción no aplicaba. Para realizar el estudio en ambas zonas, en el segundo capítulo se describió la situación actual, la problemática y el desempeño del sistema actual en el cual se muestra la distancia recorrida, el promedio de puntos de reparto. El tercer capítulo del estudio muestra el desarrollo de los modelos propuestos, la ruta inicial de ambas zonas y a partir de este punto se analiza y aplica los algoritmos para las dos zonas. La evaluación de resultados se verifica en el cuarto capítulo, en el cual se desarrolla una comparación de las distancias recorridas actualmente con las distancias recorridas al haberse aplicado los algoritmos y se selecciona cuál de los algoritmos logró optimizar las rutas de distribución. En el último capítulo se mencionan las conclusiones y recomendaciones, logrando así obtener una mejor visión del estudio realizado. TEMA DE TESIS PARA OPTAR : Título de Ingeniero Industrial ALUMNA : JAROL JERENS LUGO ORÉ CÓDIGO : 2003.7128.9. PROPUESTO POR : Ing. Walter A. Silva Sotillo ASESOR : Ing. Walter A. Silva Sotillo TEMA : OPTIMIZACIÓN DE RUTAS EN LA DISTRIBUCIÓN DE PRODUCTOS DE BELLEZA. Nº TEMA : FECHA : San Miguel, 12 de abril de 2010 JUSTIFICACIÓN: Actualmente el tema de la logística es de suma importancia ya que las empresas crean áreas específicas para su proceso, estas se han perfeccionado con el paso del tiempo y es hoy en día, un aspecto básico para ser una empresa de primer nivel. Una definición general de logística1 “es la parte del proceso de la cadena de suministros que planea, lleva a cabo y controla el flujo y almacenamiento eficientes y efectivos de bienes y servicios, así como de la información relacionada, desde el punto de origen hasta el punto de consumo, con el fin de satisfacer los requerimientos de los clientes”. Según la Consulta2 San José 2007, en América Latina más de la mitad de las empresas encuestadas indican que la infraestructura es un obstáculo grande o grave para el manejo y crecimiento de las actividades empresariales, un nivel mucho más alto que en Europa o Asia. Los costos 1 Ronald H. Ballou, Logística Administración de la Cadena de Suministro, Quinta edición 2004, pág. 4 Consulta San José 2 http://www.iadb.org/res/consultasanjose/files/summary_sp_esp/infrastructure_summary_esp.pdf (2007) logísticos en América Latina varían entre 18% y 34% del valor del producto, mientras que la cifra correspondiente en la zona de la Organización para la Cooperación y el Desarrollo Económico (OCDE) es alrededor del 9%. La empresa tiene como una de sus funciones principales realizar la distribución de los productos de belleza a nivel nacional e internacional. En las últimas campañas, las consultoras de belleza vienen quejándose por la demora en la entrega de sus pedidos, es por ello que los transportistas desean rediseñar las rutas de reparto. En la actualidad existen varias herramientas matemáticas que pueden solucionar problemas con respecto al ruteo de vehículos, las cuales pueden ser heurísticas tradicionales como también la aplicación de metaheurísticas. El presente estudio se centrará en diseñar y optimizar las rutas de distribución de las zonas, con esto se minimizará el tiempo de entrega de los pedidos, los costos logísticos y llevará a una mejor atención al cliente y una reducción en los costos para la empresa. OBJETIVO GENERAL: Optimizar las rutas de distribución en una empresa de productos de belleza OBJETIVOS ESPECÍFICOS:  Desarrollar un marco teórico necesario para la interpretación del modelo matemático a aplicar.  Analizar y describir la situación actual de la empresa.  Desarrollar el modelo heurístico elegido.  Evaluar los costos del modelo elegido. PUNTOS A TRATAR: a. Marco teórico. Se desarrollarán los conceptos, modelos y técnicas del uso del Modelo de Ruteos para mejorar la distribución de los pedidos. b. Descripción y análisis de la situación actual. Se describirá y realizará un análisis del problema actual de la empresa definiendo el alcance del estudio. c. Desarrollo del modelo Se desarrollará el modelo de ruteo para el caso en mención. d. Evaluación de los resultados Se evaluarán los resultados que implican el modelo desarrollado e. Conclusiones y recomendaciones. ------------------------------------- ASESOR INDICE CAPÍTULO 1. MARCO TEÓRICO ................................................................. 2 1.1 Programación Lineal ......................................................................... 2 1.1.1 Simbología ............................................................................... 2 1.1.2 Modelo de Asignación .............................................................. 3 1.2 Problemas de Ruteo de Vehículos (VRP)......................................... 4 1.2.1 El Problema del Agente Viajero (TSP) ..................................... 4 1.3 Heurísticas Tradicionales para el VRP ............................................. 5 1.3.1 El Algoritmo de Ahorros............................................................ 5 1.3.2 Heurística de Inserción............................................................. 6 1.3.3 Algoritmo de Pétalos ................................................................ 9 CAPITULO 2. DESCRIPCIÓN Y ANÁLISIS DE LA SITUACIÓN ACTUAL11 2.1 Descripción de la situación actual................................................... 11 2.2 Descripción de la problemática ......................................................... 12 2.3 Desempeño del sistema actual....................................................... 13 2.4 Indicadores de desempeño............................................................. 14 CAPITULO 3. DESARROLLO DE MODELOS............................................. 15 3.1 Modelo 1: Por clústers (Algoritmo de Ahorro).................................... 15 3.3. Modelo 2: Algoritmo de Pétalos......................................................... 25 3.3 Construcción del modelo propuesto 3 ................................................ 40 CAPITULO 4. EVALUACION DE RESULTADOS........................................ 44 4.1 Evaluación cuantitativa....................................................................... 44 4.1.1 Algoritmo de Ahorros ................................................................... 44 4.1.2 Algoritmo de Pétalos................................................................... 45 4.1.3 Algoritmo de Inserción ................................................................. 46 CAPITULO 5. CONCLUSIONES Y RECOMENDACIONES ........................ 47 5.1 Conclusiones...................................................................................... 47 5.2 Recomendaciones........................................................................... 48 REFERENCIAS BIBLIOGRAFICAS............................................................. 50 ANEXOS………………………………………………………………………….. 52 ANEXO 1.Direcciones en orden de ruta actual -San Juan de Miraflores… CD ANEXO 2.Direcciones en orden de ruta actual – Villa María del Triunfo… CD ANEXO 3.Gráficos en la aplicación del algoritmo de ahorros….……..…….CD ANEXO 4. Cuadros en la aplicación del algoritmo de ahorros…………….. CD i INDICE DE GRAFICOS Gráfico 1: Dos rutas antes y después de ser unidas........................................... 6 Gráfico 2: Clusters Inicial - San Juan de Miraflores ......................................... 16 Gráfico 3: Clúster con la ruta ideal – Algoritmo de Ahorros ............................. 21 Gráfico 4: Ruta ideal de clústers - San Juan de Miraflores ............................. 22 Gráfico 5: Gran Ruta Ideal- San Juan de Miraflores ......................................... 23 Gráfico 6: Ruta Final en plano real - San Juan Miraflores................................ 24 Gráfico 7: Reporte LINDO – Villa María del Triunfo .......................................... 29 Gráfico 8: Rutas seleccionadas - Villa María del Triunfo .................................. 30 Gráfico 9: Gran Ruta Ideal Villa María del Triunfo ............................................. 31 Gráfico 10: Gran Ruta Real – Villa María Del Triunfo ....................................... 32 Gráfico 11: Reporte LINDO – San Juan de Miraflores ...................................... 36 Gráfico 12: Rutas seleccionadas – San Juan de Miraflores............................. 37 Gráfico 13: Gran Ruta Ideal - San Juan De Miraflores ..................................... 38 Gráfico 14: Gran Ruta Real – San Juan De Miraflores ..................................... 39 Gráfico 15: Rutas de Villa María del Triunfo - Puntos lejanos de las rutas ... 41 Gráfico 16: Gran Ruta – Villa María del Triunfo ................................................. 43 ii INDICE DE TABLAS Tabla 1: Reclamos por campaña .......................................................................... 12 Tabla 2: Distritos en Estudio.................................................................................. 14 Tabla 3: Ahorro entre puntos (m).......................................................................... 19 Tabla 4: Ruta óptima............................................................................................... 19 Tabla 5: San Juan De Miraflores - 1° Cluster (azul)-SJM................................. 20 Tabla 6: Rutas para la zona de Villa María del Triunfo ..................................... 27 Tabla 7: Rutas para la zona de San Juan de Miraflores................................... 33 Tabla 8: Evaluación de puntos de para la inserción .......................................... 42 Tabla 9: Distancia recorrida actual ....................................................................... 44 Tabla 10: Distancia según Algoritmo Ahorros .................................................... 45 Tabla 11: Distancia Recorrida Algoritmo de Pétalos ......................................... 45 Tabla 12: Distancia Recorrida Algoritmo de Inserción ...................................... 46 Tabla 13: Cuadro Comparativo ............................................................................. 46 iii 1 INTRODUCCION En los últimos años el transporte de distribución de mercadería, refleja que las distancias y tiempos son de vital importancia tanto para el transportista como para el cliente, ya que el transportista debe entregar la mercadería en menor tiempo y en una mínima distancia recorrida. El presente estudio es una aplicación de modelos heurísticos, los cuales ayudarán a optimizar las distancias recorridas y por ende las rutas de distribución. La situación actual ocurre en una empresa dedicada a la venta y distribución de productos de belleza, se va a realizar el estudio en dos zonas críticas debido a las quejas de las consultoras en las 5 últimas campañas. Las zonas en estudio son: San Juan de Miraflores y Villa María del Triunfo. La cantidad de puntos de distribución en promedio para ambas zonas es 60. El análisis empieza a partir de la ubicación de los puntos, ahí se inicia el desarrollo de los modelos heurísticos tales como el algoritmo de Ahorros, Pétalos e Inserción. Al finalizar el planteamiento de las propuestas para ambas zonas se escoge cuál es el mejor modelo a utilizar a partir de las distancias recorridas desde el almacén hasta el último punto de reparto, indicando cuál de los algoritmos logra optimizar mejor las rutas de distribución. 2 CAPÍTULO 1. MARCO TEÓRICO 1.1 Programación Lineal La programación lineal se encarga de planear las actividades para conseguir un resultado óptimo; es decir, la mejor solución que lleve al objetivo determinado. 1.1.1 Simbología Según Winston (2006) para la formulación de problemas de programación lineal tiene 3 partes: - La función objetivo, que está compuesta por las variables de decisión (por ejemplo: X1, X2,…, Xn). Esta función se puede maximizar o minimizar. - Un conjunto de restricciones, que pertenecen a una igualdad lineal o desigualdad lineal, que limita los valores que pudiesen tomar las variables de decisión. - Las restricciones de signo o rango de existencia, que restringen todas las variables Xj que sean mayores o iguales a cero. A continuación la siguiente formulación:  Variables de decisión: njx j ,...,2,1,   Función Objetivo: Maximizar o Minimizar nn xcxcxcZ  ...2211 .  Restricciones:     22222121 11212111 ,,... ,,... bxaxaxa bxaxaxa nn nn   …   mnmnmm bxaxaxa  ,,...2211  Rango de existencia: njx j ,...,2,1,0  3 1.1.2 Modelo de Asignación El modelo más usado de aplicación de programación lineal tiene que ver con la asignación de recursos. El número de recursos está limitado, por ello la asignación debe realizarse con cuidado. El análisis de las asignaciones debe llevar a que los objetivos tengan mayor efectividad en lo posible. Formato estándar del modelo El formato para los problemas de programación lineal Se puede formular el modelo matemático del problema general de asignar recursos a actividades. Este modelo consiste en elegir valores de nxxx ,...,, 21 para: Maximizar ,...2211 nnxcxcxcZ  Sujeta a las restricciones 22222121 11212111 ... ... bxaxaxa bxaxaxa nn nn   mnmnnm bxaxaxa  ...2211 y 0,...,0,0 21  nxxx 4 1.2 Problemas de Ruteo de Vehículos (VRP) El problema de ruteo de vehículos nos explica que cuando se tienen a los clientes y almacenes ubicados en un área de forma dispersa, en la cual se debe contar con una flota de vehículos para llegar a los usuarios finales partiendo desde el almacén se debe tener en cuenta que la ruta tomada deberá ser la óptima para minimizar los costos y tiempos. A continuación se formularán algunos de los problemas clásicos y sus extensiones como problemas de Programación Entera. 1.2.1 El Problema del Agente Viajero (TSP) La forma general del Problema del Agente Viajero (o TSP por Travelling Salesman Problem) fue estudiado por el matemático Karl Menger en Viena y Harvard en la década del 1930, más adelante el problema fue promovido por Hassler Whitney3 y Merrill Flood4 en Princeton. Tras estos estudios se puede concluir que el TSP establece que un solo vehículo debe visitar a todos los clientes en una sola ruta y a costo mínimo. 3 Matématico estadounidense, visitado el 10/05/2010 http://www-history.mcs.st-and.ac.uk/Biographies/Whitney.html 4 Matématico estadounidense, visitado el 10/05/2010 http://www2.informs.org/History/Gallery/Presidents/TIMS/mflood.htm 5 El problema puede formularse como: ij Eji ij xc ),( min 1.. )(   ij ij xas Vi 1 )(   ij ji x Vj 1 S\)(,   ij ijSi x VS  {0,1}ijx Eji  ),( Esta formulación fue propuesta por Dantzig, Fulkerson y Johnson5. Las variables binarias ijx indican si el arco (i, j) es utilizado en la solución. La función objetivo establece que el costo total de la solución es la suma de los costos de los arcos utilizados. 1.3 Heurísticas Tradicionales para el VRP 1.3.1 El Algoritmo de Ahorros Este algoritmo es conocido también como el Algoritmo de Ahorros de Clarke y Wrigth6 que ha sido implementado frecuentemente y exitoso en la solución de problemas establecimiento de las rutas de vehículos en gran escala. 5 Dantzig, G., Fulkerson, D., Johnson, S.: Solution of a large scale traveling salesman problem. Operations Research 2 (1954) pp 393–410 6 Clarke, G., Wrigth, W.: Sheduling of vehicles from a central depot to a number of a delivery points. Operations Research 12 (1964) 6 Si en una solución dos rutas diferentes )1,,...,1( i y )1,,...,1( j pueden ser combinadas formando una nueva ruta )1,...,,...,1( ji como se muestra en el Gráfico 1, el ahorro en distancia obtenido por dicha unión es: ijljñij cccs  En la nueva solución los arcos (i, 0) y (0, j) no serán utilizados y se agregará el arco (i, j). En este algoritmo se parte de una solución lineal y se realizan las uniones que den mayores ahorros siempre que no violen las restricciones del problema. Gráfico 1: Dos rutas antes y después de ser unidas Fuente: Clarke, G., Wright, W. (1964). - Paso 1(Inicialización): para cada cliente i construir la ruta (0, i, 0). - Paso 2 (cálculo de ahorros): Calcular ijs para cada par de clientes. - Paso 3 (mejor unión): sea ijji ss max**  , donde el máximo se toma entre los ahorros que no han sido considerados aún. Sean *ir y *jr las rutas que contienen a los clientes *i y *j respectivamente. Si *i es el ultimo cliente de *ir y *j es el primer cliente de *jr y la combinación de *ir y *jr es factible, entonces se combinan. Para finalizar con el método se eliminan ** jis de futuras consideraciones. 1.3.2 Heurística de Inserción 7 Las heurísticas de inserción son métodos constructivos en los cuales se crea una solución mediante sucesivas inserciones de clientes en las rutas. En cada iteración se tiene una solución parcial cuyas rutas sólo visitan un subconjunto de los clientes y se selecciona un cliente no visitado para insertar en dicha solución. En las heurísticas de inserción secuencial solo se considera insertar clientes en la última ruta creada. La principal desventaja de este método es que los últimos clientes no visitados tienden a estar dispersos y por lo tanto las últimas rutas construidas son de costo muy elevado. Las heurísticas de inserción en paralelo surgen para remediar esta deficiencia, permitiendo insertar un cliente en cualquiera de las rutas de la solución. 1.3.2.1 Inserción secuencial de Mole & Jameson7 En esta heurística se utilizan dos medidas para decidir el próximo cliente a insertar en la solución parcial. Para cada cliente no visitado se calcula la mejor posición para ubicarlo en la ruta actual teniendo en cuenta solamente las distancias y sin reordenar los nodos que ya están en la ruta. Se tiene una ruta ),,...,,( 110 tt vvvv donde 10  tvv . 7 MOLE, R.H., JAMESON S.R. 1976 A sequential route-building algorithm employing a generalised saving criterion. Operational Research Quarterly 503-511 8 Si w es un cliente no visitado, el costo de insertar w entre iv y 1iv )0( ti  se define como: ),(1 wvc i siccc iiii vvvwwv 11 ,,,    ),...,,,,...,( 110  tii vvwvv  si no La mejor posición para insertar el cliente w en la ruta actual está dada por ),(minarg)( 1,...,0 wvcwi iti  . Algoritmo de Mole & Jameson i. Creación de una ruta: si todos los clientes pertenecen a una ruta. Si no, seleccionar un cliente no visitado w y crear la ruta )0,,0( wr  . ii. Inserción: sea ),,...,,( 110  tt vvvvr donde )0( 10  tvv . Para cada cliente no visitado w, calcular )(wi arg ),(min 1,...,0 iiti wvc . Si no hay inserciones factibles, ir al paso i. Calcular *w arg ),(max )(2 wvc wiw . Insertar *w luego de )( *wiv en r. iii. Optimización: aplicar el algoritmo 3-opt8 sobre r. Ir al paso ii. 8 Lin, S.: Computer solutions of the travelling salesman problem. Bell System Technical Journal (1965) 2245-2269. 9 1.3.3 Algoritmo de Pétalos Supongamos que se dispone de un conjunto de rutas R, de modo que cada ruta r R es factible, pero de cada cliente es visitado por varias de las rutas. El problema de seleccionar un subconjunto de R de costo mínimo que viste exactamente una vez a cada cliente puede formularse como un Set Partitioning Problem (SPP):  Rk kk xcmin 1..  Rk kik xaas {0}\Vi }1,0{kx Sk  Donde ika vale 1 si el cliente i es visitado por la ruta kr y 0 si no y donde kc es el costo de la ruta kr. La variable kx indica si la ruta kr es seleccionada o no en la solución final. . Esta formulación se debe a Balinski y Quandt (1964). En el caso extremo de que R contenga todas las posibles rutas factibles, solucionar el SPP es equivalente a resolver el problema en forma exacta. Como la cantidad de rutas factibles es, en el caso general, exponencial en la cantidad de clientes, se suele generar solamente un subconjunto de formado por “buenas” rutas. Cada columna del SSP representa a una ruta de R. Cuando en toda columna los ceros aparecen de forma consecutiva, el problema verifica la propiedad de Columnas Circulares y el SPP correspondiente puede ser resuelto en tiempo polinomial. 10 Trasladada al problema la propiedad establece que, para determinado ordenamiento de los clientes del problema, el conjunto de clientes visitado por cada ruta forma un intervalo (que en algunos casos tiene forma de pétalo). Diversas técnicas han sido propuestas para generar “buenos” conjuntos de rutas que verifiquen la propiedad llamadas 1-pétalos y 2-pétalos. 11 CAPITULO 2. DESCRIPCIÓN Y ANÁLISIS DE LA SITUACIÓN ACTUAL 2.1 Descripción de la situación actual El proceso que siguen los transportistas para la distribución de los productos desde el almacén hasta los clientes finales es el siguiente: - En la empresa en un año hay 36 campañas esto significa que por mes la consultora realiza 3 veces sus pedidos, un promedio de cada 10 días hay una campaña. - Cada transportista recibe la programación de horarios diaria durante la campaña para la recepción de los pedidos que serán distribuidos. - Los transportistas se dirigen a la planta (almacén) con media hora de anticipación y al ingresar deben recibir:  Control de despacho: donde se muestran la cantidad de pedidos, bultos, excesos, listado de productos fuera de caja (prendas de vestir, carteras, etc.) y el listado de las consultoras.  Guía de remisión: en esta guía se presenta las direcciones de domicilio de las consultoras.  Boletas de despacho: esta boleta señala el número de la caja (pedido), la dirección de cada consultora, los productos que contienen el pedido. - Después de haber recibido las boletas de venta, el transportista realiza el ruteo de reparto. - Con la unidad de transporte se acercan a la faja para recibir las cajas que serán almacenadas en la unidad móvil. - Al finalizar el llenado de las cajas en la unidad, el transportista se dirige a la rampa de entrega de los productos que van fuera de caja. 12 Una vez completados estos pasos se realiza el “cuadre”, que es la conformidad con el responsable de despacho y el que da el visto bueno para poder empezar el reparto. En la zona de reparto se siguen los siguientes pasos: o Una vez llegada a la zona de reparto, el transportista busca la caja que saldrá primero y así sucesivamente para todos los pedidos. o El transportista llega al domicilio de la consultora y verifica si se encuentra la consultora para entregarle el pedido, de lo contrario puede entregarlo a cualquier persona del domicilio que sea mayor de edad. 2.2 Descripción de la problemática A lo largo de las últimas campañas la empresa ha recibido numerosos reclamos con respecto a la demora de la entrega de los pedidos. Tabla 1: Reclamos por campaña Zona N° pedidos por campaña N° reclamos por campaña San Juan de Miraflores 70 30 Villa María del Triunfo 60 25 Elaboración Propia Para cada campaña las consultoras de cada zona son notificadas con anticipación por el día que van a recibir su pedido, por ello para la facilidad del transportista en el momento de entregar el pedido a la consultora deberá de encontrarse en el domicilio, la consultora titular o una persona mayor de edad. 13 Los reclamos de las consultoras son principalmente: - La demora en la llegada a los domicilios. - La hora de llegada de los transportistas a altas horas de la noche (ya que el repartidor no desea regresar para que no le genere un costo extra). - Si en la visita a la consultora no se le encuentra regresan al final del reparto de toda la zona. Los reclamos de los transportistas hacia la empresa: - El principal reclamo es que la empresa cita a una determinada hora, pero por problemas con la data de los pedidos la recepción de la mercadería se retrasa de dos a tres horas y ello dificulta el reparto posteriormente. 2.3 Desempeño del sistema actual Las zonas que se tomarán en cuenta para evaluar son:  San Juan de Miraflores.  Villa María del Triunfo. Se escogieron ambas zonas debido a que en las últimas cinco campañas han presentado numerosos reclamos entre todas las zonas de reparto (30). 14 2.4 Indicadores de desempeño Se tomarán en cuenta los indicadores que podrán ayudarnos en la comparación de los métodos: - Distancia recorrida: Distancia recorrida por cada zona desde el almacén hasta el último punto de entrega. - Número de pedidos por campaña: Números de pedidos a entregar. - Tiempo total de reparto: Es el tiempo tomado desde el almacén hasta la entrega del último pedido. - Tiempo de entrega por punto: Tiempo que se demora en entregar un pedido. La tabla 1 muestra la situación actual (Distancia Recorrida y promedio de pedidos) de las dos zonas en estudio: Tabla 2: Distritos en Estudio Zona Villa María del Triunfo San Juan de Miraflores Distancia Recorrida (km.) 12.33 8.76 Promedio de pedidos 70.00 60.00 Elaboración Propia 15 CAPITULO 3. DESARROLLO DE MODELOS El presente capitulo muestra los modelos propuestos que nos ayudarán a optimizar la distancia recorrida por el transportista. El tráfico es uno de los principales factores que influye en nuestras recomendaciones. 3.1 Modelo 1: Por clústers (Algoritmo de Ahorro) - Los clústers iniciales: Para cada zona, con la ayuda del Google Maps9 se ubicó los puntos en estudio. - Formación de clústers Con el método del barrido de arriba hacia abajo, la cantidad de puntos es igual en cada clúster. A continuación el Gráfico 2, que muestra los cinco clústers de la zona de San Juan de Miraflores, cada clúster posee en promedio 14 puntos. 9 Aplicación del portal de Google para ubicar puntos de en mapas. 16 Gráfico 2: Clùsters Inicial - San Juan de Miraflores Elaboración Propia 17 Luego de hallar los clusters, se procedió a desarrollar una ruta independiente para cada clúster. Se eligió un punto arbitrario del clúster y a partir de ese punto se empieza a desarrollar el algoritmo de ahorros para finalmente encontrar la ruta ideal. A continuación el desarrollo del algoritmo de ahorros: - Se elaboró una matriz con los puntos escogidos en este caso son 14 para cada cluster, previamente se realizaron las medidas de las distancias (Distancias entre los puntos y las distancias del almacén con cada punto de reparto) con la ayuda del Google Maps. - En la tabla 5 se muestra la matriz de un clúster de San Juan de Miraflores, que nos permitió hallar a través de los ahorros la ruta óptima para el clúster seleccionado, este paso se realizó para los clústers de cada zona. - El número de ahorros para este clúster son 91, a continuación se muestra cómo se hallo el Ahorro desde el punto 2 al punto 3 utilizando la fórmula del Ahorro : Nota: Las distancias están en metros S23 = C02 + C03-C23 S: Ahorro C23: Distancia entre punto 2 y 3 C02: Distancia entre Almacén y punto 2 C03: Distancia entre Almacén y punto 3 El ahorro desde el punto 2 al punto 3: S23 = 27,310 + 27,340 – 65.96 = 54,584.04 18 - Luego de hallar todos los ahorros (para este caso 91) se procedió a desarrollar el algoritmo tomando en cuenta las siguientes restricciones:  La ruta se empieza a formar de acuerdo al ahorro mayor que existe entre los puntos y así sucesivamente.  Si un punto ya tiene dos puntos aledaños en la ruta, ya no se considera en el análisis.  El procedimiento del desarrollo del algoritmo termina cuando se tiene la ruta con todos los puntos que conforman el clúster. - De los ahorros hallados se escogió el mayor de todos en este caso es el Ahorro del punto 12 al 14 con 55,103.47 metros y en la ruta que se va formando se coloca el punto 12 al costado del punto 14, luego se halla el 2° ahorro mayor que es del punto 13 al 14 con 55,084.03 metros y el punto 14 se coloca al costado del punto 13. - A continuación se muesta la tabla 3 de los ahorros de mayor a menor (San Juan de Miraflores) que siguen después de los dos primeros ahorros y que cumplen con las restricciones del algortimo: 19 Tabla 3: Ahorro entre puntos (m) Elaboración Propia La ruta optima es según la Tabla 4: Tabla 4: Ruta óptima Elaboración Propia El la tabla 5 muestra la matriz del 1° clúster, el cual permite hallar la ruta óptima, este paso se realizar para todos los siguientes clústers del distrito San Juan de Miraflores y Villa María del Triunfo. 0 1 3 7 9 11 12 14 13 10 8 6 5 4 2 0 S11-12 55,051.40 S10-13 55,011.80 S8-10 54,956.60 S9-11 54,955.70 S6-8 54,888.80 S7-9 54,887.70 S5-6 54,782.40 S4-5 54,693.80 S3-7 54,675.90 S2-4 54,611.30 S1-3 54,527.20 Distancia (Metros) Ahorro entre puntos Tabla 5: San Juan De Miraflores - 1° Cluster (azul)-SJM   1  2  3  4  5  6  7  8  9  10  11  12  13  14  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0    1  54506.03 54527.2  54497.54 54494.26 54505.29 54522.75 54494 54519.67 54509.51 54523.58 54521.01 54503 54525.82      2  54584.04  54611.31 54605.9 54613.57 54601.29 54602.49 54613.38 54611.96 54605.72 54611.06 54607.9 54618.34        3  54601.3 54613.66 54637.87 54675.86 54627.4 54667.55 54651.44 54675.8 54672.9 54643.45 54676.52          4  54693.76 54698.33 54658.31 54688.84 54686.03 54693.83 54670.81 54682.19 54691.84 54693.26            5  54782.44 54713.68 54774.53 54758.94 54776.6 54737.74 54755.92 54776.6 54771.11              6  54791.77 54888.75 54861.3 54893.1 54836.43 54864.3 54893.24 54885.53                7  54804.66 54887.7 54853.48 54920.65 54912.15 54851.84 54916.54      misma ruta             8  54891.47 54956.63 54876.1 54914.15 54978.93 54954.61      t=0               9  54946.12 54955.73 54975.89 54944.27 54984.64      ruta                 10  54937.42 54977.34 55011.78 55011.36                        11  55051.36 54960.11 55068.69                          12  55007.81 55103.47                            13  55084.03                              14                                                                                                                          RUTA  0  1  3  7  9  11  12  14  13  10  8  6  5  4  2  0  Elaboración Propia El gráfico 3 muestra la ruta ideal del clúster después de hallar la ruta con el algoritmo, este paso también se realiza para todos los clústers. Gráfico 3: Clúster con la ruta ideal – Algoritmo de Ahorros Elaboración Propia Al desarrollar el algoritmo para cada clúster se elabora la ruta ideal, luego se ubicó en el mapa las rutas ideales de cada clúster. A continuación el gráfico 4, muestra el mapa de las rutas de los clústers de San Juan de Miraflores después de hallar las rutas para cada clúster. Gráfico 4: Ruta ideal de clústers - San Juan de Miraflores Elaboración Propia 23 El gráfico 5 muestra un solo clúster, al ser unidos los cinco clústers de acuerdo a la menor distancia que existe entre los puntos de cada clúster para así poder hallar la gran ruta de distribución. Gráfico 5: Gran Ruta Ideal- San Juan de Miraflores Elaboración Propia 24 El gráfico 6 muestra la Gran Ruta de forma ideal, ésta será llevada a los planos reales donde se dará forma a la ruta optima la cual se verificará y validará en el capítulo 4. Gráfico 6: Ruta Final en plano real - San Juan Miraflores Elaboración Propia 25 3.3. Modelo 2: Algoritmo de Pétalos Para la elaboración de este modelo se desarrolló el algoritmo de Pétalos se siguieron los siguientes pasos: - Formación de las rutas Se forman rutas independientes de 5 a 20 puntos de reparto los cuales son cercanos entre sí, con ello se tendrá más alternativas de poder hallar una mejor Gran ruta que recorra menor distancia. - Toma de distancias entre puntos Para cada ruta se toma la distancia recorrida desde el Almacén hasta el último punto de reparto y hasta el retorno al Centro de Distribución. - Variables de Decisión Se utilizarán las variables binarias en las restricciones ya que nos indicará si la ruta es recorrida o no es decir toma los valores de 0 y 1. La variable “x” será: la distancia recorrida por la ruta para la programación del problema y el rango de existencia es mayor o igual a cero. - Puntos de reparto Los puntos de reparto pasan a ser un nodo para formar los pétalos requeridos para el modelo. - Restricciones en la programación Para formar las restricciones que se utilizarán en la programación se verifica la presencia de los nodos en las rutas diseñadas y así formar las ecuaciones en donde se sumarán las variables que pertenezcan al nodo. Aquí la suma de las variables será igual a 1. 26 - Programación Lineal Se hará uso del programa LINDO10, el cual permitirá hallar la mejor solución en cada uno de los problemas planteados. El objetivo del problema es hallar un subconjunto de rutas en las cuales se recorra la mínima distancia para que se visite una sola vez al cliente. Se minimizará las distancias recorridas por cada ruta diseñada y las restricciones serán las que permitan qué rutas serán utilizadas en la solución. Para poder generar la programación, se debe construir un número de rutas considerable ya que así el problema tendrá varias opciones de solución. La tabla 6, muestra las rutas construidas y distancias recorridas en la zona de Villa María del Triunfo, que servirán para la formulación de la programación del problema y así poder hallar las rutas y distancias optimas de cada zona. 10 Es una aplicación para computadoras que se utiliza para resolver problemas de programación lineal, cuadrática y entera. 27 Tabla 6: Rutas para la zona de Villa María del Triunfo Elaboración Propia La programación se muestra a continuación para la zona de Villa María del Triunfo: Se tiene las variables rk, donde k=1, 2,3…, etc. por la existencia de k rutas las cuales recorren todos los puntos de distribución. Se utiliza una variable binaria xk, que indica si es que la ruta es tomada o no, es decir se escoge entre los valores de 0 y 1. 28 El problema consiste en seleccionar un subconjunto de R de distancias mínimas que visite exactamente una vez a cada cliente. Min:4.71x1+3.32x2+5.53x3+4.57x4+5.81x5+7.43x6+4.8x7+7.09x8+6.36x9+8.1 x10+6.61x11+7.23x12+6.82x13+4.58x14+5.37x15+2.41x16+2.77x17+3.25x18+ 2.93x19+3.51x20+4.02x21+4.78x22+4.33x23+4.44x24+4.7x25+5.12x26+4.75x 27+5.71x28+5.54x29+6.76x30+5.95x31+1.60x32+2.25x33+2.48x34+2.82x35+3 .24x36+3.6x37+4.46x38+4.3x39+4.78x40+4.66x41+5.52x42. Sujeto a: Elaboración Propia x10+x13+x30+x31=1 x8+x10+x12+x13+x28+x29+x30=1 x6+x8+x10+x12+x13+x28+x29+x30+x42=1 x5+x6+x8+x10+x11+x12+x13+x28+x29+x30+x41=1 x6+x8+x10+x11+x12+x13+x28+x40 x4+x5+x6+x11+x12+x14+x15+x26+x38=1 x4+x5+x11+x12+x14+x15+x26+x38=1 x1+x4+x5+x9+x14+x15+x26+x37=1 x5+x8+x9+x10+x11+x12+x13+x15+x25+x26+x27+x28+x29+x30+x39=1 x8+x9+x10+x11+x12+x15+x25+x26+x27+x39=1 x8+x9+x10+x11+x12+x25+x26+x27+x39=1 x5+x6+x8+x9+x10+x11+x12+x13+x26+x27+x28+x29+x30+x39=1 x6+x8+x9+x10+x11+x12+x27+x40=1 x8+x9+x10+x11+x12+x25+x27+x40=1 x6+x8+x9+x10+x11+x12+x25+x27+x40=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x37=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x36=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x36=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x36=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x37=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x24+x36+x37=1 x1+x3+x4+x5+x6+x9+x14+x15+x20+x21+x22+x24+x36=1 x3+x6+x7+x8+x9+x10+x11+x12+x15+x21+x22+x23+x24+x25=1 x3+x6+x7+x8+x9+x10+x11+x12+x15+x21+x22+x23+x24+x25=1 x6+x7+x8+x9+x10+x11+x12+x23+x24+x25=1 x3+x6+x7+x8+x9+x10+x22+x23+x24=1 x1+x2+x3+x7+x8+x18+x19+x35=1 x1+x2+x3+x7+x8+x19+x33=1 x1+x2+x3+x7+x8+x16+x19+x33=1 x1+x2+x3+x7+x8+x16+x18+x19+x32=1 x1+x2+x3+x7+x8+x16+x17+x18+x19+x32=1 x1+x2+x3+x7+x8+x16+x17+x18+x32=1 x1+x2+x3+x7+x8+x17+x18+x19+x35=1 x1+x2+x3+x7+x8+x16+x17+x18+x34=1 x1+x2+x3+x7+x8+x17+x18+x34=1 x1+x2+x3+x7+x8+x16+x17+x18+x34=1 29 El gráfico 7, muestra el reporte del programa LINDO que nos da la solución (seleccionados de amarillo) y así hallar las rutas que conformarán la Gran ruta. Gráfico 7: Reporte LINDO – Villa María del Triunfo Elaboración Propia Al obtener la solución a través del programa LINDO, se procede a elaborar las rutas según lo que indica la solución. En el reporte generado por LINDO las rutas a utilizar son las que tienen el valor de 1 en la columna VALUE, por ello solo se debe utilizar 3 rutas: Ruta 2, ruta 4 y ruta 10 Para unir las 3 rutas se evaluó la menor distancia que existe entre los puntos más cercanos entre ellas y así poder unirlos y formar la Gran Ruta Ideal. 30  Entre las rutas 2 y 4, las distancias menores entre puntos cercanos fueron de 263m y 288m.  Entre las rutas 4 y 10, las distancias menores entre puntos cercanos fueron de 414m, 234m y 241m.  El gráfico 8 muestra las 3 rutas que nos permitirá poder hallar la ruta ideal. Gráfico 8: Rutas seleccionadas - Villa María del Triunfo Elaboración Propia 31 El gráfico 9, presenta la Gran Ruta Ideal de Villa María del Triunfo Gráfico 9: Gran Ruta Ideal Villa María del Triunfo Elaboración Propia 32 El gráfico 10, presenta la Gran Ruta Real de Villa María del Triunfo Gráfico 10: Gran Ruta Real – Villa María Del Triunfo Elaboración Propia 33 La tabla 7, muestra las rutas construidas y las distancias recorridas respectivamente para poder hallar las rutas que servirán en la formación de la Gran Ruta en la zona de San Juan de Miraflores. Tabla 7: Rutas para la zona de San Juan de Miraflores Elaboración Propia Rutas Var Ruta xi Dist. Recorrida (km) 1 r1 1-3-7-11-15-16-19-20-14-12-9-4-2 x1 1.93 2 r2 9-12-14-13-10-8-6-5-4-2 x2 1.39 3 r3 1-3-7-11-15-16-19-23-22-26-27-24-20-13-10-8-6-5-4-2- x3 2.46 4 r4 20-24-31-30-29-33-41-48-49-42-35-28-25-21-18-17 x4 3.10 5 r5 36-38-50-53-43-44-51-46-45-40-39-34-32-29 x5 3.11 6 r6 36-38-50-53-57-58-66-62-70-67-54-55-56-48-52-47-41-33-29-27- x6 3.68 7 r7 1-3-7-9-10-8-6-5-4-2- x7 1.14 8 r8 36-38-50-53-57-58-66-62-70-67-64-68-69-65-61-60-63-56-55-52-47 x8 3.76 9 r9 16-19-23-22-26-27-29-32-33-41-47-52-55-56-48-49-42-35-30-31-28-25-21-18-17 x9 3.36 10 r10 50-53-57-58-66-62-70-67-59-54-64-68-69-65-61-60-63-56-48-49- x10 3.91 11 r11 15-16-19-20-24-27-29-32-33-41-47-52-55-56-48-49-42-36- x11 3.35 12 r12 1-3-7-11-12-13-14-15-16-19-20-24-23-22-26-27-29-32-33-30-31-28-25-21-18-17 x12 3.21 13 r13 1-3-7-11-15-16-19-23-22-26-34-39-32-29-27-33-30-31-24-20-14-13-12-9-2 x13 3.06 14 r14 1-3-7-11-50-53-57-58-62-66-70-67-59-54-51-46-45-40-39-44-43-37-34-38-36-34- 26-22-23-24-20-19-16-15-14-12-13-9-10-8-6-5-4-2- x14 4.19 15 r15 1-3-7-11-12-14-15-16-19-20-24-23-22-26-27-29-32-33-41-48-49-42-35-30-31-28-25-21-18-17- x15 3.51 16 r16 1-3-7-11-12-14-15-20-24-27-29-32-33-41-47-52-55-54-59-64-67-70-68-69-65-61-60-63-56-48-49- 42-35-30-31-28-25-21-18-17 x16 3.81 17 r17 1-3-7-11-16-36-38-50-53-57-58-66-62-70-67-68-64-59-54-51-43-44-45-46-40-39-37-34-26-22-23 -19-16-15-14-12-9 x17 3.79 18 r18 1-3-7-11-50-53-57-58-62-66-70-67-64-68-69-65-61-60-63-55-52-47-54-59-51-46-45-40-39-44-43- 37-34-38-36-34-26-22-23-24-20-19-16-15-14-12-13-9-10-8-6-5-4-2- x18 4.79 19 r19 1-3-7-11-12-14-15-20-24-27-29-32-33-41-47-52-55-46-45-40-39-34-36-38-37-43-44-51-54-59-64- 67-70-68-69-65-61-60-63-56-48-49-42-35-30-31-28-25-21-18-17 x19 4.39 20 r20 1-3-7-6-5-4-2 x20 1.05 21 r21 1-3-7-11-12-9-2 x21 1.16 22 r22 1-3-10-13-8-6-5-4-2 x22 1.19 23 r23 1-3-7-11-14-12-9-2 x23 1.31 24 r24 1-3-7-11-14-13-8-6-5-4-2 x24 1.37 25 r25 1-3-7-11-14-12-9-10-8-6-5-4-2 x25 1.42 26 r26 9-10-14-13-8-6-5-4-2 x26 1.39 27 r27 15-16-19-23-22-26-24-20 x27 2.29 28 r28 15-16-19-23-22-26-20-24-17 x28 2.4 29 r29 15-16-19-23-22-26-27-24-20-17 x29 2.46 30 r30 17-24-27-28-25-21-18- x30 2.43 31 r31 17-24-27-30-31-28-25-21-18- x31 2.45 32 r32 17-24-27-29-32-33-30-31-28-25-21-18- x32 2.62 33 r33 15-19-23-22-26-32-29-27-24-20 x33 2.43 34 r34 24-27-29-32-33-30-31-28-25-21-18 x34 2.61 35 r35 36-38-37-34-39-40-32 x35 2.75 36 r36 36-38-43-37-34-39-44-45-46-40-32 x36 2.91 37 r37 36-38-43-37-34-39-44-45-46-40-32-29-27 x37 2.93 38 r38 18-21-25-28-31-30-29-32- x38 2.54 39 r39 31-35-42-49-48-56-55-52-47-41-33-30 x39 2.98 40 r40 50-53-43-44-45-46-51-52-47-41-33 x40 3.09 41 r41 31-30-33-41-47-52-55-60-63-56-48-49-42-35 x41 3.11 42 r42 33-41-47-52-55-61-60-63-56-48-49 x42 3.12 43 r43 40-45-51-59-54-61-60-63-56-48-49- x43 3.2 44 r44 57-58-66-62-70-67-64-59-54- x44 3.32 45 r45 61-54-59-64-67-70-68-69-65-63-60- x45 3.48 46 r46 57-58-66-62-67-64-70-68-69-65-61-59-54 x46 3.57 47 r47 1-3-5-4-2 x47 0.87835 48 r48 7-9-10-8-6 x48 1.14 49 r49 11-12-14-15-13 x49 1.59 50 r50 16-19-23-22-20 x50 2.1 51 r51 17-28-25-21-18 x51 2.24 52 r52 26-32-29-27-24 x52 2.38 53 r53 30-33-41-42-35-31 x53 2.71 54 r54 36-38-37-39-40-34 x54 2.75 55 r55 43-51-46-45-44 x55 2.82 56 r56 50-53-57-58-66-62 x56 3.16 57 r57 54-59-64-67-70-68 x57 3.19 58 r58 61-65-69-63-60 x58 3.18 59 r59 47-52-55-56-48-49 x59 2.96 34 La programación se muestra a continuación para la zona de San Juan de Miraflores: Se tiene las variables rk, donde k=1, 2,3…, etc. por la existencia de k rutas las cuales recorren todos los puntos de distribución. Se utiliza una variable binaria xk, que indica si es que la ruta es tomada o no, es decir se escoge entre los valores de 0 y 1. La programación se muestra a continuación: Min: 1.93X1 + 1.39X2 +2.46X3 + 3.10X4 +3.11X5 + 3.68X6 + 1.14X7 + 3.76X8 + 3.36X9 + 3.19X10 + 3.35X11 + 3.21X12 + 3.06X13 + 4.19X14 + 3.51X15+3.81X16+3.79X17+4.79X18+4.39X19+1.05x20+1.16x21+1.19x22+ 1.31x23+1.37x24+x1.42x25+1.39x26+2.29x27+2.4x28+2.46x29+2.43x30+2. 45x31+2.62x32+2.43x33+2.61x34+2.75x35+2.91x36+2.93x37+2.54x38+2.9 8x39+3.09x40+3.11x41+3.12x42+3.2x43+3.32x44+3.48x45+3.57x49 Sujeto a: x1+x3+x7+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x47 = 1 x1+x2+x3+x7+x13+x14+x18+x20+x21+x22+x23+x24+x25+x26+x47=1 x1+x2+x3+x7+x14+x18+x20+x22+x24+x25+x26+x47=1 x2+x3+x7+x14+x18+x20+x22+x24+x25+x26+x47=1 x1+x3+x7+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x23+x24+x25+x48=1 x2+x3+x7+x14+x18+x22+x24+x25+x26+x48=1 x1+x2+x7+x13+x14+x17+x18+x21+x23+x25+x26+x48=1 x2+x3+x7+x14+x18+x22+x25+x26+x48=1 x1+x3+x12+x13+x14+x15+x16+x17+x18+x19+x21+x23+x24+x25+x49=1 x1+x2+x12+x13+x14+x15+x16+x17+x18+x19+x21+x23+x25+x49=1 x2+x3+x12+x13+x14+x18+x22+x24+x26+x49=1 x1+x2+x12+x13+x14+x15+x16+x17+x18+x19+x23+x24+x25+x26+x49=1 x1+x3+x11+x12+x13+x14+x15+x16+x17+x18+x19+x27+x28+x29+x33+x49=1 x1+x3+x9+x11+x12+x13+x14+x15+x17+x18+x27+x28+x29+x50=1 x4+x9+x12+x15+x16+x19+x28+x29+x30+x31+x32+x51=1 x4+x9+x12+x15+x16+x19+x30+x31+x32+x34+x38+x51=1 x1+x3+x9+x11+x12+x13+x14+x15+x17+x18+x27+x28+x29+x33+x50=1 x1+x3+x4+x11+x12+x13+x14+x15+x16+x18+x19+x27+x28+x29+x33+x50=1 x4+x9+x12+x15+x16+x19+x31+x32+x34+x38+x51=1 x3+x9+x12+x13+x14+x15+x17+x18+x27+x28+x29+x33+x50=1 x3+x9+x12+x13+x14+x15+x17+x18+x27+x28+x29+x33+x50=1 x3+x4+x11+x12+x13+x14+x15+x16+x18+x19+x27+x28+x29+x30+x31+x32+x33+x52=1 x4+x9+x12+x15+x16+x19+x31+x32+x34+x38+x51=1 x3+x9+x12+x13+x14+x15+x17+x18+x27+x28+x29+x33+x52=1 x3+x6+x9+x11+x12+x13+x15+x16+x19+x29+x30+x31+x32+x33+x34+x37+x52=1 x4+x9+x12+x15+x16+x19+x30+x31+x32+x34+x38+x51=1 x4+x5+x6+x9+x11+x12+x13+x15+x16+x19+x32+x33+x34+x37+x38+x52=1 x4+x9+x12+x13+x15+x16+x19+x31+x32+x34+x38+x39+x41+x53=1 x4+x9+x12+x13+x15+x16+x19+x31+x32+x34+x38+x39+x41+x53=1 x5+x9+x11+x12+x13+x15+x16+x19+x32+x33+x34+x35+x36+x37+x38+x52=1 x4+x6+x9+x11+x12+x13+x15+x16+x19+x32+x34+x39+x40+x41+x42+x52=1 x5+x13+x14+x17+x18+x19+x35+x36+x37+x54=1 x4+x9+x15+x16+x19+x39+x41+x53=1 35 x5+x6+x8+x11+x14+x17+x18+x19+x35+x36+x37+x54=1 x14+x17+x18+x19+x35+x36+x37+x54=1 x5+x6+x8+x14+x17+x18+x19+x35+x36+x37+x54=1 x5+x13+x14+x17+x18+x19+x35+36+x37+x54=1 x5+x14+x17+x18+x19+x35+x36+x37+x43+x54=1 x4+x6+x9+x11+x15+x16+x19+x39+x40+x41+x42+x53=1 x4+x9+x11+x15+x16+x19+x39+x41+x53=1 x5+x14+x17+x18+x19+x36+x37+x40+x55=1 x5+x14+x17+x18+x19+x36+x37+x40+x43+x55=1 x5+x14+x17+x18+x19+x36+x37+x40+x55=1 x6+x8+x9+x11+x16+x18+x19+x39+x40+x41+x42+x59=1 x4+x6+x9+x10+x11+x15+x16+x19+x39+x41x+42x+x43+x59=1 x4+x9+x10+x11+x15+x19+x39+x41+x42+x43+x59=1 x5+x6+x8+x10+x14+x17+x18+x40+x56=1 x5+x14+x17+x18+x19+x40+x43+x55=1 x6+x8+x9+x11+x16+x18+x19+x39+x40+x41+x42+x59=1 x5+x6+x8+x10+x14+x17+x18+x40+x56=1 x6+x10+x14+x16+x17+x18+x19+x43+x44+x45+x46+x57=1 x6+x8+x9+x11+x16+x18+x19+x39+x41+x42+x59=1 x6+x8+x9+x10+x11+x16+x19+x39+x41+x42+x43+x59=1 x6+x8+x10+x14+x17+x18+x44+x46+x56=1 x6+x8+x10+x14+x17+x18+x44+x46+x56=1 x10+x14+x16+x17+x18+x19+x43+x44+x45+x46+x57=1 x8+x10+x16+x18+x19+x41+x42+x43+x45+x58=1 x8+x10+x16+x18+x19+x42+x43+x45+x46+x58=1 x6+x8+x10+x14+x17+x18+x42+x44+x56=1 x8+x10+x16+x18+x19+x41+x42+x43+x45+x58=1 x8+x10+x16+x17+x18+x19+x44+x45+x46+x57=1 x8+x10+x16+x18+x19+x45+x46+x58=1 x6+x8+x10+x14+x17+x18+x44+x46+x56=1 x6+x8+x10+x14+x16+x17+x18+x19+x44+x45+x46+x57=1 x8+x10+x16+x17+x18+x19+x45+x46+x57=1 x8+x10+x16+x18+x19+x45+x46+x58=1 x6+x8+x10+x14+x16+x17+x18+x19+x44+x45+x46+x57=1 36 El gráfico 11, muestra el reporte del programa LINDO que nos da la solución (seleccionados de amarillo) y así hallar las rutas que conformarán la Gran ruta. Gráfico 11: Reporte LINDO – San Juan de Miraflores Elaboración Propia Al obtener la solución a través del programa LINDO, se procede a elaborar las rutas según lo que indica la solución. En el reporte generado por LINDO las rutas a utilizar son las que tienen el valor de 1 en la columna VALUE, por ello se debe utilizar 3 rutas: Ruta 7, ruta 45, ruta 49, ruta 50, ruta 51, ruta 52, ruta 53, ruta 54, ruta 55, ruta 56 y ruta 59. 37 Para unir estas rutas se evaluó la menor distancia que existe entre los puntos más cercanos entre ellas y así poder unirlos y formar la Gran Ruta Ideal. El gráfico 12 muestra las 11 rutas que nos permitirá poder hallar la ruta ideal. Gráfico 12: Rutas seleccionadas – San Juan de Miraflores Ruta 7 Ruta 49 Ruta 45 Ruta 59 Ruta 56 Ruta 54 Ruta 53 Ruta 52 Ruta 50 Ruta 51 Ruta 55 Elaboración Propia 38 El gráfico 13, presenta la Gran Ruta Ideal de San Juan De Miraflores Gráfico 13: Gran Ruta Ideal - San Juan De Miraflores Elaboración Propia 39 El gráfico 14, presenta la Gran Ruta Real de San Juan De Miraflores Gráfico 14: Gran Ruta Real – San Juan De Miraflores Elaboración Propia 40 3.3 Construcción del modelo propuesto 3   Para este modelo se utilizará la Heurística de inserción secuencial de Mole & Jameson, la cual permitirá a través de rutas establecidas donde los puntos lejanos a estas puedan unirse a las rutas de acuerdo a la mínima distancia que se encuentre de la ruta donde se desee insertar. Se aprovechará las rutas que están establecidas del algoritmo de Ahorros, en la cual se quitará los puntos de reparto que son lejanos a la ruta para así poder evaluar en qué otras rutas se puede insertar o caso contrario dejar el punto en su ruta inicial. Para este modelo se ha diseñado las rutas en las cuales los puntos lejanos se han dejado de lado para que sean evaluados de acuerdo a su distancia como se mencionó anteriormente. Los puntos que se evaluarán para su inserción son aquellos que tienen dos opciones de entrar en cualquier ruta es por ello que serán evaluados si es optimo insertarlos en otras rutas que no sea la inicial. A continuación las rutas generadas por el algoritmo de Ahorros y los puntos que quedan sueltos, los cuales serán evaluados: Solo se aplicará este modelo a la zona de VMT (Villa María del Triunfo) ya que en la zona de San Juan de Miraflores todos los puntos son cercanos entre sí, no existe puntos que sean lejanos y en el cual no aplicaría para este modelo. 41 En el gráfico 15, se muestra la ruta de cada clúster y se ve a los puntos enumerados, los cuales serán evaluados en el algoritmo. Gráfico 15: Rutas de Villa María del Triunfo - Puntos lejanos de las rutas Elaboración Propia 1516 17 18 22 21 20 19 25 39 41 42 43 44 45 42 Para el desarrollo de este algoritmo se realiza las medidas ideales de las distancias de los puntos en evaluación a las rutas ya establecidas con lo cual se logrará decidir a qué ruta irá cada punto. La tabla 8, muestra la evaluación de los puntos para la inserción: Tabla 8: Evaluación de puntos de para la inserción N° punto Ruta Actual Distancia a Ruta Roja (m) Distancia a Ruta Verde (m) Distancia a Ruta Azul (m) Distancia a Ruta Amarilla (m) 15 Roja 244.38 209.89 16 Verde 407.62 489.69 17 Verde 436.38 441.64 18 Verde 355.31 356.16 19 Verde 318.23 20 Verde 286.13 21 Verde 228.56 22 Verde 236.48 137.41 25 Verde 113.52 269.02 39 Azul 209.98 208.04 40 Azul 188.83 220.26 41 Azul 150.69 461.67 42 Azul 145.16 535.79 43 Azul 147.51 616.14 44 Azul 326.92 554.85 540.49 45 Azul 422.92 649.42 558.97 Elaboración Propia Las celdas pintadas de color verde y azul son los puntos que han sido seleccionados debido a que la distancia es menor con respecto a las otras rutas. Identificadas las rutas en las cuales se insertarán los puntos se procede a construir la Gran Ruta Real que será la final y la cual será comparada con las otras Grandes Rutas desarrolladas en los algoritmos anteriores. 43 El gráfico 16, muestra la Gran Ruta Real de Villa María del Triunfa Gráfico 16: Gran Ruta – Villa María del Triunfo Elaboración Propia 44 CAPITULO 4. EVALUACION DE RESULTADOS 4.1 Evaluación cuantitativa La tabla 9, muestra la situación actual del reparto de las zonas Villa María Del Triunfo y San Juan De Miraflores con respecto a la distancia recorrida por el transportista. Tabla 9: Distancia recorrida actual Zona Villa María del Triunfo San Juan de Miraflores Distancia Recorrida (km.) 38.75 26.25 Elaboración Propia 4.1.1 Algoritmo de Ahorros Zona Villa María Del Triunfo Al desarrollar el Algoritmo de Ahorros: La distancia recorrida según la solución generada por el algoritmo indica que la ruta que realizaría sería de 28.50 kilómetros, esto supone que aproximadamente la unidad recorrerá esta distancia en todo su reparto. Zona San Juan De Miraflores La distancia recorrida según la solución obtenida por el desarrollo del algoritmo sería de 15.35 kilómetros, aproximadamente esta distancia recorrerá la unidad al realizar su reparto. 45 La tabla 10, muestra las distancias recorridas al aplicar el algoritmo de ahorros para ambas zonas. Tabla 10: Distancia según Algoritmo Ahorros Algoritmo de Ahorros Zona Villa María del Triunfo San Juan de Miraflores Distancia Recorrida (km.) 28.50 15.35 Elaboración Propia 4.1.2 Algoritmo de Pétalos Zona Villa María Del Triunfo La solución generada por este Algoritmo indica que la distancia que se recorrería sería aproximadamente de 30.85 kilómetros. Zona San Juan De Miraflores La distancia por recorrer al resolver el Algoritmo sería aproximadamente de 16.40 kilómetros, significa que la unidad se desplazaría esa distancia en todo su reparto. Tabla 11: Distancia Recorrida Algoritmo de Pétalos Zona Villa María del Triunfo San Juan de Miraflores Distancia Recorrida (km.) 30.85 16.40 Elaboración Propia 46 4.1.3 Algoritmo de Inserción En el desarrollo de este algoritmo solo se evaluó la zona de Villa María del Triunfo y la solución indica que se recorrería 28.63 kilómetros en toda la ruta de reparto. La tabla 12 muestra la distancia recorrida al aplicarse el Algoritmo de Inserción. Tabla 12: Distancia Recorrida Algoritmo de Inserción Algoritmo de Inserción Zona Villa María del Triunfo Distancia Recorrida (km.) 28.63 Elaboración Propia La tabla 13 , muestra un cuadro comparativo de los resultados del desarrollo de los algoritmos para ambas zonas en estudio: Tabla 13: Cuadro Comparativo Zona Villa María del Triunfo San Juan de Miraflores Situación actual 38.75 26.25 Algoritmo de Ahorros 28.50 15.35 Algoritmo de Pétalos 30.85 16.40 Algoritmo de Inserción 28.63 No aplica Elaboración Propia 47 CAPITULO 5. CONCLUSIONES Y RECOMENDACIONES 5.1 Conclusiones - Con relación a la solución de los problemas se llega a concluir que el Algoritmo de Ahorros es el que permitirá la optimización de las rutas de distribución con respecto a los otros dos algoritmos. - Cabe resaltar que la empresa cuenta con una flota homogénea de combis, los cuales poseen un motor gasolinero de 2000 cc, 4 cilindros, con un rendimiento promedio de 30 Km. por galón, siendo el costo promedio del galón de 90 octanos es S/. 15.00. - La aplicación del Algoritmo de Ahorros es relativamente fácil con relación a los otros algoritmos desarrollados, además del tiempo de ejecución ya que el Algoritmo de Pétalos es el que tomó más tiempo de entender y ejecutarlo. - En la zona San Juan de Miraflores la reducción de la cantidad de kilómetros respecto a la ruta diseñada es considerable con la situación actual siendo la distancia actual de 26.25 Km. comparado con la solución del algoritmo que es de 15.35 Km, es decir que se ahorra por campaña en kilómetros recorridos 10.90 y en dinero S/. 5.45, significa que al año por las 36 campañas se ahorraría S/ 196.20. - Para la zona de Villa María del Triunfo se logra reducir 10.25 Km al aplicar el algoritmo de Ahorros, es decir S/. 5.13 por campaña y al año sería S/. 184.50. - El Algoritmo de Inserción es interesante con relación a la aplicación ya que permite de manera instantánea la solución, en nuestro caso solo aplica a una zona la del distrito de Villa María Del Triunfo el cuál 48 se logra ahorrar 10.13 km que en dinero es S/. 5.06 y por las 36 campañas sería S/. 182.16. - Si se optara por escoger el algoritmo de pétalos, ahorraríamos para la zona de Villa María del Triunfo 7.90 km (S/. 3.95) y para la zona de San Juan de Miraflores 9.85 Km. (S/. 4.925). - Los ahorros en gasolina se reflejarían de una mejor forma si el estudio se aplicara a todas las zonas de reparto en la ciudad de Lima. - Estos ahorros que se logran al aplicar los algoritmos, no solo nos permite tener un ahorro en la distancia recorrida sino también generará un ahorro de tiempo y de costo respecto al combustible y el recorrido. 5.2 Recomendaciones - Para el algoritmo de Ahorros que logró optimizar las rutas con mejores resultados se puede analizar también el tiempo, y el costo que implica la ruta escogida. - Cada ruta optimizada por los algoritmos, al ser plasmados en el mapa real deben de ser trazadas según las señales viales de tránsito correctas para reflejar un resultado que se acerque a la realidad. - Los transportistas deberían de rutear los puntos de reparto antes de empezar con la distribución ya que así podrán reflejar cómo van a realizar el reparto en las zonas. Esto les generará un ahorro de tiempo ya que los transportistas pierden tiempo al realizar su ruteo en plena zona. 49 - El resultado de los algoritmos podría mostrar mejores resultados si se tuviesen pocos puntos de reparto, para las empresas en las que los transportistas tienen diariamente unos 15 a 20 puntos y la aplicación de los algoritmos les podría generar mayores ahorros. 50 REFERENCIAS BIBLIOGRAFICAS  OLIVERA, Alfredo 2004. Heurística para Problemas de Ruteo de Vehículos Montevideo: Instituto de Computación, Facultad de Ingeniería, Universidad de la República.  APPLEGATE, David 2006. “Dantzig, Fulkerson, and Johnson”. The traveling salesman problem: a computational study. New Jersey: Princeton University Press. pp. 81 – 93.  CLARKE, G., WRIGHT, W 1964 “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research 12. pp 568–581.  CORDEAU, F., DESAULNIERS, G., DESROSIRES, J., SOLOMON M., SOUMIS, F. 1999 The VRP with time windows. Technical Report Cahiers du GERAD G-99-13, Ecole des Hautes Etudes Commerciales de Montreal  DANTZIG, G., FULKERSON, D. 1954 Solution of a large scale traveling salesman problem. Operations Research 2 pp 393–410.  MARTELLO, S., TOTH, P 1990, Knapsack problems: algorithms and computer implementations. John Wiley and Sons.  MOLE, R.H., JAMESON S.R. 1976 A sequential route-building algorithm employing a generalised saving criterion. Operational Research Quarterly 503-511.  LIN, S 1965 Computer solutions of the travelling salesman problem. Bell System Technical Journal 2245-2269.  CHRISTOFIDES, N., MINGOZZIi, A., TOTH, P. 1979 The Vehicle Routing Problem. In: Combinatorial Optimization 315-338. 51  GILLET, B., MILLER, L. 1974 A heuristic algorithm for the vehicle-dispatch problem. Operations Research 22 340–349.  BRAMEL, J., SIMCHI-Levi, D. 1995 A location based heuristic for general routing problems. Operations Research 43 (1995) 649–660 52 Anexo 1: Direcciones en orden de ruta Actual – San Juan de Miraflores 1 Mz C Lte 12 36 Mz A Lte 14 2 Mz D Lte 2 37 Mz H Lte 5 3 Mz. LL Lte.7 38 Mz K Lte 4 4 Mz D Lte 9 39 Mz H Lte 10 5 Mz B Lte 21 40 Mz H Lte 15 6 Mz. L Lte 13 41 Mz F Lte 47 7 Mz H Lte 4 42 Mz F Lte 37 8 Mz J Lte 12 43 Mz G Lte 12 9 Mz LL Lte 21 44 Mz H Lte 15 10 Mz J Lte 23 45 Mz H Lte 46 11 Mz J Lte 20 46 Mz B Lte 13 12 Mz F Lte 11 47 Mz A Lte 17 13 Mz G Lte 34 48 Mz L Lte 19 14 Mz E Lte 10 49 Mz P Lte 1 15 Mz D Lte 29 50 Mz M Lte 37 16 Mz D Lte 32 51 Mz G Lte 32 17 Lilas Mz E Lte 9 52 Mz F Lte 6 18 Mz F Lte32 53 Mz E Lte 48 19 Mz I Lte 23 54 Mz N Lte 23 20 Mz I Lte 12 55 Mz G Lte 5 21 Mz H Lte 46 56 Mz A Lte 22 22 Mz H Lte 44 57 Mz K Lte 24 23 Mz H Lte 30 58 Mz B Lte 15 24 Mz A Lte 4 59 Mz J Lte 28 25 Mz. A Lte 5 60 Mz E Lte 36 26 Mz A Lte 18 61 Mz I Lte 8 27 Mz K Lte 20 62 Mz I Lte 15 28 Mz A Lte 30 63 Mz I Lte 26 29 Mz H Lte 23 64 Mz F Lte 13 30 Mz I Lte 28 65 Mz F Lte 22 31 Mz A2 Lte 14 66 Mz E Lte 7 32 Mz A2 Lte 21 67 Mz D Lte 28 33 Mz A2 Lte 26 68 Mz C Lte 36 34 Mz A Lte 37 69 Mz B Lte 3 35 Mz A1 Lte 15 70 Mz B Lte 35 53 Anexo 2: Direcciones en orden de ruta Actual – Villa Maria del Triunfo 1 Miguel Grau 2320 31 Ferrocarril 512 2 Bolognesi 1990 32 Las dunas Mz 111 Lte 2 3 Lucanas 157 33 Ferrocarril 101 4 Saenz Peña 120 34 Lima 117 5 Miguel Grau 2042 35 Inmaculada Mz. A Lte 1 6 Alfonso Ugarte 2005 36 Libertad 207 7 Nicolas de Pierola 1740 37 Praderas Mz B Lte. 7 8 Castilla 482 38 Av. Lima Mz 14 Lte 2 9 Castilla 167 39 Ica 127 10 Lima 1795 40 Jr. Lima Mz 43 Lte 1 11 Bolognesi Mz 163 41 Arequipa 176 12 Leoncio Prado 367 42 Manco Capac 999 13 Caceres 256 43 Rimac 799 14 Agricultura 100 44 Rimac 698 15 Zarumilla 1489 45 Jose De San Martín 2016 16 Zarumilla 1979 46 Marañon 241 17 Ferrocarril 1250 47 Mariam Quimper 149 18 Tacna 1097 48 Tarma 1369 19 Iquitos 478 49 Lima 1035 20 Ayacucho 960 50 Agricultura 1747 21 Iquitos 202 51 Rimac 121 22 Supe 235 52 Agricultura 1675 23 Nazca 289 53 Urubamba 134 24 Nazca 176 54 Simon Bolivar 979 25 Lima 1640 55 San Martin 1163 26 Lambayeque 140 56 San Martin 1264 27 Lambayeque 278 57 Mariam Quimper 1480 28 Lambayeque 467 58 Alcides Carrion 128 29 Ayacucho Mz. 40 59 Chilca 231 30 Apurimac 340 60 Putumayo 1490 54 Anexo 3: Gráficos para la aplicación del algoritmo de Ahorros Clúster inicial - Villa María Del Triunfo 55 Ruta ideal de Clústers – Villa Maria Del Triunfo 56 Gran Ruta Ideal – Villa María del Triunfo 57 Ruta Final en plano real – Villa María del Triunfo Ruta para el 1° cluster (rojo)-VMT Almacén 59 Ruta para el 2° cluster (verde)-VMT Almacén 60 Ruta para el 3° cluster (azul) Almacén 61 Ruta para el 4° cluster (amarillo) Elaboración Propia Almacé 62 Ruta para el 1° cluster (azul)-SJM Almacén 63 Ruta para el 2° cluster (rojo)-SJM Almacén 64 Ruta para el 3° cluster (amarillo)-SJM Almacén 65 Ruta para el 4° cluster (verde)-SJM Almacén 66 Ruta para el 5° cluster (celeste)-SJM Anexo 4: Cuadros para la aplicación del algoritmo de Ahorros 1 °Cluster (rojo)   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  0  1 0 0  0 0 0 0 0 0 0  0 0 1 0 0   1  64978 64972  65075 65046 65049 65070 64950 65041 65056  65033 65001 64935 64991 65063     2  65177  65111 65117 65134 65139 65140 65150 65196  65124 65080 65002 65073 65180       3  65147 65195 65251 65277 65295 65320 65394  65280 65230 65146 65230 65365         4  65274 65276 65277 65276 65268 65276  65260 65226 65159 65217 65290           5  65404 65404 65404 65397 65401  65386 65352 65279 65342 65418             6  65601 65600 65593 65587  65583 65545 65470 65536 65615               7  65801 65792 65760  65784 65744 65664 65736 65813        T=0          8  66122 66016  66184 66137 66050 66135 66200        misma ruta            9  66094  66152 66098 66004 66106 66222        Ahorro  max              10  66071 66030 65938 66062 66263                       11  66346 66254 66350 66393                         12  66507 66590 66510                           13  66672 66496                             14  66664                               15                                                                  ruta  0  13  14  15  12  11  8  9  10  7  6  5  4  3  2  1  0  68 2° Cluster(verde)-VMT   16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  0  1 0  0  0 0 0 0 0  0 0 0 1 0 0  0    16  66183.3  66204.92  66340.5 66199.95 66207.38 66196.48 66182.08  66174.3  66182.84 66118.44 66075.62 66016.24 66047  65989.22      17  66374.46  66540.9 66393.14 66386.79 66391.2  66329.5  66317.62 66338.8  66239.5  66169.85 66110.31 66154.65  66089.45        18  66666.9 66533.92 66541.94 66531.24 66494.69  66482.81 66501.74 66404.61 66327.46 66271.27 66317.86  66251.1          19  66847.57 66826.64 66850  66750.72  66738.3  66776.32 66637  66527.44 66481.5  66543.12  66471.55            20  66756.3  66776.37 66681.64  66669.63 66708.83 66564.55 66446.06 66404.34 66469.23  66398              21  66822.02 66765.25  66752.36 66787.79 66648.45 66525.25 66486.69 66553  66481.34                22  66888.87  66892.67 66975.08 66755.5  66580.73 66574.9  66664.2  66584.32    T=0               23  67127.19 67138.91 67006.5  66809.54 66825.54 66913.11  66841.15    misma  ruta                 24  67250.63 67108.93 66868.62 66927.49 67028.97  66960.2    Ahorro  max                   25  67125.68 66864.89 66955.5  67089.48  67034.57                        26  66907.97 66996.41 67084.07  67011.55                          27  66860.19 66887.25  66833.71                            28  67147.19  67130.02                              29  67227.74                                30                                                                  RUTA                0  27  28  29  30  26  24  25  23  22  19  20  21  18  17  16  0  69 3° Cluster (azul)-VMT   31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  0  0  0  0  0  1  0  0  0  0  0  1  0  0  0  0    31  67257.21  67223.42  67274.73 67213.26 67252.71 67276.13 67270.58  67097.97 67023.61 66817.49 66768.37 66711.81 66877.24  66879.68      32  67467.35  67491.77 67243 67388.56 67487.68 67502.28  67196.58 67093.04 66866.62 66819.38 66766.19 66956.96  66973.67        33  67573.96 67221.8 67436.51 67641.37 67713.1  67250.28 67121.27 66884.65 66841.34 66792.06 67006.17  67038.9          34  67309.86 67540.57 67675.56 67675.78  67348.3 67226.68 66991.05 66946.9 66896.7 67105.62  67131.12            35  67362.04 67336.99 67313.93  67237.18 67167.15 66962.57 66914.05 66858.01 67024.3  67025              36  67641.38 67608.87  67505.63 67385.66 67147.55 67105.04 67055.55 67263.38  67284.08                37  67887.8  67503.06 67352.36 67109.07 67071.85 67028.63 67261.72  67305.09                  38  67485.66 67325.6 67081.45 67046.99 67006.27 67249.3  67303.65         T=0            39  67670.96 67455.91 67433.92 67399.74 67635.45  67657.79         misma  ruta              40  67436.28 67397.96 67349.7 67535.69  67531.22         Ahorro  max                41  67512.14 67455.51 67550.9  67530                          42  67564.26 67621.61  67606.71                            43  67664.82  67674.38                              44  67959.22                                45                                                                                                    RUTA                             0  35  31  32  33  38  37  34  36  40  39  44  45  43  42  41  0  70 4° Cluster(amarillo)-VMT   46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0    46  68358.6 68187.42  68189.7 68168.4 68216.98 68130.9 68129.04 68229.31 68344.13 68369.21 68342 68372.85 68391.7  68372.69      47  68376.18  68400.1 68383.69 68437.29 68351.63 68351.7 68452.24 68563.93 68580.03 68556.93 68572.99 68570.62  68574.65        48  68520.72 68497.74 68514.83 68450.27 68434.76 68505.33 68460.92 68461.52 68523.65 68481.68 68432.8  68511.98          49  68674.54 68693.83 68628.78 68614.47 68684.6 68527.4 68537.82 68670.33 68598.11 68524.03  68653.93            50  68852.96 68814.44 68797.75 68856.62 68528.99 68549.92 68764.61 68654.89 68559.23  68751.47              51  68912.72 68911.23 68990.36 68597.65 68628.34 68898.06 68770.27 68662.24  68889.72                52  69160.98 69175.06 68510.39 68542.65 68860.37 68709.32 68590.96  68884.97                  53  69396.78 68518.51 68559.61 68924.56 68762.58 68637.45  68994.91                    54  68625.22 68671.75 69055.69 68894.06 68766.76  69155.27                      55  68740.22 68732.04 68738.32 68710.79  68744.44                        56  68792.8 68813 68790.71  68815.93                          57  69038.63 68911.18  69182.88                            58  68972.82  69098.87                              59  68989.61                                60                                                                                                  RUTA  0  48  49  50  51  52  54  53  57  60  58  59  56  55  47  46  0  71 1° Cluster (azul)-SJM   1  2  3  4  5  6  7  8  9  10  11  12  13  14  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0    1  54506.03 54527.2  54497.54 54494.26 54505.29 54522.75 54494 54519.67 54509.51 54523.58 54521.01 54503 54525.82      2  54584.04  54611.31 54605.9 54613.57 54601.29 54602.49 54613.38 54611.96 54605.72 54611.06 54607.9 54618.34        3  54601.3 54613.66 54637.87 54675.86 54627.4 54667.55 54651.44 54675.8 54672.9 54643.45 54676.52          4  54693.76 54698.33 54658.31 54688.84 54686.03 54693.83 54670.81 54682.19 54691.84 54693.26            5  54782.44 54713.68 54774.53 54758.94 54776.6 54737.74 54755.92 54776.6 54771.11              6  54791.77 54888.75 54861.3 54893.1 54836.43 54864.3 54893.24 54885.53                7  54804.66 54887.7 54853.48 54920.65 54912.15 54851.84 54916.54      misma  ruta             8  54891.47 54956.63 54876.1 54914.15 54978.93 54954.61      t=0               9  54946.12 54955.73 54975.89 54944.27 54984.64      ruta                 10  54937.42 54977.34 55011.78 55011.36                        11  55051.36 54960.11 55068.69                          12  55007.81 55103.47                            13  55084.03                              14                                                                                                                          RUTA  0  1  3  7  9  11  12  14  13  10  8  6  5  4  2  0  72 2° Cluster (rojo)-SJM   15  16  17  18  19  20  21  22  23  24  25  26  27  28  0  1  0  0  0  0  0  1  0  0  0  0  0  0  0    15  55479.9 55349.37  55259.85 55484 55458.17 55251.33 53194.41  55481.86 55435 55280.76 55480.43 55462.02 55321.59      16  55261.56  55348.16 55658.56 55605.79 55352.37 55684.64  55671.21 55579.52 55392.8 55667.26 55611.69 55449.14        17  55606.19 55528.97 55611.07 55603.35 55554.16  55577.39 55693.62 55628.27 55645.53 55692.34 55657.5          18  55435.19 55522.24 55701.66 55472.63  55493.78 55639.1 55705.97 55586.41 55663.59 55713.98            19  55706.38 55445.76 55749.16  55756.48 55680.69 55490.52 55757.67 55710.53 55549.79              20  55538.35 55741.55  55764.06 55771.17 55584.68 55797.85 55784.71 55643.52                21  55503.04  55520.61 55679.51 55835.99 55637.63 55736.06 55837.56                  22  55896.86 55762.44 55564.15 55953.56 55859.61 55645.53        misma  ruta             23  55779.28 55577.75 55916.66 55848.16 55625.91        t=0               24  55739.91 55884.95 55931.66 55809.04        ruta                 25  55711.8 55819.66 55942.03                          26  56037.84 55808.02                            27  55926.15                              28                                                                                                                          RUTA  0  15  16  19  23  22  26  27  24  20  17  18  25  28  21  0  73 3° Cluster (amarillo)-SJM   29  30  31  32  33  34  35  36  37  38  39  40  41  42  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0    29  56138.28  56099.96  56227.44 56212.18 56180.12 56113.55 56136.26  56176.97 56143.99 56226.09 56242.31 56221.7 56121.68      30  56201.82  56130.65 56224.22 56084.32 56193.75 56042.19  56085.65 56051.53 56149.08 56178.38 56226.49 56196.16        31  56093.59 56194.3 56047.61 56199.46 56004.84  56048.95 56015.33 56114.73 56146.13 56203.89 56200.36          32  56221.58 56253.14 56120.47 56209.56  56250.66 56217.48 56296.07 56307.28 56251.03 56132.63            33  56184.55 56238.72 56145.57  56190.23 56156.31 56260.44 56291.91 56336.03 56248.82              34  56090.47 56356.77  56393.6 56363.14 56382.82 56364.84 56320.16 56107.35                35  56057.11  56104.02 56071.91 56181.74 56220.44 56304.34 56398.83                  36  56433 56481.63 56373.41 56352.14 56210.91 56077.5      misma  ruta               37  56445.29 56419.5 56397.71 56258.1 56124.68      t=0                 38  56390.65 56370.02 56226.79 56093.89      ruta                   39  56479.26 56337.8 56204.77                          40  56376.78 56244.67                            41  56346.19                              42                                                                                                                                                        RUTA  0  29  32  34  36  38  37  39  40  41 42 35 33 30  31  0  74 4° Cluster (verde)-SJM   43  44  45  46  47  48  49  50  51  52  53  54  55  56  0  0  0  0  0  1  0  0  1  0  0  0  0  0  0    43  56520 56478.7  56424.49 56363.64 56295.96 56255.47 56514.81  56515.32 56414.95 56557.53 56513.65 56431.31 56362.61      44  56519.16  56504.35 56403.94 56335.64 56295.22 56454.65  56546.5 56452.02 56505.9 56535.08 56464.62 56397.68        45  56544.3 56444.8 56375.56 56335.64 56414.35  56563.78 56488.66 56468.68 56550.02 56497.18 56432.39          46  56479.55 56411.6 56371.28 56400.55  56576.22 56524.2 56457.36 56572.34 56531.23 56467.54            47  56488.76 56450.48 56300.33  56493.39 56566.73 56360.71 56536.11 56563.23 56525.1              48  56597.68 56235.91  56435.15 56555.27 56301.56 56510.67 56577.52 56630.21                49  56194.26  56393.12 56512.82 56259.18 56469.23 56536.62 56603.27        misma  ruta           50  56461.15 56358.48 56619.48 56476.67 56379.99 56310.71        t=0             51  56556.72 56526.45 56646.05 56575.36 56506.64        ruta               52  56425.37 56630.92 56675.01 56622.89                        53  56551.81 56451.17 56383.35                          54  56672.37 56610.2                            55  56671.62                              56                                                                                                                          RUTA  0  47  49  48  56  52  55  54  51  46  45  44  43  53  50  0  75 5° Cluster (celeste)-SJM   57  58  59  60  61  62  63  64  65  66  67  68  69  70  0  0  1  0  1  0  0  0  0  0  0  0  0  0  0    57  56867.3 56691.53  56565.37 56648.87 56845.29 56530.53 56731.59 56648.45 56890.74 56780.74 56712 56660.04 56786.18     58  56704.9  56577.82 56661.06 56854.5 56544.04 56743.69 56661.24 56885.05 56791.28 56723.35 56672.19 56795.82       59  56711.87 56788.07 56794.56 56674.98 56836.12 56778.88 56775.84 56845.84 56818.11 56881.93 56840.96         60  56832.1 56682.92 56842.4 56796.62 56873.75 56672.83 56790.19 56842.88 56871.51 56801.79           61  56770.14 56802.06 56883.87 56908.51 56760.32 56877.08 56914.63 56906.34 56885.3             62  56653.85 56861.43 56777.11 56961.33 56915.73 56844.66 56791.6 56921.19               63  56874 56866.81 56645.51 56766.45 56829.09 56873.42 56782.55                 64  56896.78 56855.16 56973.02 56956.69 56908.09 56975.13       misma  ruta             65  56775.71 56897.85 56962.38 56994.57 56914.94       t=0               66  56918.82 56849.23 56795.63 56936.18       ruta                 67  56969.46 56915.4 57035.54                         68  56985.55 56991.65                           69  56939.71                             70                                                                                                                                                        TA  0  60  63  64  67  70  68  69  65  61  59  62  66  57  58  0