APLICACIÓN DE UN MODELO DE OPTIMIZACIÓN EN LA PLANEACIÓN DE RUTAS DE LOS BUSES ESCOLARES DEL COLEGIO LICEO DE CERVANTES NORTE

TRABAJO DE GRADO Presentado como requisito parcial para la obtención del título de INGENIERO INDUSTRIAL

AUTOR: JUAN SEBASTIÁN ARIAS ROJAS

DIRECTOR: ING. JOSÉ FERNANDO JIMÉNEZ

PONTIFICIA UNIVERSIDAD JAVERIANA FACULTAD DE INGENIERÍA DEPARTAMENTO DE PROCESOS PRODUCTIVOS BOGOTÁ 2010

1

1.

TABLA DE CONTENIDO INTRODUCCIÓN ........................................................................................................ 6 1.1

2.

3.

OBJETIVOS........................................................................................................ 6

1.1.1

Objetivo General ......................................................................................... 6

1.1.2

Objetivos Específicos .................................................................................. 6

1.2

MOTIVACIÓN ..................................................................................................... 7

1.3

ALCANCE ........................................................................................................... 8

1.4

PLAN DE LECTURA............................................................................................ 8

MARCO TEÓRICO ................................................................................................... 10 2.1

LOGÍSTICA, DISTRIBUCIÓN Y TRANSPORTE................................................ 10

2.2

PROBLEMAS DE PLANEACIÓN DE RUTAS .................................................... 10

2.2.1

El problema del agente viajero (TSP) ......................................................... 10

2.2.2

Planeación de rutas para vehículos con capacidad (CVRP) ....................... 11

2.3

MÉTODOS DE SOLUCIÓN ............................................................................... 12

2.4

OPTIMIZACIÓN POR COLONIA DE HORMIGAS (ACO) .................................. 13

2.5

REVISIÓN DE LA LITERATURA ....................................................................... 15

2.5.1

Aplicación de modelos ACO en problemas de ruteo ................................... 15

2.5.2

Planeación de rutas de escolares ............................................................... 15

DEFINICIÓN DEL SISTEMA..................................................................................... 16 3.1

DESCRIPCIÓN DEL COLEGIO ......................................................................... 16

3.2

DESCRIPCIÓN DEL PROCESO DE TRANSPORTE ESCOLAR ...................... 16

3.3 DESCRIPCIÓN DEL PROBLEMA DE PLANEACIÓN DE RUTAS PARA VEHÍCULOS ................................................................................................................ 18 3.3.1

Variables .................................................................................................... 19

3.3.2

Restricciones .............................................................................................. 19

3.4 COMPARACIÓN ENTRE EL PROCESO DE TRANSPORTE ESCOLAR Y EL PROBLEMA CVRP ...................................................................................................... 19

4.

3.4.1

Variables .................................................................................................... 19

3.4.2

Restricciones .............................................................................................. 20

3.5

SISTEMA A TRABAJAR .................................................................................... 21

3.6

SITUACIÓN DE LA RUTA ACTUAL .................................................................. 21

3.7

FORMULACIÓN MATEMÁTICA ........................................................................ 27

DESARROLLO DEL MODELO DE SOLUCIÓN ........................................................ 30 4.1

ASIGNACIÓN .................................................................................................... 30

4.2

RUTEO .............................................................................................................. 31

4.2.1

Algoritmo de solución ................................................................................. 31

4.2.2

Codificación de algoritmo............................................................................ 35 2

5.

6.

EXPERIMENTACIÓN Y RESULTADOS ................................................................... 40 5.1

DEFINICIÓN DE PARÁMETROS DE EJECUCIÓN ........................................... 40

5.2

RESULTADOS .................................................................................................. 41

5.3

ANÁLISIS DE LOS RESULTADOS ................................................................... 48

5.4

ANÁLISIS DE SENSIBILIDAD ........................................................................... 48

5.5

ANÁLISIS FINANCIERO ................................................................................... 53

CONCLUSIONES Y RECOMENDIACIONES ........................................................... 56 6.1

CONCLUSIONES .............................................................................................. 56

6.2

RECOMENDACIONES ...................................................................................... 57

BIBIOGRAFÍA .................................................................................................................. 58 ANEXOS.......................................................................................................................... 60

3

ÍNDICE DE TABLAS Tabla 1. Correspondencia entre las variables del problema CVRP y las del proceso de transporte escolar. ........................................................................................................... 20 Tabla 2. Ruta inicial de la mañana. .................................................................................. 22 Tabla 3. Resumen de la ruta inicial de la mañana. ........................................................... 24 Tabla 4. Ruta inicial de la tarde. ....................................................................................... 25 Tabla 5. Resumen de la ruta inicial de la tarde. ............................................................... 27 Tabla 6. Parámetros de ejecución del modelo. ................................................................ 41 Tabla 7. Resultados de la ejecución ruta de la mañana ................................................... 42 Tabla 8. Resultados de la ejecución ruta de la tarde ........................................................ 42 Tabla 9. Ruta propuesta de la mañana. ........................................................................... 43 Tabla 10. Resumen de la ruta propuesta de la mañana. .................................................. 45 Tabla 11. Ruta propuesta de la tarde. .............................................................................. 46 Tabla 12. Resumen de la ruta propuesta de la mañana. .................................................. 48 Tabla 13. Comparación de distancias recorridas. Ruta inicial vs. ruta propuesta. ............ 48 Tabla 14. Consumo diario de combustible en la ruta inicial. ............................................. 54 Tabla 15. Consumo de combustible proyectado para la ruta propuesta de la mañana..... 54 Tabla 16. Consumo de combustible proyectado para la ruta propuesta de la tarde. ........ 55 Tabla 17. Ahorro anual proyectado de la ruta propuesta. ................................................. 55

4

ÍNDICE DE FIGURAS Figura 1. Variables y restricciones del proceso de transporte escolar. ............................. 18 Figura 2. Diagrama de flujo de modelo de ACS para la etapa de ruteo. ........................... 33 Figura 3. Código de la función “Información del programa” del algoritmo de solución para la etapa de ruteo. ............................................................................................................. 35 Figura 4. Código de la función “Archivo de datos” del algoritmo de solución para la etapa de ruteo. .......................................................................................................................... 36 Figura 5. Código de la función “Posición inicial” del algoritmo de solución para la etapa de ruteo. ............................................................................................................................... 36 Figura 6. Código de la función “Ciclo de hormiga” del algoritmo de solución para la etapa de ruteo. .......................................................................................................................... 37 Figura 7. Código de la función “Distancia recorrida” del algoritmo de solución para la etapa de ruteo. .......................................................................................................................... 37 Figura 8. Código de la función “Actualización global de la feromona” del algoritmo de solución para la etapa de ruteo. ....................................................................................... 38 Figura 9. Código de la función “Ejecución del programa” del algoritmo de solución para la etapa de ruteo.................................................................................................................. 38 Figura 10. Análisis de sensibilidad del parámetro I. ......................................................... 49 Figura 11. Análisis de sensibilidad del parámetro K. ........................................................ 50 Figura 12. Análisis de sensibilidad del parámetro q0. ....................................................... 51 Figura 13. Análisis de sensibilidad del parámetro β. ........................................................ 51 Figura 14. Análisis de sensibilidad del parámetro ρ. ........................................................ 52 Figura 15. Análisis de sensibilidad del parámetro

5

. ....................................................... 53

1. INTRODUCCIÓN El presente trabajo propone el desarrollo de un modelo de optimización basado en la meta-heurística optimización por colonia de hormigas (ACO) para el proceso de planeación de rutas para los buses escolares del colegio Liceo de Cervantes Norte. El proceso de transporte escolar se adapta a uno de los problemas logísticos más conocidos y estudiados: Planeación de rutas para vehículos con capacidad (CVRP). El ruteo de vehículos es un reto importante al que deben enfrentarse actualmente las empresas que cuentan con procesos de distribución. En términos generales, el problema se puede definir como la forma en que se asigna una flota de vehículos similares para transportar una cantidad determinada de productos desde un centro de distribución a un número n de puntos de destino distribuidos geográficamente y volver al punto de origen. Análogamente, la planeación de rutas escolares asigna una flota de buses para recoger un número de alumnos en diferentes paradas distribuidas en la ciudad y llevarlos al colegio y, de la misma forma, llevarlos de vuelta a sus casas una vez terminan las clases. El objetivo es encontrar la ruta mínimo costo. Los problemas de CVRP son considerados de tipo NP-Hard. Esto significa, en teoría computacional, que para problemas de tamaño mediano o grande no es posible encontrar una respuesta óptima en un intervalo de tiempo razonable. Por esta razón, los algoritmos de optimización tradicionales son ineficaces para atacar este tipo de problemas. Sin embargo, los modelos heurísticos y meta-heurísticos permiten encontrar en un tiempo considerablemente corto una solución que, aunque no garantiza ser óptima, tiene muy buenos resultados en la práctica. Optimización por colonia de hormigas (ACO) es un método meta-heurístico que, a pesar de ser relativamente nuevo, ha sido muy utilizado para resolver problemas NP-Hard. La literatura provee varias investigaciones que evidencian que el ACO tiene un desempeño particularmente bueno en problemas de ruteo de vehículos. La aplicación de este procedimiento en la planeación de las rutas de los buses pretende mejorar teóricamente la eficiencia del proceso de transporte escolar del colegio Liceo de Cervantes Norte. Los objetivos del trabajo se detallan a continuación. 1.1 OBJETIVOS 1.1.1 Objetivo General Diseñar una propuesta de planeación de rutas para los buses escolares del colegio Liceo de Cervantes Norte a través del desarrollo de un modelo de optimización, que permita reducir los costos involucrados y mejorar la eficiencia del proceso. 1.1.2 Objetivos Específicos A. Definir el sistema a trabajar con el fin de realizar la modelación matemática del problema y determinar su situación actual.

