potenciales beneficios del diseño de un sistema de rutas

Potenciales beneficios del diseño de un sistema de rutas de transporte

público colectivo urbano formulado a partir de un modelo matemático

multiobjetivo aplicando algoritmos genéticos. Caso de estudio: Neiva,

Huila.

Juan Guillermo Ruiz Fonseca

Universidad Nacional de Colombia

Facultad de Ingeniería, Departamento de Ingeniería Civil y Agrícola

Bogotá, Colombia

2020

Potenciales beneficios del diseño de un sistema de rutas de transporte

público colectivo urbano formulado a partir de un modelo matemático

multiobjetivo aplicando algoritmos genéticos. Caso de estudio: Neiva,

Huila.

Juan Guillermo Ruíz Fonseca

Trabajo de investigación presentado como requisito parcial para optar al título de:

Magister en Ingeniería de Transporte - Investigación

Directora:

Ph.D. Sonia Cecilia Mangones Matos

Línea de Investigación:

Planificación del Transporte

Universidad Nacional de Colombia

Facultad de Ingeniería, Departamento de Ingeniería Civil y Agrícola

Bogotá, Colombia

2020

Agradecimientos

A mi madre y hermano, quienes son las personas que me han acompañado en el camino.

A la directora de este trabajo de investigación, la Ingeniera Sonia Mangones, por su apoyo

incondicional y su orientación en el desarrollo exitoso del mismo.

A la firma Cal y Mayor y Asociados por brindarme el acceso a la información requerida

para realizar esta tesis.

A todas las personas que, de una u otra manera, contribuyeron en este logro de mi vida.

Resumen y Abstract V

Resumen

Los sistemas de transporte público colectivo urbano de las ciudades intermedias de

Colombia presentan una fuerte tendencia al deterioro en las últimas décadas debido, entre

otros, a problemas de tipo estructural y operacional, generando importantes perjuicios para

los usuarios, los operadores y la sociedad en general. A pesar de lo anterior, los métodos

que actualmente se emplean en el medio para el diseño de estos sistemas son heurísticas

de ensayo de “prueba y error”, que no garantizan que las soluciones brindadas permitan

un aprovechamiento adecuado de los recursos disponibles para la prestación de un

servicio de calidad. A partir de esto, el presente trabajo de investigación propuso un

modelo matemático multiobjetivo, solucionado a través del uso de un algoritmo genético,

mediante el cual fue posible sustentar la tesis de que se logran obtener diseños más

optimizados a través de este tipo de herramientas, generando sistemas de mayor

eficiencia operacional y de servicio al usuario.

Palabras clave: Transporte público colectivo urbano, modelo matemático

multiobjetivo, algoritmo genético, diseño de rutas.

Abstract

The urban collective public transport systems of the intermediate cities of Colombia have

a strong risk trend in recent decades due, among other things, to structural and operational

problems, generating significant damages for users, operators and society in general.

Despite the above, the methods currently used in the medium for the design of these

systems are "trial and error" test heuristics, which do not require that the solutions provided

have adequate use of the resources available for the provision of a quality service. From

this, the present research work proposed a multiobjective mathematical model, solved

through the use of a genetic algorithm, through which it was possible to support the thesis

that more optimized designs can be obtained through this type of tools , generating systems

of greater operational efficiency and user service.

Keywords: Urban collective public transport, multiobjective mathematical model,

genetic algorithm, route design.

Contenido VII

Contenido

Pág.

Resumen ......................................................................................................................... V

Lista de figuras .............................................................................................................. IX

Lista de tablas ................................................................................................................ X

Lista de Símbolos y abreviaturas ................................................................................. XI

Introducción .................................................................................................................. 12

1. Objetivos ................................................................................................................. 17 1.1 Objetivo General: ........................................................................................... 17 1.2 Objetivos Específicos:.................................................................................... 17

2. Antecedentes del problema de investigación ...................................................... 19 2.1 Situación actual del transporte público colectivo urbano en las ciudades intermedias de Colombia .......................................................................................... 20

2.1.1 Problemática del TPCU a nivel nacional.............................................. 20 2.1.2 Problemática del TPCU en Neiva, Huila .............................................. 26

2.2 Estado del arte del diseño de sistemas de rutas del TPCU ............................ 30 2.2.1 Panorama mundial .............................................................................. 30 2.2.2 Panorama latinoamericano ................................................................. 41 2.2.3 Panorama nacional ............................................................................. 42

3. Fundamentación teórica ........................................................................................ 45 3.1 Modelo matemático multiobjetivo ................................................................... 46 3.2 Algoritmos genéticos ..................................................................................... 51

4. Formulación matemática del problema ................................................................ 60 4.1 Generalidades y supuestos ........................................................................... 62 4.2 Función objetivo del modelo .......................................................................... 68 4.3 Conjunto de restricciones del modelo ............................................................ 71 4.4 Modelo matemático multiobjetivo ................................................................... 73 4.5 Limitaciones y restricciones del modelo matemático multiobjetivo ................. 76

5. Desarrollo y aplicación del algoritmo genético .................................................... 79 5.1 Generación de soluciones de diseños de sistemas de rutas de TPCU .......... 81

5.1.1 Alternativa de generación de sistemas de rutas # 1: ........................... 84 5.1.2 Alternativa de generación de sistemas de rutas # 2: ........................... 84 5.1.3 Alternativa de generación de sistemas de rutas # 3: ........................... 85

VIII Potenciales beneficios del diseño de un sistema de rutas de TPCU

formulado a partir de un modelo matemático multiobjetivo aplicando

algoritmos genéticos

5.1.4 Alternativa de generación de sistemas de rutas # 4: ........................... 86

5.2 Evaluación de los sistemas de rutas de TPCU generados aleatoriamente .... 87 5.3 Selección de los mejores sistemas de rutas de TPCU evaluados ................. 88 5.4 Proceso de crossover o cruzamiento para generar nuevas soluciones de rutas de TPCU .................................................................................................................. 89 5.5 Mutación de los sistemas de rutas de TPCU generados del proceso de cruzamiento ............................................................................................................. 90 5.6 Elección del mejor sistema de rutas de TPCU en cada población de individuos ................................................................................................................. 91 5.7 Código de programación del algoritmo genético ............................................ 94

6. Elección del mejor sistema de rutas de TPCU obtenido ................................... 102

7. Validación del modelo diseñado ......................................................................... 106 7.1 Determinación de variables de comparación ............................................... 107 7.2 Escenarios de comparación ........................................................................ 109

7.2.1 Escenario 1: situación actual ............................................................ 110 7.2.2 Escenario 2: Sistema Estratégico de Transporte Público SETP ........ 112 7.2.3 Escenario 3: Modelo Matemático Multiobjetivo ................................. 112

7.3 Cuantificación de variables .......................................................................... 115 7.3.1 Índice de pasajero por kilómetro (IPK): ............................................. 115 7.3.2 Cobertura espacial ............................................................................ 116 7.3.3 Cobertura temporal ........................................................................... 120 7.3.4 Costo generalizado del transporte .................................................... 122 7.3.5 Tamaño de la flota ............................................................................ 123 7.3.6 Longitud total .................................................................................... 124 7.3.7 Número de rutas ............................................................................... 124 7.3.8 Transferencias .................................................................................. 125

8. Comparación de resultados obtenidos .............................................................. 127 8.1 Escala de valoración ................................................................................... 127 8.2 Evaluación de los indicadores ..................................................................... 128 8.3 Ponderación de los indicadores ................................................................... 129 8.4 Resultados de la evaluación multicriterio ..................................................... 130

Conclusiones y recomendaciones ............................................................................ 133

Bibliografía .................................................................................................................. 137

Contenido IX

Lista de figuras

Pág.

Ilustración 2-1: Problemática del transporte público urbano de pasajeros ...................... 21

Ilustración 2-2: Sobreoferta en el transporte público – Caso Pereira .............................. 23

Ilustración 2-3: Kilómetros de ruta de transporte público por millón de habitantes .......... 24

Ilustración 2-4: Distribución modal de viajes en Neiva, Huila .......................................... 27

Ilustración 3-1: Métodos de optimización ........................................................................ 48

Ilustración 3-2: Método de escalarización ....................................................................... 49

Ilustración 3-3: Esquema del funcionamiento de un algoritmo evolutivo ......................... 51

Ilustración 3-4: Componentes del algoritmo genético ..................................................... 56

Ilustración 5-1: Desarrollo del algoritmo genético ........................................................... 80

Ilustración 5-2: Zonas de análisis de transporte para la generación de soluciones ......... 83

Ilustración 5-3: Proceso de evaluación de sistemas de rutas de TPCU .......................... 87

Ilustración 7-1. Oferta de rutas TPCU actual .................................................................111

Ilustración 7-2. Oferta de rutas SETP ............................................................................113

Ilustración 7-3 Oferta de rutas escenario modelo matemático multiobjetivo ...................114

Ilustración 7-4: Cobertura TPCU actual .........................................................................117

Ilustración 7-5: Cobertura SETP ....................................................................................118

Ilustración 7-6: Cobertura modelo..................................................................................119

Contenido X

Lista de tablas

Pág.

Tabla 2-1: Comparación de modelos existentes .............................................................. 39

Tabla 3-1 Ventajas y desventajas del algoritmo genético ................................................ 58

Tabla 5-1: Ejemplo del desarrollo del algoritmo genético ................................................ 87

Tabla 5-2: Ejemplo del desarrollo del algoritmo genético para una población X .............. 93

Tabla 5-3: Código de programación del algoritmo genético ............................................ 95

Tabla 6-1: Cantidad de sistemas de TPCU analizados en el algoritmo genético ........... 103

Tabla 6-2: Sistema de rutas seleccionado ..................................................................... 104

Tabla 7-1: Determinación de variables .......................................................................... 108

Tabla 7-2: Comparativo IPK .......................................................................................... 115

Tabla 7-3: Comparativo cobertura espacial ................................................................... 120

Tabla 7-4: Comparativo cobertura temporal .................................................................. 121

Tabla 7-5: Comparativo costo generalizado del transporte ........................................... 123

Tabla 7-6: Comparativa tamaño de la flota .................................................................... 123

Tabla 7-7: Comparativo longitud total ............................................................................ 124

Tabla 7-8: Comparativo número de rutas ...................................................................... 124

Tabla 7-9: Comparativo transferencias ......................................................................... 125

Tabla 8-1: Escala de valoración .................................................................................... 128

Tabla 8-2: Resumen resultados obtenidos .................................................................... 128

Tabla 8-3: Evaluación de indicadores ........................................................................... 129

Tabla 8-4: Ponderadores de los indicadores evaluados ................................................ 130

Tabla 8-5: Matriz multicriterio ........................................................................................ 131

Símbolos y abreviaturas XI

Lista de Símbolos y abreviaturas

Abreviaturas

Abreviatura Término

TPCU Transporte Público Colectivo Urbano

SETP Sistema Estratégico de Transporte Público

IPK Índice de Pasajeros por Kilómetro

MMMO Modelos matemáticos multiobjetivos

AL Algoritmos genéticos

CGT Costo generalizado de transporte

Introducción

Durante las últimas décadas, los sistemas de transporte público colectivo urbano

(TPCU) de las ciudades intermedias de Colombia han presentado fuertes

tendencias al deterioro de la calidad del servicio. Las principales manifestaciones

de las fallas del sector, relacionadas principalmente con diseños ineficientes, se

caracterizan y reflejan principalmente en sobreoferta y concentración de servicios,

paralelismo y sobreposición de rutas, sobrecostos de operación, pérdida de

demanda, externalidades negativas y las profundas crisis financieras en las que se

encuentran sumidos hoy la gran mayoría de estos sistemas, lo que ha causado que

cada vez más usuarios muden a modos de transporte no sustentables como el

vehículo privado, las motocicletas, el mototaxismo, entre otros. Los usuarios son

afectados en forma directa al tener mayores tiempos de viaje, menor confiabilidad,

comodidad, seguridad y tarifas ineficientes. Así mismo, las ciudades colombianas

sufren también externalidades negativas resultantes de sistemas de transporte

urbano inadecuados, por lo que, en lugar de contribuir al desarrollo urbano

planificado de las ciudades, la evolución del transporte urbano ha generado

patrones de crecimiento desordenados, y ha incrementado los niveles de

accidentalidad y contaminación, atentando contra el bienestar de la totalidad de la

población (Conpes 3167, 2002).

A pesar de su gran importancia, el problema del diseño óptimo de la arquitectura

de las rutas de los sistemas de transporte público colectivo urbano (topología y

número de servicios ofertados), de naturaleza combinatoria y de tipo NP-Hard, ha

sido poco estudiado en nuestro medio, solucionándose de manera aproximada por

medio de la utilización de métodos empíricos y poco estructurados, llevados a cabo

Introducción 13

mediante análisis clásicos de evaluación y comparación de alternativas o

heurísticas de prueba y error a "visión de experto", ya que la formulación y

derivación de algoritmos eficientes para su solución presenta alta dificultad

(formulación del problema, no linealidad, no convexidad, naturaleza combinatoria,

múltiples objetivos, disposición espacial y demás) (Ceder y Israeli, 1998). Los

esfuerzos realizados hasta el momento, han tratado de adaptar al mismo

metaheurísticas que han demostrado ser flexibles en otros contextos diferentes,

aplicados a casos de pruebas de dimensiones pequeñas, irreales e hipotéticas,

abriendo la posibilidad para la investigación en este campo.

La situación descrita anteriormente, permitió identificar la potencial oportunidad que

existe en el contexto de las ciudades intermedias colombianas, de obtener diseños

de sistemas de rutas más eficientes por medio de la formulación de modelos y

algoritmos matemáticos, en contravía de los métodos empíricos convencionales,

que consideren la optimización del problema desde diferentes enfoques

(multiobjetivo) y cuya finalidad específica sea el diseño de rutas de TPCU, con el

fin de reducir el impacto negativo a los usuarios y prestadores del servicio

(operadores) de los sistemas, ayudando a mejorar el deterioro del TPCU de las

ciudades intermedias de Colombia y proporcionando una verdadera herramienta

de apoyo a la toma de decisiones para los estructuradores de estos sistemas y las

entidades públicas, contribuyendo a mejorar las condiciones financieras, de

competitividad y movilidad urbana de las ciudades intermedias del país.

Con el fin de lograr validar la oportunidad identificada en esta materia, se procedió,

de acuerdo a las problemáticas identificadas, a realizar la formulación de un modelo

matemático multiobjetivo, adecuado para las condiciones colombianas, orientado

a la obtención de diseños de sistemas de rutas enfocados tanto en maximizar el

nivel de servicio al usuario, reduciendo sus costos generalizados de transporte

(tiempo de caminata, espera y viaje), así como en lograr una minimización de los

recursos necesarios por medio del mejoramiento de la ocupación promedio de los

buses, es decir el índice de pasajeros por kilómetro de estos sistemas. De esta

14 Potenciales beneficios del diseño de un sistema de rutas de TPCU



manera, la salida del modelo debió ser la cantidad y el trazado de los recorridos de

las rutas del sistema a partir de los patrones espaciales de la demanda (matriz

origen-destino) y las restricciones establecidas. En cuanto a la resolución del

problema, se utilizó un algoritmo genético, inspirados en la teoría de la evolución

darwiniana, basado en la aplicación de tres operadores básicos: selección,

cruzamiento y mutación, el cual ha demostrado buenos resultados para encontrar

soluciones aproximadas al óptimo en este tipo de problemas de alta complejidad.

Se utilizó a la ciudad de Neiva, Huila, como caso de prueba, debido a que reúne la

mayoría de problemáticas identificadas para el TPCU representativas de las

ciudades intermedias del país (sobreoferta, pérdida de demanda, aumento de

viajes en automóvil, tarifas elevadas, falta de cobertura temporal y espacial, crisis

financiera, etc.) y se podrían validar los resultados obtenidos por el método

propuesto en este trabajo de investigación.

A partir de las consideraciones anteriores, el objetivo del presenta trabajo de

investigación fue “Estimar los potenciales beneficios obtenidos mediante la

optimización del diseño de un sistema de rutas de transporte público colectivo

urbano (trazado y cantidad de servicios) a partir de la formulación de un modelo

matemático multiobjetivo aplicando algoritmos genéticos para su solución,

utilizando como caso de estudio la ciudad de Neiva, Huila, Colombia”. Para

conseguir el objetivo anterior, se partió de realizar el diagnóstico de la situación

actual del sistema de transporte público colectivo urbano en esta ciudad, la cual es

característica de las condiciones de la mayoría de urbes intermedias del país, con

el fin de establecer la línea base de comparación del estudio; así mismo, se

procedió con la formulación de un modelo matemático multiobjetivo para la

optimización del diseño del sistema de rutas de transporte público colectivo urbano

de la ciudad (trazado y cantidad de servicios), el cual permitió minimizar los costos

generalizados de transporte de los usuarios y maximizar el índice de pasajeros por

kilómetro del sistema (IPK); de otro lado, se desarrolló y aplicó un algoritmo

genético que permitió obtener una solución aproximada al óptimo del problema

Introducción 15

matemático multiobjetivo formulado y, a partir de la cuantificación de los aspectos

o factores a evaluar y los indicadores operacionales por medio de los cuales se

realizó la comparación respecto de la línea base con la solución obtenida, se

establecieron las conclusiones y recomendaciones del presente trabajo de

investigación.

1. Objetivos

1.1 Objetivo General:

Estimar los potenciales beneficios obtenidos mediante la optimización del diseño

de un sistema de rutas de transporte público colectivo urbano (trazado y cantidad

de servicios) a partir de la formulación de un modelo matemático multiobjetivo

aplicando algoritmos genéticos para su solución, utilizando como caso de estudio

la ciudad de Neiva, Huila, Colombia.

1.2 Objetivos Específicos:

• Realizar el diagnóstico de la situación actual del sistema de transporte

público colectivo urbano de la ciudad de Neiva, Huila, para establecer la

línea base de comparación.

• Formular un modelo matemático multiobjetivo para la optimización del

diseño de rutas de transporte público colectivo urbano (trazado y

cantidad de servicios) de la ciudad de Neiva, Huila, que permita minimizar

los costos generalizados de transporte de los usuarios y maximizar el

índice de pasajeros por kilómetro del sistema (IPK).

• Desarrollar y aplicar un algoritmo genético que permita obtener una

solución óptima al problema matemático multiobjetivo formulado.




• Establecer los aspectos o factores a evaluar y los indicadores

operacionales por medio de los cuales se realizará la comparación

respecto de la línea base con la solución obtenida.

• Cuantificar los indicadores operacionales definidos para el sistema de

rutas de transporte público colectivo urbano actual y el diseñado.

• Comparar los resultados obtenidos entre el diseño actual de rutas del

sistema de transporte público colectivo urbano de la ciudad de Neiva,

Huila, y el obtenido mediante el modelo de optimización propuesto en

este trabajo.

2. Antecedentes del problema de investigación

Los sistemas de transporte público colectivo urbano de las ciudades intermedias

de Colombia presentan una fuerte tendencia al deterioro en las últimas décadas

debido, entre otros, a problemas de tipo estructural y operacional, generando

importantes perjuicios para los usuarios, los operadores y la sociedad en general.

Estas deficiencias en sus diseños provocan que la constante, en la gran mayoría

de las ciudades de Colombia, sea la pérdida de pasajeros, los cuales migran cada

vez más a modos no sustentables y poco sostenibles como el automóvil privado y

la motocicleta, aumentando la ocupación de las vías y generando graves problemas

de accidentalidad y contaminación ambiental.

Entre los problemas que más se destacan se presenta la sobreoferta de servicios

y de flota de buses, el elevado paralelismo y concentración de las rutas, tarifas

ineficientes, baja ocupación de los buses, altos tiempos de viaje y de espera, largas

distancias de acceso a los servicios, entre otros.

Todo lo anterior conllevó a identificar la gran oportunidad que existe en esta materia

para conseguir diseño de rutas de transporte público más eficientes y acordes a las

necesidades de los usuarios, que conduzcan a un mejor aprovechamiento de los

recursos sin deteriorar la calidad en el servicio, pues los métodos que actualmente

se emplean en el medio para el diseño de estos sistemas son heurísticas de ensayo

de “prueba y error”, que no garantizan que las soluciones brindadas sean las

mejores que puedan conseguirse en pro de la sociedad, los usuarios y los

operadores de los sistemas.




El presente capítulo se encuentra enmarcado en los antecedentes a nivel nacional

y en el contexto latinoamericano, sobre el diseño de rutas de transporte público

colectivo urbano. En una primera parte se presentan los aspectos más relevantes

en relación a la situación actual del transporte público colectivo urbano de las

ciudades intermedias de Colombia, haciendo especial hincapié en el caso de Neiva,

Huila, como referente de estudio para el desarrollo de este trabajo de investigación,

puesto que concentra la gran mayoría de problemáticas que se presentan a nivel

nacional; mientras que de otro lado, en una segunda parte, se expone el estado del

arte a nivel mundial, latinoamericano y nacional, respecto de los métodos

matemáticos y algoritmos existentes para la solución del problema del diseño de

sistemas de oferta de transporte público que conduzcan a obtener sistemas

altamente eficientes que contribuyan a un adecuado uso de los recursos y mejoren

el nivel de servicio brindado a los usuarios, haciendo más atractivo este modo de

transporte frente a otros existentes, no sustentables y poco eficientes.

2.1 Situación actual del transporte público colectivo urbano en las ciudades intermedias de Colombia

En primera instancia se presenta una caracterización de las condiciones de

prestación del servicio a nivel nacional, y en segundo lugar, de las condiciones

particulares de Neiva, Huila; ciudad que fue el caso de estudio para validar la tesis

del presente trabajo de investigación.

2.1.1 Problemática del TPCU a nivel nacional

Los procesos de urbanización que el país ha observado durante su historia reciente

han exigido el desarrollo de nuevas capacidades en la prestación de los diferentes

servicios de transporte que requieren las ciudades para su adecuado

funcionamiento. A medida que éstas crecen en población y en superficie

Antecedentes del problema de investigación 21

urbanizada, el número de viajes aumenta requiriendo sistemas de transporte

urbano que proporcionen la movilidad adecuada para la interacción de las nuevas

comunidades que resultaron del proceso de expansión urbana (Transporte & DNP,

2002).

A pesar de la preponderancia del uso del transporte público urbano de pasajeros,

entre el 65 y 85% de los viajes motorizados, (Transporte & DNP, 2002), esto no ha

sido suficiente para cambiar la fuerte tendencia al deterioro de la calidad del

servicio prestado en las últimas décadas en las ciudades colombianas. Si bien el

comportamiento del transporte público tiene una estrecha relación con los demás

modos de transporte y el uso del suelo en las ciudades, se puede afirmar que las

principales manifestaciones de las fallas del sector, relacionadas con la oferta de

servicios e infraestructura, se reflejan fundamentalmente en los impactos negativos

sobre los usuarios y las externalidades generadas por su funcionamiento, las que

a su vez se desprenden de fallas estructurales en el diseño, como se observa en

la Ilustración 2-1.

Ilustración 2-1: Problemática del transporte público urbano de pasajeros

Fuente: Departamento Nacional de Planeación, 2012.




Los usuarios son afectados en forma directa al tener mayores tiempos de viaje,

menor confiabilidad, comodidad, seguridad y tarifas ineficientes. Esta tendencia

puede generalizarse a las principales ciudades de Colombia, de las cuales Neiva,

Huila, presenta la misma tendencia.

Las ciudades colombianas sufren también externalidades negativas resultantes de

sistemas de transporte urbano inadecuados. En lugar de contribuir al desarrollo

urbano planificado de las ciudades, la evolución del transporte urbano ha

contribuido a patrones de crecimiento desordenados, y ha incrementado los niveles

de accidentalidad y contaminación, atentando contra el bienestar de la totalidad de

la población (Transporte & DNP, 2002).

La tendencia al deterioro de los servicios de transporte público urbano se

caracteriza y refleja principalmente en los siguientes aspectos:

Sobreoferta: el mayor número de vehículos ofrecido en comparación con lo

efectivamente demandado es una constante en las principales ciudades del país.

Se estima que en promedio un 40% del parque automotor existente no se requiere

(Secretaría de Hacienda de Bogotá, 2010). En este caso se ha sobrestimado la

demanda, produciendo sistemas negativos para los operadores, los usuarios, la

ciudad y el medio ambiente.

La Ilustración 2-2 presenta como ejemplo el comportamiento diario de la oferta y la

demanda en uno de los principales corredores que conducen al centro de Pereira.

Este caso, representativo de las demás ciudades intermedias colombianas, permite

apreciar un bajo nivel de ajuste de la oferta en función del comportamiento temporal

de la demanda. Durante las horas de mayor desplazamiento de pasajeros el

número de sillas ofrecido está, en promedio, por encima de la demanda y es cerca

de tres veces el número de pasajeros durante las horas de menos

desplazamientos, como ocurre entre las nueve y once de la mañana.


Ilustración 2-2: Sobreoferta en el transporte público – Caso Pereira

Fuente: Unión temporal TTC-Systra-GGT, 2010.

Tan marcada tendencia a la baja se confirma con el incremento observado en el

tamaño de la flota de servicio público, caracterizado por la introducción de

vehículos de menor capacidad para servir las mismas rutas. Esto revierte en una

mayor ocupación de espacio vial por pasajero, menor velocidad para ofrecer la

misma capacidad y un mayor costo de capital en equipo por pasajero transportado.

En Colombia la participación de los buses, que era 80% del parque a finales de los

70, pasó a ser hoy el 50%, mientras en Santiago de Chile esta proporción apenas

cambió del 68% al 61%. En cuanto a las tasas de crecimiento de la flota durante la

última década, el 4,7% anual de la situación colombiana contrasta con el 0,5% en

Buenos Aires y el casi -2% de Santiago de Chile (TTC-SYSTRA-GGT, 2001)

Concentración de rutas: pese al amplio cubrimiento espacial de las rutas de

transporte público, la consolidación de actividades en las ciudades induce a una

concentración de rutas principalmente en los corredores que dan acceso al centro.

Se estima que entre el 70% y el 90% de las rutas de las principales ciudades del




país pasan por el centro (Instituto SER, 2003). Esto hace que un elevado número

de vehículos de mediana y baja capacidad transite por un corredor, en lugar de

utilizar un menor número de vehículos de mayor capacidad, y de esta manera hacer

uso más eficiente de la infraestructura y los equipos. En general, las rutas de

transporte público brindan un adecuado cubrimiento espacial de las ciudades. Sin

embargo, cada una busca unir en forma aislada los orígenes y destinos de viaje

pasando por zonas de alta demanda, sin tener en cuenta el resto de rutas del

sistema. El resultado es un creciente número de rutas extensas, redundantes en el