6

B. Desarrollar un modelo de solución basado en la meta-heurística Optimización por colonia de hormigas (ACO) para resolver el problema de ruteo de los buses escolares. C. Seleccionar la ruta propuesta a través de la ejecución del modelo y explorar el resultado por medio de un análisis de sensibilidad. D. Realizar una evaluación económica para determinar la efectividad del modelo propuesto, a través una comparación entre los resultados obtenidos y la situación inicial del proceso. 1.2 MOTIVACIÓN Con el correr de los años, el uso de herramientas tecnológicas se ha vuelto común en la búsqueda de eficiencia en los procesos de las empresas de cualquier sector. Establecer una ventaja competitiva en términos de reducción de costos puede marcar la diferencia entre ser el líder de una industria y desaparecer del mercado y, por esta razón, la investigación de operaciones ha empezado a desempeñar un papel muy importante no sólo en el diseño de productos, sino también de procesos. No es extraño encontrar ejemplos de compañías que gracias a la aplicación de modelos matemáticos consiguieron mejorar procesos ineficientes que antes se administraban únicamente basados en la experiencia y la intuición. La planeación de las rutas de los buses del Liceo de Cervantes es uno de esos procesos que se diseñan con base en experiencia e intuición. Por esta razón, la idea de este trabajo es desarrollar un modelo de optimización que permita resolver el problema de ruteo y entregar una solución factible que recorra la menor distancia posible. Esta solución servirá como una herramienta de toma de decisiones que, junto con el conocimiento empírico, permitirá diseñar una ruta más eficiente que siga cumpliendo con los requerimientos de los estudiantes y del colegio. Encontrar una ruta más corta traerá enormes beneficios: En primer lugar, recorrer una menor distancia implica consumir una menor cantidad de combustible y, teniendo en cuenta el alto precio de la gasolina en Colombia, esta reducción produciría un impacto muy positivo en las finanzas del colegio. En segundo lugar, minimizar los trayectos reducirá también el desgaste del vehículo, lo que permitirá ampliar los intervalos entre cada mantenimiento y prolongar su vida útil. En tercer lugar, el problema del transporte no es sólo un asunto de costos que impacta a una empresa; También es un asunto ambiental. El consumo de energía del sector del transporte es la tercera parte de la energía consumida en Estados Unidos, y el 85 por ciento de esa energía es utilizada en el transporte terrestre (Waters, 2003 P 240). Por lo tanto, reducir el consumo de combustible de los buses ayudará a reducir en alguna medida la contaminación del aire, problema que ya es bastante grave en una ciudad como Bogotá. Generalmente, las empresas que ven el de ruteo de vehículos como un problema de ingeniería son aquellas que cuentan con flotas de cientos de camiones y distribuyen toneladas de mercancía y productos dentro de una vasta región geográfica. Empresas especializadas en mensajería, o las dedicadas a la producción de bebidas gaseosas y cerveza son el tipo de organizaciones para las que tener una ruta eficiente para sus 7

vehículos es fundamental es la reducción de costos y la satisfacción del cliente. Por esta razón, la mayoría de trabajos de aplicación se enfocan en este tipo de empresas. Sin embargo, la literatura provee algunos trabajos de optimización de rutas escolares, principalmente en Estados Unidos. En estos trabajos, el problema se plantea como un CVRP, utilizando diferentes modelos de optimización para obtener una solución. La razón para que el tema de las rutas escolares haya llamado la atención de los investigadores es que en las ciudades americanas es una tarea de enormes proporciones. Según Braca, en la ciudad de Nueva York, 83.000 estudiantes deben ser recogidos y dejados en 19.000 paradas de bus, para ser llevados a uno de los 750 colegios por alguno de los 1.150 buses escolares disponibles. Esto involucra un presupuesto anual cercano a los 100 millones de dólares (Braca et al., 1997 P 693). Los buenos resultados de estos trabajos motivan a seguir investigando sobre el tema, buscando nuevos métodos de solución para resolver el problema. 1.3 ALCANCE El problema CRVP da una muy buena aproximación al contexto real de transporte de estudiantes en buses escolares. Sin embargo, en el proceso real intervienen una gran cantidad de variables y no todas pueden ser tenidas en cuenta en el modelo matemático. Un modelo de la investigación de operaciones se define como una representación idealizada (simplificada) de un sistema de la vida real (Bernabé, 2009 P 4). Por lo tanto, es necesario definir el sistema que se va a trabajar con las variables que se usarán en la modelación matemática, y probablemente algunos factores reales no podrán ser tenidos en cuenta en la modelación del sistema, ya sea porque son complejos de cuantificar o medir, o porque levantar esta información tomaría demasiado tiempo. Al no poder modelar todas las variables reales, la ruta propuesta entregada por el modelo no garantizará ser la ideal en todos los tramos del recorrido real. La ruta ideal deberá integrar la solución de un modelo científico con el conocimiento empírico del proceso. El trabajo de grado pretender entregar la parte científica, determinando una ruta propuesta que optimice las variables modeladas, y que sirva como punto de partida para ser analizada y modificada por el coordinador de rutas y de esta forma establecer la ruta que será implementada en la práctica. Debido a que el ACO es una estrategia de solución heurística y no exacta, no se puede garantizar que las respuestas obtenidas serán las óptimas globales del problema. 1.4 PLAN DE LECTURA El trabajo está distribuido de la siguiente forma: En la sección 2 se presenta el marco teórico que fundamenta el trabajo. Primero desarrolla los conceptos básicos de logística, distribución y el problema específico de ruteo de vehículos, exponiendo los métodos existentes para solucionarlo. Posteriormente presenta el modelo de solución ACO y reseña algunos trabajos previos encontrados en la literatura. 8

En la sección 3 se describe el proceso de transporte escolar del colegio, comparándolo con el problema CVRP. Esto permite definir el sistema a trabajar y realizar la modelación matemática del problema. La sección 4 presenta la estrategia de solución con base en la meta-heurística ACO desarrollada para determinar la ruta propuesta. La sección 5 muestra la ruta propuesta para los buses determinada a través de la experimentación con el algoritmo. Además, se explica el comportamiento del modelo por medio de un análisis de sensibilidad. Finalmente, la sección 6 expone las conclusiones generales del trabajo y se presentan algunas recomendaciones para proyectos futuros.

9

2. MARCO TEÓRICO 2.1 LOGÍSTICA, DISTRIBUCIÓN Y TRANSPORTE La logística puede ser definida como “la planeación y organización del suministro y movimiento de materias o bienes desde la fuente original a través de las etapas de producción, ensamble, embalaje, almacenamiento, manejo y distribución al cliente final (Lowe, 2002 P 147). Además del flujo de materia desde el proveedor hasta el cliente final, la logística también maneja un flujo de información en sentido inverso, desde el cliente final hasta el proveedor. La logística entonces busca administrar de forma eficiente toda la cadena de abastecimiento, minimizando los tiempos y costos involucrados y maximizando la utilidad y la satisfacción del cliente. Y la distribución es una etapa crítica. Se ha demostrado que el 90% del total del tiempo de ciclo de la cadena corresponde a tiempos de movimiento y/o espera, con lo que la reducción de este tiempo constituye en el reto más importante de la función logística [...] De ahí resalta la importancia de administrar efectivamente el proceso de distribución o entrega a nuestros clientes ya sean internos o externos (El lenguaje global de los negocios Año 6 No. 11, 2005). La llegada de la globalización ha redefinido la forma en la que las empresas administran y toman decisiones logísticas. Las oportunidades de acceder a la demanda internacional y obtener ingresos en nuevos mercados implican grandes desafíos, sobre todo para las empresas pequeñas. Y con el aumento de la demanda viene un aumento del volumen de producción y de distribución. En el caso de productos manufacturados, el aumento de la producción conllevará inevitablemente a un aumento en el volumen de material que debe ser transportado, tanto del producto terminado, como de la materia prima para fabricarlo. Con la globalización, el número de clientes será mucho mayor, y además muchos de ellos estarán muy lejos, algunos, probablemente al otro lado del mundo. Entonces, el reto de la distribución crece por el número de lugares a los que se debe llegar y la distancia que hay que recorrer para alcanzarlos. Si el objetivo es hacerlo al menor costo posible, tener rutas eficientes para los vehículos será vital para lograrlo. 2.2 PROBLEMAS DE PLANEACIÓN DE RUTAS 2.2.1 El problema del agente viajero (TSP) El estudio científico de la planeación de rutas inició en 1959 con la publicación de “The Truck Dispatching Problem” por Dantzig y Ramser. Después de esto, se formuló el muy conocido y ampliamente estudiado problema de agente viajero (TSP). El enunciado es sencillo: una persona debe partir desde una ciudad, visitar un número determinado de ciudades geográficamente distribuidas, y volver a la ciudad inicial. El objetivo es determinar la ruta de mínimo costo que visite todas las ciudades una vez y vuelva al punto de partida. Aunque el problema tiene pocas variables y restricciones, y es en apariencia sencillo, su solución práctica es sumamente difícil debido al astronómico número de combinaciones 10

de las rutas posibles. Por esto, en la teoría computacional, es un problema de gran complejidad por el tiempo que se tarda en ser resuelto. Éste puede solucionarse con una gran cantidad de métodos, desde algoritmos manuales sencillos, como el vecino más próximo, hasta complejos modelos computacionales. Ésta es la razón por la que el TSP tiene tanta importancia dentro de la literatura y la gran mayoría de algoritmos disponibles lo han atacado. Si bien el TSP es un problema teórico de gran complejidad, éste no es muy aplicable en una situación real de distribución de mercancía. Si los clientes que debe visitar el agente viajero demandan una cantidad determinada de producto, éste debería tener una capacidad ilimitada para transportar producto, o al menos una capacidad superior a la suma de todas las demandas de los clientes. Por lo tanto, si un sólo agente no tiene capacidad para suplir la demanda de todos los clientes, es necesario un grupo de agentes para poder entregarla cantidad demandada a todos los clientes. 2.2.2 Planeación de rutas para vehículos con capacidad (CVRP) El problema CVRP agrega una nueva variable al TSP: la cantidad de producto, tanto para la demanda de los clientes como para la capacidad de los vehículos. Las características del problema CVRP son las siguientes: Se tiene un grupo de clientes distribuidos geográficamente en una zona definida. Además, se tiene un depósito que abastecerá de un único producto a todos los clientes. Los clientes están separados, entre sí y con el depósito, por una distancia conocida. Cada cliente tiene una demanda constante de producto conocida, y deben ser visitados por una flota de vehículos idénticos con una capacidad limitada. Los vehículos están ubicados inicialmente en el depósito donde inicia cada una de las rutas, después visitar un subgrupo de clientes y finalmente volver al depósito. El subgrupo de clientes que visitará cada vehículo está restringido por su capacidad limitada, es decir, que la suma de las demandas de los clientes que visita un vehículo debe ser igual o menor a la capacidad de dicho vehículo. Cada cliente debe ser visitado por un solo vehículo. Además, se asume que el depósito cuenta con una oferta “ilimitada” del producto, es decir, que la cantidad de producto disponible en el depósito es igual o mayor que la suma de las demandas de todos los clientes. Adicionalmente, asume que la flota de vehículos es lo suficientemente grande como para satisfacer la demanda de todos los clientes, es decir, que la suma de las capacidades de todos los vehículos es mayor o igual que la suma de las demandas de todos los clientes. Esto significa que todos los clientes serán satisfechos en la totalidad de su demanda. En el Anexo 1 se encuentra la formulación matemática del CVRP. Cuando al CVRP se le agregan diferentes variables y restricciones reales de transporte, se generan distintos tipos de problemas. Éstos se pueden clasificar con base en la combinación de muchas características. Estas son algunas de ellas: único o múltiples depósitos, flota heterogénea (vehículos con diferentes capacidades), periódicos (los clientes pueden ser servidos únicamente en días específicos de la semana), ventanas de tiempo (cada cliente puede ser atendido sólo en ciertas horas del día), pick-up and delivery (además de entregar mercancía, también se puede recoger) y 11plit delivery (un 11

cliente puede ser atendido por más de un vehículo). Pero sin importar cuales de estas variables deban ser incluidas en el problema, el objetivo siempre será resolver la siguiente pregunta: ¿Cuál es la ruta de menor costo? El costo de la ruta puede tomar diferentes formas: El tiempo, la distancia, el consumo de combustible, entre otras. Sin embargo, el fin siempre será minimizarlo. 2.3 MÉTODOS DE SOLUCIÓN El objetivo del CVRP es minimizar el costo de la ruta. En otras palabras, optimizar las rutas de los vehículos. Por esto, la optimización es la metodología de investigación de operaciones en donde se encuentra la mayoría de los métodos de solución para este problema. La optimización nace de la necesidad de buscar eficiencia en las actividades económicas cotidianas. Los factores de un proceso productivo se cuantifican en variables numéricas para buscar la minimización de los costos o maximización de su utilidad. Para problemas pequeños se puede utilizar herramientas como la programación lineal, programación entera mixta o programación dinámica, que permiten encontrar rápidamente respuestas óptimas con un correcto desarrollo del modelo. Sin embargo, cuando los problemas son más grandes y el número de variables y restricciones aumenta, el conjunto de soluciones factibles crece hasta tal punto que no es posible encontrar el óptimo en un intervalo razonable de tiempo. Por lo tanto, un modelo de solución efectivo debe estar basado tanto en la calidad de la respuesta como en el tiempo de procesamiento que se requiere para alcanzarla. Como se mencionó anteriormente, los problemas de CVRP son de tipo NP-Hard, por lo que las mejores soluciones se obtienen a través de modelos heurísticos y metaheurísticos, El término “heurístico” proviene del griego heuriskein, que significa “descubrir”. Su definición es la siguiente: Un método heurístico es un procedimiento para resolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución (Marti, 2003 P 2). Los métodos heurísticos son utilizados cuando los problemas son tan grandes que no se conoce su solución óptima, y en caso de existir, su procesamiento computacional es excesivamente costoso o toma demasiado tiempo. También pueden ser utilizados como parte de un proceso global de solución óptima, en etapas iniciales o intermedias, para después buscar mejores soluciones con otros métodos de optimización combinatoria. Sin embargo, las aproximaciones de los métodos heurísticos son muchas veces estancamientos en óptimos locales y sus resultados pueden estar demasiado lejos del óptimo global. El prefijo “meta” significa más allá. Esto es precisamente lo que buscan los metaheurísticos: trascender las soluciones obtenidas con los heurísticos tradicionales. El 12

término fue acuñado por Glover en 1986. Los modelos meta-heurísticos apuntan a resolver problemas a los que los heurísticos tradicionales no dan soluciones convincentes. El mismo Glover los define de la siguiente manera: “Meta-heurísticos, en su definición original, son métodos de solución que facilitan una interacción entre procedimientos de mejora locales y estrategias de más alto nivel, para crear un proceso capaz de evitar estancamientos en óptimos locales y así realizar una búsqueda robusta dentro espacio de solución (Glover, 2003 P 12). Éstas características tan importantes que diferencian los heurísticos de los metaheurísticos han incentivado en los últimos años el desarrollo de nuevos modelos de este tipo y su aplicación para resolver problemas de Investigación de Operaciones. 2.4 OPTIMIZACIÓN POR COLONIA DE HORMIGAS (ACO) La meta-heurística Optimización por colonia de hormigas fue implementada por Dorigo y Di Caro en 1990 para ser utilizado en la resolución problemas muy complejos de optimización combinatoria. Al igual que otros meta-heurísticos, como el algoritmo genético, está inspirado en analogías biológicas que se encuentran en la naturaleza. Su método de búsqueda de soluciones está basado, como su nombre lo indica, en el comportamiento de las hormigas para encontrar alimento. Cuando una hormiga encuentra un camino corto entre su hormiguero y una fuente de alimento, deja a su paso una feromona de rastreo que es percibida por las demás hormigas que la rodean. Si la ruta hacia el alimento es buena, cada vez más y más hormigas pasarán por el camino, dejando su feromona y haciendo que la señal química se intensifique. Si por el contrario el camino no es muy bueno, las demás hormigas no lo tomarán y la feromona se evaporará. En la práctica, la elección entre distintos caminos toma lugar cuando varios caminos se cruzan. Entonces, las hormigas eligen el camino a seguir con una decisión probabilística sesgada por la cantidad de feromona: cuanto más fuerte es el rastro de feromona, mayor es la probabilidad de elegirlo (Alonso et al., P 4). El proceso finaliza en el momento en el que todas las hormigas de la colonia converjan al camino más corto de todos los posibles. Análogamente, el ACO utiliza “hormigas” artificiales representadas por agentes algorítmicos que se comunican entre sí con una “feromona artificial”. Cada hormiga determina su camino a través de un grafo de construcción dado, denotado G=(N, A), en donde N representa todos los nodos del grafo, y A, los arcos que los conectan. Cada arco (i, j) tiene asociada una variable , que es el rastro de feromona presente en el arco, el cual se actualizan constantemente dependiendo del número de hormigas que tomen este camino. De esta forma, la feromona artificial mide la “deseabilidad” aprendida de ir del nodo i al nodo j. Entre más hormigas tomen este camino, aumentará el valor de la feromona y la probabilidad de que en el futuro las demás hormigas viajen por este arco será mayor. Por el contrario, si el camino no es bueno el rastro de feromona presente se evaporará y la probabilidad de que éste sea tomado se reducirá.