centro, pero con cubrimientos temporales y confiabilidad baja en la periferia de las

ciudades.

En cuanto a los kilómetros de ruta que conforman la red de transporte público,

como se muestra en la siguiente ilustración, también tienden a ser mayores en las

ciudades colombianas. Estos valores refuerzan la tesis de superposición de

recorridos.

Ilustración 2-3: Kilómetros de ruta de transporte público por millón de habitantes

Fuente: Instituto SER de investigación, 2003.


Tarifas ineficientes: la mayoría de los aspectos anteriormente descritos generan

altos costos de operación y mantenimiento, y una menor rentabilidad para los

operadores. Esta situación ha llevado a los operadores a buscar mejorar su

rentabilidad reduciendo los costos laborales, descuidando las prácticas de

mantenimiento y reposición del equipo y presionando incrementos de las tarifas

principalmente para los vehículos más viejos.

Deterioro urbano: se ha presentado la expansión no controlada y desordenada de

las ciudades, y desvalorización inmobiliaria en los corredores de mayor

concentración de rutas.

Contaminación: se estima que el cambio tecnológico en los buses, la eliminación

de la sobreoferta, la reestructuración de rutas y la optimización operativa por la

implantación de sistemas integrados de transporte masivo modernos reduce las

emisiones de monóxido de carbono (CO) en aproximadamente un 90%, de

hidrocarburos (HC) en 60%, y de óxidos de nitrógeno (NOX) en 50%. También

habría reducciones notorias en la emisión de otros gases como dióxido de azufre,

de material particulado y de ruido. Lo anterior significa que si las ciudades contaran

con sistemas de transporte público eficientes el consumo energético sería muy

inferior y el ambiente de las ciudades recibiría cargas contaminantes mucho

menores a las actuales.

Crisis financieras: La gran mayoría de los sistemas de transporte público colectivo

del país presentan hoy profundas crisis financieras debido a la tendencia a la baja

de la demanda de usuarios que cada vez más migran a modos alternativos e

informales de transporte. En general se ha identificado que factores como la

sobreoferta, las bajas velocidades, la irregularidad de los servicios, la falta de

cobertura, el riesgo, entre otros, ha contribuido negativamente a que estos sistemas

presenten altos costosos operativos sin contar con la demanda necesaria para

hacerlos sostenibles financieramente, vacío que ha intentado llenarse con tarifas




cada vez más altas, lo que a su vez genera nuevamente pérdida de la demanda,

creando un círculo vicioso difícil de corregir.

2.1.2 Problemática del TPCU en Neiva, Huila

Neiva, capital del departamento del Huila, es una ciudad intermedia de Colombia

(con cerca de 500.000 habitantes) que presenta problemáticas en la prestación de

su servicio de transporte público, similares a las de la gran mayoría de ciudades

intermedias en Colombia, relacionadas con fallas estructurales que derivan en

sobreoferta, superposición y concentración, ineficiencia, entre otros, que han

causado como efecto un deterioro cada vez más acelerado del servicio, y por tanto

la pérdida masiva de usuarios del servicio, cambiando sus preferencias modales.

Es así como en el caso específico de Neiva, el transporte público colectivo urbano

ha pasado de 108.200 viajes diarios a 73.300 viajes diarios, lo que supone una

caída del 33% en el número de pasajeros transportados entre 2007 y 2016,

mientras que los viajes en moto y automóvil particular se han elevado a 155.300 y

86.400, respectivamente, al tiempo que el mototaxismo ha alcanzado los 31.800

viajes diarios, es decir aproximadamente el 43% de los viajes que se realizan en el

transporte público colectivo.

Por su parte, los viajes a pie son del orden de 74.200 diarios y en bicicleta son de

9.758 desplazamientos diarios. En definitiva, la ciudad ha migrado de formas de

movilidad sustentable (transporte público colectivo, a pie y en bicicleta) a mayores

viajes en modos no sustentables como los vehículos particulares y el mototaxismo,

en parte como consecuencia de un sistema de transporte público deteriorado,

desarrollo urbano desordenado y de baja densidad, así como el incremento

acelerado en las tasas de motorización.


Así, en el 2007 los viajes diarios a pie, bicicleta y transporte público colectivo

representaban el 55% del reparto modal, mientras que en 2016 solo representaron

el 33% del reparto modal (Unión temporal Cal y Mayor - Ikon, 2017), como se

presenta en la Ilustración 2-4

Ilustración 2-4: Distribución modal de viajes en Neiva, Huila

Fuente: Plan Maestro de Movilidad de Neiva, 2016.

De acuerdo a la serie histórica entre 2006 y 2016, la demanda de pasajeros ha

decrecido significativamente, pasando de aproximadamente 41 millones de

pasajeros movilizados en el 2007 a apenas 26 millones de pasajeros movilizados

en el 2016, lo que representa una reducción del 36%, similar a la identificada por

las encuestas de movilidad en valores diarios.




Esta reducción en la demanda de pasajeros ha estado relacionada con la

disminución en la flota de transporte público colectivo operativa en la ciudad,

pasando de aproximadamente 600 vehículos operativos en el año 2007 a cerca de

430 vehículos operacionales en el año 2017, lo que representa una reducción del

27% en la oferta de transporte público colectivo. Sin embargo, la flota vinculada se

ha mantenido estable entorno a los 650 y 680 vehículos, lo que denota una

reducción en la oferta ante la reducción en la demanda de pasajeros y no por una

disminución en los vehículos afiliados; esto resulta en un círculo vicioso que

empeora continuamente la calidad y cobertura del servicio

Respecto del transporte público colectivo urbano, la ciudad cuenta con 39 rutas

que tienen una cobertura cercana al 80% del área en servicio actual de la ciudad,

incluyendo algunos asentamientos fuera del perímetro urbano (Fortalecillas y

Caguán). De otro lado, cerca del 70% de las rutas en un día típico, brindan una

oferta con un intervalo de despacho inferior a 15 minutos y más del 50% de las

rutas brindan un intervalo de despacho inferior a 10 minutos, que a pesar de ser un

tiempo de espera aceptable se convierte en un tiempo de espera superior al

habitual para la espera de un servicio informal como es el “mototaxismo”. El tiempo

de ciclo promedio para las rutas es de 45 minutos, el tiempo mínimo es de 28

minutos y el tiempo máximo es de 64 minutos. La distancia promedio de los

trayectos para todas las rutas es de 12,9 km y la velocidad promedio 17,3 km/h, la

velocidad de la ruta más baja es de 11,4km/h y la más alta 23,8km/h. Respecto de

la superposición de los recorridos de las rutas, en promedio existe un paralelismo

del 33% entre todas. En general, en el sistema actual el 57% de las rutas (22

servicios) presenta una superposición media entre el 30 al 40%, mientras que el

33% entre el 20 al 30% con respecto a todas las demás (Unión temporal Cal y

Mayor - Ikon, 2017).

En relación con los indicadores operacionales del sistema, para el año 2011 el

sistema tradicional movilizaba diariamente un promedio de 114.754 pasajeros y


recorría un total de 130.908 Kilómetros, es decir un IPK de 0,85

pasajeros/kilómetro, mientras que en la actualidad el sistema presenta un IPK diario

de 0,88 pasajeros/kilómetro movilizando 73.815 pasajeros y recorriendo 86.752

kilómetros. Lo anterior permite observar que, aunque el TPC ha presentado una

disminución del 34% en kilómetros y del 36% en pasajeros, el IPK del sistema se

ha mantenido constante decreciendo en tan sólo un 3%. Lo anterior demuestra que

se ha generado un “círculo vicioso” entre la disminución de pasajeros diarios que

han migrado a otros modos de transporte como el informal, y la disminución del

número de vehículos operativos, ya que en el 2011 se cuantificaban casi 600

mientras que hoy en día se presentan 400 en promedio al día, trayendo consigo

una reducción en el número de kilómetros diarios y por ende la movilización de una

menor cantidad de pasajeros; a pesar de esto, en términos de IPK el sistema se ha

mantenido constante, ya que la disminución tanto de kilómetros como de pasajeros

ha sido similar.

Las anteriores cifras denotan un detrimento importante en la prestación del servicio

de TPCU en la ciudad de Neiva relacionado con fallas estructurales y de diseño

(sobreoferta, sobreposición, bajas velocidades, rutas extensas, baja cobertura

espacial y temporal) que han causado, entre otras, la pérdida progresiva de la

demanda y la migración de los usuarios a otros modos de transporte menos

sustentables como las motos y el mototaxismo.

Este contexto, tanto nacional como específico para el caso de Neiva, Huila,

sustentan la enorme oportunidad que existe para que desde el sector académico

se exploren y brinden soluciones técnicas que permitan orientar diseños de

sistemas cada vez más eficientes, que proporcionen altos estándares de servicios

a los usuarios con el menor uso posible de recursos, contribuyendo al desarrollo y

sostenibilidad de las ciudades colombianas.

Sin embargo, y a pesar de su gran importancia, el problema ha sido poco estudiado,

como se presenta en el siguiente apartado, y los diseños en la actualidad en




Colombia continúan realizándose por medio del uso de heurísticas de “ensayo y

error”, a visión de experto, que son altamente susceptibles de ser mejorados por

medio de modelos y algoritmos matemáticos, como se fue demostrado mediante el

presente trabajo de investigación.

2.2 Estado del arte del diseño de sistemas de rutas del TPCU

El problema del diseño óptimo de la arquitectura de las rutas de los sistemas de

transporte público colectivo urbano (topología y número de servicios ofertados), de

naturaleza combinatoria y de tipo NP-Hard, ha sido poco estudiado en nuestro

medio, solucionándose de manera aproximada por medio de la utilización de

métodos empíricos y poco estructurados, llevados a cabo mediante análisis

clásicos de evaluación y comparación de alternativas o heurísticas de prueba y

error a "visión de experto", ya que la formulación y derivación de algoritmos

eficientes para su solución presenta alta dificultad (formulación del problema, no

linealidad, no convexidad, naturaleza combinatoria, múltiples objetivos, disposición

espacial y demás) (Ceder y Israeli, 1998).

A continuación se realiza una exposición del estado del arte del diseño de sistemas

de rutas de TPCU a partir de la revisión de toda la literatura relacionada, iniciando

por el panorama histórico a nivel mundial, seguido del panorama latinoamericano

y, por último, del panorama nacional.

2.2.1 Panorama mundial

Los esfuerzos realizados hasta el momento a nivel mundial para solucionar el

problema, han tratado de adaptar al mismo metaheurísticas que han demostrado

ser flexibles en otros contextos diferentes, aplicados a casos de pruebas de


dimensiones pequeñas, irreales e hipotéticas, abriendo la posibilidad para la

investigación en este campo.

A continuación, se realiza un análisis a profundidad relacionado con los algoritmos

y modelos matemáticos más representativos en el campo de la optimización de

rutas del TPCU, en donde se describe cada uno de ellos teniendo en cuenta

principalmente los aportes que realizan y las limitaciones a las que se encuentran

sujetos.

Técnicamente, el problema de la optimización de rutas de TPCU está enmarcado

dentro del problema clásico de ruteo de vehículos VRP (Vehicle routing problem),

el cual consiste básicamente en hallar un conjunto de rutas óptimas (en términos

de costos, tiempos, distancias, recursos, etc.) para una flota homogénea de

vehículos que sirve a un conjunto de clientes geográficamente dispersos (Paolo y

Daniele, 2002). La mayoría de los esfuerzos en el área del transporte urbano se

han dirigido a la solución de este problema, tanto a nivel académico como práctico,

aunque con un enfoque más marcado hacia la distribución de mercancías y no al

transporte de pasajeros.

El primer problema planteado tipo VRP fue el del agente viajero TSP ( Hamdy,

2004) (Travelling salesman problem), formulado a mediados del siglo pasado, en

1930. Dicho problema, que consiste en obtener la ruta más óptima para que un

vendedor viajero pase por todos los puntos de un mapa, sin importar el orden en

que lo haga, volviendo al nodo origen (depósito), ha sido ampliamente estudiado

desde entonces, y su análisis y resolución para encontrar la ruta más óptima sigue

estando vigente hoy en día. Esta versión clásica del TSP se refiere al caso más

básico en que se cuenta con un solo depósito y un solo vehículo y no hay

restricciones de capacidad del vehículo, ni de demanda de los clientes, ni de

ventanas de tiempo (Golden, 2008).

A través del tiempo, al VRP inicial se han venido incluyendo un amplio número de

variables y diversos parámetros con la intensión de capturar de forma más precisa




los casos más utilizados en la práctica y algunas de las realidades del mundo de la

logística, planteando así diferentes problemas de ruteo de vehículos que han

implementado escenarios cada vez más complejos y reales. Es así como en 1959,

Dantzig y Ramser formularon una generalización del TSP modelando por primera

vez el despacho de combustible a través de una flota de camiones a diferentes

estaciones de servicio desde una terminal, dando origen a un problema que plantea

la búsqueda de la solución óptima con diferentes restricciones como: número de

vehículos, capacidad, lugares de destino, demanda de los clientes, entre otras

(Dorronsoro, 2007); ésta es una extensión del clásico TSP que considera varios

agentes viajeros, en que las rutas permitidas son limitadas por la necesidad de que

los objetos deben ser entregados desde un punto fuente hasta su destino por un

vehículo de capacidad finita.

De igual manera, en 1989, H. Min se interesó por un problema de la vida real de

transporte de libros en una biblioteca, planteando por primera vez una variación al

VRP que considera entrega y recolección simultánea (Goksal , 2012), apropiado

para el estudio de los sistemas de distribución de las cadenas de abarrotes y

alimentos.

En el año 1990, Fleischmann introdujo la idea del VRP con uso múltiple de los

vehículos, es decir que consideró la situación en la cual un vehículo puede hacer

más de un viaje en un periodo de planeación (Bulbul, 2008). Por otro lado, Brandao

y Mercer en 1997, trabajaron el supuesto de VRP con múltiples viajes (Tallard,

2012). Hasta el año 2002, Prins introdujo un VRP con viajes múltiples de flota

heterogénea y más adelante aparece el VRP con viajes múltiples periódicos y con

viajes múltiples independientes.

En la actualidad existen diversas variaciones al modelo original del VRP que

abarcan los casos más utilizados en la práctica, entre las cuales se destacan:

MDVRP (Chalasani, 1999) (Multidepot VRP) que plantea la existencia de varios

depósitos desde los cuales se deben abastecer a los clientes, VRPTW (Restrepo,


2008) (VRP with time windows) que contempla la restricción adicional de una

ventana o intervalo de tiempo asociado a cada consumidor, CVRP (Olivera, 2004)

(Capacitated VRP) que considera vehículos con capacidad definida y una

secuencia de visitas establecidas a los clientes y VRPSPD (Goksal , 2012) (VRP

with simultaneous delivery and collection) donde cada cliente presenta problemas

tanto de entrega como de recolección atendida en una sola visita del vehículo.

Específicamente en relación con el problema de optimización de rutas de TPCU,

cabe mencionar que se cuenta con poca información al respecto. Uno de los

primeros antecedentes de los que se tiene conocimiento data del año de 1979,

cuando (Mandl, 1979) planteó el problema de la red suiza de transporte y expuso

una solución al ruteo de los vehículos. La representación del modelo consistió en

una red de 15 nodos y 21 arcos. Este caso de estudio ha sido trabajado

posteriormente por otros investigadores como (Baaj and Mahmassani, 1995), entre

otros, cada uno de ellos obteniendo una optimización de rutas para el problema

planteado a través de diferentes algoritmos propuestos.

En cuanto a los métodos de solución que existen del problema, el ruteo de

vehículos corresponde a problemas de optimización combinatoria de tipo NP-hard

debido a que su solución óptima solo puede ser obtenida para pequeñas instancias

del problema, lo que ha convertido al VRP en uno de los problemas de optimización

combinatoria más importante, con muchas aplicaciones del mundo real, en la

logística de distribución y del transporte (Toth & Vigo, 2002). Sus principales

avances se deben a la llegada de la computadora digital moderna, ya que la

mayoría de los métodos actuales aceptados en la solución de problemas de

optimización combinatoria difícilmente se habrían tomado en serio hace 25 años

por la sencilla razón de que nadie habría podido llevar a cabo los cálculos

necesarios para aplicarlos (Lawler, 1976).

Inicialmente, la resolución a los problemas de optimización combinatoria, como el

ruteo de vehículos, se realizaba mediante algoritmos de fuerza bruta o métodos

exactos, sin embargo, dichos algoritmos han ido quedando obsoletos ante la




complejidad y número de restricciones que se han añadido cada vez más al

problema clásico y hacen más difícil su resolución mediante este tipo de técnicas,

por lo que a continuación surgieron soluciones con algoritmos aproximados:

métodos heurísticos y metaheurísticos.

Los métodos exactos son eficientes cuando la cantidad de variables no es

considerable debido a restricciones de tiempo computacional y limitación de la

memoria. Existen tres clases: búsqueda directa de árbol, programación dinámica y

programación lineal y entera. Entre los años 2000 y 2011, se desarrollaron métodos

exactos de solución adaptables al CVRP y al VRPTW basados en primer lugar en

la formulación de algoritmos de partición de conjuntos permitiendo la incorporación

de restricciones adicionales que pueden ser usadas en la modelación de una

situación específica, y en segundo lugar, algoritmos basados en la generación de

columnas, éstos se derivan de pequeñas modificaciones de los algoritmos

originales del VRP (Baldacce, 2011). Uno de los métodos exactos más utilizados

para resolver problemas NP-Hard, es el método simplex desarrollado en 1947 por

George Dantzig.

Los métodos heurísticos proporcionan soluciones de aceptable calidad mediante la

exploración del espacio de búsqueda (Wee-Kit Ho, 2011), los cuales fueron

desarrollados entre 1960 y 1990 (Ayala y Gonzalez, 2001). Se clasifican en

métodos constructivos y de inserción (búsqueda local) (Contardo, 2005). El primer

algoritmo que resultó efectivo para resolver el VRP fue el propuesto por Clarke y

Wrigth en 1964.

Los métodos metaheurísticos fueron desarrollados hacia finales de la década de

los 90 y se caracterizan porque realizan un procedimiento de búsqueda para

encontrar soluciones de aceptable calidad (Cordeau, 2002) basadas en fenómenos

naturales. Se clasifican en metaheurísticas de trayectoria y metaheurísticas

basadas en población (Gendreau, 2005). Dentro de éstos se encuentran: Recocido

simulado (Braysy y Wout, 2003), recocido determinístico, redes neuronales


(Hernán y Pacheco, 2007), búsqueda tabú (González, 2006), algoritmos genéticos

(González, 2007), algoritmos de hormigas, memoria adaptativa y búsqueda de

vecindades (González, 2007).

Los métodos de solución más usados para resolver las diferentes variaciones del

VRP son en su mayoría metaheurísticas, entre ellas se pueden resaltar: búsqueda

tabú, algoritmos genéticos, algoritmos de memoria adaptativa y búsqueda de

vecindades.

En relación a los primeros algoritmos desarrollados para la resolución del problema

de optimización de rutas de TPCU, surgen en la década del 70, basados en ideas

intuitivas, sin una formulación del modelo ni una función objetivo, en algunos casos

sin exploración del espacio de soluciones. En la década del 80 se formulan algunas

funciones objetivo, y se incorporan nuevos parámetros tales como el cubrimiento

de la demanda, factor de carga (proporción de pasajeros parados respecto a la

cantidad de asientos) y transferencias de los buses (Axhausen & Smith Jr, 1984).

En la década del 90 aparecen otros enfoques, como la utilización de técnicas

metaheurísticas y la exploración del espacio de soluciones.

De acuerdo a la revisión literaria realizada, dentro de los algoritmos utilizados para

la optimización de rutas de TPCU se encontró que éstos se basan en modelos de

programación matemática resueltos con métodos aproximados. En particular varias

aplicaciones utilizan algoritmos genéticos, metaheurística que ha probado ser

flexible en otros contextos (Goldberg, 1989). Los algoritmos parten de una solución

inicial (conjunto de rutas), que se mejora iterativamente, generalmente avanzando

según tres fases bien diferenciadas: 1) generación, 2) evaluación y 3) mejora de

soluciones, con algunas variantes en cada una de ellas (Mauttone & Urquart, 2009).

Baaj & Mahmassani, en su trabajo AI-Based Approach for Transit Route System

Planning and Design, en 1991, propusieron una metodología que opera en base a

la generación, evaluación y mejora de rutas. La estrategia es ensayada con el caso

de prueba generado por Mandl, en 1979. Otros dos trabajos de estos autores (Baaj




& Mahmassani, A LISP program for the analysis of transit route configurations,

1990) (Baaj & Magmassani, Hybrid route generation heuristic algorithm for the

design of transit networks, 1995) utilizan como caso de estudio la red de 140 nodos

de la ciudad de Austin (Texas, 500.000 habitantes aproximadamente). Los

algoritmos de estos autores tienen la ventaja de proveer cierto grado de

interactividad para definir algunas restricciones y parámetros; es flexible por su

modularidad y permite planificaciones tanto a mediano como largo plazo. Su

principal limitación es que no propone una manera sistemática de variar los

parámetros para generar diferentes soluciones.

Shih, Mahmassani, & M, 1998 proponen una extensión del método de Baaj &

Mahmassani, An AI-Based Approach for Transit Route System Planning and

Design, 1991, que se adecua particularmente a la planificación de servicios

coordinados de transporte multimodal, en modalidad de flota heterogénea. Utilizan

como base los mismos procedimientos heurísticos, agregándoles el concepto de

centro de transferencia (comerciales y de empleo). Los ensayos se realizan con los

casos de prueba de Baaj & Mahmassani, An AI-Based Approach for Transit Route

System Planning and Design, 1991.

Israel & Ceder, 1995, resuelven los problemas de diseño de rutas, en base a un

modelo de programación matemática no lineal, con variables mixtas, múltiples

objetivos (minimización de los tiempos de viaje y minimización del tamaño de la

flota). El método es probado en una red ficticia de 8 nodos, algo limitado como caso

de prueba. Sus principales aportes son: el tratamiento formal del problema

(reduciendo algunos subproblemas a problemas clásicos como el de set covering),

y el método propuesto para la identificación de las soluciones no dominadas.

Pattnaik & Mohan, en 1998, con base al modelo de Baaj & Mahmassani, de 1991),

proponen un algoritmo que inicialmente genera un conjunto de rutas a partir de los

caminos más cortos entre todo par de nodos y caminos alternativos. Se utilizan

algoritmos genéticos para seleccionar subconjuntos del conjunto de rutas


candidatas, siendo este un aporte en cuanto a la utilización de metaheurísticas en

la resolución del problema. El procedimiento de evaluación de soluciones es similar

al utilizado por (Baaj & Mahmassani, An AI-Based Approach for Transit Route

System Planning and Design, 1991). El caso de prueba es un subconjunto de la

red de transporte de la ciudad de Madras, India, de 25 nodos.

Ngamchai & Lovell, 2000 formulan un método que genera rutas sin tener en cuenta

la matriz de demanda, pero alcanzando a todos los nodos de la red. Dado que

utiliza algoritmos genéticos, inicialmente se crea una población de una cantidad

determinada de conjuntos de rutas. La implementación es ensayada con una red

de 19 nodos. Una limitación de este método es que parte de soluciones iniciales

que no tienen en cuenta la matriz origen-destino. Un aporte es la propuesta de

nuevos operadores genéticos que buscan mejorar las soluciones generando

nuevas subrutas, a partir de rutas en las que existe variación de flujo mayor o igual

que un parámetro dado.

Rao, Krishna, & Dhingra, 2000 desarrollan un enfoque que se basa en el modelo y

algoritmos de Baaj & Mahmassani. Inicialmente se aplica un procedimiento de

identificación de corredores, el cual implica el cálculo de caminos más cortos entre

todo par de nodos de la red, asignación de demanda a rutas y chequeo de

restricciones de mínimo y máximo flujo de pasajeros en arcos. Nuevamente se

utilizan algoritmos genéticos, donde ahora la función objetivo incorpora los

objetivos del operador, en la forma de costo de flota, y los tiempos de espera en

los costos del usuario. El principal parámetro que controla este proceso es el factor

de carga de los buses. La metodología es ensayada con la red de pruebas de

(Mandl, 1979).

Caramia, Carorenuto, & Confessore, 2001, proponen una metodología que

requiere de un conjunto inicial de rutas (las actuales del sistema de TPCU) a ser

mejoradas. Utilizan algoritmos genéticos, donde la población es de cardinalidad

prefijada, y cada gen corresponde a una línea. El enfoque es similar al utilizado por

(Pattnaik & Mohan, 1998). La particularidad de este trabajo es que utiliza una red




neuronal para la evaluación de la función objetivo. El entrenamiento de la red se

realiza “off-line” con base a un cierto número de casos de prueba, donde para cada

uno se efectúa un procedimiento de asignación y de análisis multicriterio para

determinar el valor de la función objetivo. En las pruebas se utiliza como caso de

estudio el sistema de TPCU de la ciudad de Parma (norte de Italia), con un total de

80 posibles líneas de ómnibus. Este artículo se centra en el aporte de las redes

neuronales y algoritmos genéticos en la aproximación al subconjunto óptimo de

rutas, pero no entrega mayores detalles del modelo y métodos.

Finalmente, Gruttner & Pinninghoff, en 2002, utilizan algoritmos genéticos en el

sentido clásico. La asignación de pasajeros a rutas se efectúa utilizando un modelo

logit. Se mencionan resultados obtenidos según la variación de los parámetros que

regulan el trade-off entre los distintos objetivos, consistiendo en rutas largas

concentradas en zonas de alta demanda cuando se prioriza al operador, y muchas

rutas dispersas cuando se prioriza a los usuarios. El caso de prueba utilizado es la

red de la ciudad de Los Ángeles (Chile) cuya dimensión no se especifica.

La Tabla 2-1 muestra la comparación entre los modelos más relevantes mostrando

sus principales características y las limitaciones a las que están sujetos.

Potenciales beneficios del diseño de un sistema de rutas de TPCU formulado a partir de un modelo

matemático multiobjetivo aplicando algoritmos genéticos

Tabla 2-1: Comparación de modelos existentes

AUTOR AÑO CARACTERÍSTICAS LIMITACIONES FORMULACIÓN MATEMÁTICA

Modelo de Baaj y

Mahmassani

1991 Metodología que opera en base a la generación, evaluación y mejora de rutas. Provee grado de interactividad para definición de interacciones y parámetros. Es flexible por su modularidad y permite planificaciones a mediano y largo plazo.

No propone una manera sistemática de varias los parámetros para generar diferentes soluciones.