13

Dorigo y Stützle (2004) explican el funcionamiento del algoritmo ACO de la siguiente forma: Una hormiga k construye una solución iniciando su recorrido en el nodo fuente y viajando de un nodo a otro hasta llegar al nodo de destino. En cada paso, la hormiga k escoge su siguiente movimiento con base en una decisión probabilística calculada de la siguiente forma:

es el vecindario de la hormiga k cuando está en el nodo i, es decir, los el sub-grupo de nodos que están conectados directamente con i. α es un parámetro. La hormiga k ejecuta esta política de decisión paso a paso hasta llegar al nodo de destino. En ese momento, se tiene una solución completa de la hormiga k. Una vez allí, inicia el camino de vuelta hasta la fuente para actualizar la feromona. En el camino de vuelta, la hormiga pasa exactamente por los mismos arcos que tomó durante la construcción de la solución y actualiza su rastro de feromona. La hormiga deposita una cantidad en cada arco (i, j) que visitó. Entonces, el valor de la feromona cambia así:

El valor de puede ser constante o una función que depende de la calidad de la solución obtenida por la hormiga. (Según un experimento descrito por Dorigo y Stützle, un valor de basado en la solución permite una más rápida convergencia del algoritmo). Adicionalmente, la evaporación reduce el rastro de feromona en todos los arcos del grafo con la siguiente ecuación:

[0,1] es un parámetro. Esta evaporación evita que los niveles de feromonas crezcan demasiado en las primeras instancias del proceso de búsqueda, lo que causaría que una convergencia demasiado rápido en soluciones sub-óptimas (Dorigo & Stützle, 2004 P 12 – 15). Entonces, una iteración del algoritmo ACO consta de estas tres acciones: movimiento de la hormiga, evaporación de feromona y depósito de feromona. La optimización por colonia de hormigas basa sus buenos resultados en el comportamiento cooperativo de los agentes que generan las soluciones del algoritmo. El poder compartir información entre las hormigas permite una búsqueda robusta basada en la calidad de las soluciones y la evaporación de la feromona evita que el algoritmo caiga 14

en óptimos locales, logrando así respuestas satisfactorias en tiempos de procesamiento razonable. 2.5 REVISIÓN DE LA LITERATURA 2.5.1 Aplicación de modelos ACO en problemas de ruteo Bullnheimer, Hartl y Strauss (1999) realizaron la implementación del modelo de ACO para resolver el problema VRP. Posteriormente, el mismo grupo de autores mejoró el modelo complementándolo con una función heurística local con el fin de construir soluciones más robustas. Gambardella (1999) realizó una de las implementaciones con mejores resultados demostrados en solución de problemas VRP con ventanas de tiempo, a través de un modelo multi-objetivo que basado en dos colonias de hormigas. Este modelo es conocido como el MACS-VRPTW. Guntsch, Middendorf y Schmeck (2001) utilizaron un modelo ACO para resolver el problema TSP dinámico, en el cual algunas de las ciudades son borradas y otras nuevas son insertadas en intervalos de tiempo determinados. Hermosilla y Barán (2003) implementaron un sistema de colonia de hormigas para resolver el problema VRP y compararon los resultados con los obtenidos a través de una estrategia evolutiva. Gajpal y Abad (2009) utilizaron el ACO para resolver el problema de VRP con “pick-up and delivery” simultáneos, en el que los vehículos además de dejar productos donde los clientes, también deben recogerlos. 2.5.2

Planeación de rutas de escolares

La literatura también provee varios trabajos sobre ruteo de buses escolares. Inicialmente, Newton y Thomas (1969) resolvieron el problema para un solo colegio utilizando el modelo del agente viajero. Una vez obtuvieron la ruta de menor distancia, la dividieron en rutas individuales para cada bus de acuerdo a su capacidad. Bodin y Breman (1979) resolvieron el problema para un área suburbana de 13.000 alumnos distribuidos en 25 colegios. A través de dos componentes que permitían modificar ligeramente la secuencia inicial de los nodos y dividir las paradas de bus en paradas más pequeñas lograron un ahorro del 20% en los costos. Braca y otros (1995) implementaron un modelo para resolver el problema de rutas escolares en uno de los distritos escolares más grande del mundo: el de la ciudad de Nueva York. Después de realizar una detallada descripción de las características del problema VRP orientada hacia las rutas escolares, Braca corre el algoritmo específicamente para las escuelas del distrito de Manhattan compuesto por 838 paradas de bus y 73 colegios, con el objetivo de minimizar el número de buses que se deben utilizar en el recorrido completo. En Colombia se encuentra el trabajo de grado de Vargas (2005), quien resolvió el problema para las rutas de transporte escolar de la Secretaria de Educación Distrital en la localidad de Usaquén.

15

3. DEFINICIÓN DEL SISTEMA 3.1 DESCRIPCIÓN DEL COLEGIO El Liceo de Cervantes Norte es una institución educativa de padres agustinos que ofrece los niveles de educación preescolar, básica y media. Sus inicios se remontan año 1934 en el centro de Bogotá, pero es en el año 1976 cuando se trasladan a su actual sede en la calle 153 No 19 – 39. El colegio es reconocido a nivel nacional por su excelencia académica gracias a sus destacados resultados en los exámenes de estado, además de su formación en valores y educación integral. Actualmente estudian 1.538 alumnos en el colegio. Cuenta con modernas instalaciones dotadas con laboratorios, salas de informática, coliseo, campos deportivos, una amplia cafetería y buses propios. El colegio presta directamente el servicio de transporte escolar a 538 estudiantes con una flota de 11 buses de su propiedad. Diariamente, los buses realizan dos recorridos. En la mañana recogen a los estudiantes en sus casas y los llevan al colegio. En la tarde, los estudiantes toman los buses en el colegio y son llevados de vuelta a sus casas. Como los buses pertenecen al colegio, son administrados directamente y no se involucra ninguna empresa de transporte para apoyar el proceso, como sucede en muchos de los colegios privados de Bogotá. Por lo tanto, es a la administración del colegio a quien le corresponde asignar cuáles son los alumnos que viajarán en cada bus y la secuencia en la que serán visitados. 3.2 DESCRIPCIÓN DEL PROCESO DE TRANSPORTE ESCOLAR Para poder desarrollar un modelo de solución para el ruteo de los buses escolares, es necesario definir primero el sistema del problema que se va a trabajar. Para esto se hace una descripción de las características del proceso real de transporte escolar y definir cómo éstas serán representadas en un modelo matemático en forma de variables y restricciones. Cuando se planea el recorrido que debe realizar un bus para recoger o dejar a los estudiantes, el tiempo es el factor más importante. La razón es que entre menos tiempo pasen los estudiantes dentro del bus viajando desde sus casas hacia el colegio, más satisfechos se sentirán sus padres y, por ende, la administración del colegio. Si la ruta matutina de un bus es muy extensa los estudiantes deberán despertarse más temprano. Si la ruta de la tarde es muy extensa, podría dificultar las actividades que realizan después de clases. El tiempo que pasan los estudiantes, y cualquier otra persona, transportándose dentro de la ciudad es tiempo inutilizado y, por lo tanto, no es difícil entender por qué es importante reducirlo al máximo. Entonces, el objetivo principal al asignar y planear las rutas es minimizar el tiempo del recorrido de cada uno de los buses. El tiempo es una variable fácil de medir y esto lo hace ideal para determinar la calidad de la ruta escogida. Para comparar dos rutas diferentes que recorren los mismos nodos, la forma más sencilla es calcular el tiempo que tomó cada una y escoger la más corta. El tiempo que tarda un recorrido entre dos puntos es 16

una relación entre dos parámetros: la distancia que se recorre y la velocidad a la que se mueve el vehículo. Para determinar la ruta más rápida lo más lógico es pensar, en un principio, en la ruta más corta en términos de distancia. Cuando se viaja a velocidad constante, el tiempo y la distancia son variables directamente proporcionales. Por esta razón, es necesario conocer la malla vial de la ciudad para saber cuál es el recorrido más corto entre dos puntos. Entre menos distancia recorra la ruta, menor será el tiempo que pasen los estudiantes dentro del bus. La distancia entre dos puntos es un parámetro constante y por lo que es una información confiable en el tema de las rutas. Si la velocidad fuera constante en toda la malla vial, la ruta de menor distancia sería con seguridad la que menor tiempo tomaría recorrer. Sin embargo, en el contexto real, las características de las vías que hacen que la velocidad difiera entre los diferentes tramos de las rutas posibles de un recorrido, lo que implica que la ruta más corta no necesariamente es la más rápida. Las características de los tramos de la malla vial son las siguientes: 





Tráfico: Éste representa el volumen de vehículos que transitan por los diferentes tramos de un recorrido en un intervalo de tiempo. Si una vía tiene un tráfico alto, ésta se congestiona y se reduce la velocidad a la que se puede transitar. Por el contrario, si la vía no tiene mucho tráfico, es posible transitarla más rápidamente. Semaforización: La cantidad los semáforos que se encuentran en un recorrido entre dos puntos, y la duración de éstos indican momentos en el que el bus deberá detenerse por completo. Entre mayor sea el tiempo que debe permanecer el bus detenido en semáforos, menor será la velocidad promedio en este tramo. Estado de las vías: Para principios de 2009, solamente el 38% de la red vial de Bogotá se encuentra en buen estado (El Tiempo 31 de enero de 2009). Cuando las vías no están en el mejor estado buses deben transitarlas más despacio, no sólo porque puede ser peligroso, sino porque el vehículo puede deteriorarse. En algunos casos, las vías llegan a ser intransitables para los buses, debido a que no están muy estropeadas o a que son tan estrechas que el bus no puede transitar por ellas.

Estas tres variables determinan en gran medida la velocidad a la que se puede mover el bus en el recorrido entre dos paradas. Además, el proceso de trasporte escolar está restringido de la siguiente forma: 

Capacidad de los vehículos: Los buses escolares del Liceo de Cervantes Norte tienen una capacidad de 54 pasajeros, por lo que éste es el número máximo que puede transportar cada bus tanto en el recorrido de la mañana como en el de la tarde. Como cada bus debe, por ley, llevar una monitora de ruta, se le pueden asignar un máximo de 54 pasajeros por ruta a cada bus.

17







Tamaño de la flota: El bus cuenta con 11 buses para realizar el proceso de transporte de estudiantes. El colegio no tiene intenciones de ampliar su flota, por lo que el máximo número de estudiantes que puede transportar son 594. Hora de inicio de clases: Debido a que las clases inician a las 6:45 a.m., todos los buses deben llegar a más tardar a las 6:40 a.m. Por lo tanto, los buses deben salir con suficiente antelación como para completar su recorrido y no llegar tarde. Límite de velocidad: Según la legislación, la velocidad máxima de los vehículos que prestan servicio de rutas escolares es de 40 Km/h (Proyecto de acuerdo No. 449 DE 2007). Esta restricción pretende minimizar el riesgo de accidentes y proteger así la integridad de los niños y niñas que viajan en los buses.

La figura 1 muestra un diagrama representativo de la forma cómo interactúan las variables y restricciones identificadas en el proceso de transporte de estudiantes en los buses escolares. Las variables están en verde y las restricciones, en rojo. 

Tamaño de a flota



Capacidad de los vehículos

Tiempo de recorrido

Distancia

Hola de inicio de clases

Límite de velocidad

Velocidad

Tráfico

Semáforos

Estado de las vías Figura 1. Variables y restricciones del proceso de transporte escolar.

3.3 DESCRIPCIÓN DEL PROBLEMA DE PLANEACIÓN DE RUTAS PARA VEHÍCULOS Según Braca y otros, los problemas de ruteo de buses escolares caen dentro del clásico problema de transporte VRP (Vehicle Route Planning) (Braca et al., 1997 P694). Los problemas VRP consisten en atender un grupo de clientes geográficamente distribuidos desde un depósito inicial. Cuando los vehículos que visitan los clientes tienen una 18

capacidad limitada, como en el caso de los buses escolares, el problema se vuelve CVRP (Capacitated Vehicle Route Planning). 3.3.1

Variables

La información requerida en el CVRP es la siguiente:   

 

Un conjunto de nodos de tamaño N que incluye el depósito inicial. Un conjunto de arcos que conectan cada par de nodos, de tal forma que cada uno de los nodos tiene N arcos asociados. Una matriz de costos de tamaño NxN asociada a cada arco. De esta forma, se tiene un costo asociado a viajar desde y hacia cualquiera de los nodos del sistema. Cada uno de los clientes demanda una cantidad específica de un único producto. Se cuenta con una flota de vehículos con una capacidad limitada, ubicada inicialmente en el depósito.

3.3.2

Restricciones

El problema se restringe de la siguiente forma: 

No se puede exceder el número de vehículo, ni la capacidad máxima que estos pueden transportar. Además, cada cliente puede ser visitado únicamente por un vehículo.

El objetivo es encontrar la ruta de menor costo que visite a todos los clientes y vuelva al punto de origen. La formulación matemática del problema CVRP puede encontrarse en el Anexo 1. Al analizar las variables y restricciones del CVRP se puede ver la gran similitud con la planeación de rutas de buses escolares del Liceo de Cervantes Norte. Con base en la comparación realizada en la sección 3.4, se determinará el sistema que se trabajará en el proyecto. 3.4 COMPARACIÓN ENTRE EL PROCESO DE TRANSPORTE ESCOLAR Y EL PROBLEMA CVRP 3.4.1 Variables La tabla 1 muestra la correspondencia entre las variables del CVRP y las del proceso de transporte de estudiantes en los buses escolares

19

CVRP Depósito Inicial Nodos o clientes

Transporte en buses escolares

Colegio Paradas donde se suben o bajan los estudiantes (en la mayoría de los casos son sus casas) Costo asociado a cada Costo asociado a viajar entre un par de paradas del bus. arco entre un par de nodos Demanda asociada a Número de estudiantes que suben o bajan del bus en cada cada nodo o cliente parada (en algunos conjuntos residenciales se suben dos o más estudiantes) Flota de vehículos con Flota de 11 buses propios del colegio capacidad limitada Tabla 1. Correspondencia entre las variables del problema CVRP y las del proceso de transporte escolar.

 Matriz de Costos La matriz de costos es la información que definirá en gran medida el camino que tomará la solución del problema. Ésta se puede definir de la siguiente manera: En la matriz C = (cij) de tamaño NxN, cada valor cij indica lo que cuesta transitar del nodo i al nodo j. Lo más común es que este costo se asuma como tiempo, distancia o consumo de combustible. En este trabajo se asumirá como costo la distancia euclidiana entre los nodos. La decisión se basa en el tiempo y esfuerzo que tomará el levantamiento de los datos. La distancia es una medida fija. La distancia que hay que recorrer para llegar de un punto a otro novaría, siempre que se tome la misma ruta. Por lo contrario, el tiempo es una medida que depende de la velocidad del vehículo, por lo que sería necesario tomar varias medidas con el fin de tener un tamaño de muestra estadísticamente confiable y obtener el promedio. Comparativamente con la distancia, obtener datos de tiempo de recorrido es mucho más largo y dispendioso. Debido al corto tiempo que se dispone para realizar el trabajo y a la cantidad de nodos que tiene el sistema, se decidió por la distancia como la variable de costo para la matriz. Además, la distancia permite calcular el ahorro económico teniendo en cuenta el consumo promedio de combustible de los buses. 3.4.2

Restricciones

Cada bus puede transportar un máximo de 54 estudiantes. Además, la flota de 11 vehículos no puede ser excedida, ya que el colegio no tiene entre sus planes ampliar la flota. Por lo tanto, el máximo número de estudiantes que pueden ser transportados son 594. Al igual que en el CVRP, cada una de las paradas donde se recogen los alumnos puede ser visitado solamente por un bus.

20