Israeli y Ceder 1993 Modelo de programación matemática no lineal, con variables mixtas y múltiples objetivos. Tratamiento formal del problema (reduciendo algunos subproblemas a problemas clásicos como el de set covering Método propuesto para la identificación de las soluciones no dominadas

Aplicable únicamente a redes pequeñas (hasta de 8 nodos)

40 Potenciales beneficios del diseño de un sistema de rutas de TPCU formulado a partir de un modelo

matemático multiobjetivo aplicando algoritmos genéticos

Ngamchai y Lovell

2000 Método que genera rutas sin tener en cuenta la matriz de demanda, alcanzando todos los nodos de la red. Calcula frecuencia de los buses en las rutas donde se quiere minimizar el costo de la flota. Propuesta de nuevos operadores genéticos que buscan mejorar las soluciones generando nuevas subrutas, a partir de rutas en las que existe variación de flujo mayor o igual que un parámetro dado.

Parte de soluciones iniciales que no tienen en cuenta la matriz origen-destino. Es decir que no considera la demanda.

Gruttner, Pinninghoff, Tudela, y Díaz

2002 Utiliza algoritmos genéticos en el sentido clásico. La asignación de pasajeros a rutas se efectúa utilizando un modelo logit. Se mencionan resultados obtenidos según la variación de los parámetros que regulan el trade-off entre los distintos objetivos, consistiendo en rutas largas concentradas en zonas de alta demanda cuando se prioriza al operador, y muchas rutas dispersas cuando se prioriza a los usuarios

No considera la demanda.

Fuente: Elaboración Propia


Recientemente, la facilidad computacional de integrar módulos existentes y de

incorporar interfases gráficas, ha estimulado el desarrollo de nuevos métodos de

solución al problema de ruteo de vehículos de TPCU, los que se diferencian por

factores como: su adaptabilidad (respecto de los datos disponibles, principalmente

aquellos relativos a la topología de la red de tránsito y a la demanda de viajes y

matrices origen-destino), interactividad (con el usuario, de modo que permiten la

incorporación de conocimiento técnico humano en el proceso de toma de

decisiones), eficiencia (calidad en los resultados y tiempos de procesamiento

razonables) y flexibilidad (en cuanto al horizonte de planificación, ya que los

primeros métodos que surgieron se refirieron a planificaciones de corto y mediano

plazo).

2.2.2 Panorama latinoamericano

En cuanto a casos de aplicación de algoritmos para la solución del problema de

optimización de rutas de TPCU a nivel latinoamericano, de acuerdo a las

búsquedas realizadas, la información existente sobre modelos aplicados en países

de Suramérica como Ecuador, permitió encontrar un estudio y propuesta de nuevas

rutas y líneas de transporte para el Distrito Metropolitano de Quito, para el corredor

suroccidental del sistema Metro Bus – Q, mediante el cual se estimaron los tiempos

de viaje de las unidades de transporte público en este corredor, se determinó el

modelo de rutas de transporte más apropiado para desarrollar el proyecto tomando

en cuenta la matriz origen-destino del área de estudio y la función flujo velocidad,

y se generó una herramienta que permite analizar futuras asignaciones o

reasignaciones de rutas a operadores de transporte por parte del organismo

regulador del transporte público urbano en la ciudad de Quito (Bayas Meza, 2011)

Otro caso de aplicación para Suramérica, se encontró en Chile, mediante la tesis

de maestría en Ingeniería Industrial “Optimización en el diseño de redes de

transporte público con objetivos medioambientales mediante algoritmos evolutivos

(Durán Micco, 2016) de la Universidad de Concepción, en la cual se estudia el VRP




multiobjetivo con el fin de minimizar tiempo de viaje y emisiones de CO2 mediante

la formulación de un modelo de programación matemática y dos algoritmos

evolutivos, el segundo correspondiente al problema bimodal, probados en

instancias pequeñas y medianas. Como conclusión de este trabajo se encontró que

los algoritmos evolutivos en general proporcionan mejores resultados y en menor

tiempo que el modelo de programación matemática, resultando competitivos con

otros métodos existentes en la literatura.

2.2.3 Panorama nacional

En relación a Colombia, en los últimos años se ha despertado el interés por el

estudio de problemas tipo VRP, especialmente en aplicaciones concretas, como lo

evidencia la participación en congresos internacionales como el CLAIO (Congreso

Latinoamericano de Investigación de Operaciones) y otros, donde se han

destacado ponencias de casos aplicados del uso de algoritmos para la optimización

de rutas, pero enfocados hacia la distribución de mercancías y la logística

empresarial y no hacia las rutas de transporte público colectivo en el contexto

urbano.

En cuanto a la utilización de algoritmos para el ruteo de vehículos de TPCU en

nuestro país, se puede resaltar la tesis para optar al título de Ingeniero Industrial

“Un modelo de optimización de rutas de transporte urbano en el área metropolitana

de Bucaramanga con VRPTW mediante un algoritmo de optimización por enjambre

de partículas evolutivo (Marín, 2017)” de la Universidad Industrial de Santander –

UIS, en la cual se realizó la formulación de un modelo de optimización de rutas de

transporte urbano en Bucaramanga y su zona metropolitana mediante el uso del

software MATLAB, permitiendo rediseñar las rutas actuales del sistema integrado

de transporte masivo “Metrolínea”, con el fin de disminuir tanto las distancias

recorridas como los tiempos de viaje en cumplimiento de las ventanas de tiempo

establecidas. Los autores decidieron aplicar una metaheurística de optimización


por enjambre de partículas evolutivo (EPSO) por las buenas soluciones que brinda

en comparación con otras técnicas. Como conclusión de este trabajo investigativo

se encontró que aunque el algoritmo EPSO resuelve el problema de ruteo de

vehículos con ventanas de tiempo, el modelo de rutas resultante no se ajusta al

entorno real, generando un número excesivo de servicios, rigiéndose netamente

por la formulación matemática del problema. Al final se proponen algunas

recomendaciones futuras para la obtención de mejores resultados mediante esta

técnica de optimización.

A pesar de estos avances, se pudo constatar que los mecanismos para el

modelamiento de rutas en Colombia son empíricos (Marín, 2017), y no se realiza

la aplicación de las metodologías de optimización existentes en otros lugares del

mundo. El diseño de rutas de transporte público en Colombia continúa realizándose

de manera subjetiva y manual por medio de metodologías clásicas de evaluación

y comparación de alternativas, sin contar con verdaderas herramientas de apoyo a

la toma de decisiones, que, complementando el conocimiento y experiencia

profesional con elementos cuantitativos, orienten diseños más óptimos en el uso

de recursos como lo exige el contexto social y económico actual del país. Lo

anterior se sustenta en que no se logró evidenciar en ninguno de los rediseños de

rutas de los Sistemas Estratégicos de Transporte Público (SETP) de Colombia, la

utilización de métodos y algoritmos matemáticos como los descritos anteriormente,

sino por el contrario, se validó el uso de métodos empíricos, poco estructurados.

Las ineficiencias en los diseños de los sistemas de transporte público colectivo

urbano de las ciudades intermedias del país ha llevado a que la gran mayoría de

estos sistemas hoy afronten profundas crisis estructurales, perdiendo cada vez más

participación dentro de la distribución modal, lo que redunda en menor demanda

de usuarios. Las personas están migrando a formas de movilizarse menos

sustentables e informales con las graves consecuencias que esto conlleva para la

sostenibilidad ambiental y financiera de estos sistemas (Cal y Mayor – Ikon, 2017).




La anterior oportunidad del conocimiento en nuestro medio abre la puerta para

formular un modelo multiobjetivo de optimización de rutas de transporte público

colectivo urbano (recorridos y cantidad) para las ciudades medianas de Colombia,

que contemple el problema desde varias perspectivas (usuarios, operadores y

sociedad), a partir de la utilización de algoritmos genéticos, proporcionando una

herramienta práctica, funcional, eficiente y flexible, adaptada al contexto

profesional y académico del país, que oriente diseños más óptimos en el uso de

los recursos disponibles a través de elementos cuantitativos que apoyen a los

tomadores de decisiones y diseñadores de estos sistemas, a diseñar

adecuadamente las rutas en cumplimiento con los requerimientos y necesidades

de los usuarios del servicio, contribuyendo a mejorar las condiciones financieras de

los sistemas y la movilidad urbana de las ciudades colombianas. Se validaron las

bondades y la funcionalidad del algoritmo propuesto mediante la comparación de

indicadores operacionales aplicados al caso de prueba real de Neiva, Huila,

Colombia, como se presenta a lo largo de este trabajo de investigación.

Fundamentación teórica 45

3. Fundamentación teórica

Una vez definido el problema de investigación, identificado como la ineficiencia de

los métodos convencionales utilizados en el medio para el diseño de sistemas de

rutas de transporte público colectivo urbano (TPCU) que conduzcan a un mejor

aprovechamiento de los recursos disponibles, brindando altos estándares de

servicio a los usuarios, lo que ha contribuido al deterioro estructural de los sistemas

de la gran mayoría de las ciudades intermedias en Colombia, se procedió a

desarrollar, mediante el presente trabajo de investigación y de acuerdo al resultado

de la revisión del estado del arte en la materia, un modelo matemático multiobjetivo,

solucionado a través del uso de un algoritmo genético, por medio del cual fue

posible sustentar la tesis de que se logran obtener diseños más optimizados a

través de este tipo de herramientas, generando sistemas de mayor eficiencia

operacional y de servicio al usuario en comparación con los métodos tradicionales.

En este sentido, se presenta este capítulo, a través del cual se busca exponer y

comprender toda la fundamentación teórica base para la realización del trabajo de

investigación. La estructura general del capítulo está compuesta por dos acápites

principales: por una parte, se expone el marco teórico de los problemas de

optimización multiobjetivos en el cual se abarca la revisión bibliográfica relacionada

con los mismos, describiendo así, de manera detallada, los parámetros que son la

base fundamental para el desarrollo de la investigación; mientras, de otra parte, se

realiza una exposición similar relacionada con el fundamento teórico y conceptual

de los algoritmos genéticos y su proceso de resolución de problemas de alta

complejidad tipo NP-Hard.




Considerado como el soporte de los conceptos utilizados para el desarrollo del

trabajo de investigación, se ha realizado una ardua revisión bibliográfica en pro de

obtener la información necesaria que permita cumplir con el objetivo de la presente

tesis. Ha sido a partir de dicha revisión de información que se ha estructurado el

presente apartado denominado “Fundamentación teórica”, el cual recoge los

conceptos fundamentales relacionados con algoritmos genéticos y modelos

matemáticos multiobjetivo, base principal de la investigación. A continuación se

realiza la descripción detallada de cada uno de ellos y sus diferentes componentes,

los cuales fueron de gran utilidad dentro del marco del desarrollo de la investigación

en cuanto a los aspectos de formulación matemática y obtención de resultados.

3.1 Modelo matemático multiobjetivo

Como fue presentado en el capítulo anterior, el diseño de un sistema de rutas de

transporte público colectivo urbano (TPCU) puede ser tratado como un problema

de optimización de uno o varios objetivos.

De acuerdo al estado del arte de la materia, a lo largo del tiempo, y en la medida

que ha evolucionado el desarrollo y la capacidad computacional, se han venido

desarrollando diferentes aportes que buscan resolver el problema desde diferentes

ópticas particulares, algunos con algunas limitaciones importantes y otros con

enfoques muy diferentes.

En este caso en particular, luego de la revisión literaria realizada, y a partir de los

objetivos definidos para la validación de la hipótesis de trabajo, se consideró

adecuado que el problema fuera tratado como un problema matemático

multiobjetivo que recogiera, por un lado, la necesidad de optimización de los costos

generalizados de transporte de los usuarios y, por otro, la eficiencia de los recursos

necesarios de los operadores del servicio. Es decir, que la solución del problema

debió proporcionar un sistema de rutas de TPCU balanceado entre los intereses


de ambas partes, sin favorecer a ninguno en particular, lo que se denomina como

un “problema multiobjetivo”.

Es así como en la mayoría de este tipo de problemas de decisión no se tiene un

único objetivo, sino diversos objetivos y muchas veces, en conflicto entre sí. Los

modelos que reflejan dicha situación se denominan multiobjetivo y se caracterizan

por no poseer una única solución óptima, sino que poseen un conjunto de

Soluciones Eficientes o Soluciones No Dominadas. La posibilidad de trabajar con

modelos multiobjetivo brinda flexibilidad, ya que se retira la condición de

representar los objetivos en una única función, lo que muchas veces conduce a

simplificaciones erradas, pero esta mayor flexibilidad genera una mayor

complejidad en la resolución (Collete & Siarry, 2004). A continuación se describen

los principales elementos conceptuales y teóricos de este tipo de problemas de

optimización matemática.

En general, la estructura de un modelo con k objetivos tiene la estructura que se

muestra a continuación:

𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟: ⌊𝑍1(𝑥), 𝑍2(𝑥), 𝑍3(𝑥), … , 𝑍𝑘(𝑥) ⌋ = 𝑍(𝑥)

𝑆𝑢𝑗𝑒𝑡𝑜 𝑎: 𝑔(𝑥) ≤ 0

𝑥 ≥ 0

Donde:

Z(x): define el conjunto de las distintas funciones objetivo

Zh(x): es una función objetivo en particular, con h=1,2 …. k

En este caso no se dispone de una sola solución óptima, ya que una solución

factible X1 puede ser mejor que otra solución X2 de acuerdo al objetivo Z1, pero

peor según el objetivo Z2, por lo que, sin una jerarquización clara de las funciones

objetivo no se puede determinar qué solución es mejor. Así es como se definen las

soluciones no dominadas, encontrándose que X1 es dominada por X2 si y solo si

se cumple (Durán Micco, 2016):




𝑍ℎ(𝑥2) ≥ 𝑍ℎ(𝑥1); ℎ = 1,2, … , 𝑘

𝑍ℎ(𝑥2) > 𝑍ℎ(𝑥1); 𝑝𝑎𝑟𝑎 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑎𝑙𝑔ú𝑛 ℎ

En otras palabras, X2 domina a X1 si es mejor o igual de acuerdo a todas las

funciones objetivo y estrictamente mejor para al menos un objetivo (Durán Micco,

2016).

Luego, se dice que una solución factible es eficiente si no es dominada, por ninguna

otra solución. El conjunto de soluciones eficientes también se llama conjunto de

Pareto (Durán Micco, 2016).

Para seleccionar una única solución del conjunto de Pareto, se debe asignar algún

valor de comparación entre los distintos objetivos. Según la etapa en que se realice

dicho proceso, los métodos de solución de problemas multiobjetivo, se dividen en

tres familias (Durán Micco, 2016), las cuales se muestran en la Ilustración 3-1.

Ilustración 3-1: Métodos de optimización


•La comparación o ponderación entre los objetivos se realiza antes de la ejecución de la optimización. Así, se tiene que realizar solo un proceso de búsqueda, que entregará la solución que represente las prioridades asignadas en un principio. El hecho de realizar solo una búsqueda implica un menor esfuerzo, pero se debe tener en cuenta el trabajo de realizar las ponderaciones antes de la optimización (Durán Micco, 2016)

Métodos de optimización A Priori

•Se requiere participación del tomador de decisiones durante el proceso de optimización para guiar el proceso de búsqueda, según sus preferencias respecto a los objetivos. Es difícil ejecutar este tipo de métodos por la necesidad de monopolizar la atención del tomador de decisiones por un prolongado periodo de tiempo (Durán Micco, 2016).

Métodos de Optimización Progresivos

•Se busca un conjunto de soluciones que están igualmente espaciados dentro del conjunto de Pareto, para luego seleccionar una solución desde este conjunto generado. Estos métodos requieren de un mayor esfuerzo al realizarse múltiples procesos de búsqueda, pero evitan la necesidad de modelar las preferencias del tomador de decisiones (Durán Micco, 2016).

Métodos de Optimización A Posteriori


Por otra parte, existen múltiples métodos para resolver modelos multiobjetivos, no

pudiéndose elegir o destacar unos mejores que otros. Sin embargo, uno de los más

destacados es el método de escalarización que se describe en la siguiente

ilustración.

Ilustración 3-2: Método de escalarización


Es importante destacar que para problemas no combinatorios, estos métodos son

capaces de entregar todos los puntos de la frontera de Pareto, si se consideran los

parámetros adecuados. Sin embargo, para problemas combinatorios

multiobjetivos, existen soluciones eficientes o no dominadas que, no pueden ser

encontradas por métodos de escalarización. Esta es una de las complejidades que

presentan los problemas combinatorios multiobjetivos. (Ehrgott & Gandibleux,

2004).

Método de escalarización

Objetivo

Convertir el problema

multiobjetivo en un problema

con un objetivo, el que

se resuelve para encontrar

soluciones eficientes.

Métodos

Suma ponderada

consiste en sumar las

funciones en una única

función, con ponderaciones que pueden ser

obtenidas según distintos

criterios

Dado que las preferencias del

decisor se asignan antes del proceso de optimización, corresponde a un método de optimización A

Priori

E-restricción

consiste en dejar uno de los

objetivos, convertir los

otros en restricciones y

resolver el problema

resultante.

método de optimización A Posteriori, ya

que se obtiene un conjunto de

soluciones eficientes sin considerar las

preferencias del tomador de decisiones




Metaheurísticas multiobjetivo: Debido a la complejidad de los problemas

combinatorios multiobjetivo, es muy difícil resolverlos en forma exacta, por lo que

en general se usan métodos para encontrar aproximaciones de la frontera de

Pareto, principalmente metaheurísticas (Durán Micco, 2016).

Las metaheurísticas son estrategias de alto nivel para explorar el espacio solución

de un problema, mediante la operación en forma iterativa de heurísticas

subordinadas. Estos algoritmos pueden ser adaptados y aplicados a un gran

número de problemas distintos por lo que han sido ampliamente estudiados durante

los últimos años, demostrando su capacidad de resolver problemas complejos.

(Osman & Laporte, 1996) (Talbi, 2009).

Los algoritmos evolutivos (AE) han sido especialmente exitosos en la aplicación a

problemas multiobjetivo, ya que al trabajar con poblaciones de soluciones en vez

de soluciones particulares, permiten encontrar conjuntos de soluciones no

dominadas diversas en una sola ejecución. Estos algoritmos se caracterizan por

aplicar conceptos de la evolución natural de las especies al campo de la

optimización (Durán Micco, 2016).

Los AE corresponden a metaheurísticas basadas en población capaces de resolver

problemas combinatorios de alta complejidad, siendo especialmente apropiados

para la resolución de problemas multiobjetivo, por su habilidad de encontrar

conjuntos de soluciones no dominadas en una única ejecución (Durán Micco,

2016).

A partir de una población inicial, generada mediante un proceso de inicialización

determinado, se inicia el proceso iterativo. En cada iteración o generación, y

mientras no se alcance la condición de término, se seleccionan las soluciones

“padres”, que a través de operadores de cruzamiento y mutación dan origen a la

descendencia. Luego, cada una de las nuevas soluciones debe ser evaluada y

posteriormente se procede a una nueva etapa de selección y reemplazo, en la que

se debe considerar factores de calidad y diversidad (Durán Micco, 2016).


La principal diferencia entre los AE simples y multiobjetivos es que en los últimos

se busca tanto la convergencia de la solución (cercanía a la frontera de Pareto

real), como la diversidad de la misma (que el conjunto de soluciones encontrado

se encuentre bien distribuido sobre la frontera de Pareto). Lo anterior convierte a

las metaheurísticas multiobjetivo en problemas biobjetivos por sí mismos. (Talbi,

2009)

Existen distintos indicadores para determinar la calidad de un conjunto de

soluciones, así como comparar el desempeño de distintos algoritmos. Estos se

pueden dividir entre indicadores basados en convergencia, indicadores basados en

diversidad e indicadores híbridos. Dada la naturaleza biobjetivo de estos métodos,

por lo general se utiliza más de un indicador (Durán Micco, 2016).

Ilustración 3-3: Esquema del funcionamiento de un algoritmo evolutivo

Fuente: Elaboración propia.

3.2 Algoritmos genéticos

El presente aparte comprende la descripción general en cuanto a algoritmos

genéticos se refiere en el caso del ruteo de vehículos, abarcando posteriormente




los componentes y principales características del mismo, las cuales son de vital

importancia dentro del desarrollo del presente trabajo de investigación, pues a partir

de ellos se realizará la programación del algoritmo que cumpla con el objetivo

principal de la investigación.

Generalidades

Basado en la teoría de la evolución de C. Darwin que parte de una población inicial

de individuos para éste caso ruteo de vehículos donde cada uno representa

soluciones iniciales factibles, pero subóptimas, cada una posee un valor que

representa la bondad de dicha solución, ésta bondad representa una adaptación

del ruteo de vehículos al problema, que en su incremento verá proporcionalmente

aumentada la probabilidad de ser seleccionado para el proceso de selección en el

cruzamiento de la información con otro sistema de igual manera. El cruce produce

nuevos sistemas de ruta, los cuales serán descendientes de los anteriores y

compartirán características de las diferentes bondades que maximizan el nivel del

servicio al usuario, ellas son las soluciones obtenidas en el algoritmo que

evolucionan mediante la aplicación de tres operadores: selección, cruzamiento y

mutación que combinan y modifican a los individuos de la población creando una

nueva.

Para la solución del problema de ruteo de vehículos de transporte público,

usualmente se consideran cuatro operadores de mutación: intercambio de la

posición de dos nodos en una ruta, inversión del orden de la ruta, reinserción de un

nodo en una ruta diferente a la original y selección de una sub-ruta para insertarla

en otro lugar de la solución (Petch & Salhi, 2007).

Operadores evolutivos del algoritmo genético

Selección: el algoritmo genético suele utilizar distintas técnicas para seleccionar a

los individuos que deben copiarse hacia la siguiente generación. Algunos de estos

métodos son mutuamente exclusivos, mientras que otros pueden utilizarse en


combinación, un proceso que se lleva a menudo. Las técnicas de selección más

comunes son las que se describen a continuación:

o Selección elitista: garantiza la selección de los miembros más aptos de

cada generación (Aguado & Jiménez, 2013).

o Selección proporcional a la aptitud: los individuos más aptos tienen

más probabilidad de ser seleccionados, pero no la certeza (Aguado &

Jiménez, 2013)

o Selección por rueda de ruleta: es una forma de selección proporcional

a la aptitud en la que la probabilidad de que un individuo sea seleccionado

es proporcional a la diferencia entre su aptitud y la de sus competidores

(Aguado & Jiménez, 2013).

o Selección escalada: al incrementarse la aptitud media de la población,

la fuerza de la presión selectiva también aumenta y la función de aptitud

se hace más discriminadora. Este método puede ser útil para seleccionar

más tarde, cuando todos los individuos tengan una aptitud relativamente

alta y sólo les distingan pequeñas diferencias en la aptitud (Aguado &

Jiménez, 2013).

o Selección por torneo: se eligen subgrupos de individuos de la

población, y los miembros de cada subgrupo compiten entre ellos.

Sólo se elige a un individuo de cada subgrupo para la reproducción


o Selección por rango: a cada individuo de la población se le asigna

un rango numérico basado en su aptitud, y la selección se basa

en este ranking, en lugar de las diferencias absolutas en aptitud.

La ventaja de este método es que puede evitar que individuos muy




aptos ganen dominancia al principio a expensas de los menos

aptos, lo que reduciría la diversidad genética de la población y

podría obstaculizar la búsqueda de una solución aceptable


o Selección generacional: la descendencia de los individuos

seleccionados en cada generación se convierte en toda la

siguiente generación. No se conservan individuos entre las

generaciones (Aguado & Jiménez, 2013).

o Selección por estado estacionario: la descendencia de los

individuos seleccionados en cada generación vuelve acervo

genético preexistente, reemplazando a algunos de los miembros

menos aptos de la siguiente generación. Se conservan algunos

individuos entre generaciones (Aguado & Jiménez, 2013).

o Selección jerárquica: los individuos atraviesan múltiples rondas

de selección en cada generación. Las evaluaciones de los

primeros niveles son más rápidas y menos discriminatorias,

mientras que los que sobreviven hasta niveles más altos son

evaluados más rigurosamente. La ventaja de este método es que

reduce el tiempo total de cálculo al utilizar una evaluación más

rápida y menos selectiva para eliminar a la mayoría de los

individuos que se muestran poco o nada prometedores, y

sometiendo a una evaluación de aptitud más rigurosa y

computacionalmente más costosa sólo a los que sobreviven a esta

prueba inicial (Aguado & Jiménez, 2013)

Cruce y mutación (Aguado & Jiménez, 2013): Una vez que la selección ha elegido

a los individuos aptos, éstos deben ser alterados aleatoriamente con la esperanza


de mejorar su aptitud para la siguiente generación. Existen dos estrategias básicas

para llevar a cabo este procedimiento las cuales se describen a continuación:

o Cruce: implica elegir a dos individuos para que intercambien segmentos

de su código, produciendo una “descendencia” artificial cuyos individuos

son combinaciones de sus padres. Este proceso pretende simular el

proceso análogo de la recombinación que se da en los cromosomas

durante la reproducción sexual. Las formas comunes de cruzamiento

incluyen al cruzamiento de un punto, en el que se establece un punto de

intercambio en un lugar aleatorio del genoma de los dos individuos, y

uno de los individuos contribuye todo su código anterior a ese punto y el

otro individuo contribuye todo su código a partir de ese punto para

producir una descendencia, y al cruzamiento uniforme, en el que el valor

de una posición dada en el genoma de la descendencia corresponde al

valor en esa posición del genoma de uno de los padres o al valor en

esa posición del genoma del otro padre, elegido con un 50% de

probabilidad.

Los operadores genéticos en este caso son operadores con memoria,

guardando en cada iteración los códigos genéticos de los mejores

individuos a través de las generaciones. Los procesos de evolución

darwiniana generalmente son procesos miméticos a través de

generaciones.

o Mutación: al igual que una mutación en los seres vivos cambia un

gen por otro, una mutación en un algoritmo genético también causa

pequeñas alteraciones en puntos concretos del código de un

individuo.




Componentes de un algoritmo genético

Los componentes del algoritmo genético son los mostrados en la Ilustración 3-4.

Ilustración 3-4: Componentes del algoritmo genético


o Problema a optimizar: Generalmente los problemas a optimizar por

medio de algoritmos genéticos son problemas de optimización

complejos, donde se tienen diferentes parámetros o conjuntos de

variables que deben ser combinadas para su solución, así como

problemas con muchas restricciones y problemas con espacios de

búsqueda muy grandes. (Aguado & Jiménez, 2013).

Gracias a sus ventajas, los algoritmos genéticos no requieren

información matemática adicional sobre optimización, por lo que

pueden tomar otro tipo de funciones objetivo y todo tipo de

restricciones definidas sobre espacios discretos, continuos o espacios

de búsqueda combinados (Aguado & Jiménez, 2013).

o Representación para la solución del problema: En cuanto a la

solución del problema lo importante es definir la estructura del

Problema a optimizar

Representación para la solución del problema

Decodificación del cromosoma

Evaluación de un individuo


cromosoma de acuerdo con el espacio de búsqueda. En este caso, la

representación más utilizada es la binaria, debido a la facilidad de

manipulación por los operadores genéticos, su fácil transformación en

números enteros o reales, además de la facilidad que da para la

demostración de teoremas (Aguado & Jiménez, 2013).

o Decodificación del cromosoma: La codificación de números reales

en cadenas de números binarios se debe realizar teniendo en cuenta

que la cadena no representa un número real, sino que este número

binario etiqueta un número dentro del intervalo inicialmente fijado


o Evaluación de un individuo: muestra el valor de aptitud de cada uno

de los individuos. Esta aptitud viene dada por una función que es la

unión entre el mundo natural y el problema a resolver

matemáticamente. Esta función de aptitud es particular para cada

problema particular a resolver y representa para un algoritmo

genético lo que el medio ambiente representa para los humanos


Ventajas y limitaciones de un algoritmo genético:

La tabla siguiente muestra un comparativo entre las ventajas y limitaciones que

presenta el desarrollo o la aplicación de algoritmos genéticos para la solución de

problemas de optimización.




Tabla 3-1 Ventajas y desventajas del algoritmo genético

VENTAJAS LIMITACIONES

Son intrínsecamente paralelos

El lenguaje para especificar soluciones candidatas debe ser robusto, capaz de tolerar cambios aleatorios que no produzcan errores fatales o resultados son sentido. Por lo que se debe definir una representación del problema.

Tienen descendencia múltiple por lo que pueden explorar el espacio de soluciones en múltiples direcciones a la vez.

Elección cuidadosa de la función de aptitud, al elegirla mal o de manera inexacta, el algoritmo puede terminar resolviendo un problema equivocado o no puede encontrar la solución al problema.

Habilidad para manipular muchos parámetros simultáneamente.

Si el tamaño de la población es muy pequeño, puede que el algoritmo no explore suficientemente el espacio de soluciones para encontrar las más consistentes.

Trabajan sobre un conjunto codificado de soluciones, no sobre las soluciones mismas.

Si el ritmo de cambio genético es demasiado alto o el sistema de selección se escoge inadecuadamente, puede alterarse el desarrollo de esquemas beneficiosos y la población puede entrar en catástrofe.

Utilizan información simple para determinar la aptitud de los individuos

No se recomienda la utilización de algoritmos genéticos en problemas resolubles de manera analítica ya que se utilizaría más tiempo del debido para su solución, pudiéndose realizar por el método analítico tradicional que requiere menos tiempo.

Usan procesos de transición probabilística para la búsqueda de la solución.

Convergencia prematura en poblaciones pequeñas en donde emerge un individuo excesivamente apto que hace que el algoritmo converja hacia el óptimo local que representa ese individuo.

Es bastante útil para resolver problemas cuyo espacio de soluciones potenciales es realmente grande (problemas no lineales)

Funciones de aptitud engañosa, en las que la situación de los puntos mejorados ofrece información engañosa sobre donde se encuentra probablemente el óptimo global.

El paralelismo implícito del algoritmo permite superar un gran número de posibilidades y encontrar resultados óptimos en un corto período de tiempo, tras muestrear directamente solo regiones pequeñas del vasto paisaje adaptativo.

Se desenvuelven bien en problemas con un paisaje adaptativo complejo.


No dependen de un conocimiento previo, sus soluciones son aleatorias, todos los caminos de solución están abiertos por lo que puede generar soluciones novedosas y creativas que de haber estado sujeto a conocimiento previo, posiblemente se hubiese descartado.


4. Formulación matemática del problema

Como ha sido mencionado a lo largo de todo este trabajo, la hipótesis central de

esta investigación busca identificar la potencial oportunidad que existe en el

contexto de las ciudades intermedias colombianas, como en el caso de Neiva,

Huila, de obtener diseños de sistemas de rutas de transporte público colectivo

urbano más eficientes (medida dicha eficiencia en términos de indicadores

operacionales que permitan demostrar esta condición a través de un ejercicio

comparativo entre varias alternativas de diseño) por medio de la formulación de un

modelo matemático (Ortúzar, J. de D. y Willumnsen, L., 1996), en contravía de los

métodos empíricos convencionales.

Con el fin de lograr el objetivo anterior, y una vez realizada la revisión del estado

del arte y los fundamentos teóricos que soportan los modelos matemáticos que se

han desarrollado para la resolución de este tipo de problemas de optimización, se

procedió con la formulación de un modelo que considerara la optimización del

problema desde diferentes enfoques (multiobjetivo), con el fin de reducir el impacto

negativo a los usuarios y prestadores del servicio (operadores) de los sistemas,

ayudando a mejorar el deterioro del TPCU de las ciudades intermedias de

Colombia, y proporcionando una verdadera herramienta de apoyo a la toma de

decisiones para los estructuradores de estos sistemas y las entidades públicas,

contribuyendo a mejorar las condiciones financieras, de competitividad y movilidad

urbana de las ciudades intermedias del país.

Con el fin de lograr validar la oportunidad identificada en esta materia, se procedió,

de acuerdo a las problemáticas identificadas, a realizar la formulación de un modelo

Formulación matemática del problema 61

matemático multiobjetivo, adecuado para las condiciones colombianas, orientado

a la obtención de diseños de sistemas de rutas enfocados tanto en maximizar el

nivel de servicio al usuario, reduciendo sus costos generalizados de transporte

(principalmente tiempo de viaje), así como en lograr una minimización de los

recursos necesarios por medio del mejoramiento de la ocupación promedio de los

buses, representado en términos del índice de pasajeros por kilómetro (IPK) de

estos sistemas.

La formulación del modelo matemático multiobjetivo propuesto en este trabajo de

investigación, partió de la revisión detallada de todo el marco conceptual y de

referencia de estudios similares realizados en diferentes partes del mundo

(Mauttone Vidales, Cancela, & Urquhart, 2003), así como de la propuesta emanada

de la iniciativa del investigador a partir de su propia experiencia y comprensión de

la temática. Los principales modelos identificados, que sirvieron como referente de

estudio, se presentaron condensados en el correspondiente capítulo de

“Fundamento teórico”.

De esta manera, el presente capítulo, se estructura de la siguiente manera: en

primer lugar, es necesario establecer las generalidad y supuestos que se

consideraron previamente para la formulación del modelo matemático de

optimización, tales como: su naturaleza multiobjetivo, su aplicabilidad en un caso

de prueba real, los resultados esperados, los insumos necesarios para su

funcionamiento, la definición de su alcance, las restricciones que se considera

tendrán el modelo, entre otros; en segundo lugar, se realiza la formulación formal

del modelo matemático de optimización, es decir las dos (2) ecuaciones

matemáticas que serán objeto de optimización mediante la utilización del algoritmo

genético que será desarrollado más adelante; en tercer lugar, se presenta el

conjunto de restricciones que tendrá el modelo y con las cuales se controlará que

los resultados obtenidos mediante el proceso de optimización se encuentren dentro

de un rango deseable de parametrización, lo cual garantizará la coherencia,

aplicabilidad y equilibrio de los resultados obtenidos; en cuarto lugar, se presenta




de manera general toda la formulación del modelo matemático finalmente definido

por el investigador (funciones objetivo y conjunto de restricciones), el cual se

someterá a prueba mediante el presente trabajo, a fin de demostrar si su uso en

efecto conduce a resultados de sistemas más óptimos en comparación con los

métodos convencionales usados en el medio nacional; finalmente, en quinto lugar,

se resaltan las limitaciones y las restricciones que tiene la herramienta formulada,

con el objeto de establecer la verdadera expectativa de su funcionabilidad, restando

espacio a interpretaciones inadecuadas acerca de sus resultados.

Se destaca que la resolución del modelo matemático multiobjetivo formulado en

este capítulo, será el foco del siguiente, por medio de la presentación del

funcionamiento del algoritmo genético y cómo se emplea para encontrar un valor

cercano al óptimo del problema evaluado, lo que conducirá a establecer la cantidad

de rutas y la secuencia de su trazado que proporcionará los mejores indicadores

de eficiencia en razón de los costos generalizados de transporte y el IPK del

sistema, en los términos establecidos en la función de optimización del problema.

4.1 Generalidades y supuestos

A nivel general, la formulación matemática del problema presenta las siguientes

características preponderantes:

Formulación del problema: Puede realizarse desde diferentes enfoques,

dependiendo del objetivo que se busque. Por tanto, las soluciones podrán ser muy

diferentes en función del actor que busque beneficiarse. Algunos modelos

proponen beneficios para el usuario, otros para el operador del servicio, otros para

la sociedad en general, mientras que otros lo hacen combinando los intereses de

varios actores (funciones multiobjetivos). En general, las formulaciones de los

modelos analizados, varían sustancialmente entre uno y otro, dependiendo

también del contexto en el que deseen ser replicados (Israel & Ceder, 1995). En


este caso, se buscó que la formulación del problema permitiera obtener un sistema

de rutas de transporte público, es decir, la cantidad de servicios y el trazado de sus

recorridos, que a partir de los patrones espaciales de viaje, permita atender la

demanda maximizando el servicio al usuario (en términos de tiempo de viaje), a la

vez que maximice los recursos necesarios para su operación (índice de ocupación

o de aprovechamiento de los buses). En otros términos, el producto del modelo

matemático deberá ser un sistema de oferta de transporte público, que atienda la

demanda en el momento y el lugar adecuado, de modo tal que permita la

optimización del mismo, en los términos mencionados anteriormente.

No convexidad y no linealidad: La característica principal de este tipo de

problemas, denominados NP-hard, es que no presentan una única solución debido

al número infinito del espectro de posibles soluciones (Mao-Chang, Hani S, & M.

Hadi, 1998). Por tanto, los problemas no presentan convexidad y linealidad,

haciendo más complejo hallar soluciones óptimas o por lo menos cercanas a esto,

lo que conlleva al uso de metaheurísticas para su solución, encontrándose valores

aproximados. En este caso, se buscó resolver el problema por medio de una

metaheurística evolutiva (como se presenta en el siguiente capítulo), que, aunque

dadas las características del problema, no conducen a una solución única exacta,

sí permitirá obtener una solución lo más óptima posible.

Naturaleza combinatoria: En este tipo de problemas, la posibilidad de incluir

diferentes variables es diversa y dependerá del alcance y objetivo que quiera

dársele al modelo. Es bien entendido, que entre más variables se incluyan, la

complejidad del problema aumentará exponencialmente, requiriéndose de una

mayor complejidad para su resolución, debido a la naturaleza combinatoria del

mismo. Para el caso presente, la formulación del problema buscará reducir al

máximo posible las variables involucradas con el fin de minimizar la cantidad de

operaciones y niveles de decisión del algoritmo al momento de su solución. Las

variables empleadas buscarán representar adecuadamente los intereses tanto de

los usuarios (tiempos de viaje), como de los operadores (IPK).




Múltiples objetivos: Generalmente, la formulación matemática en pro de un actor,

irá en dirección contrapuesta a la de otro diferente. Esto ocurre más directamente

en la relación usuario (o sociedad) versus los intereses de los actores privados

como los operadores del sistema (Kepaptsoglou & Karlaftis, 2009). En el primer

caso, típicamente la solución del sistema será un número elevado de rutas de

recorridos muy cortos, mientras que en el segundo, se obtendrán pocas rutas de

gran extensión que tendrán como consecuencia altos tiempos de viajes para los

usuarios. Por esta razón, la solución al problema, debe encontrar un punto medio

de equilibrio mediante la inclusión de factores que propenden a favor de uno y del

otro.

Disposición espacial de las rutas: Uno de los problemas más difíciles de superar

mediante la utilización de modelos matemáticos para el diseño de sistemas de rutas

de transporte público colectivo, tiene que ver con el arreglo espacial de las rutas en

el territorio (Barra & Kawamoto, 2000), ya que no se logran disposiciones

adecuadas en función de garantizar una cobertura adecuada a la totalidad de la

demanda, debido a la complejidad matemática que su formulación supone. Así

mismo, generalmente estos modelos no consideran elementos como usos del suelo

o del sistema de actividades, por tanto en sus resultados no se ven reflejados de

manera directa estos aspectos importantes en la generación y atracción de los

viajes. Con el fin de superar esta dificultad, será necesario utilizar una red de

transporte que permita representar adecuadamente la disposición espacial del

sistema de rutas analizado, a la vez que la visión del experto seguirá siendo

necesaria para realizar un acomodo adecuado de las mismas en el territorio.

Una vez realizada la búsqueda y analizados los modelos existentes, de acuerdo al

estado del arte presentado, se procedió a la formulación del modelo matemático

multiobjetivo propuesto en este trabajo de investigación, por medio del cual se

espera poder validar la hipótesis del mismo, conduciendo a sistemas de rutas que

contribuyan a mejorar el deterioro actual de estos sistemas en las ciudades


intermedias de Colombia, corrigiendo las fallas estructurales derivadas de diseños

ineficientes y que, por tanto, no satisfacen adecuadamente los niveles de servicio

esperado por los usuarios para ser un modo atractivo para la realización de los

viajes frente a otros menos sustentables, como en el caso de Neiva, Huila.

Las principales consideraciones y supuestos realizados para su formulación, fueron

las siguientes:

El modelo debe ser de naturaleza multiobjetivo, considerando

los intereses de los usuarios y de los operadores. El primero,

se deberá ver reflejado en la minimización de los costos

generalizados de transporte (representado principalmente

por el tiempo de viaje a bordo del vehículo), mientras que el

segundo deberá considerarse en el valor del índice de

pasajeros por kilómetro recorrido de las rutas, lo que es una

medida efectiva del grado de aprovechamiento y de

utilización del sistema y un insumo fundamental para la

evaluación financiera y equilibrio de los sistemas de TPCU.

El modelo deberá poder ser aplicado a un caso real, con el fin

de validar sus potenciales beneficios, que sea representativo

de las condiciones preponderantes del servicio en una ciudad

de tamaño intermedio de Colombia, ya que los casos de

referentes analizados generalmente se han realizado a

situaciones hipotéticas de dimensiones reducidas. Así

mismo, deberá ser contrastable con el diseño de un sistema

realizado por medio de los métodos convencionales y

tradicionales, con el fin de evaluar sus potenciales beneficios

(Cal y Mayor, 2018)




El resultado del modelo matemático deberá ser un modelo de

oferta de servicios, es decir, deberá establecer el recorrido y

la cantidad de rutas que mejor proporcionen una

configuración que atienda la demanda en el momento y en el

lugar que sea ser consumida de acuerdo a la necesidad y a

los patrones de viajes de la población, garantizando un mejor

aprovechamiento de los recursos y contribuyendo a la

viabilización financiera de los sistemas, no solo a través de la

tarifa sino de una mayor productividad de los vehículos.

Los insumos fundamentales para el funcionamiento del

modelo matemático deberán ser dos: la matriz de viajes

origen – destino para un periodo de tiempo determinado y la

red de infraestructura vial (con sus características físicas y

operativas como velocidad, capacidad, número de carriles,

ancho de calzada y demás). La matriz deberá ser utilizada

como elemento que refleje las dinámicas de los patrones

espaciales del comportamiento de la demanda y será

considerada como un reflejo adecuado del sistema de

actividades y de usos del suelo que gobiernan la producción

y atracción de los viajes de una ciudad dentro de un periodo

de tiempo determinado, generalmente el periodo más crítico

de utilización del sistema (hora “pico” o “punta” de mayor

congestión); mientras que, de otro lado, la red vial será

empleada para obtener trazados de rutas que atiendan

adecuadamente la demanda en función de los corredores de

mayor concentración e importancia dentro de la ciudad,

consiguiendo una distribución espacial acorde con las

necesidades de los usuarios y la configuración urbanística de

la ciudad.


Otro elemento que resulta fundamental en la formulación del

modelo matemático multiobjetivo para el diseño de un

sistema de rutas de transporte público colectivo urbano, es la

definición del alcance que se busca del mismo. En este caso

en particular, se estableció que la salida del modelo deberá

ser un conjunto de rutas que orienten el trazado más

favorable para que los costos generalizados de transporte del

usuario sean los menores posibles, así como para que el

valor global del IPK del sistema obtenido sea el mayor. Sin

embargo, no se pretende eliminar el análisis humano para

conseguir una distribución más adecuada de los servicios,

sino que el modelo sea solamente una verdadera herramienta

de apoyo para la toma de decisiones al estructurador, ya que

como fue mencionado anteriormente, existen elementos que

quedan fuera de la formulación del modelo, dada la

complejidad que esto supone.

Finalmente, el modelo propuesto en este trabajo de

investigación, deberá estar sujeto a un conjunto de

restricciones por medio de las cuales se busca garantizar

soluciones sujetas a la realidad de la operación de los

sistemas y que propendan por garantizar unos niveles de

servicio adecuados para los usuarios de los mismos,

viéndose reflejados principalmente en la capacidad de los

buses con la que será diseñado el sistema y en los intervalos

máximos de despacho que serán permitidos para el cálculo

de la longitud real de recorrido de los buses, variables

fundamental para estimar el valor del IPK de todo el sistema

y que reflejan el nivel del servicio prestado al usuario.




A partir de estas definiciones expuestas anteriormente, y de la revisión del estado

del arte de la materia, se procedió a realizar la formulación matemática del

problema, como es presentado en el siguiente numeral.

4.2 Función objetivo del modelo

El primer paso para la formulación matemática del problema de optimización

multiobjetivo, consistió en la definición de la función objetivo del mismo.

Como fue mencionado anteriormente, el problema es de tipo multiobjetivo,

requiriéndose entonces dos (2) funciones objetivo: una que refleje los intereses de

los operadores y otra el de los usuarios.

La primera función, enfocada en el IPK del sistema, representada por medio de Z1,

buscará la maximización de la relación entre la demanda total movilizada (Q) para

el sistema de rutas evaluado, y la distancia total recorrida por todas las rutas (m)

que pertenecen a tal sistema. Esta última deberá ser el resultado de la sumatoria

del producto entre la distancia (D) de cada ruta (j) y la cantidad de buses requeridos

para su operación dentro del espacio de tiempo definido en su segmento más

cargado (qmáxm) considerando la capacidad de los buses (Cbusm). La longitud

total de cada ruta será obtenida como la sumatoria de la distancia de todos los

segmentos (k) que compongan cada ruta, es decir la distancia entre cada par origen

– destino (i) que atienda de la matriz de viaje, incluyendo los tramos que requiera

recorrer para conectar con el próximo segmento a atender.

A partir de las consideraciones anteriores, la formulación de la primera función

objetivo del problema matemático, es la siguiente:


𝑀𝑎𝑥 𝑍1 =𝑄

∑ {[∑ (𝐷𝑜𝑖𝑑𝑖+𝑘−1

𝑖=1 𝐷𝑑𝑖𝑜𝑖+1) + 𝐷𝑜𝑘𝑑𝑘

] ∗𝑞𝑚á𝑥𝑚

𝐶𝑏𝑢𝑠𝑚}

𝑗𝑚=1

∀ 𝑖 ∈ 𝑚 ∈ 𝑅

Donde:

𝑍1 = Índice total de pasajeros por kilómetro del sistema de rutas R (pax/km)

𝑄 = Número total de pasajeros por hora que moviliza el sistema de rutas R (pax)

𝑗 = Número de rutas que componen el sistema de rutas R

𝑚 = Ruta del sistema R

𝑘 = Número de segmentos que componen cada ruta m

𝑖 = Segmento de la ruta m

𝐷𝑜𝑖𝑑𝑖= Distancia asociada a la ruta de tiempo mínimo de viaje entre el origen y el

destino del segmento i (km)

𝐷𝑑𝑖𝑜𝑖+1= Distancia asociada a la ruta de mínimo tiempo entre el destino del

segmento i y el origen del segmento i+1 (km)

𝐷𝑜𝑘𝑑𝑘= Distancia asociada a la ruta de tiempo mínimo de viaje entre el origen y el

destino del segmento k (km)

𝑞𝑚á𝑥𝑚 = Número de pasajeros movilizados en el par origen - destino más cargado

de la ruta m (pax/hora)

𝐶𝑏𝑢𝑠𝑚 = Capacidad de pasajeros movilizados por unidad de transporte de la ruta

m (pax/bus)

𝑞𝑚á𝑥𝑚

𝐶𝑏𝑢𝑠𝑚= Número de buses necesarios para atender la cantidad de pasajeros del

segmento más cargado de la ruta m (buses/hora)

𝑅 = Sistema de rutas evaluado

Respecto de la segunda función objetivo, que representa los intereses de los

usuarios a través del tiempo de viaje, denominada Z2, ésta busca minimizar el

costo del tiempo de viaje de todos los usuarios que utilizan cada ruta (m) que

pertenece al sistema R. El tiempo de viaje de cada ruta será la sumatoria del




producto de la cantidad de usuarios movilizados entre un segmento (i) y el tiempo

de viaje entre el origen – destino del mismo y el necesario para conectar con el

siguiente segmento.

A partir de las consideraciones anteriores, la formulación de la segunda función

objetivo del problema matemático, es la siguiente:

𝑀𝑖𝑛 𝑍2 = ∑ {∑ 𝑞𝑜𝑖𝑑𝑖∗ (𝑡𝑜𝑖𝑑𝑖

+𝑘−1𝑖=1 𝑡𝑑𝑖𝑜𝑖+1

) + 𝑞𝑜𝑘𝑑𝑘∗ 𝑡𝑜𝑘𝑑𝑘

}𝑗𝑚=1 ∀ 𝑖 ∈ 𝑚 ∈ 𝑅

Donde:

𝑍2 = Tiempo total de viaje de los usuarios del sistema de rutas R (min)





𝑞𝑜𝑖𝑑𝑖= Cantidad de pasajeros movilizados entre el origen y el destino del segmento

i (pax)

𝑡𝑜𝑖𝑑𝑖= Tiempo de viaje entre el origen y el destino del segmento i (min/pax)

𝑡𝑑𝑖𝑜𝑖+1= Tiempo de viaje entre el destino del segmento i y el origen del segmento

i+1 (min/pax)

𝑞𝑜𝑘𝑑𝑘= Cantidad de pasajeros movilizados entre el origen y el destino del

segmento k (pax)

𝑡𝑜𝑘𝑑𝑘= Tiempo de viaje entre el origen y el destino del segmento k (min/pax)



4.3 Conjunto de restricciones del modelo

En segundo lugar, para la formulación del problema matemático de optimización,

es fundamental formular el conjunto de restricciones a las que estará sujeta su

solución. En este caso se establecieron dos (2) restricciones con las cuales se

buscó generar una solución realista enfocada en la capacidad de diseño de los

buses del sistema y otra en un tiempo mínimo de paso de los buses.

La primera restricción, denominada “Restricción de frecuencia mínima”, está

representada por un parámetro mínimo establecido en términos de la cantidad de

buses por unidad de tiempo (fmin) por medio de los cuales debe ser atendida la

demanda de todas las rutas (m) que pertenecen al sistema R. Es decir, que si la

relación qmáxm/Cbusm es inferior al valor establecido, se deberá realizar el ajuste

para trabajar siempre al menos con la frecuencia mínima establecida, para

garantizar la prestación adecuada del servicio. Esta restricción busca que la

solución del problema no conduzca a diseños de rutas de sistemas de transporte

público colectivo urbano TPCU deficientes con intervalos de paso altos en contravía

a lo requerido por los usuarios.

A partir de las consideraciones anteriores, la formulación de la primera restricción

del problema matemático, es la siguiente:

𝑞𝑚á𝑥𝑚

𝐶𝑏𝑢𝑠𝑚≥ 𝑓𝑚𝑖𝑛 ∀ 𝑚 ∈ 𝑅

Donde:


𝑞𝑚á𝑥𝑚 = Número de pasajeros movilizados en el par origen - destino más cargado

de la ruta m (pax/hora)


m (pax/bus)




𝑞𝑚á𝑥𝑚



𝑓𝑚𝑖𝑛 = Frecuencia mínima permitida para todas las rutas del sistema R

(buses/hora)


La segunda restricción del modelo matemático, denominada “Restricción de

capacidad máxima de los buses”, busca limitar la solución del problema matemático

a un valor real de capacidad ofertada por unidad de transporte en términos de

pasajeros movilizados para un nivel de servicio determinado. Esta limitación

pretende asegurar la prestación del servicio con un nivel de ocupación adecuada

con el fin de garantizar al usuario una comodidad mínima, ya que de otro modo, el

problema conduciría a soluciones irreales sin considerar la capacidad de los

vehículos.

A partir de las consideraciones anteriores, la formulación de la segunda restricción

del problema matemático, es la siguiente:

𝐶𝑏𝑢𝑠𝑚 ≤ 𝐶𝑚á𝑥 ∀ 𝑚 ∈ 𝑅

Donde:



m (pax/bus)

𝐶𝑚á𝑥 = Capacidad de pasajeros movilizados por unidad de transporte de la ruta m

(pax/bus)



4.4 Modelo matemático multiobjetivo

Las consideraciones plasmadas anteriormente permitieron orientar la formulación

de un modelo matemático multiobjetivo que responda adecuadamente a las

características de los sistemas de transporte urbano de las ciudades intermedias

de Colombia, con el fin de orientar diseño más adecuados que permitan un mejor

aprovechamiento de los recursos disponibles, a la vez que mejoren los niveles de

servicio prestados a los usuarios. Estas consideraciones llevaron a la formulación

formal del problema que es presentado a continuación:

Función objetivo:

𝑀𝑎𝑥 𝑍1 =𝑄

∑ {[∑ (𝐷𝑜𝑖𝑑𝑖+𝑘−1

𝑖=1 𝐷𝑑𝑖𝑜𝑖+1) + 𝐷𝑜𝑘𝑑𝑘

] ∗𝑞𝑚á𝑥𝑚

𝐶𝑏𝑢𝑠𝑚}

𝑗𝑚=1

∀ 𝑖 ∈ 𝑚

𝑀𝑖𝑛 𝑍2 = ∑ {∑ (𝑞𝑜𝑖𝑑𝑖∗ 𝑡𝑜𝑖𝑑𝑖

+𝑘−1𝑖=1 𝑡𝑑𝑖𝑜𝑖+1

) + 𝑞𝑜𝑘𝑑𝑘∗ 𝑡𝑜𝑘𝑑𝑘

}𝑗𝑚=1 ∀ 𝑖 ∈ 𝑚

Sujeto a:

𝑞𝑚á𝑥𝑚

𝐶𝑏𝑢𝑠𝑚≥ 𝑓𝑚𝑖𝑛 ∀ 𝑚 ∈ 𝑅 (𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑓𝑟𝑒𝑐𝑢𝑒𝑛𝑐𝑖𝑎 𝑚í𝑛𝑖𝑚𝑎)

𝐶𝑏𝑢𝑠𝑚 ≤ 𝐶𝑚á𝑥 ∀ 𝑚 ∈ 𝑅 (𝑅𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑐𝑎𝑝𝑎𝑐𝑖𝑑𝑎𝑑 𝑚á𝑥𝑖𝑚𝑎 𝑑𝑒 𝑙𝑜𝑠 𝑏𝑢𝑠𝑒𝑠)

Donde: 𝑍1 = Índice total de pasajeros por kilómetro del sistema de rutas R (pax/km)

𝑍2 = Tiempo total de viaje de los usuarios del sistema de rutas R (min)

𝑄 = Número total de pasajeros por hora que moviliza el sistema de rutas R

(pax)








𝐷𝑜𝑖𝑑𝑖= Distancia asociada a la ruta de tiempo mínimo de viaje entre el origen y

el destino del segmento i (km)

𝐷𝑑𝑖𝑜𝑖+1= Distancia asociada a la ruta de mínimo tiempo entre el destino del

segmento i y el origen del segmento i+1 (km)

𝐷𝑜𝑘𝑑𝑘= Distancia asociada a la ruta de tiempo mínimo de viaje entre el origen y

el destino del segmento k (km)

𝑞𝑚á𝑥𝑚 = Número de pasajeros movilizados en el par origen – destino más

cargado de la ruta m (pax/hora)

𝐶𝑏𝑢𝑠𝑚 = Capacidad de pasajeros movilizados por unidad de transporte de la

ruta m (pax/bus)

𝑞𝑚á𝑥𝑚



𝑞𝑜𝑖𝑑𝑖= Cantidad de pasajeros movilizados entre el origen y el destino del

segmento i (pax)

𝑡𝑜𝑖𝑑𝑖= Tiempo de viaje entre el origen y el destino del segmento i (min/pax)

𝑡𝑑𝑖𝑜𝑖+1= Tiempo de viaje entre el destino del segmento i y el origen del

segmento i+1 (min/pax)

𝑞𝑜𝑘𝑑𝑘= Cantidad de pasajeros movilizados entre el origen y el destino del

segmento k (pax)

𝑡𝑜𝑘𝑑𝑘= Tiempo de viaje entre el origen y el destino del segmento k (min/pax)

𝑓𝑚𝑖𝑛 = Frecuencia mínima permitida para todas las rutas del sistema R

(buses/hora)

𝐶𝑚á𝑥 = Capacidad máxima permitida para todos los buses del sistema R

(pax/bus)



El modelo matemático multiobjetivo formulado, busca la optimización del sistema

desde dos componentes principales: el servicio al usuario, a través de la

minimización del tiempo de viaje entre cada par origen – destino de la matriz,

mientras que, de otro lado, busca la maximización del valor del índice de pasajeros

por kilómetro cuadrado, en favor del prestador del servicio.

El primer componente, se consigue por medio de la unión de todo par origen –

destino a través del camino que resulte más corto en términos de tiempos de viajes,

pero al modelo se ingresa la longitud que corresponda a este camino, lo cual

garantiza que los trazados de las rutas sean los más directos posibles para la

satisfacción de los viajes de los usuarios. Así mismo, la restricción de frecuencia

mínima (cantidad de vehículos por unidad de tiempo de una misma ruta),

garantizan que los tiempos de viaje sean inferiores o al menos los mismos del

sistema de rutas actual, ya que de lo contrario, esto significaría un desmedro a la

condición de prestación del servicio actual.

El segundo componente, busca que el servicio sea prestado a través de la

configuración de rutas que presenten la longitud recorrida más corta posible en

función tanto del intervalo máximo de paso como de la capacidad permitida de los

buses. Lo anterior, se logra evaluando tantas soluciones posibles de sistemas de

rutas como sea posible (trazados y cantidad), hasta encontrar aquella que

represente el valor más alto de IPK. Las diferentes configuraciones de rutas se van

construyendo de manera aleatoria, uniendo cada par origen – destino de la matriz

en términos del camino más corto y luego buscando la conexión del siguiente par

origen – destino a través de la conexión que represente el traslado en vacío más

cercano. La infinitud de posibles combinaciones que esto representa, hace que el

modelo matemático no pueda ser resuelto por medio de metodologías

tradicionales, sino que requiera de métodos más avanzados como metaheurísticas

de poblaciones, que vayan probando diferentes soluciones hasta encontrar cada

vez una mejor.




Una vez este modelo matemático multiobjetivo sea solucionado, deberá aportar la

configuración del sistema de rutas que mejor relación de IPK y tiempos de viaje

represente, reflejado en el número de rutas y la orientación de su trazado sugerido

en función del orden consecutivo en que debe enlazar todos los pares origen –

destino para conseguir la mejor relación de longitud recorrida del sistema,

atendiendo toda la demanda existente durante el periodo de diseño, generalmente

la hora de mayor demanda del mismo (hora “pico”).

4.5 Limitaciones y restricciones del modelo matemático multiobjetivo

Finalmente, resulta importante para una mejor comprensión del alcance y

funcionamiento del modelo matemático multiobjetivo formulado anteriormente, las

siguientes limitaciones que el mismo supone:

Su resultado no es la configuración automática del recorrido nodo a nodo

que deben seguir cada una de las rutas, si no que por el contrario, lo que

persigue es convertirse en una herramienta de apoyo que busca orientar al

estructurador y tomador de decisiones hacia la obtención de diseños más

óptimos en términos físicos y operacionales, para lo cual se sugiere que los

resultados obtenidos sean contrastados vía modelo de asignación frente a

otras opciones como el sistema actual o el obtenido mediante los métodos,

para validar su efectividad.

Pueden plantearse diferentes formas alternativas de configurar los sistemas

de rutas con el fin de encontrar los diseños que mejor relación de IPK

representen. Estas configuraciones podrán variar en función del intervalo

máximo permitido (5, 10, 15 o más minutos), la capacidad límite de los buses

establecida (20, 30, 40 o más pasajeros), la cantidad de rutas evaluadas (10,

15, 20, 30, 40, etc.), el número de opciones de sistemas evaluados (que


podrán superar los millones de eventos), un valor mínimo permitido de IPK

para cada ruta (> 1,0, por ejemplo), etc. Así mismo, podrán establecerse

soluciones particionadas del problema, prefiriendo por ejemplo, solucionar

el diseño de las rutas subdividiendo el problema en partes menores (3, 4,

10, etc.), en función en el porcentaje que concentra la demanda (partes

iguales del 20%, por ejemplo). Otra opción, puede llegar a ser la evaluación

individual de cada par origen – destino y el camino más corto para conectar

el siguiente sin caer por debajo de un valor mínimo establecido de IPK. Todo

lo anterior puede conducir a obtener escenarios más favorables que

permitan obtener diseños más óptimos y podrán ser evaluados.

Otro elemento que puede llegar a ser objeto de discusión, tiene que ver con

las variables a evaluar para determinar si el sistema diseñado mediante el

modelo matemático propuesto es más eficiente comparado con otro

existente o diseñado por los métodos convencionales. Este trabajo de

investigación propone que elementos como el tiempo promedio de viaje y de

espera, el valor global del IPK de todo el sistema, el intervalo promedio de

despacho, el porcentaje de cobertura espacial, el tamaño de la flota de

buses, el porcentaje de transferencias, porcentaje de superposición del

sistema, entre otros, sirvan de referente de comparación y sea mediante su

contraste que se pueda concluir si el diseño obtenido efectivamente conduce

a potenciales beneficios o por el contrario no lo consigue.

Así mismo, se destaca que el método propuesto no erradica la participación

subjetiva del experto, ya que en todo caso, deberá ser éste quién defina a

detalle el recorrido calle a calle de cada una de las rutas, solucionando

factores como su disposición espacial, la pertinencia de sus recorridos

(sentidos de circulación de las calles), zonas de retorno, extensión de los

trazados, entre otros elementos a considerar para la operación y prestación

del servicio exitosa del sistema finalmente diseñado.




Un elemento considerado como una deficiencia del método propuesto, es

que no considera aquellas zonas que dentro de la matriz origen – destino no

tengan viajes ni producidos ni atraídos, por tanto no genera rutas que den

cobertura a dichas zonas. Esto puede ser solventado por el experto al

momento de trazar los recorridos.

De igual manera, el modelo matemático propuesto no tiene la capacidad de

considerar recorridos que se concentran en las mismas calles, por tanto no

brinda una solución desde el punto integral al problema, ya que lo hace

únicamente considerando los casos individuales para para par origen -

destino. Esto se convierte en una alternativa de optimización que puede

llegar a ser considerada por el experto al momento del diseño final del

sistema.

Con el fin de reducir la cantidad de operaciones matemáticas a realizar para

la solución del problema, se sugiere la simplificación de la zonificación

empleada (trabajando un valor entre 30 a 50 zonas de acuerdo al tamaño

de la ciudad), así como emplear una red vial igualmente simplificada que

permita darle al problema un tratamiento más manejable. Entre más tamaño

tenga la zonificación y la red vial, el problema tiene mayores dificultadas para

su solución en términos de software.

En el siguiente capítulo se presenta el desarrollo y aplicación del algoritmo genético

por medio del cual es posible solucionar el problema matemático multiobjetivo

formulado, permitiendo encontrar la mejor solución al mismo en los términos

establecidos.

5. Desarrollo y aplicación del algoritmo genético

De acuerdo con la revisión del estado del arte, presentada en capítulos anteriores,

el investigador de este trabajo concluyó que el método más adecuado para resolver

el problema de optimización multiobjetivo planteado en el numeral anterior, deberá

ser una metaheurística de tipo evolutivo, dados los casos de éxito que se han

presentado en investigaciones de este mismo tipo. En particular, se eligió el

algoritmo de tipo genético, el cual permite hacer una exploración del campo de

soluciones por medio del principio de generación, mutación y cruzamiento,

evaluando millones de soluciones posibles, lo que conduce a resolver el problema

encontrando soluciones muy cercanas al óptimo por medio de un proceso iterativo

que es descrito a continuación.

A partir de lo anterior, el presente capítulo expone el procedimiento llevado a cabo

en esta investigación para el desarrollo y la aplicación del algoritmo genético por

medio del cual se solucionó el problema matemático multiobjetivo formulado.

El algoritmo genético desarrollado y aplicado para resolver el problema, consta de

seis (6) partes fundamentales, las cuales se desarrollan de manera sistemática y

secuencial, tantas veces como sea posible, acercándose cada vez más a la

solución óptima del problema, presentadas en la Ilustración 5-1.

80

Potenciales beneficios del diseño de un sistema de rutas de TPCU



Ilustración 5-1: Desarrollo del algoritmo genético


A continuación, se explica a detalle cada una de las fases desarrolladas por medio

de las cuales se va realizando la aproximación a soluciones cada vez mejores,

explorando de manera aleatoria todo el campo posible de soluciones. Al finalizar,

se presenta el código de programación que se realizó para la automatización del

proceso, dada la alta complejidad matemática del mismo, empleando el lenguaje

de programación Visual Basic (VB) de Microsoft, lo que permitió poner en

funcionamiento el algoritmo para dar tratamiento a una mayor cantidad de

alternativas de solución.

1. Generación

2. Evaluación

3. Selección

4. Crossover

5. Mutación

6. Elección

Desarrollo y aplicación del algoritmo genético 81

5.1 Generación de soluciones de diseños de sistemas de rutas de TPCU

En primer lugar, el desarrollo del algoritmo genético, parte de la generación de

diferentes soluciones de diseños de rutas de TPCU para ser evaluadas en el

modelo matemático formulado. Es decir, un sistema de rutas consta de un arreglo

de X cantidad de rutas, cada una con un trazado o recorrido definido y por tanto

con una longitud de cada ruta conocida.

La generación de soluciones consiste en establecer sistemas de oferta de rutas

que atiendan la demanda de usuarios de transporte público colectivo urbano para

un periodo de tiempo determinado, en este caso, la hora pico del sistema.

Un sistema de oferta de rutas consiste en determinar el número de servicios

prestados así como la secuencia espacial que debe recorrer cada uno para atender

adecuadamente la demanda de los usuarios, en el lugar y en el instante que es

requerida.

De acuerdo con los principios del algoritmo genético, la generación de soluciones

debe obedecer a un proceso aleatorio, en el cual las mismas se generan a partir

de parámetros que vayan siendo resueltos al azar.

En este caso, los parámetros que determinan un sistema de rutas (R) consisten en

el número (j) de rutas (m) y en la cantidad (k) y orden de los segmentos (i) de la

matriz origen – destino, que atiende cada una. Dichos parámetros son generados

de manera aleatoria, permitiendo obtener tantas soluciones como se desee, las

cuales llegan a superar los miles de millones.

En otras palabras, la cantidad de rutas de un sistema R se genera de manera

aleatoria, siendo por ejemplo 25 rutas, y a su vez el número de segmentos O-D que

atiende cada una, así como su secuencia, es generada también de manera

82




aleatoria, estableciendo por ejemplo que la ruta 1 será conformada por 12

segmentos O-D y el orden de los mismos será la secuencia 5-33-2-67-101-99-20-

205-1-68-175-14, mientras que la ruta 2 será conformada por 45 segmentos los

cuales serán…..,etc, etc. Es importante considerar que los segmentos no podrán

repetirse en ninguna de las rutas establecidas y que también debe considerarse la

distancia que debe recorrer el bus para alcanzar el próximo segmento que

conforma la ruta. El camino que recorre el bus siempre deberá ser el mínimo

existente de acuerdo a la matriz de tiempos mínimos entre pares OD. Así mismo,

se resalta que entre más segmentos existan en la matriz de demanda origen –

destino, la generación de soluciones será un proceso de programación

computacional más complejo, por lo cual se recomienda trabajar con zonificaciones

simplificadas que oscilen entre las 30 y 50 ZATs.

Para el caso de estudio de este trabajo de investigación, se simplificó la zonificación

de la ciudad de Neiva, Huila, a un número total de 33 ZAT (ver Ilustración 5-2),

resaltando que el modelo utilizado para el diseño del SETP empleó 190 zonas.

La anterior zonificación, permitió obtener un total de 1089 segmentos OD (33 X 33),

los cuales hubiesen sido de 36.100 segmentos utilizando la zonificación anterior, y

el problema hubiese presentado una complejidad casi inmanejable para la

programación del algoritmo genético.

En la primera iteración el sistema de rutas parte de cualquier configuración posible,

construida de manera aleatoria; mientras que en las sucesivas se genera siempre

y cuando el sistema predecesor no logre encontrar otra opción más eficiente luego

de su evaluación en la función objetivo del modelo matemático, una vez surtido el

proceso de selección/crossover/mutación, como se explica más adelante.

Cada sistema de rutas generado es denominado un cromosoma dentro de una

población compuesta por una cantidad predefinida, en este caso 100.


Ilustración 5-2: Zonas de análisis de transporte para la generación de soluciones


Dado que el proceso de generación de sistemas de rutas posibles, es totalmente

aleatorio, el investigador de este trabajo logró plantear diferentes alternativas para

su generación, variando parámetros como la cantidad de parámetros o segmentos

origen-destino máximos que componen cada una de las rutas generadas. Cada

alternativa de generación de sistemas fue proporcionando cada vez más soluciones

con mayores grados de eficiencia, producto del proceso de aprendizaje incremental

del propio investigador y su entendimiento del problema y funcionamiento de la

herramienta.

84




En total, se plantearon cuatro (4) formas diferentes de generar aleatoriamente

sistemas de rutas a partir de la matriz origen-destino del transporte público para

una unidad de tiempo determinada, en este caso la hora de mayor demanda del

sistema para la ciudad de Neiva, Huila; las cuales son descritas a continuación.

5.1.1 Alternativa de generación de sistemas de rutas # 1:

Consiste en generar “j” cantidad de rutas “m” (la cantidad es un número aleatorio

entre 1 y un número máximo permitido, dependiendo del tamaño de la matriz OD,

para este caso se usó 30) y para cada ruta se configura de manera aleatoria la

secuencia “k” de los diferentes pares OD “i” que debe atender. El número de

opciones de sistemas evaluados podrán superar los millones de eventos,

dependiendo de la cantidad que se desee.

Esta alternativa tiene como dificultad especial que termina generando rutas que

unen segmentos OD separados por grandes distancias y de magnitudes de viajes

muy disímiles, lo que repercute en bajos valores de IPK y elevados tiempos de viaje

lo que conduce, por tanto, a resultados indeseados en la función objetivo, como se

observa en los resultados presentados más adelante.


Surge como una oportunidad de mejorar la alternativa anterior, buscando generar

sistemas de rutas que tengan un número prefijo de rutas. Es así como de antemano

se establece que cada uno de los sistemas de rutas de TPCU deberá tener X rutas.

De tal forma, se generan soluciones para diferentes cantidades de rutas “m”

prestablecidas (j = 10, 15, 20, 30, 40, etc.) y para cada uno de estos escenarios se

configura de manera aleatoria la secuencia “k” de los diferentes pares OD “i” que


debe atender cada una de las rutas. El número de opciones de sistemas evaluados

podrán superar los millones de eventos para cada escenario de cantidad de rutas

predefinidas.

Esta alternativa permite hacer un barrido más amplio del espacio de soluciones

posibles, identificando el tamaño del sistema que conduce a resultados más

óptimos, para hacer un énfasis más exhaustivo cerca de esta cantidad de rutas.

Sin embargo, esta alternativa mantiene el problema de la anterior, puesto que

conduce a la estructuración de servicios que relaciona aleatoriamente segmentos

disímiles en ubicación espacial y cantidad de viajes, lo que repercute en largas

rutas con baja ocupación, totalmente contrario a lo buscado en este trabajo de

investigación, ya que el IPK de estas rutas es bajo y el tiempo de viaje es alto.


La alternativa de generación de sistemas de rutas 3, surge como otro intento por

mejorar el proceso de producción aleatorio de sistemas de rutas. En este caso se

generan soluciones particionadas del problema, prefiriendo por ejemplo, solucionar

el diseño de las rutas subdividiendo el problema en partes menores (3, 4, 10, etc.),

en función del porcentaje que concentra la demanda (partes iguales del 20%, por

ejemplo). Estos porcentajes podrán ser propuestos por medio del análisis de la

concentración de demanda organizando los pares OD de mayor a menor y

particionando el problema en función de rangos definidos.

En otras palabras, el problema se resuelve en partes independientes, pero

asegurando una mayor homogeneidad entre la magnitud de los viajes de cada

segmento. Esto se consigue organizando los segmentos en grupos de similares

cantidades de viajes y generando entre ellos sistemas de rutas de manera

aleatoria. Esta alternativa asegura que se relacionen segmentos del mismo orden

de magnitud de los viajes, lo que conduce a obtener mejores valores de IPK. Sin

embargo el problema de las grandes distancias de conexión entre segmentos

86




persiste al igual que en las alternativas anteriores lo que provoca altos tiempos de

viaje en desmedro de los usuarios del sistema.

Posteriormente, cada parte el problema puede ser solucionado por medio de la

alternativa 1 o 2.


Finalmente, la mejor alternativa que pudo ser desarrollada para la generación de

sistemas de rutas a ser evaluadas en la función objetivo del problema de

optimización, fue el producto de buscar una opción que pudiera suplir la necesidad

de homogenización de los segmentos a enlazar, tanto en magnitud como en

ubicación espacial.

De tal forma, esta alternativa consiste en generar cualquiera de las alternativas

anteriores, pero realizando la evaluación individual de segmentos jerarquizados de

pares origen – destino y la secuencia del siguiente par origen – destino, es decir,

ya no se configura de manera aleatoria la secuencia de los diferentes pares OD

que debe atender, sino que se realiza de manera individual y secuencial buscando

la menor distancia entre los mismos, siendo preferible aquellos cuyo destino del

primero sea igual al origen del siguiente, puesto que su distancia de conexión es

cero (0).

Esta alternativa permite obtener sistemas de mayor eficiencia, como se presenta

en el capítulo de elección del mejor sistema de rutas a ser comparado con los

obtenidos por medio de métodos convencionales.

Para este trabajo de investigación se generaron cerca de 110 millones de

soluciones de sistemas posibles, por medio de las 4 alternativas descritas

anteriormente, como se presenta en la siguiente tabla.


Tabla 5-1: Ejemplo del desarrollo del algoritmo genético

Alternativa de generación de

sistemas de rutas de TPCU

Cantidad de

soluciones evaluadas

1 10+E6

2 50+E6

3 30+E6

4 20+E6


5.2 Evaluación de los sistemas de rutas de TPCU generados aleatoriamente

En segundo lugar, una vez generado de manera aleatoria el sistema de oferta de

rutas de transporte público colectivo urbano, éste es evaluado en la función

multiobjetivo presentada en el capítulo anterior.

Como se presenta en la siguiente ilustración, cada uno de los sistemas de rutas de

TPCU generados de manera aleatoria por cualquiera de las alternativas descritas

anteriormente, es evaluado en la función objetivo y su conjunto de restricciones

para lo cual requiere de los insumos de longitud y tiempo total de recorrido en la

hora de análisis del sistema en estudio, así como que se establezca un intervalo

de paso y una capacidad de los buses máxima.

Ilustración 5-3: Proceso de evaluación de sistemas de rutas de TPCU


Longitud y tiempo total

de recorrido del

sistema generado

Intervalo de paso

máximo permitido

Capacidad máxima

de los buses

IPK del

sistema

CGT del

sistema

Modelo

matemático

multiobjetivo

88




Para la evaluación de la solución respectiva en el modelo, es necesario contar con

los siguientes insumos:

Matriz de tiempos mínimos entre cada par origen – destino.

Matriz de distancias asociadas al camino de tiempo mínimo entre cada par

origen – destino.

Matriz de viajes entre cada par origen - destino

Así mismo, la evaluación de la función objetivo puede realizarse para diferentes

valores de la frecuencia mínima permitida (2, 4, 6 o más buses/hora) y una

capacidad límite de los buses establecida (20, 30, 40 o más pasajeros).

Con los insumos anteriores, la evaluación de la función multiobjetivo para cada

sistema de rutas de transporte público colectivo urbano generado, permite

establecer el valor de la longitud real recorrida por el sistema, y mediante la relación

entre la cantidad de pasajeros total de la matriz y lo anterior, permite obtener el

valor del IPK global del sistema; así mismo, permite determinar el valor del tiempo

total de viaje de todos los usuarios de las rutas del sistema, en función de los

diferentes segmentos origen – destino que componen cada una, incluyendo la

conexión entre los mismos.

5.3 Selección de los mejores sistemas de rutas de TPCU evaluados

En tercer lugar, luego de la evaluación de cada solución generada, denominada

“cromosoma” de una determinada población, el algoritmo genético requiere

desarrollar la etapa de selección de los individuos que deben permanecer hacia la

siguiente generación. Algunos de estos métodos son mutuamente exclusivos,

mientras que otros pueden utilizarse en combinación, un proceso que se lleva a

menudo.


Para este caso, el método de selección empleado fue la “selección por rango”, en

el cual a cada individuo de la población se le asigna un rango numérico basado en

su aptitud, y la selección se basa en este ranking, en lugar de las diferencias

absolutas en aptitud. Como ya fue mencionado, la ventaja de este método es que

puede evitar que individuos muy aptos ganen dominancia al principio a expensas

de los menos aptos, lo que reduciría la diversidad genética de la población y podría

obstaculizar la búsqueda de una solución aceptable.

Esta fase del desarrollo del algoritmo genético, permite identificar los sistemas de

rutas de TPCU que tienen un mejor resultado hasta el momento, para proseguir

con éstas a las subsiguientes etapas. Es decir, se realiza una selección de los

sistemas de rutas que, una vez evaluados en la función objetivo de la manera

descrita en la sección anterior, presentan hasta ese instante un mejor resultado,

descartando a los que, por el contrario, tienen los valores más alejados dentro de

la población de sistemas que se está analizando.

En este caso cada población de sistemas de rutas de TPCU evaluado estuvo

conformada por 100 “cromosomas”, es decir, 100 diferentes sistemas generados

aleatoriamente por cualquiera de las 4 alternativas presentadas con anterioridad.

De esos 100 cromosomas, este paso permitió elegir, mediante la evaluación de

cada sistema de rutas de TPCU generado aleatoriamente en la función

multiobjetivo, los 50 que mejores resultados arrojaron (individuos aptos) dentro del

total, para proseguir únicamente con éstos en la siguiente fase del proceso del

desarrollo del algoritmo genético.

5.4 Proceso de crossover o cruzamiento para generar nuevas soluciones de rutas de TPCU

En cuarto lugar, una vez que la selección ha elegido a los individuos más aptos,

éstos deben ser alterados aleatoriamente con la esperanza de mejorar su aptitud

para la siguiente generación.

90




Esta fase del algoritmo genético implica elegir a dos individuos para que

intercambien segmentos de su código, produciendo una “descendencia” artificial

cuyos individuos son combinaciones de sus padres.

Para este caso se ha empleado el método de cruzamiento que incluyen al

cruzamiento de un punto, en el que se establece un punto de intercambio en un

lugar aleatorio del genoma de los dos individuos, y uno de los individuos contribuye

todo su código anterior a ese punto y el otro individuo contribuye todo su código a

partir de ese punto para producir una descendencia.

En otras palabras, en esta parte del código, de los 50 sistemas de rutas de TPCU

generados aleatoriamente, que fueron seleccionados mediante su evaluación en la

función objetivo en el paso anterior por ser los individuos más aptos de su

respectiva generación, se toman de a dos sistemas y se realiza el cruzamiento de

su respectivo código, estableciendo un punto aleatorio dentro de su genoma, lo que

hace posible que de estas dos opciones de sistemas, se produzca una tercera que

deriva de los dos anteriores (padres). Este hijo es el que continúa en el siguiente

paso de ejecución del proceso, como se sigue describiendo en los siguientes

numerales.

Este proceso permite guardar, en cada iteración, los códigos genéticos de los

mejores sistemas de rutas de transporte público colectivo urbano a través de las

generaciones subsecuentes.

5.5 Mutación de los sistemas de rutas de TPCU generados del proceso de cruzamiento

En quinto lugar, al igual que en una mutación en los seres vivos se cambia un gen

por otro, en un algoritmo genético también se emula este proceso con el fin de


causa pequeñas alteraciones en puntos concretos del código de una solución en

particular.

Es así como, para cada uno de los “hijos” de los sistemas de rutas generados en

el paso anterior, mediante el proceso de cruzamiento o crossover, se realiza la

mutación o alteración de un punto específico de su código o genoma, mediante una

alteración aleatoria, lo que conduce a que se genere un sistema de rutas de TPCU

diferente al anterior.

En este caso, el proceso de mutación permite obtener aleatoriamente una nueva

solución del sistema de rutas para que sea evaluada y se identifique si presenta

un mejor resultado que el sistema actual.

5.6 Elección del mejor sistema de rutas de TPCU en cada población de individuos

Finalmente, el desarrollo y aplicación del algoritmo genético, culmina con la

elección de los mejores padres que son identificados luego de los procesos de

cruzamiento y mutación para ser evaluados posteriormente en la siguiente

población.

En este sentido, nuevamente se evalúan en la función multiobjetivo, cada uno de

los nuevos sistemas de rutas de TPCU que se han producido aleatoriamente luego

de surtido el proceso de cruzamiento de dos sistemas y la mutación del hijo que se

produjo de dicha unión. La evaluación de cada sistema se realiza como ya fue

descrito en el paso 2 de este algoritmo, es decir, que a partir de la longitud y el

tiempo total de recorrido de todas las rutas que componen el respectivo sistema

(generadas aleatoriamente), se determina por medio de la ecuación matemática

multiobjetivo, los valores del IPK total y del Costo Generalizado de Transporte,

sujetos a los valores de restricciones del intervalo de paso y la capacidad de los

buses determinado.

92




En este punto el algoritmo realiza la comparación de los resultados de la evaluación

de cada uno de los sistemas de TPCU iniciales versus los resultados de los

sistemas que se produjeron luego de la selección, cruzamiento y mutación de sus

genes, con el fin de determinar cuál presentó los mejores resultados en cada uno

de los casos. Cuando el algoritmo encuentra que el “hijo” reportó un mejor resultado

en la función objetivo, conserva este sistema para que vuelva a surtir todo el

proceso descrito en la siguiente población o, en caso contrario, lo descarta y

continúa con el sistema inicial en la siguiente población.

Este es un proceso iterativo que se repite tantas veces como sea requerido hasta

encontrar convergencia hacia una solución específica, la cual presente los valores

más altos de IPK y los menores de tiempos de viaje para los usuarios.

Se reitera que en este caso, cada población estuvo conformada por un total de 100

cromosomas o sistemas de rutas de TPCU generadas aleatoriamente. En total se

procesaron en el algoritmo más de un millón de poblaciones hasta encontrar la que

reportó mejores resultados en la función objetivo, como se presenta en el siguiente

capítulo.

En la siguiente tabla, se presenta un ejemplo del proceso descrito anteriormente

para la evaluación y selección de una población de sistemas de rutas de TPCU en

particular (solamente se muestran los primero 20 cromosomas de un total de 100

por población).

Allí se observa cómo al final se logran identificar los sistemas que mejores

resultados aportan luego de surtir el proceso descrito del algoritmo, los cuales

conforman la solución inicial de la siguiente población a analizar.

Tabla 5-2: Ejemplo del desarrollo del algoritmo genético para una población X

Cromosoma Población

Inicial Generada

Población Generada en

Bits

f(x)=Z1 ¡¡META!!

MAXIMIZAR

f(x)=Z2 ¡¡META!!

MINIMIZAR

Selección Por

Ranking

Mejores del

Ranking

Mejores Padres en

Binario

Crossover (Aleatoria)

Punto de

Cruce

Mutación (Aleatoria)

Posición del Bit Mutado

Mejores Padres

1 365 101101101 1,19 267120 462 462 111001110 111001111 1 111101111 6 435

2 495 111101111 0,58 294668 487 487 111100111 111100110 111110110 5 502

3 6 000000110 1,33 228831 459 459 111001011 111000110 5 111100110 6 6

4 462 111001110 1,50 224624 6 6 00000110 000001011 000001011 462

5 483 111100011 1,31 241956 483 483 111100011 111010001 6 111010001 465

6 193 011000001 0,59 265005 465 465 111010001 111100011 111100011 193

7 171 010101011 0,77 306667 365 365 101101101 101101011 4 101111011 5 379

8 324 101000100 0,88 266540 475 475 111011011 111011011 111011011 475

9 25 000011001 0,38 238798 52 52 000110100 001001001 7 001001001 73

10 472 111011000 0,74 316874 457 457 111001001 110110100 111110100 7 472

11 73 001001001 0,50 243613 324 462 111001110 111001111 2 111001101 2 461

12 261 100000101 0,03 233370 111 487 111100111 111100110 111100110 486

13 475 111011011 1,14 262394 171 459 111001011 111001010 1 111001010 458

14 111 001101111 0,85 279938 472 6 000000110 000000111 000000011 3 3

15 459 111001011 1,37 269706 193 483 111100011 111100001 4 111100011 2 459

16 398 110001110 0,30 281473 495 465 111010001 111010011 111010011 467

17 52 000110100 1,09 261101 73 365 101101101 101101101 1 101101101 365

18 465 111010001 1,21 298016 25 475 111011011 111011011 111011011 465

19 487 111100111 1,41 280137 398 52 000110100 000101001 5 000101001 41

20 457 111001001 1,08 314163 261 457 111001001 111010100 111010100 468


94




5.7 Código de programación del algoritmo genético

Dada la complejidad matemática que conlleva la ejecución del algoritmo genético

descrito en los numerales anterior, fue necesario realizar su programación en

lenguaje Visual Basic (VB) con el fin de automatizar el proceso. Con este fin se

programó la ejecución de cada una de los pasos de generación, evaluación,

selección, cruzamiento, mutación y elección, para el análisis de sucesivas

poblaciones.

Es importante resaltar que el investigador de este trabajo, adecuó un código de

programación prexistente a las necesidades particulares de este problema con el

fin de agilizar la búsqueda de las mejores soluciones. En ningún momento el

objetivo del trabajo fue como tal producción de un código de programación de alta

complejidad. Éste simplemente se utilizó como una herramienta o recurso para

alcanzar el verdadero fin del trabajo que es el diseño de un sistema de rutas de

transporte público colectivo urbano que demuestre eficiencia en comparación con

los sistemas que son diseñado a partir de los métodos convencionales que se

emplean en el medio a través de heurísticas de “ensayo y error” a visión de experto.

Así mismo, no todo el proceso matemático es adelantado en el código del

algoritmo, dada la complejidad de su programación que esto conllevaría, por tanto

alguna información que requiere el código es suministrada desde fuentes externas

de resultados generados previamente.

Finalmente, en la siguiente tabla, se presenta el código de programación del

algoritmo genético empleado para desarrollar el proceso descrito en el numeral

anterior.


Tabla 5-3: Código de programación del algoritmo genético

PASO 1: GENERACIÓN

Public Sub Genera_Aleatorio()

CantHijoGene = Val(frmControl.txtCantHijoGene.Text) 'generando cantidad de hijos

deseada entre 1 a 100

'Generando Población inicial con valores aleatorios y su conversión a números

binarios

Randomize

With Worksheets("Genetica")

For i = 2 To CantHijoGene + 1

.Cells(i, 1).Value = i - 1

.Cells(i, 2).Value = Int(Rnd() * (10E6 - 0) + 1) 'generando numeros entre 1 al

10E6

.Cells(i, 3).Value = DecToBin(.Cells(i, 2).Value) 'numeros anteriores convertidos a

binario

Next i

End With

PASO 2: EVALUACIÓN

'Copiando la primera generación (osea, los peores padres)


Worksheets("Resultados").Cells(i, 1).Value = Worksheets("Genetica").Cells(i,

2).Value

Next i

'Etiquetando la Hoja "Resultados"

Worksheets("Resultados").Cells(1, 1).Value = "Inicial"

For i = 2 To Val(frmControl.txtNumeGene.Text) + 1

Worksheets("Resultados").Cells(1, i).Value = i - 1

Next i

End Sub

96




PASO 3: SELECCIÓN

Public Sub Ejecuta_Funciones()


SumaFunc = 0


.Cells(i, 4).Value = BinToDec(.Cells(i, 3).Value)

.Cells(i, 5).Value = (.Cells(i, 4).Value) 'Evalúa la función objetivo Z1

SumaFunc = SumaFunc + .Cells(i, 4).Value

Next i

'Selección Ranking - ordenando de mayor a menor (método sort)

Dim tFin, Limite, Switch

Dim tPermt As Variant

ReDim Preserve Nombre(CantHijoGene)

For i = 1 To CantHijoGene

Nombre(i) = Cells(i + 1, 4)

Next i

tFin = CantHijoGene \ 2

Do While tFin > 0

Limite = CantHijoGene - tFin

Do

Switch = False

For i = 1 To Limite

If Nombre(i) < Nombre(i + tFin) Then

tPermt = Nombre(i)

Nombre(i) = Nombre(i + tFin)

Nombre(i + tFin) = tPermt

Switch = i


End If

Next i

Limite = Switch

Loop While Switch

tFin = tFin \ 2

Loop

For i = 1 To CantHijoGene

Cells(i + 1, 6) = Nombre(i)

Next i

'Rotulando los mejores valores

For i = 1 To CantHijoGene / 2

.Cells(i + 1, 9).Value = .Cells(i + 1, 6).Value

.Cells(i + (CantHijoGene / 2) + 1, 9).Value = .Cells(i + 1, 6).Value

Next i

End With

End Sub

PASO 4: CROSSOVER O CRUZAMIENTO

Public Sub Crossover()

Dim i, corte As Integer

Dim Temp1, Temp2, Padre1, Padre2, PrePadre1, PrePadre2 As String

Dim Cadena1, Cadena2 As String


'Convirtiendo a Binario


.Cells(i, 10) = DecToBin(.Cells(i, 9))

Next i

Randomize

For i = 2 To CantHijoGene Step 2

98




'Punto de Cruce creado aleatoriamente

corte = Int(Rnd() * (8 - 1) + 1) 'Para 8 bits

.Cells(i, 12) = corte

'Completamos los valores de la cadena con ceros

Cadena1 = "00000000" 'Total de Bits con los que se trabajaran

Cadena2 = "00000000" 'para cruzar los dos padres a recombinar

'Cadenas que se cruzarán y formarán los dos padres

Temp1 = .Cells(i, 10)

Temp2 = .Cells(i + 1, 10)

'Padres convertidos en Bits, para ejecutar el Crossover

Mid(Cadena1, 9 - Len(Temp1)) = Temp1 'Padre1

Mid(Cadena2, 9 - Len(Temp2)) = Temp2 'Padre2

Padre1 = Cadena1 'Asignar padre Nº 1

Padre2 = Cadena2 'Asignar padre Nº 2

PrePadre1 = Cadena1 'Padre Temporal 1

PrePadre2 = Cadena2 'Padre Temporal 2

'Ejecutar la Recombinación o Crossover

Mid(Padre1, 9 - corte) = Mid(PrePadre2, 9 - corte, corte)

Mid(Padre2, 9 - corte) = Mid(PrePadre1, 9 - corte, corte)

.Cells(i, 11) = Padre1

.Cells(i + 1, 11) = Padre2

Next i

End With


End Sub

PASO 5: MUTACIÓN

Public Sub Mutacion()

Dim i, TotalAlelos, TotalMutac As Integer

Dim mutar, bit As Integer

Dim Cadena, Temp, num As String


'Copiar los cromosomas, para sobreponer los bits mutados


.Cells(i, 13) = .Cells(i, 11)

Next i

'Porcentaje total de alelos (Bits x CantHijoGene)

TotalAlelos = 8 * CantHijoGene '8 es el número de bits con los que se trabajará en

toda la aplicación

TotalMutac = Int(TotalAlelos * Val(frmControl.txtPorcMuta.Text) / 100)

For i = 1 To TotalMutac

'Seleccionar aleatoriamente un cromosoma para mutar

mutar = Int(Rnd() * (CantHijoGene) + 2)

'Iniciar los valores de la cadena con ceros

Cadena = "00000000"

'Valor del vector a mutar

Temp = .Cells(mutar, 11)

'Cadena completa para mutar

Mid(Cadena, 9 - Len(Temp)) = Temp 'Cadena para mutar

'Seleccionar al azar "1" de los "8" bits

100




bit = Int(Rnd() * (8 - 1) + 1)

num = Mid(Cadena, 9 - bit, 1)

'Mutar el gen (bit) seleccionado

If num = "1" Then

num = "0"

Else

num = "1"

End If

Mid(Cadena, 9 - bit, 1) = num 'Cadena mutada

.Cells(mutar, 13) = Cadena 'Cromosoma mutado

'mostrar el punto mutado

.Cells(mutar, 14) = bit

Next i

PASO 6: ELECCIÓN


'Convertir los datos obtenidos a decimales

.Cells(i, 15) = BinToDec(.Cells(i, 13))

'Penalizar

Temp = .Cells(i, 15)

While Temp > 10E6

Temp = Temp – 10E6

Wend

.Cells(i, 16) = Temp

'Mejores Padres

If .Cells(i, 16) >= .Cells(i, 4) Then


Else



End If

Next i

End With

End Sub


102




6. Elección del mejor sistema de rutas de TPCU obtenido

Como fue presentado en el capítulo anterior, el algoritmo genético permite,

mediante un proceso iterativo de análisis de poblaciones de sistemas de rutas de

TPCU generadas aleatoriamente y su correspondiente evaluación en la función

multiobjetivo formulada, ir encontrando soluciones cada vez más óptimas, que

presentan mejores resultados en comparación con la población anterior, hasta

identificar la más cercana a la mejor solución, luego de un barrido exhaustivo del

espacio casi infinito de soluciones posibles.

Para este trabajo de investigación llegaron a evaluarse más de 1 millón de

poblaciones, cada una compuesta por 100 cromosomas o sistemas de rutas de

TPCU generados, en la primera iteración de manera aleatoria, y en las

subsiguientes como producto de los procesos de selección, cruzamiento y

mutación que permite desarrollar el algoritmo genético mediante la alteración de

sus códigos o genes.

La cantidad máxima de iteraciones es establecida por el investigador, luego de

encontrar un punto de convergencia, donde los resultados no logren alcanzar

mayor optimización más respecto de los ya obtenidos en iteraciones anteriores.

La siguiente tabla presenta un resumen de la cantidad de sistemas evaluados

mediante el desarrollo y aplicación del algoritmo genético descrito anteriormente

para alcanzar convergencia.

Elección del mejor sistema de rutas 103

Tabla 6-1: Cantidad de sistemas de TPCU analizados en el algoritmo genético

Alternativa

generación

soluciones

Número

de rutas

Intervalo

máximo

Capacidad

máxima

Secuencia

OD

Esc

Evalua

Longitud

total km IPK

1 Aleatoria Variable Variable Aleatoria 10+E6 7.776 1,04

2 Fija Variable Variable Aleatoria 50+E6 6.854 1,17

3 Mixta Variable Variable Aleatoria 30+E6 4.336 1,86

4 Variable Variable Variable Secuencial 20+E6 3.209 2,51


De esta manera, y como fue mencionado párrafos antes, las diferentes alternativas

de generación aleatoria de sistemas, fue conduciendo a soluciones cada vez más

optimizadas. Esto debido, a que a medida que avanzaba el trabajo, el investigador

iba identificando oportunidades de realizar mejoras y ajustes al algoritmo genético,

hasta llegar a la alternativa 4, en la cual se superaron los problemas de la

separación de los segmentos y la homogenización de sus magnitudes. La tabla

anterior evidencia el progreso obtenido.

Finalmente, el sistema de rutas de TPCU que mejores resultados obtuvo fue

encontrado en una de las poblaciones de la alternativa 4 de generación, el cual

tiene una longitud total recorrida por las rutas durante el periodo de análisis (hora

pico) de 3.209 kilómetros, lo que conduce a un IPK total del sistema de 2,51 pax/km

y a un tiempo de viaje de todos los usuarios del sistema de cerca de 210.000

minutos.

Este sistema se elige luego de que se identifica que la aplicación del algoritmo

genético no conduce a mejores soluciones, siendo marginal la optimización de los

sistemas luego de la población 200.000.

El sistema obtenido orienta el diseño de un total de 13 rutas de TPCU, las cuales

se presentan en la siguiente tabla.

104




Tabla 6-2: Sistema de rutas seleccionado

No Ruta Sentido Longitud (Km)

1 101 E-N 11,7

2 101 N-E 11,3

3 102 E-S 10,5

4 102 S-E 9,8

5 103 N-S 15,4

6 103 S-N 17,0

7 104 E-N 10,0

8 104 N-E 11,5

9 105 E-S 14,8

10 105 S-E 15,1

11 106 E-N 11,2

12 106 N-E 10,1

13 107 N-S 24,4

14 107 S-N 23,4

15 108 E-N 10,5

16 108 N-E 12,2

17 109 E-N 9,9

18 109 N-E 9,9

19 110 E-S 12,1

20 110 S-E 10,7

21 111 N-S 10,9

22 111 S-N 10,0

23 112 N-S 11,9

24 112 S-N 10,9

25 113 N-S 12,0

26 113 S-N 11,7


Elección del mejor sistema de rutas 105

Una vez seleccionado el mejor sistema de rutas de TPCU obtenido a través del

proceso iterativo del algoritmo genético, se procede a realizar su comparación con

otros sistemas que hayan sido diseñados a través de los métodos heurísticos

convencionales, con el fin de poder validar la hipótesis de este trabajo investigativo,

sustentando la tesis de que un sistema obtenido mediante herramientas y modelos

matemáticos conduce a unos potenciales beneficios en cuanto a la cantidad de

recursos necesarios y en relación con el nivel de servicio que se le presta al usuario

del mismo.

Lo anterior redundará en sistemas más óptimos que contribuyan al mejoramiento

de estos sistemas en las ciudades intermedias de Colombia, pues permitirá superar

fallas estructurales asociadas a la sobreoferta, el paralelismo, la baja ocupación,

el exceso de parque automotor, los altos tiempos de espera y de viaje, entre otros.

106




7. Validación del modelo diseñado

La validación del sistema seleccionado, obtenido mediante la aplicación y uso del

algoritmo genético para solucionar el problema de optimización multiobjetivo

formulado, como fue descrito en los capítulos anteriores, se realiza mediante el

contraste de indicadores operativos y de servicio del mismo en comparación con

otras dos opciones de diseño determinadas, obtenidas mediante métodos

convencionales.

Como ya fue mencionado, Neiva, Huila, fue seleccionada como la ciudad que sirve

como caso de prueba de la validación, puesto que, no solo reúne las principales

problemáticas de TPCU que son comunes a las ciudades intermedias en Colombia,

sino que además en el año 2017 su sistema de rutas de transporte público colectivo

urbano fue rediseñado en el marco de la estructuración del Sistema Estratégico de

Transporte Público (SETP) de la ciudad. Dicho rediseño fue elaborado por el

CONSORCIO CAL Y MAYOR - IKON en el marco del Contrato de Consultoría No.

109 de 2017 que tuvo por objeto la “Elaboración de la Estructuración Técnica, Legal

y Financiera de Detalle del Sistema Estratégico de Transporte (SETP) de la ciudad

de Neiva”; el cual empleó métodos tradicionales en el medio, a visión de experto,

para realizar este rediseño del sistema actual.

Es así como el presente capítulo constituye el análisis de resultados para el

desarrollo del trabajo de investigación, a partir de los resultados obtenidos para el

diseño del sistema de rutas de TPCU obtenido por medio del modelo matemático

multiobjetivo formulado en este trabajo y su comparación con dos escenarios clave

mediante un modelo de transporte desarrollado en PTV Visum, a fin de determinar

Validación del modelo diseñado 107

si éste cumple con las características y requerimientos para la formulación de un

sistema de rutas de TPCU y cuáles son sus potenciales beneficios al poderse

aplicar.

Se muestra entonces la definición de variables o indicadores de comparación, los

cuales se han seleccionado a partir de la información primaria y secundaria de la

investigación, se definen además los tres escenarios a comparar haciendo una

breve descripción de cada uno, posteriormente se cuantifican las variables y,

finalmente, se realiza la comparación de resultados y la validación del modelo por

medio de la construcción de una matriz multicriterio.

7.1 Determinación de variables de comparación

Con el fin de realizar la comparación entre los tres escenarios propuestos, se hace

necesario definir las variables de comparación mediante la información con la que

se cuenta de cada sistema de rutas, en este caso se considera información

geográfica, temporal y operacional de los sistemas, la cual pueda ser objeto de

validación y comparación como parámetros que representen las características de

los sistemas de la manera más adecuada.

Luego de una revisión exhaustiva de información relacionada, el desarrollador de

este trabajo de investigación definió que las variables de comparación a tener en

cuenta dentro de la validación del modelo obtenido en este trabajo, dado que

representan de manera acertada tanto los intereses de los usuarios como los de

los operadores de los sistema, son las mostradas en la Tabla 7-1.

Estas variables representan los aspectos más comunes que son utilizados en la

práctica para evaluar las bondades de un sistema de rutas de TPCU, puesto que

permiten cubrir los elementos más importantes que toma en consideración un

usuario al momento de realizar su elección modal, a la vez que también permiten

medir el grado de eficiencia del sistema, en relación a recursos utilizados y la

adherencia entre la oferta y la demanda del servicio.

108




Tabla 7-1: Determinación de variables

VARIABLE DE COMPARACIÓN

NOTACIÓN DESCRIPCIÓN FÓRMULA

INDICE DE PASAJEROS

POR KILÓMETRO

IPK

Siendo una de las bases principales del modelo, el

IPK es una de las variables que más

información puede revelar en cuanto a la eficiencia y

efectividad operacional del sistema. Índica

cuántos pasajeros se transportan por kilómetro recorrido en el sistema.

COBERTURA ESPACIAL

CE

La cobertura espacial se establece como el alcance geográfico que tienen las

rutas del sistema de transporte que se utiliza,

refiriéndose a la disponibilidad de

transporte entre todos los orígenes y destinos de la

ciudad.

COBERTURA TEMPORAL

CT

Se refiere a la capacidad que tiene la ruta del

sistema de alcanzar la mayor longitud posible

mediante el recorrido del cual se debe disponer.

TIEMPO DE VIAJE

TV

Variable con la cual se establece el tiempo que se tardará el vehículo en recorrer la totalidad de la

ruta propuesta por el sistema, desde su origen

a su destino.

TIEMPO DE ESPERA

TE

Se establece como la duración de un usuario en el paradero del sistema,

hasta que el vehículo está disponible en el

transcurso de la ruta.


TAMAÑO DE LA FLOTA

TF

Se refiere al número de vehículos que hacen parte del parque automotor del

sistema.

LONGITUD TOTAL

LT Variable que representa la distancia total de las rutas

que utiliza el sistema.

NÚMERO TOTAL DE

RUTAS NR

Representa la cantidad de rutas del sistema


7.2 Escenarios de comparación

Posterior a la identificación y determinación de las ocho (8) variables que van a ser

empleadas para el proceso de validación de los potenciales beneficios del diseño

del sistema de TPCU de Neiva, Huila, mediante un modelo matemático

multiobjetivo solucionado a través de un algoritmo genético, se establecieron

cuáles iban a ser los tres (3) escenarios contrastados.

A partir de lo anterior, el presente numeral, comprende la selección y descripción

de los diferentes escenarios a evaluar para la validación del modelo, teniendo como

estudio de caso la ciudad de Neiva en el departamento del Huila.

En este caso se han considerado tres (3) escenarios los cuales describen de

manera precisa el comportamiento del TPCU de la ciudad bajo diferentes enfoques:

el primero un sistema de transporte de la manera tradicional, el segundo un sistema

diseñado para la implementación de un Sistema Estratégico de Transporte Público

que busca la mejora en las condiciones de movilidad de la ciudad pero que de igual

manera ha sido formulado bajo el método tradicional y, el tercero, el obtenido por

110




medio del desarrollo de este trabajo de investigación que busca obtener un sistema

de rutas más óptimo bajo la formulación de un modelo matemático multiobjetivo

aplicando algoritmos genéticos.

El investigador considera que la comparación de estos (3) enfoques, permitirá

satisfacer el objetivo de este trabajo, el cual busca establecer si existe oportunidad

de obtener beneficios al diseñar sistemas de rutas de TPCU mediante un modelo

matemático en contravía con los heurísticas tradicionales de “prueba y error”, a

visión de experto.

A continuación se describe, de manera general, cada uno de los tres escenarios a

evaluar.

7.2.1 Escenario 1: situación actual

El escenario uno (1) representa el diagnóstico de la situación actual del sistema de

transporte público colectivo urbano (TPCU) para la ciudad de Neiva, éste

diagnóstico se ha obtenido a partir de un exhaustivo análisis de la información

secundaria recolectada a lo largo del desarrollo del trabajo de investigación.

Allí se encontró que el diseño de rutas se realizó de manera empírica, sin ningún

sustento técnico y sin la realización de estudios, razón por la cual la operación del

TPCU de Neiva presenta sobreoferta de rutas, paralelismo, falta de cobertura,

exceso de paradas, entre otros aspectos que derivan en una mala prestación del

servicio, ya que las rutas establecidas obedecen a diseños tradicionales

acompañados de malas estructuras empresariales. La Ilustración 7-1 muestra la

oferta de rutas en la situación actual.


Ilustración 7-1. Oferta de rutas TPCU actual


112




7.2.2 Escenario 2: Sistema Estratégico de Transporte Público SETP

El segundo escenario representa el SETP de la ciudad de Neiva. El diseño de éste

fue realizado por la firma Cal y Mayor en el año 2017, por medio de procesos

iterativos, a visión de experto, a partir de la identificación de las respectivas líneas

de deseo de los usuarios actuales y potenciales con base en la matriz origen-

destino de transporte público, probando diferentes esquemas de rutas (circulares,

radiales, etc.) hasta obtener un sistema equilibrado entre la eficiencia y la calidad

del servicio prestado al usuario, sin utilizar algún método que permitiera garantizar

que el resultado obtenido llegara a ser lo más cercano posible al óptimo,

simplemente empleando un proceso heurístico subjetivo de prueba y error a visión

de experto que no garantizan diseños más óptimos en el uso de recursos como lo

exige el contexto social y económico actual del país. La Ilustración 7-2 muestra la

oferta de rutas del SETP.

7.2.3 Escenario 3: Modelo Matemático Multiobjetivo

El tercer escenario representa el resultado del desarrollo del trabajo de

investigación, por medio de la aplicación de un modelo matemático multiobjetivo y

un algoritmo genético en donde se buscó optimizar el IPK y el tiempo de viaje de

los usuarios, obteniendo finalmente 13 rutas diametrales de acuerdo a los patrones

de viaje de la ciudad de Neiva. El modelo matemático permite entonces tener una

herramienta para la toma de decisiones en cuanto al sistema de transporte público

colectivo urbano de las ciudades intermedias del país, siendo en este caso Neiva

el caso de estudio. La Ilustración 7-3 muestra la oferta de rutas para el escenario del

MMM.


Ilustración 7-2. Oferta de rutas SETP


114




Ilustración 7-3 Oferta de rutas escenario modelo matemático multiobjetivo



7.3 Cuantificación de variables

El presente aparte comprende la cuantificación de las variables determinadas para

llevar a cabo la validación del modelo matemático. A continuación se enumerará

cada una de las variables mostrando el valor obtenido para cada una para los tres

escenarios a evaluar, en los casos de los escenarios 1 y 2 los valores se han

obtenido por medio del procesamiento de información secundaria, para el

escenario 3 se han utilizado los valores arrojados por el modelo matemático y/o su

modelación en la herramienta PTV Visum.

7.3.1 Índice de pasajero por kilómetro (IPK):

El primer parámetro a calcular entre los sistemas de comparación, es el valor del

índice de pasajeros por kilómetro recorrido de cada uno.

Este parámetro se obtiene sencillamente mediante la determinación de la longitud

total recorrida por todas las rutas que componen el sistema durante la hora pico.

Para ello debe considerarse la frecuencia de los despachos y la longitud de cada

ruta.

Por medio del cálculo de la demanda OD total para cada sistema y la longitud total

de cada uno, se obtuvo el valor de IPK para cada escenario con el fin de evaluar el

desempeño de cada sistema, el cual se muestra en la Tabla 7-2.

Tabla 7-2: Comparativo IPK

ESCENARIO Actual SETP MODELO

IPK (pax/km) 1,39 2,12 2,51 Fuente: Elaboración Propia

Al realizar un análisis al valor del IPK, es importante tener en cuenta que siendo

una medida de la eficiencia del sistema, se espera que su valor sea alto ya que

representará la eficiencia del sistema a evaluar.

116




En este caso en la Tabla 7-2 se puede observar que el escenario actual tiene el

valor más bajo de IPK, seguido del escenario del SETP y del obtenido por el modelo

matemático de la tesis, lo que muestra que el sistema más eficiente es el del

escenario 3 ya que su valor de IPK es el más alto y está mostrando al sistema más

eficiente ya que éste mueve más cantidad de personas por cada kilómetro

recorrido.

Por su parte el valor tan bajo para el escenario 1 puede deberse principalmente a

que en el transporte convencional no se ha realizado ningún tipo de optimización

en el uso de los vehículos del sistema la cual podría mejorarse con una

programación de servicios realizada técnicamente, entre otros.

Este parámetro es el principal insumo para la evaluación financiera de los sistemas,

por tanto su valor es primordial para establecer la eficiencia y aprovechamiento de

recursos de un determinado sistema, lo que conducirá a obtener tarifas más bajas

y a reducir notablemente los costos de operación de los servicios.

7.3.2 Cobertura espacial

La cobertura espacial de un sistema es una medida que tiene relación con la

capacidad que tiene un sistema de TPCU de brindar servicio a todo un territorio,

incluyendo sus zonas más apartadas.

La determinación de este valor es relativamente fácil, pues consiste en una

comparación entre el área urbana de la ciudad y el área de servicio de cualquier

sistema, medido este último como una franja a lado y lado de los servicios, con

distancia menor a 300 metros, la cual es considerada como la cuenca de cobertura

de una ruta.

La Ilustración 7-4:, la Ilustración 7-5: y la Ilustración 6-6 muestran la distribución de

rutas de TPCU en la ciudad de Neiva, para los escenarios 1, 2 y 3 respectivamente.

A estas rutas se les realizó un análisis espacial de cobertura por medio de un buffer


o zona de influencia de 300 metros, el cual arrojó la cobertura de cada sistema de

rutas para el área urbana de la ciudad de Neiva.

Ilustración 7-4: Cobertura TPCU actual


118




Ilustración 7-5: Cobertura SETP



Ilustración 7-6: Cobertura modelo


120




A partir del buffer trazado, se obtuvo el área de éste y teniendo el área urbana total

de Neiva, Huila, se calculó la cobertura espacial para los tres escenarios

analizados, por medio de la comparación entre estas áreas. La Tabla 7-3 muestra

los resultados obtenidos para cada caso.

Tabla 7-3: Comparativo cobertura espacial


Cobertura espacial (%) 85% 99% 96%


Como se puede observar, la mayor cobertura espacial se presenta en el escenario

perteneciente al SETP, mientras que el sistema de transporte actual presenta

únicamente una cobertura del 85%.

En este punto es importante destacar, que el diseño de rutas obtenido mediante el

modelo matemático multiobjetivo formulado, no considera el trazado de rutas por

zonas espaciales que no contengan viajes dentro de la matriz OD que se utilice

como base para la evaluación del modelo. Por tanto, es importante que el tomador

de decisiones, consiente de esta falencia, supla el trazado hacia esas zonas, con

el fin de brindar una cobertura más acorde a la ciudad.

En este caso, fue necesario prolongar dos rutas, con el objeto de alcanzar lugares

apartados del territorio que no reportaron viajes en la matriz OD, lo que permitió

alcanzar una cobertura del 96% de la ciudad.

Lo anterior constituye una oportunidad importante de mejora para mejorar la

formulación del problema en investigaciones posteriores.

7.3.3 Cobertura temporal

Debido a que el indicador anterior desconoce la temporalidad con la que se atiende

la demanda, se hace necesario evaluar el problema también desde esta dimensión.


Con este fin se analiza el parámetro de la cobertura temporal de la demanda,

entendido como el tiempo promedio que debe esperar un usuario para que pase

un servicio determinado.

En este caso, este indicador se determinó como el promedio aritmético de la

frecuencia de todas las rutas de cada sistema, lo que condujo a un valor

representativo de cada uno.

La cobertura temporal para cada escenario se muestra en la Tabla 7-4 .

Tabla 7-4: Comparativo cobertura temporal


Cobertura temporal (min) 12,0 7,1 7,0


Como se puede observar en la Tabla 7-4, para el escenario actual el valor de la

cobertura temporal se encuentra en 12 minutos, el escenario del SETP tiene un

valor de 7,1 minutos y en el escenario del modelo es de 7 minutos, en este caso la

eficiencia se muestra con el valor más bajo por lo que el mejor valor es el del

escenario 3, ya que al relacionar directamente el intervalo del sistema con el total

de rutas, se obtiene una medida de eficiencia del sistema ya que entre más bajo

sea el intervalo de las rutas de transporte público mejor será su cobertura temporal

pues tardará menor tiempo en satisfacer las necesidades de la demanda del

sistema. En cuanto al escenario del SETP su valor es similar al del escenario del

modelo por lo que se considera que es bueno, mientras que el escenario actual

muestra un valor que casi duplica a los dos escenarios en comparación, mostrando

que los intervalos de las rutas de este sistema son bastante altos y por ende su

cobertura temporal es ineficiente.

Al revisar a detalle se encontró que cerca del 80% de los servicios del sistema

obtenido mediante el modelo matemático multiobjetivo presentaron intervalos de

paso menores o iguales a 5 minutos, y el 30% menores o iguales a 3 min, lo cual

significa que el diseño condujo a un sistema con altos estándares de atención al

usuario, pues un intervalo de esta magnitud corresponde a un nivel A.

122




7.3.4 Costo generalizado del transporte

La determinación del costo generalizado de transporte de los usuarios es, junto al

indicador de IPK, la medida más importante de la evaluación de la eficiencia de un

sistema de transporte público colectivo urbano, pues permite realizar la evaluación

desde la óptica de los usuarios del sistema.

Conseguir diseños de sistemas que proporcionen a los usuarios bajos costos en

comparación con otros modos de transporte, lo hará altamente atractivo como

solución de viaje, favoreciendo la partición modal hacia éste.

En este sentido, el costo generalizado de transporte, se ha definido acá como la

suma de los tiempos medios de acceso, espera y viaje a bordo de los usuarios de

las rutas del sistema evaluado.

Este aspecto, dada la complejidad de su análisis, debió ser simulado por medio de

una modelación del sistema en un software especializado. En este caso se ha

utilizado PTV Visum.

Con este fin se utilizó el mismo modelo de transporte que se empleó en la

estructuración del SETP de la ciudad de Neiva, Huila, el cual, en ese entonces, fue

calibrado utilizando los datos de demanda del sistema convencional. Lo anterior

permitió garantizar que la herramienta de simulación con la que se contaba era

totalmente estándar para la evaluación de los tres (3) sistemas de análisis de este

trabajo de investigación, por tanto, los valores obtenidos son comparables entre sí.

En ese sentido, se evaluó el nuevo diseño de rutas de TPCU, producto de este

trabajo de investigación, en la herramienta de modelación, utilizando las mismas

matrices de viajes y parametrización de las funciones de utilidad de los usuarios,

que en los casos anteriores.

Luego de surtido este proceso, la Tabla 7-5 muestra, para este caso, que el menor

valor promedio de costos generalizado de transporte es de 25,2 min para el diseño

del escenario del SETP, siendo el más favorable ya que representa que los


usuarios tienen acceso más rápido al transporte y el tiempo de viaje es menor; en

el caso del escenario del modelo el valor obtenido es de igual forma favorable ya

que no dista del valor del SETP, mientras que el escenario actual presenta un valor

elevado que muestra que una persona permanece en promedio más de 30 minutos

en el sistema.

Tabla 7-5: Comparativo costo generalizado del transporte


Costo generalizado del transporte (min) 31,4 25,2 26,0

Fuente: elaboración propia

7.3.5 Tamaño de la flota

El tamaño de la flota de cada sistema se determinó mediante la cuantificación del

número de buses necesarios por cada ruta para atender la hora de mayor demanda

del sistema, en función del intervalo máximo permitido y el segmento de mayor

carga de cada servicio.

El tamaño de la flota para cada escenario se muestra en la tabla Tabla 7-6.

Tabla 7-6: Comparativa tamaño de la flota


Tamaño de la flota (buses) 400 271 219


De la Tabla 7-6 se puede concluir que el sistema que presenta mayor favorabilidad

en cuanto al tamaño de la flota es del modelo con 219 vehículos de transporte

público, seguido del escenario del SETP con 271 y finalmente el escenario actual

con 400. Se tiene en cuenta la mayor favorabilidad con menor número de vehículos

en la flota ya que se requiere de menos parque automotor para satisfacer las

necesidades del sistema de transporte y cubrir la demanda del mismo, generando

así, beneficios al sistema como menores costos al operar y mantener la flota de

vehículos.

124




7.3.6 Longitud total

La cuantificación de la variable relacionada con la longitud total del sistema se

muestra en la Tabla 7-7 , donde se da un valor para cada escenario analizado.

Tabla 7-7: Comparativo longitud total


Longitud total (Km) 5.793 3.810 3.209 Fuente: Elaboración Propia

En este caso, el mejor indicador para el sistema es el que tiene el menor valor de

longitud, es decir, el escenario del modelo ya que tiene una longitud total de 3.209

metros, mientras que el escenario del SETP tiene 3.810 metros y el escenario

actual 5.793. La razón por la cual es escenario del modelo es mejor en este análisis

es porque recorre una menor longitud a lo largo de la ciudad y cubre las

necesidades del sistema, derivándose de allí de igual manera menores tiempos de

viaje y demostrando un trazado óptimo en las rutas de transporte. Mientras que el

escenario actual es el más crítico ya que tiene menor cubrimiento espacial y

temporal y recorre una longitud mucho más elevada demostrando la deficiencia en

el trazado de sus rutas.

7.3.7 Número de rutas

En cuanto al número de rutas para cada sistema, la Tabla 7-8 muestra los valores

obtenidos en cada caso, considerando el doble sentido de los servicios.

Tabla 7-8: Comparativo número de rutas


Longitud total (Km) 74 32 26 Fuente: Elaboración Propia

En cuanto al número de rutas y al igual que en el caso anterior, el escenario más

favorable es el del modelo con menor número de rutas, 26 considerando ambos

sentidos o 13 en total, seguido del SETP con 32 y el actual con 74. De estos valores

se puede concluir que el mejor escenario es el del modelo ya que con un bajo


número de rutas logra satisfacer todo el sistema de transporte, cubriendo no

únicamente la demanda de usuarios sino que también el área geográfica de la

ciudad; mientras que para el sistema actual se nota de nuevo una deficiencia ya

que cuenta con casi el triple de rutas que el escenario modelo y sin embargo no

logra cubrir las necesidades en la demanda de la población de la ciudad, mostrando

así que no se necesita de un gran número de rutas de TPCU para ser un sistema

eficiente que satisfaga las necesidades del sistema y a un bajo costo.

7.3.8 Transferencias

Este indicador también fue obtenido mediante el modelo de transporte en PTV

Visum, de acuerdo a las condiciones descritas con anterioridad, lo que permitió

estimar el porcentaje de transferencias de cada sistema. Este valor es obtenido

como la relación porcentual entre la cantidad de los viajes que presentaron al

menos 1 trasbordo y la cantidad total de viajes del sistema.

Esta variable se encuentra relacionada con las transferencias o los transbordos en

el sistema de transporte que debe realizar el usuario con el fin de llegar a su

destino, la Tabla 7-9 muestra el porcentaje de transferencias para cada escenario

evaluado.

Tabla 7-9: Comparativo transferencias


Transferencias (%) 1,5 15,2 8,2

Fuente: Elaboración propia

En este caso, el escenario más favorable resulta siendo el actual con un 1,5% de

transferencias, mientras que el escenario más desfavorable es el del SETP ya que

el porcentaje de transferencia supera 15 veces al actual con un valor de 15,2%, en

donde se establece que a menores transferencias el usuario del sistema se sentirá

más cómodo ya que necesitará de un único servicio de transporte para realizar su

recorrido.

126




El modelo generado con el algoritmo genético logra una importante eficiencia en

este aspecto, en comparación con el rediseño del SETP, con apenas el 8,2% del

total de los viajes.

8. Comparación de resultados obtenidos

Finalmente, el presente aparte comprende la comparación de resultados de los tres

(3) escenarios evaluados, presentados en el capítulo anterior, con el fin de

establecer cuál es el mejor escenario el cual satisfaga las necesidades de los

usuarios y de los operadores, y que brinde los mejores indicadores en cuanto a

eficiencia del sistema.

Mediante esta comparación podrá establecerse si la hipótesis de este trabajo de

investigación es válida o si, por el contrario, se rechaza por no encontrarse los

argumentos suficientes que permitan concluir si realmente existen beneficios

ostensibles al diseñar un sistema de rutas de TPCU mediante la utilización de un

modelo matemático multiobjetivo de optimización, solucionado mediante un

algoritmo genético, en contraste con los resultados obtenidos mediante los

métodos convencionales que se usan en el medio.

Ésta comparación se realizará por medio de una matriz multicriterio la cual se

describe a continuación.

8.1 Escala de valoración

Con el fin de realizar la comparación de resultados se ha establecido el utilizar una

matriz multicriterio que permita el análisis de los diferentes escenarios y de los

valores obtenidos para cada indicador, por medio de un análisis que establezca un

estándar de comparación y permita evaluarlos a todos por igual sin tener en cuenta

aspectos tales como las diferentes unidades de medida de cada indicador.

128




En este caso con el fin de facilitar el proceso y estandarizarlo, se estableció una

escala de evaluación la cual se muestra en la Tabla 8-1, donde 1 resulta siendo el

valor más desfavorable, 2 es medianamente favorable y 3 será el más favorable.

Tabla 8-1: Escala de valoración

ESCALA DESCRIPCIÓN

1 Desfavorable

2 Medianamente favorable

3 Más favorable

Fuente: Elaboración propia

8.2 Evaluación de los indicadores

Posterior a la definición de la escala de valoración de los indicadores obtenidos, se

procede con la evaluación de los resultados de cada sistema.

A partir de lo anterior, la Tabla 8-2 muestra el resumen de los resultados obtenidos

para indicador los cuales fueron analizados en el aparte anterior.

Tabla 8-2: Resumen resultados obtenidos

Escenario IPK

(pax/km)

Costo generaliza

do de transporte

(min)

Cobertura espacial

(%)

Cobertura temporal

(min)

Tamaño de la flota

(buses)

Longitud total (Km)

Número total de

rutas (Unidade

s)

Transferencias (%)

ACTUAL 1,39 31,4 85% 12,0 400 5.793 74 1,5

SETP 2,12 25,2 99% 7,1 271 3.810 32 15,2

MODELO 2,51 26,0 96% 7,0 219 3.209 26 8,2


Comparación de resultados obtenidos 129

Los resultados anteriores, son valorados de acuerdo a la escala determinada donde

1 es el resultado más desfavorable y 3 el más favorable.

La Tabla 8-3 muestra la aplicación de la escala para estandarizar los resultados a

partir de la cual se realizará la matriz multicriterio.

Tabla 8-3: Evaluación de indicadores

Escenario IPK Costo generalizado

de transporte

Cobertura espacial

Cobertura temporal

Tamaño de la flota

Longitud total

Número total de

rutas

Transferencias

ACTUAL 1 1 1 1 1 1 1 3

SETP 2 3 3 2 2 2 2 1

MODELO 3 2 2 3 3 3 3 2


8.3 Ponderación de los indicadores

Teniendo la escala de valoración que permite estandarizar, se hace necesario de

igual manera establecer porcentajes de ponderación para cada uno de los

indicadores, el cual dependerá directamente de la importancia de cada uno, la cual

viene dada en cuanto a la importancia de cada indicador en el desempeño del

sistema.

Para establecer el peso de cada indicador en la evaluación final de los escenarios,

el investigador analizó su importancia en función de los objetivos propios de este

trabajo, los cuales buscaban conducir a la obtención de diseños de rutas de TPCU

que permitieran tener un balance entre los intereses tanto de los usuarios como de

los operadores, representado principalmente en el valor del IPK y al costo

generalizado del transporte por ser las variables clave en el desarrollo del modelo

matemático.

Lo anterior condujo a la escala de ponderación que se presenta en la Tabla 8-4

dada para cada indicador.

130




Tabla 8-4: Ponderadores de los indicadores evaluados

Indicador IPK

Costo generalizado

de transporte

Cobertura espacial

Cobertura temporal

Tamaño de la flota

Longitud total

Número total de

rutas Transferencias

Ponderación 25% 25% 10% 10% 5% 5% 10% 10%


De la tabla anterior se aprecia que los indicadores con un mayor peso dentro de la

evaluación final (50% entre ambos) son los del IPK y el CGT, por las razones

expuestas anteriormente. En un segundo nivel se encuentran: la cobertura

espacial, la cobertura temporal, el número de rutas y el porcentaje de

transferencias; con un peso del 10% cada uno dentro de la evaluación, dado que

representan una medida, aunque menos directa, del nivel de servicio así como del

uso de recursos para la atención de la demanda, por tanto también son importante

en la evaluación, pero con una menor ponderación. Finalmente, en tercer nivel, se

encuentran los indicadores de tamaño total de la flota y la longitud total, los cuales

tienen un menor peso, ya que de una u otra manera son evaluados de manera más

integral en los indicadores anteriores.

8.4 Resultados de la evaluación multicriterio

A partir de lo anterior se construyó la matriz multicriterio multiplicando el valor de

cada indicador por su respectiva ponderación, obteniendo como resultado la Tabla

8-5.

Comparación de resultados obtenidos 131

Tabla 8-5: Matriz multicriterio

Escenario IPK

Costo generalizado

de transporte

Cobertura espacial

Cobertura temporal

Tamaño de la flota

Longitud total

Número total de

rutas Transferencias TOTAL

ACTUAL 0,25 0,25 0,10 0,10 0,05 0,05 0,10 0,30 1,25

SETP 0,50 0,75 0,30 0,20 0,10 0,10 0,20 0,10 2,20

MODELO 0,75 0,50 0,20 0,30 0,15 0,15 0,30 0,20 2,55


A partir de los resultados de la Tabla 8-5, se puede establecer que a partir de la

escala dada y los valores de ponderación, el escenario más favorable y el mejor en

este caso es del modelo con un valor de 2,55 que es el más cercano a 3, seguido

del escenario del SETP con 2,2 siendo este el medianamente favorable y

finalmente el escenario actual es el más desfavorable con un valor de 1,25.

De los resultados anteriores se concluye que son lógicos teniendo en cuenta las

características de cada uno de los escenarios y como se ha construido cada

sistema de rutas, en el caso del escenario actual, es tan desfavorable ya que su

diseño no tiene ningún tipo de sustento técnico y cada una de las modificaciones

que se le realizan, como inclusión de rutas, de flota, cambios de trazado se realizan

sin ningún tipo de estudio sino que se hacen desde el punto de vista de la persona

encargada del sistema de transporte en ese momento.

En cuanto al resultado obtenido para el escenario del SETP, es un valor

representativo, que ofrece un sistema de transporte medianamente favorable y que

ha mejorado significativamente respecto al escenario actual, pues sus condiciones

operativas son mejores, además de contar con estudios técnicos que lo sustentan

como la solución al sistema de transporte de la ciudad de Neiva. Sin embargo a

pesar de tener sustento técnico, no deja de ser un sistema diseñado a partir de

métodos tradicionales de iteraciones de prueba y error, soportados en “visión de

experto”, en donde no se busca optimizar el resultado y garantizar que éste sea el

que brinde las mejores condiciones al sistema con las variables que éste necesita.

132




Finalmente, el resultado obtenido para el modelo matemático producto del

desarrollo del proyecto de investigación es satisfactorio ya que es el escenario más

favorable para el sistema de transporte y es una herramienta de toma de decisiones

que se encuentra fundamentada técnica y teóricamente con el desarrollo del trabajo

de investigación, en este caso el sistema de transporte que se ha obtenido como

resultado es producto de un análisis exhaustivo del sistema de transporte de la

ciudad de Neiva, en donde se ha logrado optimizar variables como el IPK y el

tiempo de viaje del usuario las cuales son indicadores de gran importancia en el

momento de establecer la eficiencia de un sistema de transporte público, al haber

realizado este proceso, otras variables como longitud, número de rutas, cobertura,

se vieron beneficiadas y optimizadas de igual manera, obteniendo finalmente un

resultado que deriva en un sistema de transporte con mayor IPK, tiempo de viaje

corto, menor número de rutas, menor longitud recorrida, etc, mostrando que se

puede diseñar un sistema de transporte útil que satisfaga necesidades de

operadores, usuarios y sea amable de igual manera con la ciudad.

Conclusiones y recomendaciones

La realización de este trabajo de investigación logró sustentar suficientemente la

hipótesis de que es posible obtener diseños de rutas de transporte público colectivo

urbano (TPCU) más óptimos en términos de indicadores operacionales y de

prestación del servicio, por medio de la formulación de un modelo matemático

multiobjetivo, cuya función objetivo consideró tanto los intereses de los prestadores

del servicio como de los usuarios, solucionado a partir de una metaheurística

evolutiva como los algoritmos genéticos.

El presente caso de estudio, Neiva Huila, cuenta en la actualidad con un sistema

de rutas de TPCU compuesto por 37 rutas (74 si se cuentan por separado ambos

sentidos de circulación), que operan por medio de una flota que alcanza los 400

buses, cubriendo el 85% de la huella urbana de la ciudad, que moviliza cerca de

8.050 usuarios durante la hora de mayor demanda del sistema, es decir entre las

12:00 y 1:00 pm del día hábil, lo que conduce a un valor de pasajeros por kilómetro

del sistema de apenas 1,39. Si sumado a lo anterior, se considera que la ciudad en

general viene presentando en la última década un fuerte deterioro en la prestación

del servicio de este sistema que ha causado la proliferación de modos alternativos

no sustentables como el vehículo particular, las motocicletas y el mototaxismo (que

en la actualidad alcanzan cerca del 50% de la partición modal de la ciudad), se

puede asegurar que en general existe una crisis de prestación del servicio producto

de fallas estructurales en el diseño y la operación del sistema, tal como sucede en

la gran mayoría de ciudades intermedias y principales del país.

En el marco de la estructuración técnica, tecnológica, legal y financiera del Sistema

Estratégico de Transporte Público Colectivo (SETP), en el año 2018, la Unión

temporal Cal y Mayor – Ikon, desarrolló el rediseño de las rutas de Neiva, por medio

134




de heurísticas tradicionales de iteraciones sucesivas de asignaciones de diferentes

propuestas de sistemas hasta encontrar valores que resultaran adecuados a la

visión y propósito del experto encargado del diseño. Como resultado de este

proceso, se logró establecer un sistema de oferta de rutas de TPCU compuesto por

16 rutas (32 en ambos sentidos), requiriéndose una flota de 271 buses, con una

cobertura espacial del 99% del territorio y un valor de IPK de 2,12 pasajeros por

kilómetro. Lo anterior supuso una importante optimización del sistema actual,

puesto que redujo en cerca del 57% la cantidad de rutas actuales, aumentó la

cobertura espacial a casi el 100% y maximizó el IPK en un 152% respecto del

sistema actual. Todo lo anterior, condujo a un mejor aprovechamiento de los

recursos disponibles, a la vez que mejoró temas operativos y de prestación del

servicio, en pro de los usuarios y la comunidad, contribuyendo a un mejor

funcionamiento financiero del sistema.

A partir de lo anterior, el presente trabajo de investigación, buscó superar la

importante optimización conseguida del sistema actual en el marco del diseño del

SETP de la ciudad, empleando para ello una herramienta matemática formulada

con dos objetivos principales: minimizar el servicio al usuario (a través del tiempo

de viaje) y maximizar el aprovechamiento del sistema (por medio del valor del

índice de pasajeros por kilómetro), solucionada por medio de un algoritmo genético.

Es así como los resultados obtenidos mediante este proceso investigativo,

permitieron generar el diseño de un sistema de oferta de rutas de transporte público

colectivo urbano de mayor eficiencia, puesto que lograron mantenerse e incluso

superarse muchos de los indicadores operacionales y de prestación del servicio

establecidos para su comparación. En el caso de la cantidad de servicios, el diseño

obtenido vía modelo matemático permitió establecer 13 rutas (26 en ambos

sentidos), que se prestan con una flota total de 219 buses, en una cobertura

espacial del 96% de la huella urbana, un promedio de paso de los buses de 7

minutos, un valor de costo generalizado de transporte (medido en términos de

Conclusiones y recomendaciones 135

tiempo de viaje, tiempo de espera y tiempo de caminata) de 26 minutos en

promedio y un valor de pasajeros por kilómetro de 2,51.

Los resultados anteriores permitieron validar la eficiencia lograda a través del

modelo matemático multiobjetivo formulado, solucionado mediante un algoritmo

genético, puesto que representa una maximización del valor del IPK de cerca del

120% respecto del SETP y del 180% respecto del sistema actual, resultado que se

convierte en una medida fundamental que representa la optimización del sistema

alcanzada vía modelo matemático. Así mismo, en términos de flota, se consiguió

una reducción del 45% respecto del sistema actual y del 20% del SETP. Respecto

de la cantidad de servicios, se redujo en 65% del actual y 20% del SETP. Así

mismo, parámetros de servicio como el intervalo promedio de paso de los buses y

el costo generalizado de transporte (tiempo de viaje, tiempo de espera y tiempo de

caminata) lograron mantenerse similares respecto del diseño del SETP y se

morigeraron en un 40% para el primero y un 25% para el segundo, en comparación

con los valores actuales.

Como oportunidades de mejora del modelo, logró establecerse la necesidad de dar

un mejor tratamiento al tema de la cobertura espacial, puesto que fue necesario

modificar algunos servicios para que dieran cobertura a zonas apartadas de la

ciudad, que no registraron viajes dentro de la matriz OD empleada en la modelación

y por tanto no fueron consideradas por el modelo. Aún así, la cobertura fue menor

respecto del diseño del SETP alcanzando el 96% de territorio, comparado con el

99% de este último. Así mismo, se recomienda realizar una simplificación adecuada

de las zonas de análisis de transporte, así como de la red de infraestructura vial

empleada, puesto que zonas demasiado agrupadas conducirán a valores altos de

transferencias. En este caso, la tasa de transferencias fue del 8%, que comparada

con la del 15% del SETP, significa una reducción de casi el 50%, sin embargo, este

valor sigue siendo elevado para una ciudad como Neiva, dadas sus condiciones

topográficas y climatológicas, lo que hace menos atractivo el uso del sistema.

Para finalizar, se destaca que el modelo matemático y el algoritmo genético,

presentados en este trabajo de investigación, no se constituyen en un método

136




automático de diseño de rutas, sino que es una verdadera herramienta de apoyo a

la toma de decisiones que orienta a los estructurados y tomadores de decisiones

de estos sistemas hacia el diseño más optimizado de los mismos, como fue

argumentado y demostrado a lo largo de este trabajo de investigación. Por lo

anterior, el papel del experto no desaparece, sino que por el contrario basa sus

decisiones en los resultados del modelo, conduciendo a un mejor aprovechamiento

de los recursos, en pro de la sostenibilidad y competitividad de las ciudades

colombianas.

Para posteriores trabajos de investigación, se recomienda usar el modelo en

ciudades de mayor tamaño y complejidad, que permitan validar sus resultados en

diferentes entornos y mejorar la programación del modelo matemático y el

algoritmo genético para hacerlo cada vez más eficiente.

Bibliografía

Aguado, A., & Jiménez, J. (2013). Optimización de rutas de transporte. Madrid.

Axhausen, K. W., & Smith Jr, R. L. (1984). Evaluation of Heuristic Transit Network

Optimization Algorithms. Transportation Research Record, 7-20.

Baaj, M., & Magmassani, H. (1995). Hybrid route generation heuristic algorithm for the

design of transit networks. Transportation Research Record, 31-50.

Baaj, M., & Mahmassani, H. (1990). A LISP program for the analysis of transit route

configurations. Transportation Research Record, 125-135.

Baaj, M., & Mahmassani, H. (1991). An AI-Based Approach for Transit Route System

Planning and Design. Journal of Advanced Transportation, 187-210.

Barra, A., & Kawamoto, E. (2000). Roteirização de ônibus urbano: escolha de um

método. Engenharia de Tráfego e Transportes 2000: Avanços para, 729-742.

Bayas Meza, P. G. (2011). Estudio y propuesta de nuevas rutas y líneas de transporte

público urbano del Distrito Metropolitano de Quito, caso de aplicación corredor

Sur Occidental del sistema Metro Bus. Quito: Quito,2011.

Cal y Mayor. (2018). Estudio de Estructuración de detalle del SETP de Neiva. Bogotá

D.C.

Caramia, M., Carorenuto, P., & Confessore, G. (2001). Metaheuristics techniques in bus

network optimization. European Strategies in the Globalising Markets, (págs. 16-

18). Helsinki.

Collete, Y., & Siarry, P. (2004). Multiobjetive Optimization Principles and Case Studies.

Berlín: Springer-Verlag Berlin y Heidelberg GmbH & Co. KG.

Durán Micco, J. V. (2016). Optimización en el Diseño de Redes de Transporte Público

con Objetivos Mediambientales mediante Algoritmos Evolutivos. Concepción.

Ehrgott, M., & Gandibleux, X. (2004). Approximative Solution Methods for Multiobjective.

Revista de la Asociación Española de Estadística e, 1-89.

Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning.

Boston: Addison-Wesley Longman Publishing Co., Inc.

Gruttner, E., & Pinninghoff, M. (2002). Recorridos Óptimos de Líneas de Transporte

Público Usando Algorítmos Genéticos. Jornadas Chilenas de Computación.

Instituto SER, d. i. (2003). Bases de una política integral de transporte urbano en

Colombia. Bogotá D.C.

Israel, Y., & Ceder, A. (1995). Transit Route Design Using Scheduling and Multiobjective

Programming Techniques. En J. Daduna, I. Branco, & J. Paixão, Computer-Aided

Transit Scheduling (págs. 56-75). Lisboa: Springer, Berlin, Heidelberg.

Kepaptsoglou, K., & Karlaftis, M. (2009). Transit Route Network Design Problem: Review.

Journal od Transportation Engineering, 491-505.

Mandl, C. (1979). Evaluation and optimization of urban public transportation networks.

European Journal of Operational Research, 396-404.

Mao-Chang, S., Hani S, M., & M. Hadi, B. (1998). Planning and Design Model for Transit

Route Networks with Coordinated Operations. Transportation Research Record,

16-23.

Mauttone Vidales, A. D., Cancela, H., & Urquhart, M. E. (2003). Diseño y optimización de

rutas y frecuencias en el transporte colectivo urbano :modelos y algoritmos.

Montevideo: UR. FI – INCO.

Mauttone, A., & Urquart, M. (2009). A multi-objective metaheuristic approach for the

transit network design problem. Public Transport, 253-273.

Ngamchai, S., & Lovell, D. (2000). Optimal Time Transfer in Bus Transit Route Network

Design Using a Genetic Algotithm. Computer-Aided Scheduling of Public

Transport, 21-23.

Osman, I., & Laporte, G. (1996). Metaheurística: una bibliografía. Annals of Operations

Research, 511-623.

Pattnaik, S., & Mohan, S. (1998). Urban Bus Transit Route Network Design Using Genetic

Algorithm. Journal of Transportation Engineering, 368-375.

Petch, R., & Salhi, S. (2007). A GA Based Heuristic for the Vehicle Routing Problem with

Multiple Trips. Journal of Mathematical Modelling and Algorithms, 591-613.

Rao, K., Krishna, M., & Dhingra, S. (2000). Public Transport Routing And Scheduling

Using Genetic Algorithms. Computer-Aided Scheduling of Public Transport, 21-23.

Shih, M., Mahmassani, H., & M, B. (1998). Planning and Desing Model for Transit Route

Networks with Coordinated Operations. Transportation Research Record, 16-23.

Talbi, E. (2009). Metaheuristics From Desing To Implementation. New Jersey: John

Wiley.

Transporte, M. d., & DNP. (2002). Conpes 3167: Política para mejorar el servicio de

transporte público urbano de pasajeros. Bogotá D.C.

TTC-SYSTRA-GGT, U. T. (2001). Estudio del diseño conceptual del sistema integrado de

transporte masivo para el área metropolitana de Pereira, Dosquebradas, La

Virginia. Pereira.

Ahmet Sen y Kerem Bulbul, “A survey on multi trip vehicle routing problem”. VI international

logistics and supply chain congress, Turklye, 2008.

Arbex, R.O., da Cunha, C.B., 2015. Efficient transit network design and frequencies setting

multi-objective optimization by alternating objective genetic algorithm. Transp. Res. Part B

Methodol. doi:10.1016/j.trb.2015.06.014

Asadi Bagloee, S., Ceder, A. (Avi), 2011. Transit-network design methodology for actual-

size road networks. Transp. Res. Part B Methodol. 45, 1787–1804.

doi:10.1016/j.trb.2011.07.005

Axhausen, K. W. y Smith, R. L. (1984) Evaluation of Heuristic Transit Network Optimization

Algorithms. Transportation Research Record, Vol 976, 7-20.

Ayala Rodriguez Alexander y Gonzalez Butrón Edgar, “Asignación de rutas de vehículos

para un sistema de recolección de residuos sólidos en la acera”, Revista de ingeniería –

Universidad de Los Andes, No. 13, 2001, pp 5-11.

Baaj, M.H., Mahmassani, H.S., 1991. AI-based approach for transit route system planning

and design. J. Adv. Transp. 25, 187–210.

Bagloee, S., Ceder, A. (Avi), 2011. Transit-network design methodology for actual-size road

networks. Transp. Res. Part B Methodol. 45, 1787–1804. doi:10.1016/j.trb.2011.07.005

Borndörfer, R., Grötschel, M., Pfetsch, M.E., 2007. A Column-Generation Approach to Line

Planning in Public Transport. Transp. Sci. 41, 123–132. doi:10.1287/trsc.1060.0161

Baaj, M. H. y Mahmassani, H. S. (1991) An AI-Based Approach for Transit Route System

Planning and Design. Journal of Advanced Transportation, Vol 25(2), 187-210.

Baaj, M. H. y Mahmassani, H. S. (1990) TRUST: A LISP program for the analysis of transit

route configurations. Transportation Research Record, Vol 1283, 125-135.

Baaj, M. H. y Mahmassani, H. S. (1995) Hybrid route generation heuristic algorithm for the

design of transit networks. Transportation Research , Vol 3C(1), 31-50.

Baaj and Mahmassani, Hybrid Route Generation Heuris-tic Algorithm for The Design of

Transit Networks, (1995)

Baldacce Roberto, Mingozzi Aristide y Roberti Roberto, “Recent exact algoritms for solving

the vehicle routing problem under capacity and time windows constraints”, European

journal of operational research, vol. 218, 2011, pp 1-6.

Barra, A. y Kawamoto, E. (2000) Roteirização de ônibus urbano: escolha de um método

apropiado às cidades brasileiras. Engenharia de Tráfego e Transportes 2000: Avanços

para uma era de mudanças. Río de Janeiro: ANPET, 729-742.

Bayas Meza Patricio G., “Estudio y propuesta de nuevas rutas y líneas de transporte

público urbano del distrito metropolitano de Quito, caso de aplicación corredor sur

occidental del sistema metro bus”, tesis grado, magister en ingeniería industrial y

productividad, 2011, escuela politécnica nacional, facultad de ingeniería química y

agroindustrial.

Braysy Oll y Wout Dullaert, “A fast evolutionary metaheuristic for the VRP with time

windows”, International journal on artificial intelligence tools, vol. 12, 2003, pp 153-172.

Bruce Golden, Raghavan S. y Wasil Edward, “The vehicle routing problem: latest advances

and new challenges”. Springer, New York, 2008, pp 3-122.

Caramia, M., Carotenuto, P. y Confessore, G. (2001) Metaheuristics techniques in bus

network optimization. NECTAR Conference no 6 EUROPEAN STRATEGIES IN THE

GLOBALISING MARKETS; Transport Innovations, Competitiveness and Sustainability in

the Information Age, 16-18 Mayo de 2001, Helsinki, Finlandia.

Ceder, A. e Israeli, Y. (1998) User and Operator Perspectives in Transit Network Design.

Transportation Research Record, Vol 1623, 3-7.

Ceder, A. y Wilson, N. H. M. (1986) Bus Network Design. Transportation Research, Vol

20B(4), 331-344.

Cal y Mayor y Asociados, Estudio de estructuración de detalle del SETP de Neiva, 2018

Cal y Mayor - Ikon. Estructuración técnica, legal y financiera de detalle del Sistema

Estratégico de Transporte (SETP) de la ciudad de Neiva. Producto 3: Análisis y diagnóstico

de información secundaria e información de campo. TRANSFEDERAL, 2017.

Cancela, H., Mauttone, A., Urquhart, M.E., 2015. Mathematical programming formulations

for transit network design. Transp. Res. Part B Methodol. 77, 17–37.

doi:10.1016/j.trb.2015.03.006

Cascetta, Ennio, 2009. Transportation Systems Analysis, Models and Applications. Second

Edition, Springer.

Collette, Y., Siarry, P., 2004. Multiobjective Optimization: Principles and Case Studies.

Springer Science & Business Media.

Contardo Vera Claudio Andrés, “Formulación y solución de un problema de ruteo de

vehículos con demanda variable en tiempo real, trasbordos y ventanas de tiempo”,

memoria para optar al título de ingeniero civil matemático, departamento de ingeniería

matemática, Universidad de Chile, Santiago de Chile, Chile, 2005.

Cordeau Jean-Francois, Gendreau Michel, Laporte Gilbert, Potvin Jean-Yves y Semet

Frederic, “A guide to vehicle routing heuristics”, The journal of operational research society,

vol. 53, No. 5, 2002, pp 512 – 522.

Crespo Hernan, Marti Rafael y Pacheco Joaquin, “Procedimientos metaheurísticos en

economía y empresa”, revista electrónica de comunicaciones y trabajos de ASEPUMA, 1ª

edición, Tirant lo Blanch, Valencia, España, 2007.

Curtin, K.M., Biba, S., 2011. The Transit Route Arc-Node Service Maximization problem.

Eur. J. Oper. Res. 208, 46–56. doi:10.1016/j.ejor.2010.07.026

Daganzo, C.F., 2010. Structure of competitive transit networks. Transp. Res. Part B

Methodol. 44, 434–446. doi:10.1016/j.trb.2009.11.001

Daneshzand, F., 2011. 8 - The Vehicle-Routing Problem, in: Kardar, R.Z.F.R. (Ed.),

Logistics Operations and Management. Elsevier, London, pp. 127–153.

Departamento Nacional de Planeación, Dirección de estudios económicos, CONPES 3167,

año 2002


año 2003


año 2013


año 2015


año 2017

Dorronsoro Diaz Bernabé, The VRP Web, collaboration between AUREN and the

Languages and Computation Sciences department of the University of Malaga, última

actualización: marzo de 2007, disponible en http://neo.lcc.uma.es/radiaeb/WebVRP/.

Durán Micco Javier Vicente, “Optimización en el Diseño de Redes de Transporte Público

con Objetivos Medioambientales Mediante Algoritmos Evolutivos”, Facultad de Ingeniería,

Departamento de Ingeniería Industrial, Universidad de Concepción, Chile, 2016.

Ehrgott, M., Gandibleux, X., 2004. Approximative solution methods for multiobjective

combinatorial optimization. Top 12, 1–63. doi:10.1007/BF02578918

Eric D. Tallard, Laporte Gilbert y Gendreau Michel, “Vehicle routeing with multiple use of

vehicles”, The journal of the operational research society, Vol. 47, No. 8, 1996, pp 1065 –

1070.

Estrada, M., Roca-Riu, M., Badia, H., Robusté, F., Daganzo, C.F., 2011. Design and

implementation of efficient transit networks: Procedure, case study and validity test. Transp.

Res. Part Policy Pract., Select Papers from the 19th International Symposium on

Transportation and Traffic Theory (ISTTT) 45, 935–950. doi:10.1016/j.tra.2011.04.006

Farahani, R.Z., Miandoabchi, E., Szeto, W.Y., Rashidi, H., 2013. A review of urban

transportation network design problems. Eur. J. Oper. Res. 229, 281–302.

doi:10.1016/j.ejor.2013.01.001

Fu, Q., Liu, R., Hess, S., 2012. A Review on Transit Assignment Modelling Approaches to

Congested Networks: A New Perspective. Procedia - Soc. Behav. Sci., Proceedings of

EWGT2012 - 15th Meeting of the EURO Working Group on Transportation, September

2012, Paris 54, 1145–1155. doi:10.1016/j.sbspro.2012.09.829

Gendreau, Michel y Potvin, Jean-Yves, “Metaheuristics in combinatorial optimization”, en:

Annais of operations research, 2005, vol. 140, pp 189 – 213.

Gobierno Nacional de Colombia, Plan nacional de desarrollo 2006 – 2010 “Estado

comunitario: Desarrollo para todos”

Gobierno Nacional de Colombia, Decreto 3422 de 2009

Gobierno Nacional de Colombia, Plan nacional de desarrollo 2010 – 2014 “Prosperidad

para todos”

Gobierno Nacional de Colombia, Plan nacional de desarrollo 2014 – 2018 “Todos por un

nuevo país”

Goldberg, D. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning.

Addison-Wesley.

Goksal, F.P., Karaoglan, I., Altiparmak, F. A., Hybrid discrete particle swarm optimization

for vehicle routing problem with simultaneous pickup and delivery. Jan 2012, Computers &

Industrial Engineering, 2012.

Gonzalez Vargas Guillermo y Gonzalez Aristizabal Felipe, “Metaheurísticas aplicadas al

ruteo de vehículos, parte 1: formulación del problema”, revista de ingeniería e investigación

– Universidad Nacional de Colombia, vol. 26, No. 3, 2006, pp 149 – 156.


ruteo de vehículos, parte 2: algoritmo genético, comparación con una solución heurística”,

revista de ingeniería e investigación – Universidad Nacional de Colombia, vol. 27, No. 1,

2007, pp 149 – 157.


ruteo de vehículos, parte 3: Genetic clustering and tabu routing”, revista de ingeniería e

investigación – Universidad Nacional de Colombia, vol. 27, No. 2, 2007, pp 106 – 113.

Gruttner, E., Pinninghoff, M. A., Tudela, A. y Díaz, H. (2002) Recorridos Optimos de Líneas

de Transporte Público Usando Algoritmos Genéticos. Jornadas Chilenas de Computación.

Noviembre de 2002, Copiapó, Chile.

Hernan Restrepo Jorge, Medina Petro Daniel y Cruz Eduardo Arturo, “Un problema

logístico de programación de vehículos con ventanas de tiempo”, Scientia et technica –

Universidad Tecnológica de Pereira, Vol. 14, No 39, 2008.

Hutter, F., Stuetzle, T., Leyton-Brown, K., Hoos, H.H., 2009. ParamILS: An Automatic

Algorithm Configuration Framework. J. Artif. Intell. Res. 36, 267–306. doi:10.1613/jair.2861

Interconsult (1997) Estudio sobre utilización del Transporte Colectivo Urbano de Pasajeros

en la ciudad de Montevideo.

Instituto SER de Investigación, (2003), “Bases de una política integral de transporte urbano

en Colombia”, Asesoría contratada por el DNP, Bogotá.

Israeli, Y. Y Ceder, A. (1993) Transit Route Design Using Scheduling and Multiobjective

Programming Techniques. Computer-Aided Transit Scheduling, Julio de 1993, Lisboa,

Portugal, 56-75.

Izquierdo, Samir. Optimización de rutas de transporte público con Algoritmos Genéticos,

Máster en Ingeniería Informática, Universidad de Cataluña, 2016.

Kepaptsoglou, K., Karlaftis, M., 2009. Transit route network design problem: Review. J.

Transp. Eng. 135, 491–505. doi:10.1061/(ASCE)0733-947X(2009)135:8(491)

K-Shortest Path- Yen‘s algorithm - File Exchange - MATLAB Central [WWW Document],

n.d. URL http://www.mathworks.com/matlabcentral/fileexchange/32513-k-shortest-path-

yen-s-algorithm (accessed 12.18.15).

Lawler, Eugene. Combinatiorial Optimization: Networks and Matroids. Courier Dover, 1976,

disponible en http://www.plouffe.fr/simon/math/combinatorialoptimization.pdf

Litman, T., 2010. Evaluating public transit benefits and costs: Best Practices Guidebook.

World Transit Res.

Magnanti, T.L., Wong, R.T., 1984. Network Design and Transportation Planning: Models

and Algorithms. Transp. Sci. 18, 1–55. doi:10.1287/trsc.18.1.1

Mandl, C.E., 1980. Evaluation and optimization of urban public transportation networks.

Eur. J. Oper. Res. 5, 396–404. doi:10.1016/0377-2217(80)90126-5

Mauttone, A., Urquhart, M.E., 2009. A multi-objective metaheuristic approach for the transit

network design problem. Public Transp. 1, 253–273. doi:10.1007/s12469-010-0016-7

Mandl, C. E. (1979) Evaluation and optimization of urban public transportation networks.

European Journal of Operational Research, Vol 5, 396-404.

Mandl, Applied Network Optimization, Academic Press, London, 1979

Marín Leidy et al. “Un modelo de optimización de rutas de transporte urbano en el área

metropolitana de Bucaramanga con VRPTW mediante un algoritmo de optimización por

enjambre de partículas evolutivo”, Facultad de Ingenierías Fisicomecánicas, Escuela de

estudios industriales y empresariales, Universidad Industrial de Santander, Bucaramanga,

2017.

Mauttone Antonio, Cancela Héctor, Urquhart María, “Diseño y optimización de rutas y

frecuencias en el transporte colectivo urbano, Modelos y algoritmos”. Departamento de

Investigación Operativa Instituto de Computación, Facultad de Ingeniería, Universidad de

la República, 2016

Ngamchai, S., y Lovell, D. J. (2000) Optimal Time Transfer in Bus Transit Route Network

Design Using a Genetic Algorithm. Computer-Aided Scheduling of Public Transport. 21-23

Junio 2000, Berlin, Alemania.

Nayeem, M.A., Rahman, M.K., Rahman, M.S., 2014. Transit network design by genetic

algorithm with elitism. Transp. Res. Part C Emerg. Technol. 46, 30–45.

doi:10.1016/j.trc.2014.05.002

Nikolić, M., Teodorović, D., 2014. A simultaneous transit network design and frequency

setting: Computing with bees. Expert Syst. Appl. 41, 7200–7209.

doi:10.1016/j.eswa.2014.05.034

Ortúzar, J. de D. y Willumnsen, L. (1996) Modelling transport. John Wiley and Sons, Inc.

Olivera Alfredo, “Heurísticas para problemas de ruteo de vehículos”, reporte de

investigación, Instituto de computación – Facultad de Ingeniería, Universidad de la

República, Montevideo, Uruguay, 2004, disponible en:

http://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf.

Osman, I.H., Laporte, G., 1996. Metaheuristics: A bibliography. Ann. Oper. Res. 63, 511–

623. doi:10.1007/BF02125421

Patriksson, M., 1994. The Traffic Assignment Problem---Models and Methods.

Perederieieva, O., Ehrgott, M., Raith, A., Wang, J.Y.T., 2015. A framework for and empirical

study of algorithms for traffic assignment. Comput. Oper. Res. 54, 90–107.

doi:10.1016/j.cor.2014.08.024

Pattnaik, S. B., Mohan, S. y Tom, V. M. (1998) Urban Bus Transit Route Network Design

Using Genetic Algorithm. Journal of Transportation Engineering, Vol 124(4), 368-375.

Prasad Chalasani and Rajeev Motwani. Aproximating capacitated routing and delivery

problems. SIAM journal on computing, 28 (6): 2133 – 2149, 1999.

Rao, K. V. Krishna, Muralidhar, S. y Dhingra, S. L. (2000) Public Transport Routing And

Scheduling Using Genetic Algorithms. Computer-Aided Scheduling of Public Transport. 21-

23 de Junio de 2000, Berlin, Alemania.

Rodríguez, Daniel, “Planeación de transporte y uso de suelo: ¿automovilidad o

accesibilidad? (Presente y Futuro de la Movilidad Urbana en Bogotá)”, Bogotá, 2000.

Shih, M. C., Mahmassani, H. S., & Baaj, M. H. (1998) Planning and Design Model for Transit

Route Netwoks with Coordinated Operations. Transp. Research Record, Vol 1623, 16-23.

Szeto, W.Y., Jiang, Y., 2014. Transit route and frequency design: Bi-level modeling and

hybrid artificial bee colony algorithm approach. Transp. Res. Part B Methodol. 67, 235–

263. doi:10.1016/j.trb.2014.05.008

Taha, Hamdy. Investigación de Operaciones. 7ma. Edición. Pearson Educación. México,

2004.

Talbi, E.-G., 2009. Metaheuristics: From Design to Implementation. Wiley Publishing.

Toth, P., Vigo, D., 2014. Vehicle Routing, MOS-SIAM Series on Optimization. Society for

Industrial and Applied Mathematics.

Toth Paolo y Vigo Daniele, “The vehicle routing problema”. Society of industrial and applied

mathematics (SIAM) monographs on discrete mathematics and applications, Philadelphia,

USA, 2002, pp 1-23, 109-149.

Unidad Coordinadora de Proyectos – Secretaría de Hacienda de Bogotá, (2010), “Proyecto

de transporte urbano II (Borrador Preliminar)”, Bogotá.

Unión Temporal Steer Davies Gleave - AKIRIS, Estudio de diseño conceptual del SETP de

Neiva, 2008

Unión Temporal TTC-SYSTRA-GGT, (2001), “Estudio del diseño conceptual del sistema

integrado de transporte masivo para el área metropolitana de Pereira, Dosquebradas, La

Virginia”, Asesoría contratada por el DNP, Pereira.

Wan, Q.K., Lo, H.K., 2009. Congested multimodal transit network design. Public Transp. 1,

233–251. doi:10.1007/s12469-009-0015-8

Wan, Q.K., Lo, H.K., 2003. A Mixed Integer Formulation for Multiple-Route Transit Network

Design. J. Math. Model. Algorithms 2, 299–308.

doi:10.1023/B:JMMA.0000020425.99217.cd

Wee-Kit Ho, Juay Chin Ang y Andrew Lim, “A hybrid search algorithm for the vehicle routing

problem with time windows”, Internacional journal on artificial intelligenc tools, vol. 10, No.

3, 2011, pp 431 – 449.

Wren, A. (1999) Heuristics Ancient and Modern; Transport scheduling through the ages.

Leeds Artificial Intelligence Seminar Series, University of Leeds.

(http://www.scs.leeds.ac.uk/seth/seminars/nov-17-99b.DOC, Mayo 2003)

Yen, J.Y., 1971. Finding the K Shortest Loopless Paths in a Network. Manag. Sci. 17, 712–

716.

Zhai, H., Frey, H.C., Rouphail, N.M., 2008. A Vehicle-Specific Power Approach to Speed-

and Facility-Specific Emissions Estimates for Diesel Transit Buses. Environ. Sci. Technol.

42, 7985–7991. doi:10.1021/es800208d

Zhang, L., Yang, H., Wu, D., Wang, D., 2014. Solving a discrete multimodal transportation

network design problem. Transp. Res. Part C Emerg. Technol. 49, 73–86.

doi:10.1016/j.trc.2014.10.008

potenciales beneficios del diseño de un sistema de rutas

Documents