3.5 SISTEMA A TRABAJAR El problema bajo estudio requiere la solución de dos problemas de rutas: el de la mañana y el de la tarde. Las soluciones se obtendrán a partir de la minimización del costo total de las rutas de cada bus, el cual está representado por la distancia entre las paradas, distribuidas en un plano cartesiano. Para asignar el par de coordenadas (x, y) de cada parada, se utilizaron las coordenadas geográficas de la tierra. Bogotá se encuentra entre las coordenadas 4°29’ y 4°47’ latitud norte y las coordenadas 74°01’ y 74°12’ longitud oeste. Por medio del programa Google Earth y el mapa callejero de la Alcaldía Mayor de Bogotá1 se ubicaron las paradas en el mapa y se tomaron los datos de minutos y segundos de las coordenadas de cada una. Como las coordenadas geográficas se expresan en grados sexagesimales, éstas se transformaron a coordenadas en unidades de metros, quedando como el nodo (0, 0) el colegio. Un minuto latitudinal es equivalente a 1.855,3 m. y un minuto longitudinal equivale a 1.852,2 m. La información de la dirección y las coordenadas de cada parada de la mañana y de la tarde se encuentran en los Anexos 2 y 3 respectivamente. Las variables del sistema a trabajar se definen a continuación. 

Ruta de la mañana Paradas: 367 Estudiantes transportados: 466 Tamaño de la flota: 11 buses Capacidad de la flota: 54 estudiantes



Ruta de la tarde Paradas: 398 Estudiantes transportados: 521 Tamaño de la flota: 11 buses Capacidad de la flota: 54 estudiantes

3.6 SITUACIÓN DE LA RUTA ACTUAL Con el fin de establecer un punto de partida para comparar los resultados de la aplicación del modelo de optimización, se presentan los datos de las rutas actuales de la mañana y la tarde. Las tablas 2 y 4 muestran las paradas en el orden en el que son visitadas y el número de estudiantes recogidos o dejados en cada una. Los Anexos 4 y 5 contienen información más detallada de las distancias recorridas por las rutas actuales.

1

Disponible en http://www.bogota.gov.co/mad/buscador.php

21



Ruta de la Mañana BUS 1 BUS 2 BUS 3 BUS 4 BUS 5 BUS 6 Orden Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. 0 0 0 0 0 0 0 1 1 1 40 2 142 1 182 1 75 1 110 1 2 2 1 41 1 143 1 183 1 76 1 111 1 3 3 1 42 1 144 1 184 1 77 1 112 1 4 4 1 43 1 145 1 185 1 78 1 113 1 5 5 1 44 1 146 1 186 1 79 1 114 1 6 6 1 45 1 147 1 187 3 80 1 115 1 7 7 1 46 1 148 1 188 1 81 1 116 1 8 8 2 47 1 149 1 189 1 82 2 117 1 9 9 1 48 1 150 1 190 1 83 1 118 1 10 10 1 49 1 151 1 191 1 84 1 119 1 11 11 2 50 1 152 2 192 1 85 1 120 1 12 12 2 51 1 153 1 193 2 86 1 121 1 13 13 1 52 1 154 1 194 1 87 1 122 1 14 14 1 53 2 155 1 195 2 88 1 123 1 15 15 1 54 1 156 1 196 1 89 1 124 1 16 16 1 55 2 157 2 197 1 90 1 125 1 17 17 1 56 1 158 1 198 1 91 1 126 1 18 18 1 57 1 159 1 199 2 92 1 127 1 19 19 1 58 1 160 1 200 1 93 1 128 2 20 20 1 59 1 161 1 201 3 94 1 129 1 21 21 1 60 1 162 2 202 4 95 1 130 2 22 22 1 61 1 163 1 203 1 96 2 131 1 23 23 1 62 1 164 1 204 1 97 1 132 1 24 24 1 63 2 165 2 205 1 98 1 133 1 25 25 1 64 1 166 1 206 1 99 3 134 1 26 26 1 65 2 167 1 207 2 100 1 135 3 27 27 1 66 3 168 1 208 1 101 1 136 1 28 28 1 67 1 169 1 209 1 102 2 137 6 29 29 1 68 2 170 1 210 1 103 2 138 1 30 30 1 69 2 171 1 211 1 104 1 139 1 31 31 2 70 1 172 1 212 1 105 1 140 1 32 32 1 71 1 173 1 0 106 1 141 1 33 33 1 72 1 174 1 107 1 0 34 34 1 73 1 175 1 108 1 35 35 1 74 1 176 1 109 1 36 36 1 0 177 3 0 37 37 1 178 1 38 38 1 179 1 39 39 1 180 1 40 0 181 1 41 0 42 43 Total 39 43 35 44 40 46 31 42 35 41 32 41 Tabla 2. Ruta inicial de la mañana.

22

BUS 7 BUS 8 BUS 9 BUS 10 BUS 11 Orden Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. 0 0 0 0 0 0 1 213 1 269 2 301 1 343 3 236 1 2 214 1 270 1 302 1 344 1 237 1 3 215 3 271 1 303 2 345 1 238 1 4 216 1 272 1 304 1 346 1 239 1 5 217 1 273 1 305 1 347 2 240 1 6 218 1 274 1 306 2 348 1 241 1 7 219 1 275 1 307 1 349 2 242 1 8 220 2 276 1 308 2 350 1 243 1 9 221 2 277 1 309 1 351 1 244 1 10 222 1 278 1 310 1 352 1 245 1 11 223 1 279 2 311 1 353 1 246 1 12 224 2 280 1 312 1 354 2 247 1 13 225 1 281 2 313 1 355 1 248 1 14 226 1 282 1 314 1 356 1 249 1 15 227 1 283 1 315 1 357 1 250 1 16 228 1 284 1 316 2 358 1 251 1 17 229 2 285 2 317 1 359 1 252 2 18 230 2 286 2 318 1 360 2 253 1 19 231 3 287 1 319 3 361 2 254 1 20 232 1 288 1 320 2 362 1 255 1 21 233 2 289 1 321 1 363 1 256 1 22 234 4 290 3 322 1 364 1 257 1 23 235 1 291 2 323 1 365 1 258 2 24 0 292 1 324 1 366 5 259 1 25 293 1 325 1 367 4 260 1 26 294 3 326 2 0 261 1 27 295 3 327 1 262 1 28 296 2 328 1 263 1 29 297 1 329 1 264 1 30 298 1 330 1 265 1 31 299 1 331 1 266 1 32 300 1 332 1 267 1 33 0 333 2 268 1 34 334 1 0 35 335 2 36 336 2 37 337 1 38 338 1 39 339 1 40 340 2 41 341 1 42 342 1 43 0 Total 23 36 32 45 42 54 25 39 33 34 Tabla 2. Ruta inicial de la mañana..

23

La tabla 3 resume la información de la ruta actual de cada bus: el total de paradas visitadas, el total de estudiantes recogidos y el total de la distancia recorrida de la ruta inicial de la mañana. Bus

Total Paradas

Total estudiantes

Distancia recorrida

Bus 1

39

43

12.319,0 m.

Bus 2

35

44

22.124,1 m.

Bus 3

35

41

20.236,0 m.

Bus 4

32

41

33.087,5 m.

Bus 5

40

46

24.099,4 m.

Bus 6

31

42

20.336,2 m.

Bus 7

23

36

11.934,4 m.

Bus 8

33

35

22.190,4 m.

Bus 9

32

45

31.884,5 m.

Bus 10

42

54

14.324,4 m.

Bus 11

25

39

11.028,0 m.

Total

367

466

223.563,9 m.

Tabla 3. Resumen de la ruta inicial de la mañana.

24



Ruta de la Tarde BUS 1 BUS 2 BUS 3 BUS 4 BUS 5 BUS 6 Orden Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. 0 0 0 0 0 0 0 1 1 1 48 1 158 1 204 1 88 1 124 1 2 2 1 49 3 159 1 205 2 89 2 125 1 3 3 1 50 1 160 1 206 1 90 2 126 1 4 4 1 51 2 161 2 207 1 91 1 127 1 5 5 1 52 1 162 1 208 1 92 1 128 1 6 6 2 53 1 163 1 209 1 93 1 129 1 7 7 1 54 2 164 1 210 1 94 1 130 1 8 8 1 55 2 165 1 211 2 95 2 131 1 9 9 1 56 1 166 1 212 1 96 1 132 1 10 10 1 57 2 167 1 213 3 97 1 133 1 11 11 1 58 1 168 1 214 4 98 1 134 1 12 12 1 59 1 169 1 215 1 99 3 135 1 13 13 1 60 1 170 1 216 1 100 1 136 1 14 14 1 61 3 171 1 217 1 101 1 137 1 15 15 1 62 2 172 1 218 1 102 3 138 1 16 16 1 63 1 173 1 219 1 103 1 139 1 17 17 2 64 1 174 1 220 1 104 1 140 2 18 18 1 65 1 175 1 221 3 105 1 141 1 19 19 1 66 1 176 1 222 1 106 1 142 1 20 20 1 67 1 177 2 223 1 107 1 143 1 21 21 1 68 1 178 1 224 1 108 1 144 3 22 22 1 69 1 179 1 225 1 109 1 145 1 23 23 1 70 1 180 1 226 1 110 1 146 1 24 24 1 71 1 181 4 227 1 111 1 147 2 25 25 1 72 1 182 2 228 1 112 1 148 1 26 26 1 73 1 183 1 229 3 113 1 149 1 27 27 1 74 1 184 1 230 2 114 1 150 1 28 28 1 75 1 185 1 231 1 115 1 151 1 29 29 1 76 2 186 1 232 2 116 2 152 3 30 30 1 77 2 187 1 233 1 117 1 153 1 31 31 1 78 1 188 1 234 1 118 1 154 1 32 32 2 79 1 189 1 235 1 119 1 155 5 33 33 1 80 2 190 1 236 1 120 1 156 1 34 34 1 81 1 191 1 0 121 1 157 1 35 35 1 82 1 192 1 122 1 0 36 36 1 83 1 193 1 123 1 37 37 1 84 1 194 2 0 38 38 1 85 1 195 1 39 39 2 86 1 196 1 40 40 3 87 1 197 1 41 41 1 0 198 2 42 42 1 199 1 43 43 2 200 1 44 44 1 201 1 45 45 1 202 1 46 46 1 203 1 47 47 1 0 48 0 Total 47 54 39 52 45 54 32 46 35 44 33 44 Tabla 4. Ruta inicial de la tarde.

25

BUS 7 BUS 8 BUS 9 BUS 10 BUS 11 Orden Parada # Est. Parada # Est. Parada # Est. Parada # Est. Parada # Est. 0 0 0 0 0 0 1 237 1 301 1 333 2 369 1 265 1 2 238 2 302 1 334 1 370 1 266 1 3 239 4 303 1 335 1 371 1 267 1 4 240 1 304 1 336 2 372 1 268 1 5 241 1 305 1 337 2 373 1 269 1 6 242 2 306 1 338 2 374 1 270 1 7 243 1 307 2 339 1 375 2 271 1 8 244 3 308 2 340 1 376 2 272 1 9 245 1 309 1 341 1 377 1 273 1 10 246 3 310 1 342 3 378 2 274 1 11 247 2 311 1 343 1 379 1 275 1 12 248 2 312 1 344 1 380 1 276 1 13 249 1 313 1 345 1 381 3 277 1 14 250 1 314 1 346 1 382 1 278 1 15 251 1 315 2 347 1 383 1 279 1 16 252 2 316 1 348 1 384 1 280 1 17 253 1 317 1 349 1 385 1 281 1 18 254 3 318 1 350 3 386 3 282 1 19 255 1 319 1 351 1 387 3 283 1 20 256 1 320 1 352 1 388 1 284 1 21 257 3 321 1 353 1 389 1 285 1 22 258 2 322 2 354 1 390 1 286 1 23 259 2 323 2 355 2 391 2 287 1 24 260 1 324 1 356 1 392 4 288 2 25 261 2 325 1 357 1 393 1 289 1 26 262 1 326 3 358 1 394 2 290 1 27 263 1 327 2 359 2 395 1 291 1 28 264 1 328 1 360 1 396 1 292 1 29 0 329 1 361 2 397 1 293 1 30 330 3 362 1 398 1 294 1 31 331 3 363 2 0 295 1 32 332 2 364 2 296 1 33 0 365 1 297 2 34 366 1 298 1 35 367 4 299 1 36 368 1 300 2 37 0 0 38 39 40 41 42 43 44 45 46 47 48 Total 27 47 31 45 35 52 29 44 35 39 Tabla 4. Ruta inicial de la tarde.

26

La tabla 5 resume la información de la ruta actual de cada bus: el total de paradas visitadas, el total de estudiantes recogidos y el total de la distancia recorrida de la ruta inicial de la tarde. Bus

Total Paradas

Total estudiantes

Distancia recorrida

Bus 1

47

54

13.945,6 m.

Bus 2

40

52

18.367,8 m.

Bus 3

36

44

24.568,4 m.

Bus 4

34

44

33.546,2 m.

Bus 5

46

54

41.552,3 m.

Bus 6

33

46

26.795,0 m.

Bus 7

28

47

11.957,0 m.

Bus 8

36

39

20.599,8 m.

Bus 9

32

45

32.556,1 m.

Bus 10

36

52

13.537,2 m.

Bus 11

30

44

13.196,4 m.

Total

398

521

250.621,7 m.

Tabla 5. Resumen de la ruta inicial de la tarde.

Sumando las distancias recorridas durante la mañana y la tarde se obtiene que la distancia total del recorrido diario de la ruta inicial de los buses escolares es de 474.185,6 m. 3.7 FORMULACIÓN MATEMÁTICA A continuación se realizará la formulación matemática de los sistemas a trabajar que permitirá modelar y resolver el problema. Esta formulación se basa en la formulación matemática del problema CVRP que se encuentra en el Anexo 1.  Ruta de la mañana Función objetivo:

Sujeto a:

27

 Ruta de la tarde Función objetivo:

Sujeto a:

28

De esta forma el sistema a trabajar queda definido y modelado matemáticamente. La siguiente sección presenta el desarrollo de la estrategia de solución para encontrar la ruta propuesta con base en este sistema.

29

4. DESARROLLO DEL MODELO DE SOLUCIÓN Para desarrollar el modelo de solución se utilizó una estrategia conocida como “agrupar primero, rutear después”, encontrada en trabajos como el de Thangiah (Thangiah, 1995). Ésta consiste en dividir el problema CVRP en dos sub-problema. En primera instancia los nodos se agrupan y se asignan a un vehículo. Después, se toma cada subgrupo de nodos y se resuelve como un problema TSP. En la etapa de agrupación, los subgrupos definidos deben respetar las restricciones de tamaño de la flota y capacidad máxima de los vehículos. En la etapa de ruteo se debe garantizar que cada nodo sea visitado una sola vez. Si se realizara un solo ruteo para todos los nodos, es posible que por la característica de aleatoriedad presente en la decisión probabilística del ACO, algunas soluciones conectaran nodos lejanos. Esto frenaría al algoritmo en su búsqueda de altos niveles de optimalidad. En cambio, al realizar ruteos más pequeños con subgrupos de nodos cercanos previamente agrupados, se evitan estas conexiones lejanas y se aprovecha al máximo el procesamiento del algoritmo. Otro punto a favor de esta estrategia es que permite impedir que pares de nodos que no deben ser visitados por el mismo vehículo, por alguna razón diferente a las restricciones del problema, sean agrupados por el algoritmo. Esta ventaja es importante en el caso bajo estudio y será expuesta en la sección 4.1 Para encontrar la ruta propuesta de los buses escolares las paradas se dividirán manualmente en 11 grupos, uno para cada bus. Posteriormente, se obtendrá la ruta de cada bus utilizando un algoritmo de solución basado en ACO para el problema TSP simétrico. 4.1 ASIGNACIÓN La asignación de las paradas de cada bus se realizo agrupando los nodos cercanos por sectores de la ciudad de forma manual, utilizando como criterio la delimitación de las vías principales de la ciudad, buscando evitar que los buses las crucen durante su recorrido. Las avenidas principales, a diferencia de las secundarias y de las calles entre barrios, sólo pueden ser atravesadas en puntos específicos de la ciudad. Esto implica que para viajar entre un par de nodos separados por una avenida se deba realizar un recorrido mucho más largo que la distancia euclidiana utilizada por el algoritmo. El proceso de agrupación se realizó ordenando las paradas de norte a sur y de occidente a oriente y se utilizaron filtros de Excel para hacer la delimitación de las vías. Después, se iban tomando las paradas consecutivamente, cuidando que cada una fuera asignada a un único bus, y cumpliendo las restricciones de capacidad máxima, tamaño de la flota y que cada parada sea visitada por un solo vehículo. Las asignaciones de los buses para los recorridos de la mañana y de la tarde se encuentran en los Anexos 6 y 7. 30

4.2 RUTEO Para encontrar la ruta propuesta de cada uno de los buses, se utilizó un procedimiento basado en la meta-heurística optimización por colonia de hormigas conocido como ant colony system (ACS). Éste fue propuesto por Dorigo y Gambardella para resolver problemas TSP simétricos y asimétricos (Dorigo & Gambardella, 1996). El modelo utiliza las funciones básicas de movimiento de la hormiga, actualización de la feromona y evaporación de la feromona para encontrar el orden en el que las paradas de cada bus deben ser visitadas de tal forma que el recorrido sea lo más corto posible. La etapa de ruteo debe garantizar que cada parada sea visitada una sola vez y que todas las paradas sean visitadas. De esta forma, todas las restricciones de un problema CVRP son cumplidas por la estrategia de solución. 4.2.1

Algoritmo de solución

Dado el conjunto de nodos V= {v1, …, vn} definido como el subgrupo de de N paradas asignadas a un bus y E = {(i, j), i, j ϵV} el conjunto de arcos entre cada par de nodos. Sea dij la distancia euclidiana asociada a cada arco (i, j). Sea K el número de hormigas de cada ciclo e I el número de ciclos realizados por el algoritmo. Sea la matriz heurística de tamaño NxN donde cada ηij=1/dij corresponde a nivel de deseabilidad de ir desde el nodo i al nodo j. Sea la matriz de feromonas de tamaño NxN donde cada corresponde al nivel de rastro de feromona presente en el arco (i, j). Los valores de la matriz heurística son constantes, mientras que los de la matriz de feromonas se actualizan a lo largo de la construcción de la solución cuyo valor inicial es dado. Cada hormiga parte del colegio y debe recorrer todas las paradas de V y volver al colegio. La hormiga construye la ruta a partir de una decisión probabilística paso a paso, basada en las ecuaciones 1 y 2, descritas a continuación:

donde q es un valor aleatorio de una distribución uniforme [0,1] y q0 (0≤q0≤1) es un parámetro dado. El termino exploración se refiere a la preferencia de una hormiga por escoger rutas que no han sido recorridas, mientras que la explotación utiliza las rutas más recorridas con altos niveles de feromonas. Jk(i) se refiere al conjunto de paradas a las puede ir la hormiga k cuando se encuentra en la parada i, es decir, las paradas que aún no se han visitado. El parámetro β determina la importancia relativa de la función heurística con respecto al rastro de feromona en el momento de la decisión. El valor S está definido por la siguiente distribución probabilística.

31

En cada parada, la hormiga escoge su siguiente movimiento con el cálculo de estas dos fórmulas. Una vez llega al último nodo, vuelve al colegio, calcula la distancia recorrida y actualiza localmente la matriz de feromonas utilizando la siguiente ecuación.

Cuando todas las hormigas del ciclo han realizado el recorrido se escoge la ruta más corta de todas y se premia el recorrido con la actualización global de la feromona, con la siguiente ecuación.

donde Lmc corresponde a la mejor ruta del ciclo. Las ecuaciones 3 y 4 actualizan el rastro de la matriz de feromonas agregando feromona a las rutas recorridas y evaporando la feromona de todos los demás caminos. El valor ρ corresponde al coeficiente de evaporación de feromona. Este proceso se realiza en todos los ciclos del algoritmo. Al finalizar el último ciclo, se escoge la ruta más corta entre las Lmc de cada ciclo, la que será la solución final del algoritmo. Para un mejor entendimiento, la figura 2 muestra el diagrama de flujo del funcionamiento del modelo.

32

Inicio

Definir parámetros: K hormigas I ciclos β, ρ, τ₀, q₀

Determinar matriz de distancias y matriz heurística

Coordenadas de las paradas

Ciclo=1 3 Hormiga=1 2 Posicionar hormigas en el colegio

Parada=1

q=aleatorio [0,1]

SÍ

NO

¿q≤q₀?

Escoger siguiente parada con base en la ecuación 1

Escoger siguiente parada con base en la ecuación 2

Parada=N-1

NO

Parada= Parada+1

SÍ

1

Figura 2. Diagrama de flujo de modelo de ACS para la etapa de ruteo.

33

1

Volver al colegio

Calcular distancia recorrida

Actualizar localmente rastro de feromona con la ecuación 3

NO ¿Hormiga=K?

Hormiga= Hormiga+1

2

Ciclo= Ciclo+1

3

SÍ Determinar la mejor ruta del ciclo Lmc

Actualizar globalmente rastro de feromona con la ecuación 4

NO ¿Ciclo=I? SÍ Imprimir ruta propuesta: mejor Lmc

Fin

Figura 2. Diagrama de flujo de modelo de ACS para la etapa de ruteo.

34

4.2.2

Codificación de algoritmo

Para la codificación del algoritmo del procedimiento de ruteo se utilizo el programa Matlab R2009A. Matlab es un software computacional basado en un ambiente matricial. Su interfaz es bastante amigable, permite ejecutar varias operaciones con un solo comando y facilita la implementación de algoritmos. El problema presentado en este trabajo se basa un grafo de nodos y arcos, por lo que las variables más importantes, como la distancia, la función heurística y el rastro de feromonas están representadas por matrices. Por esta razón, Matlab es un programa ideal para el desarrollo de este modelo de solución. Su ambiente matricial permite una fácil codificación de las funciones y un tiempo de procesamiento eficiente. El código está dividido en siete funciones que se ejecutan desde la pantalla principal del programa. A continuación se describe cada una con su respectivo código fuente. 1. Información del programa Información del programa function [longitud,latitud,matrizdedistancias,rastrodeferomona,matrizheuristica,nu merodeiteraciones,observacion,rastro,coeficientedeevaporacion,numerodehor migas,numerodenodos,primeraparada]=informacionprograma; numerodeiteraciones=200;%número de ciclos. numerodehormigas=200;%número de hormigas. [longitud,latitud]=archivodedatos('T4.tsp');%Comando que importa el archivo con la información de los nodos, latitud y longitud. numerodenodos=length(longitud);%Comando que establece el número de nodos. for i=1:numerodenodos%Generación de la matriz de distancias. for j=1:numerodenodos matrizdedistancias(i,j)=sqrt((longitud(i)longitud(j))^2+(latitud(i)-latitud(j))^2);% Cálculo de la distancia euclidiana entre los nodos. end end coeficientedeevaporacion=.1;%coeficiente de evaporación de la feromona. observacion=2;% Beta importancia de la función heurística en la decisión. rastro=1;%Importancia del rastro de feromona en la decisión. for i=1:numerodenodos%Generación de la matriz heurística. for j=1:numerodenodos if matrizdedistancias(i,j)==0 matrizheuristica(i,j)=0; else matrizheuristica(i,j)=1/matrizdedistancias(i,j); end end end rastrodeferomona=0.0001*ones(numerodenodos);%Generación de la matriz de feromonas inicial. Figura 3. Código de la función “Información del programa” del algoritmo de solución para la etapa de ruteo.

La función “Información del programa” determina los parámetros del problema. Número de ciclos, número de hormigas, número de nodos y el valor de α y β. También importa el archivo con la información de las coordenadas de las paradas, que permite calcular los 35

valores dij de la matriz de distancias y ηij de la matriz heurística. Finalmente, genera la matriz de feromonas inicial con valor τij = τ0. 2. Archivo de datos Archivo de datos function [longitud,latitud]=archivodedatos(inputfile)%Comando que permite extraer las coordenadas de las paradas del archivo importado fid=fopen(inputfile,'r');% nodes = textscan(fid,'%n%n%n%n', 'headerlines', 6); fclose(fid); longitud=(nodes{2})'; latitud=(nodes{3})'; Figura 4. Código de la función “Archivo de datos” del algoritmo de solución para la etapa de ruteo.

La función “Archivo de datos” permite extraer las coordenadas de las paradas de un archivo de texto. Los archivos con las coordenadas se crean en bloc de notas y después se modifica su nombre de .txt a .tsp para poder ser leído. Esto evita que sea necesario ingresar las coordenadas directamente en el código de Matlab. 3. Posición Inicial Posición Inicial function [posicioninicialdelashormigas]=posicioninicial(numerodehormigas,numeroden odos,primeraparada); for i=1:numerodehormigas posicioninicialdelashormigas(i,1)=1;%Posición inicial de las hormigas. posicioninicialdelashormigas(i,2)=primeraparada;%Posición inicial de las hormigas. end Figura 5. Código de la función “Posición inicial” del algoritmo de solución para la etapa de ruteo.

La función “Posición inicial” ubica primeramente a las hormigas del ciclo en el primero nodo, el colegio. Todas las hormigas deben partir del colegio y volver a él después de la última parada. 4. Ciclo de hormiga Ciclo de hormiga function [construccion,rastrodeferomona]=ciclodecadahormiga(posiciondelashormigas, numerodehormigas,numerodenodos,matrizheuristica,rastrodeferomona,observac ion,rastro,coeficientedeevaporacion); for i=1:numerodehormigas mh=matrizheuristica; for j=1:numerodenodos-1%Proceso de decisión paso a paso de las hormigas c=posiciondelashormigas(i,j); mh(:,c)=0; temp=(rastrodeferomona(c,:).^rastro).*(mh(c,:).^observacion); s=(sum(temp)); p=(1/s).*temp;%Ecuación 2 explotación

36

r=rand;%Valor q s=0.9;%Valor q sub cero for k=1:numerodenodos s=s+p(k); if r