universidad de chile facultad de ciencias fisicas y … · nueva estrategia de transporte público...
TRANSCRIPT
UNIVERSIDAD DE CHILE
FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS
DEPARTAMENTO DE INGENIERIA INDUSTRIAL
PROGRAMACIÓN DE LOS HORARIOS DE SALIDA DE LOS ÚLTIM OS TRENES DE LAS ESTACIONES TERMINALES DEL METRO.
TESIS PARA OPTAR AL GRADO DE MAGISTER EN GESTIÓN DE OPERACIONES
TESIS PARA OPTAR AL TÍTULO DE INGENIERO CIVIL INDUS TRIAL
MARÍA-PAZ MACARENA SALVATIERRA ROASENDA
PROFESOR GUÍA:
PABLO ANDRÉS REY
PROFESOR COGUÍA:
CRISTIAN CORTÉS CARRILLO
MIEMBROS DE LA COMISION:
GUILLERMO ALFREDO DURÁN
VICENTE ROMERO SOLIMANO
SANTIAGO DE CHILE
MARZO, 2008
A mi familia…
RESUMEN EJECUTIVO
Actualmente, la empresa Metro S.A enfrenta una serie de problemas que se producen a la
hora de cierre. Pasajeros que consiguen entrar a la red no pueden finalizar sus viajes ya
que cuando desean realizar trasferencias de trenes, la operación de éstos ya ha finalizado.
El foco de esta tesis es la creación de un modelo matemático capaz de resolver esta
problemática. Para esto se distingue dos temas: el primero, es la programación de
horarios de salida de los últimos trenes en servicio; y el segundo, es la optimización de los
recursos a la hora de cierre, para que cada pasajero pueda concretar los trasbordos que
son necesarios para su viaje.
El problema se enfrenta con dos modelos de programación matemática entera. El primero
programa la salida de los trenes a partir de las 22:00 hrs, hasta la hora de cierre de
puertas, que debe ocurrir después de las 23:00 hrs. El segundo, programa las
transferencias que se deben realizar con los últimos trenes, decidiendo además si es
necesaria la utilización de trenes extra para poder completar todas las rutas demandadas
a la hora de cierre.
Estos modelos son integrados para obtener una solución final. Los resultados obtenidos
por el segundo modelo, indican el horario de salida del último tren de cada estación
terminal, lo cual se incorpora como restricción en el primer modelo. En caso de existir
trenes extra, sus horarios de salida también son ingresados como restricciones al primero.
Como resultado inicial se obtiene la programación de los viajes que resultan ser 126 sobre
toda la red. Se realiza un análisis sobre los tiempos de espera de los pasajeros y se
incorporan trenes intermedios (entre el último tren y el extra) desde 4 estaciones
terminales, para brindar una mejor calidad de servicio, disminuyendo los tiempos de
espera de los últimos pasajeros entre un 62% y 100%. La solución final consta de 130
viajes. La forma actual de operar de Metro bajo los mismos estándares de calidad, posee
20 viajes más, lo que repercute fuertemente en los costos operacionales de la empresa.
i
TABLA DE CONTENIDOS
1. INTRODUCCIÓN ......................................................................................................... 1
2. REVISIÓN BIBLIOGRÁFICA .......................................................................................... 5
2.1 Planificación del transporte público de trenes .................................................................. 5
2.1.1 Pasos generales de la planificación del transporte público de trenes ............................. 5
2.1.2 Planificación de la oferta de transporte en Metro S.A. ................................................... 8
2.2 Programación de trenes................................................................................................. 13
2.3 Coordinación de trasbordos ........................................................................................... 18
2.3.1 Introducción a las transferencias ................................................................................. 18
2.3.2 Costos asociados a los trasbordos ................................................................................ 20
2.3.3 Restricciones sobre las ventanas de tiempo ................................................................. 22
3. MODELACIÓN PROPUESTA ....................................................................................... 24
3.1 Enfoque del problema ................................................................................................... 24
3.2 Modelo de Salida de trenes con Tiempos Fijos (MSTF) .................................................... 25
3.2.1 Conjuntos .................................................................................................................... 27
3.2.2 Parámetros .................................................................................................................. 28
3.2.3 Variables ..................................................................................................................... 29
3.2.4 Restricciones ............................................................................................................... 30
3.2.5 Función Objetivo ......................................................................................................... 42
3.3.6 Cuadro resumen del MSTF ........................................................................................... 42
3.3 Modelo de Salida de trenes con Tiempos Variables (MSTV) ............................................ 44
3.3.1 Conjuntos .................................................................................................................... 46
3.3.2 Parámetros .................................................................................................................. 48
3.3.3 Variables ..................................................................................................................... 49
3.3.4 Restricciones ............................................................................................................... 50
3.3.5 Función Objetivo ......................................................................................................... 56
3.3.6 Cuadro resumen del MSTV .......................................................................................... 57
3.4 Integración de los modelos ........................................................................................... 58
3.4.1 Conversión de resultados del MSTV al MSTF ................................................................ 58
3.4.2 Nuevas restricciones del MSTF ..................................................................................... 59
ii
4. APLICACIÓN DE LOS MODELOS................................................................................. 61
4.1 Tamaño de las instancias ............................................................................................... 61
4.1.1 Tamaño del MSTF ........................................................................................................ 61
4.1.2 Tamaño del MSTV ........................................................................................................ 62
4.2 Resolución de los modelos ............................................................................................. 63
4.2.1 Resolución del MSTV ................................................................................................... 64
4.2.2 Resolución del MSTF .................................................................................................... 70
4.3 Análisis y experimentos ................................................................................................. 75
4.3.1 Horarios de salida ........................................................................................................ 75
4.3.2 Generación de rutas .................................................................................................... 77
4.3.3 Tiempos de espera ...................................................................................................... 80
4.3.4 Análisis de la situación actual ....................................................................................... 87
5. SÍNTESIS Y CONCLUSIONES ....................................................................................... 90
6. BIBLIOGRAFÍA .......................................................................................................... 94
ANEXOS ...................................................................................................................... 96
1. Red de Metro, Diciembre 2007. .................................................................................... 96
2. Siglas Estaciones de Metro. .......................................................................................... 97
iii
INDICE DE FIGURAS
Figura 2.1: Proceso jerárquico de planificación del transporte público de trenes. ............... 6
Figura 2.2: Esquema general de la planificación de la oferta de transporte en Metro S.A. .. 9
Figura 2.3: Problema de programación de horarios a costo mínimo. .................................. 16
Figura 2.4: Representación de los trenes feeder, critical y next. ......................................... 20
Figura 3.1: Red espacio temporal de viajes en una línea. .................................................... 30
Figura 3.2: Diagrama de conservación de flujo. ................................................................... 33
Figura 3.3: Maniobra tras-estación. ..................................................................................... 36
Figura 3.4: Maniobra ante-estación. .................................................................................... 37
Figura 3.5: Estacionamiento de trenes en una estación terminal........................................ 37
Figura 3.6: Diagrama de satisfacción de demanda............................................................... 41
Figura 3.7: Modelo de Salida de trenes con Tiempos Fijos (MSTF). .................................... 43
Figura 3.8: Combinación Estación Los Héroes. ..................................................................... 47
Figura 3.9: Red del Metro de Santiago. ................................................................................ 48
Figura 3.10: Combinación de un tren a otro. ....................................................................... 52
Figura 3.11: Modelo de Salida de trenes con Tiempos Variables (MSTV). .......................... 57
Figura 4.1: Llegadas a las estaciones de combinación. ........................................................ 65
Figura 4.2: Gráfico de la demanda en Línea 1 dirección SP-EM. .......................................... 73
Figura 4.3: Gráfico de la demanda en Línea 1 dirección EM-SP. .......................................... 73
Figura 4.4: Rutas L1-L4-L4A y L5-L4-L4A. .............................................................................. 78
Figura 4.5: Rutas L2-L4A-L4 y L4-L4A-L2. .............................................................................. 79
Figura 4.6: Rutas L4A-L4-L1 y L4A-L4-L5. .............................................................................. 79
Figura 4.7: Incorporación de trenes intermedios. ................................................................ 83
Figura 4.8: Tramos de la red. ................................................................................................ 85
iv
INDICE DE TABLAS
Tabla 4.1: Cantidad de variables del MSTF. .......................................................................... 61
Tabla 4.2: Cantidad de restricciones del MSTF. ................................................................... 62
Tabla 4.3: Cantidad de variables del MSTV .......................................................................... 62
Tabla 4.4: Cantidad de restricciones del MSTV. ................................................................... 62
Tabla 4.5: Tiempos de viaje entre estaciones de combinación............................................ 66
Tabla 4.6: Tiempos de viaje desde las estaciones terminales a las de combinación. .......... 66
Tabla 4.7: Número de trenes extras c/r a Tmax. .................................................................. 67
Tabla 4.8: Instantes de salida de los últimos trenes de las estaciones terminales. ............. 69
Tabla 4.9: Instantes de salida de los trenes extra desde la estaciones terminales.............. 69
Tabla 4.10: Disponibilidad inicial de los trenes en las estaciones terminales...................... 71
Tabla 4.11: Parámetros co, cap, tv y m. ............................................................................... 72
Tabla 4.12: Tiempos mínimos y máximos entre trenes consecutivos. ................................ 72
Tabla 4.13: Instantes de salida de los últimos trenes y de los trenes extra. ........................ 74
Tabla 4.14: Cantidad de viajes por línea............................................................................... 75
Tabla 4.15: Horarios de salida de los últimos trenes y los trenes extra. .............................. 76
Tabla 4.16: Cantidad de trenes extra c/r a emax. ................................................................ 77
Tabla 4.17: Tiempos de espera por último tren. .................................................................. 81
Tabla 4.18: Tiempos de espera por trenes extra. ................................................................. 82
Tabla 4.19: Tiempos de espera con trenes intermedios. ..................................................... 84
Tabla 4.20: Tiempos en ruta L1-L4-L4A. ............................................................................... 86
Tabla 4.21: Tiempos en ruta L5-L4-L4A. ............................................................................... 86
Tabla 4.22: Tiempos en ruta L2-L4A-L4. ............................................................................... 86
Tabla 4.23: Tiempos en ruta L4-L4A-L2. ............................................................................... 86
Tabla 4.24: Tiempos en ruta L4A-L4-L1. ............................................................................... 86
Tabla 4.25: Tiempos en ruta L4A-L4-L5. ............................................................................... 87
Tabla 4.26: Tiempos de espera actuales por últimos trenes................................................ 88
1
1. INTRODUCCIÓN
La programación horaria de trenes, constituye una parte fundamental dentro del proceso
de planificación del trasporte público de trenes. En este proceso se debe programar las
salidas y llegadas de trenes para puntos específicos de una red. Además dependiendo de
los distintos propósitos que se busquen, la información es requerida en distintos niveles
de agregación, según las características de la red.
Esta tesis aborda un problema de programación de horarios de trenes que circulan en una
red. Específicamente, la red en estudio corresponde al Metro de Santiago, ferrocarril
metropolitano que cruza gran parte de la capital, siendo uno de los principales operadores
de transporte público del país, transportando a más de dos millones de personas a diario.
Actualmente lo componen 5 líneas, y se está trabajando en proyectos para su extensión,
con lo que abarcaría 21 comunas de la capital1.
Actualmente, Metro S.A. ha enfrentado un sin número de problemas de aspectos
operacionales que han sido noticia pública, principalmente por la incorporación de una
nueva estrategia de transporte público implementada en la capital, en donde un gran
porcentaje de santiaguinos ha cambiado su modalidad de viaje, prefiriendo el antiguo y
conocido sistema de Metro, a la utilización de nuevos buses con nuevos recorridos. El
principal resultado de esto es un aumento inesperado en la demanda de viajes en Metro,
lo que ha significado un mayor control y precisión en cuanto a la operación.
Algunos de estos problemas son causados a la hora de cierre, en donde se ha encontrado
a pasajeros que quedan dentro de la red sin poder llegar a sus destinos. Este problema
ocurre cuando los pasajeros que deben realizar combinaciones, para llegar a su destino, y
no alcanzan a tomar el tren que corresponde para realizar la transferencia. Como solución
a esto, en algunos casos, Metro ha debido pagar por un trasporte público alternativo para
que estas personas puedan completar su viaje.
1 http://www.metrosantiago.cl/organizacion.php
2
La motivación de esta tesis surge debido a los costos asociados a esta medida y por la
calidad de servicio que desea brindar Metro, por lo que se desea solucionar esta situación
a la hora de cierre, asegurando a cada pasajero la llegada a su destino.
El tema abordado en este trabajo es la programación horaria de trenes a partir de un
cierto instante cercano a la hora de cierre, en donde se genere una programación viaje a
viaje que permita ir disminuyendo su frecuencia de salida y así comenzar a guardar los
trenes en sus cocheras, teniendo siempre en cuenta el trade-off producido entre el nivel
de servicio entregado a los pasajeros y los costos operacionales en los que se incurre.
El alcance de esta tesis es el planteamiento de un modelo que permita a los pasajeros que
consiguieron entrar a la red de Metro, poder llegar a sus destinos con al menos un camino
lógico factible. Al decir lógico se refiere a realizar rutas directas y con un único destino. La
palabra factible hace referencia a que exista un camino por donde circulen trenes para
poder realizar combinaciones si fuese necesario.
El problema será abordado con la creación de modelos matemáticos, que se basarán
principalmente en problemas relacionados a la programación de trenes, y a la
coordinación de transferencias respectivamente.
Referente a lo anterior, existe una amplia línea de investigación sobre estos temas. Para el
problema de programación de horarios, en la literatura, principalmente se abarca el tema
de la programación bajo el supuesto que el resultado obtenido se replica durante toda la
jornada de operación, con el fin de enfrentar la demanda por transporte, junto a una serie
de restricciones operativas de por medio, que hay en común. Para enfocarse en el
problema planteado en esta tesis, es decir, el cierre de la jornada, se debe incorporar el
hecho de guardar trenes en sus cocheras, y así disminuir la frecuencia de salida de éstos.
En cuanto a la literatura sobre la coordinación de transferencias se discute principalmente
el tiempo que deben esperar los pasajeros para poder realizar combinaciones. Esto servirá
para poder trabajar con las transferencias, identificándolas y alineando objetivos según las
características del problema planteado.
3
De acuerdo a lo expuesto, el problema general de esta tesis será abordado con la creación
de dos modelos. El primero de ellos tiene por objetivo generar las salidas de trenes a
partir de un cierto instante y el estacionamiento final de los mismos, sujeto a un conjunto
de restricciones, con el fin de minimizar la cantidad de viajes realizados en una línea. El
segundo modelo trabajará con las líneas en forma conjunta y consistirá en programar las
salidas de los últimos trenes desde cada estación terminal con el fin de poder satisfacer las
rutas entre todos los pares origen-destino de la red, después de la hora de cierre.
Una diferencia que hay entre los modelos, es que en el primero de ellos no se pueden
manejar los tiempos de estacionamiento de los trenes en las estaciones intermedias de la
red, debido al gran número de viajes que se producen, lo que resultaría difícil de operar
para Metro (muchos trenes con distintos tiempos de parada en las estaciones), a
diferencia del segundo donde sólo se trabaja con un tren desde cada estación terminal.
Una vez concebidos ambos modelos, éstos se podrán juntar añadiendo restricciones que
surjan a partir de los resultados del segundo de ellos, al primero, y así poder obtener la
solución final deseada para el problema.
En cuanto a la estructura del informe, en el Capítulo 2 se realiza una revisión bibliográfica
que contiene los principales temas de esta tesis. Se comienza con una descripción en
cuanto a la planificación del transporte público en general y cómo se realiza en Metro S.A.
Además, se analiza los temas de la programación de horarios y la coordinación de
transferencias, mostrando las principales formulaciones.
En el Capítulo 3 se presenta la creación de los modelos desarrollados en el marco de esta
tesis. Se comienza con el primer modelo que se hace cargo de la programación de horarios
de trenes hasta la hora de cierre, en donde la principal característica es la disminución de
la frecuencia de salida de los trenes pudiendo satisfacer la demanda que se enfrenta a esa
hora.
Luego se presenta la creación del segundo modelo que se hace cargo de la coordinación
que debe existir en los trasbordos. El capítulo concluye con una explicación de cómo
4
ocurre la integración de ambos modelos, incorporando resultados del segundo en forma
de restricciones en el primero.
En el Capítulo 4 se presentan los resultados de los modelos, se realiza análisis de los
principales indicadores de desempeño de la operación, se plantea alternativas de solución
y se hacen comparaciones con respecto a la situación actual con la que trabaja Metro S.A.
Finalmente en el Capítulo 5 se discute los resultados y los principales análisis obtenidos de
ellos, pudiendo concretar y sintetizar lo realizado escogiendo una solución final
satisfactoria. Además se presenta las conclusiones del trabajo.
5
2. REVISIÓN BIBLIOGRÁFICA
En el presente capítulo se realiza una descripción de la planificación del transporte público
de trenes desarrollada en países europeos y además se muestra cómo Metro S.A. trabaja
su planificación, dando una breve descripción de cada una de sus etapas.
Además, se revisa algunos casos estudiados por ciertos autores, donde se incluye los dos
temas que se mencionaron en la Introducción, que sirven de referencia para el desarrollo
de los modelos para esta tesis, esto es, la programación de horarios de trenes y las
combinaciones o trasbordos que se realizan en una red.
2.1 Planificación del transporte público de trenes
El proceso de planificación de transporte público de trenes posee dos grandes
componentes que se relacionan con la determinación de las rutas entre cada origen y
destino, y con la asignación de recursos necesaria para poder satisfacer las necesidades de
los pasajeros. En relación a dichas componentes, a continuación se presenta un esquema
general del proceso de planificación del transporte público de trenes, que se utiliza en
países europeos, analizando brevemente cada una de sus partes. En seguida se describe
cómo Metro trabaja actualmente este tema.
2.1.1 Pasos generales de la planificación del transporte público de trenes
En la actualidad, la planificación del transporte público de trenes es una tarea bastante
compleja debido a la gran cantidad de factores que deben interactuar simultáneamente.
Entre ellos predominan los kilómetros que componen la red, la cantidad de trenes que se
utilizan, la cantidad de kilómetros recorridos a diario, la cantidad de empleados, y las
grandes cantidades de dinero que mueve todo este sistema. Por ejemplo, para redes de
trenes en países europeos, las cifras que se observan son del orden de billones de
kilómetros viajados, y un número similar con
transportados (Lindner, 2000
Es precisamente por estas enormes cifras, que se constituye un concepto de
jerárquico (Bussieck, 1998
transporte público de trenes utilizado en Alemania
En él se observa que el proceso comienza con el análisis
por el servicio, la cual por lo general
siguiente tarea es la planificación
puntos de parada, conexiones y tiempos de ciclo, es decir, su ruta y su frecuencia; en
seguida para la planificación
trenes deben ser fijadas de acuerdo a
más adelante en base a variaciones temporales y restricciones operativas;
viaje programado se le debe asignar una cantidad de coches para la operación, y para
finalizar el proceso se debe asignar
Figura 2.1: Proceso jer
6
kilómetros viajados, y un número similar con respecto a la cantidad de pasajeros
er, 2000).
por estas enormes cifras, que se constituye un concepto de
, 1998). La Figura 2.1 representa el esquema de
de trenes utilizado en Alemania.
En él se observa que el proceso comienza con el análisis sobre la demanda de pasajeros
por el servicio, la cual por lo general se expresa como una matriz Origen
planificación de las líneas, lo que implica la determinación
puntos de parada, conexiones y tiempos de ciclo, es decir, su ruta y su frecuencia; en
planificación de los horarios de trenes, todas las llegadas y salidas de
trenes deben ser fijadas de acuerdo a los tiempos de ciclo, lo cual se pu
más adelante en base a variaciones temporales y restricciones operativas;
viaje programado se le debe asignar una cantidad de coches para la operación, y para
finalizar el proceso se debe asignar una tripulación a cargo de cada viaje
Proceso jerárquico de planificación del transporte público
Administración de la tripulación
Planificación del material rodante
Planificación de los horarios de trenes
Planificación de líneas
Demanda de pasajeros
respecto a la cantidad de pasajeros
por estas enormes cifras, que se constituye un concepto de planificación
igura 2.1 representa el esquema de planificación de
la demanda de pasajeros
una matriz Origen-Destino; la
de las líneas, lo que implica la determinación de sus
puntos de parada, conexiones y tiempos de ciclo, es decir, su ruta y su frecuencia; en
de los horarios de trenes, todas las llegadas y salidas de
o, lo cual se puede ir afinando
más adelante en base a variaciones temporales y restricciones operativas; luego a cada
viaje programado se le debe asignar una cantidad de coches para la operación, y para
viaje.
ción del transporte público de trenes.
7
2.1.1.1 Demanda de pasajeros
Con el fin de establecer un servicio de transporte orientado a las necesidades de los
pasajeros, el volumen de tráfico o la demanda de pasajeros debe ser dada o se debe
estimar. La forma convencional de demanda de pasajeros es la llamada matriz Origen-
Destino, en donde una entrada (i,j) entrega la cantidad de personas que desean viajar
desde i a j, donde i representa la estación de origen y j la estación de destino. Esta matriz
es calculada cada cierto intervalo de tiempo definido, durante todo un día de operación.
Cabe destacar que los resultados obtenidos de esta matriz, sólo reflejan la demanda de los
pasajeros para una red que ya se encuentra establecida (líneas y programación horaria
determinadas). Si la planificación de líneas o la programación de los trenes cambiaran, tal
vez la elección de los pasajeros se podría ver afectada.
2.1.1.2 Planificación de las líneas
Se puede definir una línea por la ruta que se le asigna y la frecuencia con la que opera.
Una ruta queda definida por un camino en la red, y la frecuencia determina que tan
seguido se operará con trenes en esa línea dentro del período programado. En esta etapa
se busca seleccionar líneas dentro de un conjunto de líneas factibles de operar, sujeto a
una serie de restricciones y un objetivo final.
Dentro de las restricciones que se deben cumplir, una primordial es que la cantidad de
viajes programados debe ser suficiente para poder transportar a todos los pasajeros.
Comúnmente a la hora de elegir un objetivo se debe lidiar con el trade-off entre la calidad
de servicio ofrecido y la minimización de costos operacionales.
2.1.1.3 Planificación de los horarios de los trenes
La generación de horarios de trenes consiste en fijar los tiempos de salida y llegada de
todos los trenes a todas las estaciones de la red. Según el número de trenes programados
8
que pasan por una determinada estación y la frecuencia con que lo hacen, la
programación de los horarios podría estar orientada a la optimización de diferentes
criterios (Vega et al, 2002): costos del usuario (tiempos totales empleados, ya sea de viaje
y de espera), costos de operación (tiempos de operación y cantidad de vehículos
utilizados), y costos de la calidad de servicio (costos por viajar de pie y la densidad de
viajeros que viajan a pie)
2.1.1.4 Planificación del material rodante y de la tripulación
Los viajes establecidos por la programación de horarios deben ser realizados por algún
vehículo (coches por ejemplo) y por una tripulación (conductores principalmente). Hay
que destacar que la administración de la tripulación no solo involucra a quienes van a
bordo del tren, si no que también incluye a la gente de aseo de cada una de la estaciones,
a los encargados de atender en boletería, y personal de seguridad entre otros.
La integración de cada uno de estos pasos, permite que se construya en forma clara y
ordenada la planificación del transporte público de trenes. La realización de cada uno de
estos pasos es de suma importancia, ya que cada uno de ellos depende del anterior para
poder tomar las decisiones correspondientes.
2.1.2 Planificación de la oferta de transporte en Metro S.A.
A continuación se describe cómo Metro trabaja la planificación de su oferta de viajes con
el fin de cumplir con la demanda que enfrenta, entregando un nivel de servicio
satisfactorio para sus pasajeros. Su forma de trabajo particular, se asemeja en algunos
pasos al esquema mencionado en la sección anterior.
Como lo establece Romero (2005), la forma en que opera Metro se puede representar en
base a cuatro etapas claves, las cuales se muestran a continuación:
Asignación de conductores y generación de rotaciones
Generación de tableros de presencia de conductores
Planificación agregada del transporte público
Figura 2.2: Esquema general de la
Realizando un pequeño paralelo con el proceso jerárquico establecido para la
planificación del transporte público de trenes en Europa, se reconocen en éste último las
etapas del anterior. Las dos primeras etapas del modelo europeo se encuentran en la
primera del proceso utilizado por Metro, la
encuentran en la segunda etapa del modelo de Metro, y la última etapa del modelo
europeo se descompone en las dos últimas etapas del modelo de Metro.
Es preciso notar que una parte importante de esta tesis tiene su foco
del modelo utilizado por Metro y
tema que se abordará en la siguiente sección.
A continuación de detalla cada uno de los pasos que componen el proceso
de la oferta de transporte en Metro
2.1.2.1 Planificación agregada de
Esta etapa está compuesta por tres aspectos que de
entrada para poder generar la planificación de la producción de viajes para dar servicio.
Éstos son, la demanda de pasajeros por viajes, los estándares de calidad que se desean
9
Asignación de conductores y generación de rotaciones
Generación de tableros de presencia de conductores
Generación de programas de circulación
Planificación agregada del transporte público
: Esquema general de la planificación de la oferta de transporte en Metro S.A.
Realizando un pequeño paralelo con el proceso jerárquico establecido para la
planificación del transporte público de trenes en Europa, se reconocen en éste último las
l anterior. Las dos primeras etapas del modelo europeo se encuentran en la
ilizado por Metro, la tercera y cuarta etapa del modelo europeo se
encuentran en la segunda etapa del modelo de Metro, y la última etapa del modelo
descompone en las dos últimas etapas del modelo de Metro.
preciso notar que una parte importante de esta tesis tiene su foco en la segunda etapa
del modelo utilizado por Metro y en particular en la tercera etapa del modelo europeo,
en la siguiente sección.
cada uno de los pasos que componen el proceso
de la oferta de transporte en Metro.
agregada del transporte público
Esta etapa está compuesta por tres aspectos que deben ser considerados como datos de
entrada para poder generar la planificación de la producción de viajes para dar servicio.
la demanda de pasajeros por viajes, los estándares de calidad que se desean
de transporte en Metro S.A.
Realizando un pequeño paralelo con el proceso jerárquico establecido para la
planificación del transporte público de trenes en Europa, se reconocen en éste último las
l anterior. Las dos primeras etapas del modelo europeo se encuentran en la
etapa del modelo europeo se
encuentran en la segunda etapa del modelo de Metro, y la última etapa del modelo
descompone en las dos últimas etapas del modelo de Metro.
en la segunda etapa
en particular en la tercera etapa del modelo europeo,
cada uno de los pasos que componen el proceso de planificación
ben ser considerados como datos de
entrada para poder generar la planificación de la producción de viajes para dar servicio.
la demanda de pasajeros por viajes, los estándares de calidad que se desean
10
brindar y las restricciones operativas generales. A continuación se explica cada uno de
ellos.
Análisis de la demanda
La demanda es uno de los datos de entrada más importantes para la planificación del
transporte público de trenes. A partir de ella, se pueden definir los requerimientos que
deben ser satisfechos durante la operación.
La forma de trabajar con estos datos dependerá del día de operación y del período horario
en cuestión, es decir, se debe trabajar en forma separada los datos de demanda
correspondientes a un día laboral v/s fin de semana, y además dependerá si los datos
corresponden a un período punta o no (por lo general se presentan horas punta en la
mañana y en la tarde que no son comparables con la demanda que se presenta al medio
día o en la noche, las cuales son mucho menores).
Las técnicas utilizadas actualmente por Metro para la estimación de demanda de
pasajeros son las que se describen a continuación:
• Caldas
El sistema Caldas es un software orientado a estimar los flujos en la red tales como
demanda de viajes en las interestaciones, subidas y bajadas de pasajeros en las
estaciones y trasbordos en las estaciones que conectan una línea con otra. La
demanda de pasajeros en una interestación para un período horario es igual a la
cantidad de personas que desean pasar por ese punto en ese período horario
determinado. La metodología consiste en establecer la demanda de viajes en Metro a
partir de la distribución espacio-temporal de la afluencia.
Se entienede por afluencia en un punto determinado el total de viajes demandados
con origen en el punto de interés dentro del período de análisis.
11
El sistema recibe los siguientes datos de entrada: (a) afluencias de pasajeros por
estación desagregadas en períodos de 15 minutos; (b) matriz de tiempos de viaje entre
cada par de estaciones de la red, construida a partir de las marchas tipo de los trenes y
suponiendo tiempos de trasbordo; (c) matriz de probabilidades de viaje obtenida a
través de la encuesta origen-destino que periódicamente realiza Metro, la
probabilidad de viaje entre la estación A y B representa el porcentaje de la afluencia
de la estación A, que tiene como destino la estación B.
Sea Pik la probabilidad de pasar por la interestación k dado que se comenzó un viaje en
i, �������,� la afluencia en la estación i entre los instantes de tiempo t1 y t2, y vik el
tiempo de viaje entre la estación i y la interestación k, la demanda para una
interestación k entre los instantes t1 y t2 queda representada por la siguiente ecuación:
�� ��,� � ��� � �����������,������ �2.1�
La demanda por cada interestación es la desagregación máxima que se puede tener
por concepto de espacio.
• Sistema de pesaje
La metodología de Sistema de pesajes utiliza sensores eléctricos ubicados en ciertos
puntos de la red, capaces de identificar cada tren y estimar el peso de cada coche. La
ubicación de los sensores corresponde a donde se registra la demanda máxima. Con
este sistema se puede determinar la carga de los coches, estimando un peso promedio
por persona, y así calcular cuántas personas pasan por ese tramo.
Hay que notar que entre el sistema de Caldas y el de pesaje, existe una diferencia
conceptual en términos de lo que se mide, ya que el primero de ellos mide demanda
(demanda efectiva), mientras que el otro método mide carga (demanda estimada).
12
El sistema de Caldas se considera el más apropiado para trabajar en esta tesis, ya que
analiza en detalle, en cuanto a espacio, una estimación de la demanda efectiva por viajes
en la red.
Calidad de servicio
En cuanto a los estándares de calidad que se debe tener para ofrecer un servicio
adecuado, se debe establecer la densidad de pasajeros en los viajes y las restricciones de
intervalo máximo permitido en la frecuencia de operación de trenes. Esto reflejará cuánto
es lo máximo que un pasajero esperará por un tren en cualquier estación de la red. Ambos
parámetros deben ser trabajados dependiendo del día y del período horario.
Restricciones operativas generales
Las restricciones operativas generales que se deben considerar son las que manejan el
sistema de operación de los trenes en régimen normal. Éstas son las restricciones de
intervalos mínimos de salida entre trenes, la disponibilidad de éstos, el estado de las
cocheras para estacionar trenes, los tiempos de viaje entre estaciones y los tiempos de
maniobra en las estaciones terminales.
2.1.2.2 Generación de programas de circulación
Para la generación de los programas de circulación, actualmente se utiliza Hastus2, un
software canadiense que además se encarga de la programación de las últimas dos etapas
del proceso de planificación (tableros de presencia de conductores y rotación de
personal). Como datos de entrada para la programación, se necesita el número de trenes
y/o frecuencia por período horario. Este cálculo se realiza en base a los datos de demanda
(para la planificación agregada se utiliza Afluencia y para estimar demanda proyectada al
año, en el corto plazo, se utiliza Caldas y pesaje), y a los estándares de calidad de servicio
2 Gerencia de Operaciones, Metro S.A.
13
(densidad de pasajeros). Además se deben introducir otros parámetros propios de la
operación. Con todo esto se consigue una generación viaje a viaje de toda la jornada.
2.1.2.3 Generación de tableros de presencia de conductores
En esta etapa se debe programar y organizar las actividades que se desprenden del punto
anterior, a modo que sean factibles de ser realizadas por las personas que componen el
grupo de servicio de conducción. Para esto se deben considerar restricciones que son
propias de la actividad de conducción, las cuales reflejan la duración máxima de una
jornada de trabajo para un conductor y la cantidad máxima de horas consecutivas que
puede estar conduciendo.
2.1.2.4 Asignación de conductores y generación de rotaciones
El último paso, consiste en la determinación de las cargas de trabajo mensuales tanto de
conductores internos como de empresas externas, en base a los servicios definidos en la
etapa anterior (disponibilidad de conductores internos o de empresas externas).
Así es como finaliza la planificación del transporte público de trenes en Metro S.A. en
donde el principal resultado es la estimación en detalle de los recursos necesarios para
poder operar y ofrecer un servicio de alta calidad y eficiente, para un período de un año.
2.2 Programación de trenes
A continuación se describe el tercer paso de la planificación de transporte público de
trenes, que corresponde a la planificación de los horarios de los trenes.
Diversos autores han trabajado este tema, en el cual se centran en la creación de modelos
que permitan programar horarios de trenes para un período de tiempo determinado, el
cual se replica durante la jornada de operación. La base de muchos de estos problemas
14
viene del problema de programación de eventos periódicos, PESP (Periodic Event
Scheduling Problem). En éste se construye una programación para períodos de tiempo en
donde el último evento ocurrido en uno de los períodos programados se coordina
exactamente con el primer evento del período siguiente, conexión que permite la
extensión de la programación para el resto de la jornada.
La mayoría de los trabajos relacionados al PESP (Villumsen, 2006; Nielsen et al, 2006;
Lindner and Zimmermann, 2005), se basan en el paper de Serafini and Ukovic (1989), en
donde se introduce el PESP.
En este problema, un período de tiempo T y un conjunto de eventos V son dados. Los
eventos sólo ocurren dentro del período en consideración T. Estos eventos corresponden
a salidas y llegada de trenes a las estaciones, y el objetivo final es la programación de cada
uno de estos sucesos con el fin de optimizar una función objetivo dada.
Para modelar la conexión entre eventos, se introduce un conjunto de restricciones A. Cada
restricción (p,q) conecta un par de eventos con respecto a una cota superior e inferior,
l(p,q) y u(p,q) respectivamente. La idea es que para dos eventos, la diferencia entre el tiempo
t(p) para p y el tiempo t(q) para q debe ser al menos l(p,q) y a lo más u(p,q). La diferencia de
ocurrencia de los eventos es tomada por módulo T, de tal forma que sólo pueda tomar
valores entre 0 y T.
����� � �� � � ��!,"�# $%� & ' ��!,"� � ��!,"� �2.2�
Por lo general, la función que se desea minimizar es como la que se muestra a
continuación.
� (�!,"� � ����� � �� � � ��!,"�# $%� &�!,"�)* �2.3�
En la ecuación anterior c(p,q) representa el costo por unidad de tiempo asociado a los
eventos (p,q).
15
Otro modelo basado en el PESP, está orientado a la minimización de costos, tal como lo
hace Lindner and Zimmermann (2005), basado en el modelo planteado por Claessens et al
(1998). En el trabajo de Lindner and Zimmermann (2005) se consideran costos fijos por
período, por trenes y por coches (lo que incluye depreciación, costos de capital,
mantención y estacionamientos nocturnos), y costos variables (por distancia recorrida,
cantidad de trenes y coches utilizados).
El modelo considera un coso operacional dependiendo del tipo de tren que sea asignado a
cada línea, luego los autores proponen un problema de programación lineal mixto, donde
se busca el mínimo costo de operación para cada línea según el tipo de tren utilizado, de
un conjunto T de tipos de trenes disponibles para la operación (cuya principal diferencia
son las distintas velocidades que pueden alcanzar).
Las variables involucradas en el modelo son las siguientes:
,-,.,/: 1 si la línea 8 ) 9, utiliza tren tipo @ ) &- , con ( ) BЦ…ПF coches; 0 si no. �-,J� : instante de llegada de un tren de la línea 8, con dirección � a la estación M. �-,J� : instante de salida de un tren de la línea 8, con dirección � a la estación M. O: vector de enteros para las restricciones del �QR�. Aquí Tr denota el conjunto de trenes que pueden ser utilizados en la línea r є R, Ц es el
número mínimo de coches de un tren, П el máximo número de coches. La dirección u
puede ser 0 ó 1, correspondiendo respectivamente a las dos direcciones de cada línea. El
modelo de minimización de costos de programación horaria es el que se muestra en la
Figura 2.3.
La función objetivo planteada resume todos los costos involucrados en la operación. El
primer término representa los costos fijos, mientras que el segundo representa los costos
por kilómetro recorrido. Los parámetros utilizados son los siguientes:
tr,g: tiempo empleado en viajar de un extremo de la línea r al otro y volver, con un tren
tipo g.
16
S.T�U V S.T�UW: costo fijo por operar con tren tipo g y costo por coche respectivamente.
S. X V S. XW: costo por km. por operar con tren tipo g y costo por coche por km.
respectivamente.
YZ[� � �\�-,./^^&_ � �S.T�U ` ( � S.T�UW#,-,.,/ ` �- � �S. X ` ( � S. XW�,-,.,/П
/aЦ.)bc-)d
e. �. � � �f. � ( � ,-,.,/
П/aЦ.)bc-)d g [h i j ) Q
� �,-,.,/ � 1П/aЦ.)bc i 8 ) 9
� �k.�,�l � ,-,.,/П
/aЦ.)bc ' �-,J�l � �-,J� ' � �m.�,�l � ,-,.,/П
/aЦ.)bc i 8 ) 9, �M, Mn� ) 8; 8je�8o((oóp �QR�
,-,.,/ ) B0,1F i 8 ) 9, i@ ) &- , i ( ) BЦ…ПF �-,J� , �-,J� ) q
O, Mj(�%8 jp�j8%
Figura 2.3: Problema de programación de horarios a costo mínimo.
dr: largo (en kilómetros) de la línea r.
Kg: capacidad de un coche correspondiente a un tren tipo g.
Ne: capacidad mínima que debe ser ofrecida (se entiende como la demanda a abastecer).
k.�,�n y m.�,�n: cota inferior y superior respectivamente, del tiempo de viaje para ir de v a v’,
utilizando tren tipo g.
17
En el trabajo de Nielsen et al (2006), se describe un modelo de programación lineal entera
para la generación de horarios de trenes para una compañía de trenes Danesa.
El modelo toma como entrada el tiempo de viaje entre estaciones, los tiempo de
maniobra en cada estación terminal para que los trenes puedan dar la vuelta y los
patrones de los tiempos de parada en las estaciones para cada tipo de tren y línea. Los
costos de operación vienen dados según la programación horaria que se haga y son
proporcionales al número de trenes requeridos, luego el principal objetivo es la
programación de estos horarios con el fin de minimizar el número de trenes necesarios
para poder operar el horario generado.
Además, en el modelo se trabaja con la interacción de las líneas que tienen estaciones de
trasbordo, y entre las líneas que realizan viajes entre las mismas estaciones, pero sólo en
líneas paralelas.
Al modelo también se agregan restricciones sobre los intervalos de salida de los trenes y
para aquellos pasajeros que realizan combinaciones. El modelo se restringe para que los
pasajeros no esperen tiempos demasiado grandes por el tren de trasbordo.
En dicho trabajo también se utilizan nociones del PESP, para un período de 20 minutos.
Las principales variables de decisión del modelo son los instantes de salida de los trenes
de cada estación, y los tiempos de espera en cada estación terminal. Además, se considera
un tiempo de holgura (slack time) extra de espera en las estaciones en caso de ser
necesario, el cual también es una variable más de decisión del modelo.
En la función objetivo, como ya se mencionó, se busca la minimización del número de
trenes necesarios y además se introduce la minimización de estos tiempos de espera extra
considerados, es decir, se busca también que el tiempo de viaje entre estaciones sea el
mínimo.
El análisis de estos trabajos servirá para el desarrollo del primer modelo de esta tesis,
tema al cual se le deberán agregar características sobre la hora de cierre, esto es, la
18
decisión de comenzar a guardar trenes, tema que no ha sido estudiado por los autores
mencionados.
2.3 Coordinación de trasbordos
En esta sección se discute el problema de la coordinación que debe existir en el transporte
público tanto de trenes, sistema de buses o mixto. Este tema es de interés para el
desarrollo de la tesis ya que se debe realizar una coordinación para los últimos trenes que
salen desde las estaciones terminales, con el fin de que todos los pasajeros puedan
realizar las combinaciones que requieran para llegar a sus destinos.
El tema ha sido estudiado por varios autores, teniendo como objetivo común la
optimización de los sistemas de costos asociados (costos operacionales, costos por tiempo
de espera de los pasajeros y/o costos asociados a la calidad de servicio brindada)
2.3.1 Introducción a las transferencias
Dentro de las actividades de toda ciudad, la cantidad de rutas origen-destino demandadas
resulta cada vez más compleja de abastecer en forma directa con transporte público
(trenes o buses). Es por esto que para poder satisfacer la demanda, son necesarias las
transferencias, las cuales deben ser coordinadas con el propósito de cumplir con las rutas
demandadas.
Las transferencias en transporte público permiten una baja en los costos al hacer
interactuar dos sistemas, en vez de crear caminos directos para el gran número de rutas
demandadas.
En este ámbito se enfrentan dos típicos problemas (Knoppers and Muller, 1995): la
reducción del tiempo necesario para realizar la transferencia, y la reducción de la
probabilidad de perder una conexión.
19
Se podría pensar que existe una relación entre los tiempos de espera y la probabilidad de
perder una conexión, ya que perder una conexión se traduce en un mayor tiempo de
espera.
Para efectos de esta tesis, los tiempos necesarios para realizar combinaciones dentro de la
red se consideran fijos, pues la red se encuentra predeterminada y no se puede modificar,
luego bastaría con la disminución de la probabilidad (en particular llevándola a cero) que
un pasajero pierda una conexión, y así se estaría minimizando el tiempo de espera de los
pasajeros.
Por lo general, para realizar la coordinación de vehículos, éstos son programados para
encontrarse de tal forma que el primero de ellos que llega al lugar de combinación es
demorado (held), hasta la llegada del segundo vehículo.
Abkowitz et al (1987), trabaja con distintos escenarios para la realización de sincronización
y coordinación de transferencias. Entre ellos se destacan los que se mencionan a
continuación.
• Estrategia de detención simple: el vehículo en la línea de menor frecuencia es
detenido hasta que el vehículo en la línea de mayor frecuencia llega.
• Estrategia de detención doble: el vehículo que llega primero es detenido hasta que
el otro vehículo llega.
Por las características de la hora de operación de los trenes para esta tesis (en donde la
coordinación se trabaja para los últimos trenes), se cree conveniente utilizar la estrategia
de detención doble, bajo ciertas condiciones que serán descritas en el Capítulo 3, que
hacen referencia a la calidad de servicio establecida con los tiempos máximos permitidos
de espera de los pasajeros por los últimos trenes.
20
2.3.2 Costos asociados a los trasbordos
Algunos autores (Bookbinder, 1992; Hall, 2001), proponen minimizar una función de
costos con respecto a los usuarios en la que se involucran los tiempos de espera. La
coordinación de transferencias es entendida como una estrategia de programación de
horarios donde ciertos viajes son programados para encontrarse en un punto de
combinación (llamados puntos focales). Existen dos tópicos que pueden ser tratados en
relación a este problema. Uno de ellos es definir una función objetivo que sea capaz de
reflejar todos los inconvenientes de realizar transferencias bajo un horario de trenes
previamente establecido, y el segundo punto, es desarrollar un algoritmo para encontrar
un horario que permita minimizar una función objetivo.
Para comprender el planteamiento de la función objetivo propuesta se debe introducir
algunas definiciones.
Sea F (feeder) el tren que accede por la línea Lf, en el cual vienen pasajeros y desea realizar
una combinación en un punto focal. Sea C (critical), en Lr, el tren con el que F debiera
combinar. Sea N (next) un tren posterior a C, en Lr, que se llevará a los pasajeros de F si es
no pudieron irse en C por que llegaron después.
Figura 2.4: Representación de los trenes feeder, critical y next.
Además se definen los siguientes tiempos de llegada al punto focal para cada uno de los
trenes respectivamente tc, tn y tf, y se asume además que dichos tiempos pertenecen a un
intervalo finito acotado por [af, af + zf], [ac, ac + zr] y [an, an + zr] respectivamente. Estos
F
C N
21
intervalos son ventanas de tiempo, y donde z corresponde a la tasa de llegada (arrival
spread). Se puede notar que a corresponde al menor instante de llegada posible.
Con esto se puede definir una función w(·) la cual indica el tiempo de espera de los
pasajeros:
,��/ , �s , �T# � t �/ � �T eo �/ g �T�s � �T jp %�8% (�e%^ �2.4� Otro ejemplo donde se trabaja con política de demora de trenes, considera el caso donde
se cuenta con los tiempos de salida de los trenes desde el punto focal: dc, dn, df .
Luego si se dispone de los tiempos t y d, y se asume que los viajes se realizan
inmediatamente si es que éstos están atrasados, la función queda definida como sigue:
w ��/ , �s, �T# � w dx � ty si tx ' dx, ty ' dxtx � ty si tx z dx, tx g tyd{ � ty si ty z dx, ty z dx, t{ ' d{tx � ty en otro caso ̂ (2.5)
Una vez conocido el tiempo de espera de los pasajeros, es posible crear una función de
desutilidad la cual tenga como entrada este tiempo. Sea g la función de desutilidad, un
caso particular de esta función podría ser g(w)=w, dado que el tiempo de espera
representa un costo (no monetario) para los usuarios.
Sea D = E(g(w)), la esperanza del tiempo de espera, se puede demostrar (Bookbinder,
1992) que D queda completamente determinado por los valores de los parámetros af, ac,
zf y zr.
Hasta el momento la función de desutilidad encontrada mide el “costo” de un pasajero
sólo por realizar un trasbordo. Ahora se quiere encontrar una función que sea capaz de
juntar en ella todos los trasbordos para una programación de horarios de trenes conocida,
T.
22
Para esto, sean todos los posibles trasbordos k definidos para T, con k = {1, 2… M}. Luego
para cada trasbordo se tendrá una función Dk(T) que representa la esperanza del tiempo
de espera, por realizar el trasbordo k, bajo T. Además sea nk el flujo de la transferencia, es
decir, la cantidad de pasajeros que realiza el trasbordo. Con esto se puede definir la
siguiente función de costos:
S�&� � �p �&�| a} �2.6�
Con esta función dada, se podría encontrar la programación de horarios T, que minimice
dicha función de costos.
2.3.3 Restricciones sobre las ventanas de tiempo
Cuando un pasajero desea realizar un trasbordo, es decir, en una estación determinada
bajarse de un tren t y subirse a un tren t’, suponiendo que el tiempo que demora en
realizar esta acción va entre los 2 y 4 minutos, debe suceder que
dt’ – at ) [2,4]T �2.7� donde dt’ representa la salida del tren t’ desde la estación de trasbordo, at la llegada del
tren t a la estación, y [2,4]T la periodicidad. Luego un equivalente sería
��n � ��� ` ��$%� & � ) [2,4] �2.8�
Generalizando el modelo, como lo discute (Giesemann, 2002) basado en el PESP, la
restricción sobre la ventana de tiempo que debe existir entre la llegada de t y la salida de
t’ se podría representar de la siguiente forma:
�� � ��� ` ��$%� & � ) ����, ���� �2.9�
23
En la Ecuación 2.9 T є � es el período establecido por el horario de programación, y lij y uij
є � las cotas inferiores y superiores respectivamente, para el trasbordo de i a j. Además se
puede asumir que lij - uij є [0,T].
De lo anterior se puede apreciar que i, j son eventos que corresponden a las llegadas o
salidas de los trenes a la estación de trasbordo, y ti, tj las variables de decisión de
ocurrencia de los eventos.
Con esta información, se tiene una noción sobre el problema que se enfrenta en esta
tesis, en donde la principal decisión son los tiempos de ocurrencia de los eventos
asociados a los últimos trenes.
Los temas tratados en las secciones 2.2 y 2.3 recientemente expuestas, referentes a la
programación de trenes y la coordinación de trasbordos respectivamente, son los que
alimentan la creación de los modelos desarrollados en el siguiente capítulo, modelos que
intentan resolver la problemática planteada en esta tesis.
24
3. MODELACIÓN PROPUESTA
En el presente capítulo se describe los modelos realizados para la hora de cierre del
Metro, en donde la principal característica es la toma de decisiones en cuanto a los
instantes de salida de los últimos trenes y cómo cada tren se va guardando, hasta finalizar
la jornada.
Todo lo anterior debe ir respaldado por un conjunto de restricciones, tanto operativas, de
calidad de servicio y de consistencia del modelo, las que permiten que la toma de
decisiones este estructurada bajo ciertos patrones, pudiendo así llegar a soluciones reales
y por sobre todo aplicables a la red en cuestión.
A continuación se presenta el enfoque del problema a resolver, posteriormente se
presentan las formulaciones de los modelos planteados, y finalmente se establece la
forma en que ambos modelos son integrados.
3.1 Enfoque del problema
Se busca resolver el problema de la programación de viajes de trenes, cercana a la hora de
cierre de las estaciones, para cada una de las líneas que compone la red de Metro, y las
posteriores entradas de trenes a cochera. Para esto es necesario definir un modelo que
sea capaz de coordinar los horarios de salida de los trenes desde las estaciones
terminales, hasta la hora en que ninguno de ellos esté circulando. Además la formulación
deber ser capaz de resolver el problema que se presenta a la hora de cierre de puertas de
cada estación, hora en la cual se debe garantizar que cada pasajero que consiguió entrar a
la red sea capaz de llegar a su destino.
En base a estos dos problemas, se ha desarrollado dos modelos. El primero de ellos se
encarga de realizar una programación de horarios en forma independiente para cada
línea, en la cual se debe ir disminuyendo la frecuencia de salida de los trenes hasta que
todos estén estacionados en sus cocheras. El segundo problema enfrenta la coordinación
que debe existir entre los trenes de las distintas líneas para poder realizar los últimos
25
trasbordos después de la hora de cierre de las puertas de las estaciones de Metro.
Posteriormente, éstos deben ser integrados para poder obtener una solución final capaz
de dar respuesta al problema en conjunto.
Otra característica que distingue a los modelos es que en el primero de ellos se trabaja
con los tiempos de estacionamiento fijos para cada estación intermedia, por lo tanto el
tiempo que emplea un tren en ir desde un extremo de una línea al otro será conocido y
fijo. Éste es el Modelo de Salida de trenes con Tiempos Fijos (MSTF). En el segundo
modelo se podrá decidir cuánto permanecer estacionado en las estaciones intermedias de
la red, para así poder coordinar los trasbordos, luego el tiempo de viaje para una línea no
será conocido y dependerá de la decisión tomada. Este último, es llamado Modelo de
Salida de trenes con Tiempos Variables (MSTV).
La razón de lo anterior, es que trabajar con tiempos de estacionamientos distintos para los
últimos n trenes presenta complicaciones operativas para Metro, por lo que se decide
operar con los mismo tiempos de estacionamiento para un intervalo de tiempo dado, y
existe la posibilidad de modificar estos tiempos para el último tren de cada línea.
En las siguientes secciones se presenta en detalle cada uno de los modelos.
3.2 Modelo de Salida de trenes con Tiempos Fijos (MSTF)
En esta sección se describe cada una de las partes que componen el MSTF. A continuación
se muestra ciertas consideraciones y supuestos que se deben tomar en cuenta a la hora
de modelar el problema descrito.
• La modelación del problema es válida a partir de un cierto instante T, instante en el
cual todos los datos son conocidos. Esto incluye la cantidad de trenes en operación
en cada una de las líneas, la posición de cada uno de ellos, el instante en que
llegarán a la estación terminal a la cual se dirigen, y las capacidades efectivas de las
cocheras en ese instante.
26
• Sólo se trabajará con material rodante de configuración fija3. De esta forma no se
debe incurrir en los tiempos de enganche y desenganche de coches en las
estaciones terminales.
• No se realizarán operaciones bucle4. Esto principalmente por trabajar en un
período que no es horario punta.
• La maniobra realizada en las estaciones terminales para cambiar la dirección de los
trenes será de tipo ante-estación. Esto se debe a las restricciones sobre los trenes
que deben estacionarse en la misma estación, (ver Sección 3.2.4).
• Se define un instante Tm después de cual no se podrá seguir operando, después del
cual todos los trenes deben estar estacionados en sus cocheras. Este instante
dependerá de lo que demore el viaje en cada una de las líneas y de un instante Tc
que es el horario mínimo permitido para el cierre de puertas para el ingreso a las
estaciones.
Antes de comenzar a formular el problema se debe aclarar ciertas definiciones que serán
utilizadas en el transcurso del trabajo.
• Nodo: un nodo corresponde a un punto en la red representado por una estación,
ya sea terminal o no. Las acciones permitidas en un nodo son, la llegada de trenes
al nodo, estacionar trenes en el nodo por un intervalo de tiempo, y la salida de
trenes del nodo. Se entiende que cada una de estas acciones, para un mismo nodo,
deben realizarse en instantes de tiempo distintos, ya que por ejemplo, en el caso
de los nodos que representan estaciones no terminales, la capacidad de
estacionamiento en un sentido alcanza sólo para un tren. Esta consideración está
incluida dentro de las restricciones de intervalos mínimos de salidas entre trenes
consecutivos, la cual es explicada en mayor detalle en la Sección 3.2.4.
3 Esto es para los trenes que operan en la Línea 4, los cuales son de configuración variable, pero para este problema se utilizará un solo tipo de tren. 4 Corresponden a subcircuitos que se realizan en una línea. Válido para la línea 1, 2 y 5.
27
• Arco: un arco representa la unión de dos nodos en la red, es decir, representa el
tramo existente entre dos estaciones pertenecientes a una misma línea. Se
trabajará con tres tipos de arcos: arcos que comienzan en una estación terminal y
terminan en una estación terminal; arcos que comienzan en una estación terminal
y terminan en cualquier estación, y arcos que unen nodos consecutivos de la red.
A continuación se presenta todos los elementos que hacen posible el desarrollo del MSTF,
el cual determina las salidas de trenes bajo los supuestos mencionados anteriormente.
3.2.1 Conjuntos
A continuación se presenta los conjuntos con los que se trabaja en el MSTF:
• I: conjunto de estaciones terminales, i є I.
• P: conjunto de períodos, t є P.
• R: conjunto de divisiones de P, r є R.
• Tr: conjunto de períodos en r, tr є Tr
• K: conjunto de trenes en operación, k є K.
• A: conjunto de arcos, a є A.
El conjunto P de períodos t, es dividido en r intervalos, en donde en el intervalo r los
períodos son denotados por tr.
El conjunto de arcos definido para una línea corresponde al tercer tipo de arcos definido,
es decir, a cada uno de los tramos que conectan estaciones consecutivas de la línea en
cuestión.
28
3.2.2 Parámetros
Se definen los siguientes parámetros para el MSTF:
• T: instante de inicio de la operación.
• Tm: instante máximo de operación.
• h: número de trenes en operación en T.
• coi: 1 si la estación terminal i se utiliza como cochera; 0 si no.
• capi: capacidad de la cochera correspondiente a estación terminal i.
• mi: tiempo empleado en realizar la maniobra ante-estación en i.
• tminr: tiempo mínimo de salida entre trenes consecutivos permitido en r.
• tmaxr: tiempo máximo de salida entre trenes consecutivos permitido en r.
• tvi: tiempo de viaje si comienzo en estación terminal i, hasta la otra estación
terminal de la línea.
• tsia: tiempo de viaje desde la estación terminal i hasta el inicio del arco a.
• d: período de medición de la demanda.
• ddaiat: demanda por arco a, accediendo desde i entre t y t+d.
• capa: capacidad del tren.
Los parámetros tminr y tmaxr son crecientes en r, es decir, a medida que avanzan los
intervalos de tiempo, los tiempos mínimos entre salida de trenes consecutivos van
aumentando y el tiempo máximo permitido de espera de un pasajero por un tren también
lo hace a través del tiempo. Esto resulta necesario para poder disminuir la frecuencia de
salida de trenes.
Los parámetros de demanda se miden en intervalos de tiempo de d unidades, para cada
uno de los arcos de la red. Así el parámetro ddaat representa la demanda en el arco a (de
nodos consecutivos) entre los instantes de tiempo t y t+d.
29
Los tiempos de viaje tvi y tsi,a representan los tiempos empleados en viajar partiendo
desde la estación terminal i hasta el otro extremo de la línea, y hasta el inicio del arco a
respectivamente.
La capacidad de los trenes (capa) es fija por línea y no depende del tipo de tren, pues se
trabajará con configuración fija, luego como el modelo trabaja con las líneas en forma
independiente, el parámetro capa dependerá exclusivamente de cada caso particular.
3.2.3 Variables
Las variables para el modelo de salida de trenes son las siguientes:
• Xikt: 1 si el tren k inicia viaje en instante t en i; 0 si no.
• Yikt: 1 si el tren k se guarda en instante t en i; 0 si no.
• Wikt: 1 si el tren k está disponible en instante t en i; 0 si no.
Las tres variables utilizadas son binarias e indican la realización de ciertas actividades para
todo instante t. Las actividades representadas son la salida de trenes a operación, los
estacionamientos de trenes en sus cocheras y la disponibilidad de éstos en las estaciones
terminales para poder iniciar un nuevo viaje o ser enviado a cochera.
Tal como se muestra en la Figura 3.1, se puede concebir a priori una red espacio-temporal
donde se permita la ocurrencia de los tres eventos antes mencionados, y tratar el
problema como uno de flujo en redes (Vaidyanathan et al, 2007) al cual se le debe agregar
un serie de restricciones propias de la conservación de flujo, otras operacionales y otras
que reflejan la calidad de servicio del sistema.
30
Estación terminal 1 Estación terminal 2
espera viaje salida a cochera
Figura 3.1: Red espacio temporal de viajes en una línea.
3.2.4 Restricciones
Existe un gran número de consideraciones que se deben respetar a la hora de cierre del
Metro, además de los patrones de calidad de servicio que se quiere entregar a los
pasajeros. A continuación se describe cada una de ellas.
• Disponibilidad inicial de los trenes.
Como se mencionó en los supuestos asociados al problema, existe un cierto
instante T en el cual el modelo comienza a operar, instante en el cual la posición
de cada uno de los trenes que operan en la línea en cuestión es conocida.
Entonces, se puede establecer el instante de disponibilidad de los trenes en las
Tiempo
31
estaciones terminales a las que se dirigen, fijando los valores de las variables Wikt
en 1 para los instantes de tiempo correspondientes a cada tren.
En conjunto con esto se fija en 0 los valores de las variables Wikt para todo instante
t anterior al instante de disponibilidad de dicho tren en su próxima estación
terminal.
• Disponibilidad de un tren para realizar acciones.
Cada vez que se quiera tomar una decisión sobre un tren, tanto como para iniciar
un viaje como para guardarlo, éste sólo podrá realizar la acción si se encuentra
disponible en la estación terminal en la cual se está tomando la decisión, de lo
contrario el modelo reflejará que el tren no se encuentra en esa posición y por lo
tanto no se puede realizar las acciones (iniciar viaje o gurdarlo).
Además se debe asegurar que el modelo no tome decisiones simultáneas sobre un
mismo tren, es decir, si en el instante t decide iniciar un viaje, no puede además
tomar la decisión de guardarlo, por lo tanto al tratarse de variables binarias, la
suma de ellas para un mismo i, k, t deberá ser menor o igual a uno.
La restricción anterior se refleja en la siguiente ecuación.
�� � ` �� � ' �� � io, i�, i� �3.1�
De esta forma se asegura que la suma de las variables Xikt e Yikt sea menor o igual a
que el valor la variable de disposición Wikt (1 si está disponible y 0 si no)
• Desactivación de disponibilidad.
En conjunto con la restricción anterior, se agrega esta restricción la cual cambia el
estado de la variable Wikt cuando se realiza una acción en el instante anterior.
�1 � �� � � �� �# g �� ��} io, i�, i�: 1………&X � 1 �3.2�
32
La Ecuación 3.2 asegura que si se inicia un viaje con un tren o si éste es guardado,
la variable Wikt+1 tomará valor 0. Además hay que recordar que Xikt e Yikt no pueden
tomar valor 1 simultáneamente, por lo tanto el lado izquierdo de la ecuación
tendrá cota inferior y superior, 0 y 1 respectivamente, por lo que los valores para
Wikt+1 quedan bien definidos.
• Conservación de flujo.
Así como en la restricción anterior se puede cambiar el valor de la variable Wikt de
0 a 1, debe existir una restricción que sea capaz de activar el valor de dicha
variable, con la nueva disposición de trenes.
La Figura 3.2 representa el diagrama de conservación de flujo que debe existir para
este problema. Las estaciones i y j representan las estaciones terminales de una
línea. La flecha en verde (Xikt’) que sale de la estación i representa la salida del tren
k en el instante t’ y su llegada a la estación j en el instante t-1. La flecha en verde
(Wikt-1) en la estación j que va desde t-2 a t-1 representa la disponibilidad del tren k
en el instante t-1. Luego como un tren no se puede encontrar en dos lugares
simultáneamente, sólo una de estas dos acciones es posible (sólo una de las
flechas en verde).
Por otra parte las flechas en azul que salen de la estación j en t-1 (Xikt-1, Wikt, Yikt-1)
representan la salida del tren k desde j en dirección a i en t-1, la disponibilidad del
tren k en j en t y la salida del tren k a su cochera en t-1, respectivamente. Como los
trenes sólo pueden realizar una acción a la vez, sólo una de éstas es posible (sólo
una flecha en azul).
33
Estación i Estación j
t’
t-2
t-1
t
Figura 3.2: Diagrama de conservación de flujo.
Lo anterior se puede escribir analíticamente de la siguiente forma.
�� �l `�� ��} � �� � ` �� ��} ` �� ��} io, �, i�, i� �3.3�
En la ecuación (3.3), el término t’ es igual a (t-tvi-mj), es decir, que si la variable Xikt’
toma valor 1, significa que el tren k inicia un viaje desde i en t’ y por lo tanto estará
disponible en la estación j en el instante t, ya que tvi representa el tiempo
empleado en viajar desde la estación i a la otra estación de la línea, y mj el tiempo
empleado en realizar la maniobra ante-estación en la estación terminal j.
Esta ecuación representa al lado derecho la salida de un tren en el instante t’ o la
disposición de este tren en la estación terminal opuesta en t-1, de las cuales sólo
Xikt’
Wikt-1
Wikt
Xikt-1 Yikt-1
tvi + mj
Tiempo
34
una de ellas puede tomar valor 1, o ambas 0. El lado izquierdo de la ecuación
representa la disponibilidad del tren en el instante t, la realización de una salida de
la estación j en el instante anterior, o si el tren fue guardado en t-1. Al igual que al
otro lado de la ecuación, sólo una de estas tres variables puede tomar valor 1, o las
tres en conjunto el valor 0.
Hay que notar que la restricción planteada es válida para valores de t mayores a
tvi+mj (y mayores a tvj+mi en el caso de estar en la otra estación terminal). Se
podría pensar que las dos restricciones anteriores presentadas (Ecuaciones 3.1 y
3.2) podrían incluirse en esta última, pero esas dos restricciones son capaces de
hacerse cargo de los casos para valores de t entre 1 y tvi+mj (o entre 1 y tvj+mi), por
lo tanto se considera relevante utilizarlas en el modelo.
• Un tren es guardado hasta el día siguiente
Esta restricción refleja el instante en que un tren es guardado, instante después del
cual, el modelo no puede contar más con la disposición de ese tren, y por lo tanto,
tampoco seguir generando salidas con éste.
��� �b��a� ' Y�1 � �� �# io, i�, i� �3.4�
El lado izquierdo de la ecuación anterior representa todas las salidas posibles
generadas por el tren k a partir del instante t, luego si se decide guardar el tren k
(reflejado al lado derecho de la ecuación), todas las variables de salidas posibles
para el tren k en instantes posteriores a t deberán tomar valor 0. El parámetro M,
representa un número grande, que en este caso el valor que se le asigna, es la
máxima cantidad de viajes que puede realizar un tren saliendo desde la estación
terminal i, es decir, (Tm/tvi).
35
• No se guardan trenes simultáneamente en una misma estación
Se debe procurar que el modelo no decida guardar trenes simultáneamente5, de lo
contrario podrá generar soluciones factibles teóricamente pero que en la realidad
retrasarían todo el proceso.
��� � ' 1 io, i� �3.5�
Hasta el momento se ha definido sólo restricciones que tienen que ver con la consistencia
del modelo y la relación entre las variables de decisión. A continuación se muestra las
restricciones operativas del modelo que son específicas para el trabajo.
• Capacidad de las cocheras.
Cada una de las estaciones terminales tiene asociado un sector de
estacionamientos para los trenes que terminan sus viajes en tal estación. En
algunas estaciones, este sector corresponde a las mismas estaciones terminales y
en otras se puede asignar a un cochera que se ubica en algún tramo de la línea.
���� � �
�ab `��� � � (%� ' (� � io, i� �3.6�
En la Ecuación 3.6 se observa al lado derecho la capacidad de estacionamiento de
trenes del lugar asignado a la estación terminal i. Al lado izquierdo de la ecuación
se observa dos términos. El primero de ellos corresponde a la cantidad de trenes
que han sido estacionados en ese lugar hasta el instante t. El segundo término está
acompañado por el parámetro coi, parámetro binario que toma valor 1 si una
estación terminal es utilizada como lugar de estacionamiento de trenes, y 0 si los
5 Lo mismo para que no genere viajes simultáneamente, pero esa restricción queda contenida en los
intervalos mínimos de salida permitidos para trenes consecutivos.
36
trenes de esa estación son asignados a una cochera, luego para aquellas estaciones
donde el parámetro tome valor 1, la capacidad de la cochera será utilizada a la vez
por los trenes que se encuentren disponibles en la estación para, ya sea iniciar un
nuevo viaje o bien para ser guardados.
• Último tren estacionado.
Cuando un tren llega a una estación terminal, para poder cambiar la dirección del
viaje, debe realizar el cambio de dirección, para esto cuenta con dos tipos de
maniobra, ante- estación y tras-estación.
andén
andén
Figura 3.3: Maniobra tras-estación.
En la maniobra tras-estación mostrada en la Figura 3.3, una vez que el tren llega a
la estación, los pasajeros descienden en el andén, y en seguida el tren continúa en
la misma dirección para detenerse más adelante, en donde el chofer debe caminar
hasta el otro extremo del tren e iniciar un nuevo viaje pero esta vez en la otra
dirección y cambiando de vía las por medio de las líneas intermedias que conectan
los andenes.
La Figura 3.4 representa la maniobra ante-estación, en donde el cambio de vía se
produce antes del descenso de los pasajeros, los cuales deben bajar en el andén
opuesto.
37
andén
andén
Figura 3.4: Maniobra ante-estación.
Dentro de los supuestos que se plantean para abordar el problema, se estipula que
las maniobras que realizaran los trenes serán ante-estación, esto principalmente
por la condición que debe cumplir el último tren que se estaciona en una estación
terminal cuando coincide con el lugar de estacionamiento.
Esto hace referencia a que, una vez que se han ocupado todos los lugares de
estacionamientos en la estación, la operación se debe terminar, es decir, no
pueden volver a iniciarse viajes desde esa estación, ni tampoco pueden llegar
nuevos trenes pues no habrá espacio disponible para realizar cualquiera de las
maniobras.
Figura 3.5: Estacionamiento de trenes en una estación terminal
38
Luego, cuando quede sólo un espacio disponible en la estación terminal, si un tren
llega, éste sólo podrá realizar la maniobra ante-estación e iniciar su viaje hacia la
otra estación. De lo contrario si en el lugar que queda frente al andén se encuentra
un tren estacionado, no se podrán iniciar viajes posteriores porque el tren no
tendrá donde realizar la maniobra para viajar hacia la otra estación. La restricción
operativa se refleja en la siguiente ecuación.
���� �b��a� ' Y � �(� � � � �� ��
�a�} � ` Y � �1 � (%�� io, i� �3.7�
El lado izquierdo de la ecuación representa la salida de trenes de la estación. El
lado derecho de la ecuación sólo tomará valor 0 cuando la capacidad del lugar de
estacionamiento de trenes sea copada, y si además el parámetro coi toma valor 1,
de lo contrario, la condición para el último tren no será valida para aquellas
estaciones que tengan asignada una cochera.
En este caso el valor que toma M, es el mismo que en la Ecuación 3.4, que
corresponde a la cantidad máxima de viajes que se pueden realizar por un tren
dentro del período de tiempo a considerar.
• Todos los trenes deben guardarse.
Dentro de los parámetros del problema, se establece una hora máxima de
operación de los trenes, es decir, para todos los trenes se debe haber tomado la
decisión de guardarlos antes de ese instante.
����� �� � � � �3.8�
39
• Intervalos mínimos entre salidas de trenes consecutivos.
Existen dos razones por las cuales se debe establecer esta restricción. La primera
de ellas es por un tema operativo, ya que para que la red opere correctamente no
se puede mandar trenes desde una estación terminal en instantes de tiempo muy
cercanos pues, podrían encontrarse en alguna estación intermedia de la línea. La
segunda razón por la que se debe tener este tipo de restricción es porque se debe
tener intervalos de tiempo crecientes entre las salidas de trenes consecutivos, es
por eso que se ha dividido el período de operación en intervalos de tiempo r, en
los cuales los tiempos mínimos permitidos entre salidas de trenes consecutivos van
aumentando según r, parámetro que se expresa como tminr.
� � �� ��-��X�sc�}�a�- ' 1 io, i�8 �3.9�
La ecuación anterior evita que se genere más de un viaje dentro de un intervalo de
tiempo tminr para todo instante t perteneciente a un subconjunto tr.
Con esta restricción se concluye con las restricciones que hacen referencia a la parte
operativa del modelo, incluyendo en ellas consideraciones propias de la forma de operar
de Metro.
Las restricciones que faltan para completar el modelo, son las que reflejan la calidad de
servicio que se desea entregar a los pasajeros de Metro, esto es, la frecuencia de salida de
los viajes y la satisfacción de demanda.
• Intervalo máximo de espera por un tren.
Esta restricción es la que refleja la calidad de servicio que se ofrece. En ella se
establece el tiempo máximo permitido de espera de un pasajero por un tren, el
40
cual es creciente en el tiempo. Esto principalmente porque la demanda que se
enfrenta disminuye a medida que crece t.
� � �� ��-��X�Uc�}�a�- g 1 io, i�8 �3.10�
En la ecuación anterior se obliga al modelo a que en un intervalo tmaxr al menos se
realice un viaje. La restricción es valida para todo tr, y como se mencionó
anteriormente con tmaxr creciente en r.
• Satisfacción de demanda.
Se podría pensar que por tratarse de la hora de cierre del Metro esta restricción no
sea activa en el modelo, pero es necesario incluirla porque la hora de inicio de
operación para el modelo podría variar, e incluso extenderse a horas punta del día,
en donde sí serían de suma importancia.
���� � � (� �����a� g ����,�,�����,� i�, io, i� �3.11�
El lado izquierdo de la ecuación representa la oferta de transporte para todo
intervalo de largo d, mismo intervalo de tiempo en el cual es medida la demanda.
La ecuación representa que en cada intervalo de largo d debe salir la cantidad
suficiente de trenes, para que se haga cargo de la demanda que se espera en un
arco a, con el tiempo desviado en lo que se demora un tren partiendo desde una
estación terminal i al inicio del arco a. En el siguiente diagrama se representa
gráficamente la restricción.
41
Estación i Inicio Arco a
t+d
t+tsia
t+tsia+d
Figura 3.6: Diagrama de satisfacción de demanda.
En la Figura 3.6 se observa que la salida de trenes de la estación terminal i coincide
con la llegada de trenes al inicio del arco a, transcurrido el tiempo de viaje
correspondiente, luego la demanda observada en ese arco en (t+tsi,a), debe ser
satisfecha por la cantidad de trenes que salgan de i en t.
Con la restricción anterior se completan las restricciones para el MSTF, bajo las
condiciones estipuladas por el Metro de Santiago.
d
d
t +tsi,a
t
Tiempo
42
3.2.5 Función Objetivo
Existe un gran número de funciones objetivo a optimizar por la empresa que se podrían
utilizar para este modelo (Vega et al, 2002). En este caso la función objetivo escogida,
apuntará a la minimización de costos operacionales. Estos costos pueden expresarse de
distintas formas, ya sea por la cantidad de viajes realizados, los kilómetros recorridos o las
horas de conducción necesarias, entre otros.
Para este problema, y por la forma del modelo, se ha decidido minimizar la cantidad de
viajes realizados, lo cual haría que todos los trenes se guardaran en su disponibilidad
inmediata, si no fuese por las restricciones de intervalos máximos de espera por trenes, y
la restricción de satisfacción de demanda.
Luego la función objetivo asociada a este modelo, se presenta en la siguiente ecuación.
YZ[����� �� � �3.12�
Los valores entregados por esta función, sólo serán validos si se desea resolver un
problema para el secuenciamiento de estacionamientos de trenes en un terminal, pero no
entrega el resultado buscado por esta tesis, aún.
Al problema de le debe agregar restricciones adicionales que provienen de los resultados
del segundo modelo que se presenta. Al final del capítulo se muestra cómo es que los
modelos se integran para finalmente obtener el modelo definitivo.
3.3.6 Cuadro resumen del MSTF
La Figura 3.7 presenta un cuadro resumen del MSTF, con todas sus restricciones.
43
YZ[����� �� �
s.a �� � ` �� � ' �� � io, i�, i� �1 � �� � � �� �# g �� ,��} io, i�, i�: 1………&X � 1 �� �l `��, ,��} � �� � ` �� ,��} ` �� ,��} io, �, i�, i�
��� �b��a� ' Y�1 � �� �# io, i�, i�
��� � ' 1 io, i�
���� � �
�ab `��� � � (%� ' (� � io, i� ���� �b�
�a� ' Y � �(� � � � �� ���a�} � ` Y � �1 � (%�� io, i�
����� �� � � �
� � �� ��-��X�s-�}�a�- ' 1 io, i�8
� � �� ��-��X�U-�}�a�- g 1 io, i�8
���� � � (� ����a� g ����,�,�����,� i�, io, i�
�� �, �� �,�� � ) B0,1F io, i�, i� Figura 3.7: Modelo de Salida de trenes con Tiempos Fijos (MSTF).
Como se mencionó en la sección 3.2.4, las dos primeras restricciones que aparecen en el
cuadro resumen podrían omitirse dentro del modelo al estar incluidas en la tercera
44
restricción, pero como esta última no es válida para todo t, es necesario incorporarlas
para hacerse cargo del resto de los casos, fundamentalmente por la relación entre las
variables.
Así se finaliza con el primer modelo, donde el objetivo es minimizar la cantidad de trenes
utilizados para la hora de cierre de Metro, de tal forma de ir disminuyendo su frecuencia
de salida, satisfaciendo la demanda enfrentada en esa hora, hasta el instante en que todos
los trenes estén estacionados.
3.3 Modelo de Salida de trenes con Tiempos Variables (MSTV)
En esta sección se presenta el segundo modelo diseñado en esta tesis. El MSTV tiene
como objetivo identificar los horarios de salida de los últimos trenes de las estaciones
terminales, pudiendo decidir el tiempo que permanece estacionado en estaciones
intermedias para así lograr la coordinación de los trasbordos posibles con otros trenes.
Con esto se busca que cada pasajero que consiguió entrar a la red, sea capaz de llegar a su
destino, a través de al menos una ruta.
Los supuestos planteados para la generación de este modelo son los siguientes:
• Sólo se manejará el tiempo de estacionamiento en las estaciones de combinación,
sin alterar aquel utilizado en el otro modelo para las estaciones intermedias que no
corresponden a estaciones terminales ni de combinación.
• Se establecerá un tiempo mínimo y máximo de estacionamiento permitido en las
estaciones de combinación, por razones operativas y de calidad de servicio
respectivamente.
• Se considera un tiempo de trasbordo conocido en las estaciones de combinación,
el cual considera el tiempo desde que un pasajero se baja de un tren hasta que
llega al andén en donde tomará el siguiente tren.
45
• Se realizará un solo viaje por cada línea en cada dirección, tratando de maximizar
la cantidad de alimentaciones de un tren a otro, para lograr la mayor cantidad de
rutas realizables a la hora de cierre con los trenes disponibles.
• En caso que un tren no pueda combinar con otro en una estación de combinación,
se realizará un viaje extraordinario por la línea que debe recoger a los pasajeros
que esperan del otro tren.
Además se considera una serie de características que debe cumplir la red bajo estudio.
Éstas son:
• Cada estación que sea capaz de realizar una combinación de líneas, sólo conectará
dos de ellas en ese punto, es decir, no existen combinaciones de tres o más líneas
en un mismo punto.
• Si dos líneas pueden realizar combinación entre ellas, éstas lo realizarán en una
sola estación.
• Una línea no necesariamente se conecta con todas las demás, pero al menos lo
hace con otras dos.
• Para cualquier par de nodos de la red, el número de combinaciones necesarias
para llegar de uno a otro es a lo sumo dos.
Estas características se cumplen para la red del Metro de Santiago, en su estado
Diciembre, 2007 (ver Anexos 1).
Las definiciones utilizadas en este modelo son similares en algunos aspectos al modelo
anterior, pero es necesario aclarar sus diferencias:
• Nodos: para este modelo los nodos quedan representados sólo por estaciones de
combinación de la red, y por estaciones terminales.
• Arco: un arco quedará determinado por la unión de dos nodos consecutivos de la
red, notando que cada arco puede contener un conjunto de estaciones
intermedias.
46
A continuación se presenta todos los elementos que hacen posible la creación del modelo.
3.3.1 Conjuntos
A continuación se presenta los conjuntos con los que se trabaja en el MSTV:
• I: conjunto de direcciones de llegada a todas las estaciones de combinación de la
red, i є I.
• ady: conjunto de pares (i,j) adyacentes de la red, (i,j) є ady, i,j є I.
• com: conjunto de pares (i,j) factibles de combinación, (i,j) є com, i,j є I.
• doub: conjunto de rutas de doble combinación, C є doub.
• K: conjunto de líneas de la red, k є K.
• Rk: conjunto de subíndices i que pertenecen a la línea k, i є I, k є K.
• ext: conjunto de subíndices i, que corresponden al primer elemento de cada línea.
El subíndice i representa básicamente las distintas formas para acceder a una estación de
combinación. Por ejemplo como se muestra en la Figura 3.8, para la combinación
realizada en Los Héroes por las líneas 1 y 2, existirán 4 posibles llegadas a este punto,
arribando desde La Moneda, República, Santa Ana y Toesca respectivamente.
Luego de la estación de combinación Los Héroes, se desprenden 4 elementos del conjunto
I: {Los Héroes llegando por La Moneda, Los Héroes llegando por Toesca, Los Héroes
llegando por República, Los Héroes llegando por Santa Ana}
47
Figura 3.8: Combinación Estación Los Héroes.
El conjunto ady es un subconjunto de pares (i,j), donde i y j pertenecen a I, y son
direcciones de llegada a estaciones de combinación adyacentes en la red (sin considerar
estaciones intermedias que no corresponden a estaciones de combinación). Por ejemplo
en la Figura 3.8 sea i = Los Héroes llegando por Toesca y j = Santa Ana llegando por Los
Héroes, entonces el par (i,j) pertenece al conjunto ady.
El conjunto com es un subconjunto de pares (i,j), donde i y j son direcciones de llegada a
una misma estación de combinación de la red provenientes de distintas líneas. Por
ejemplo, en la Figura 3.8 sea i = Los Héroes llegando por Toesca, j = Los Héroes llegando
por La Moneda y r = Los Héroes llegando por República, los pares (i,j) y (i,r) pertenecen al
conjunto com, pero el par (j,r) no pertenece.
El conjunto doub está formado por las etiquetas de rutas distintas que requieren dos
combinaciones para ir de un nodo a otro. En la Figura 3.9 se representa la red de Metro,
en la cual se puede observar que, por ejemplo, un par (i,j) donde i pertenezca a la línea 4 y
j pertenezca a la línea 2, la ruta que los unirá requiere dos combinaciones. Se observa que
se puede generar 3 rutas distintas realizando la primera combinación con la línea 1, la
línea 5 o la línea 4A.
REPUBLICA
TOESCA LA MONEDA
48
Figura 3.9: Red del Metro de Santiago.
El conjunto K está compuesto por todas las líneas de la red, diferenciando entre aquellas
que tienen sentidos opuestos. Por ejemplo para la línea 4, se distingue entre la línea con
dirección Sur y la con dirección Norte.
Los conjuntos Rk están conformados por subconjuntos de I, donde cada i є I, pertenece a
la línea k. Por ejemplo, para la línea 4 con dirección al Norte, el conjunto está formado por
los tres arribos a las estaciones de combinación con dirección al Norte.
3.3.2 Parámetros
A continuación se definen los siguientes parámetros para el MSTV
• emin: intervalo de tiempo mínimo de estacionamiento.
• emax: intervalo de tiempo máximo permitido de estacionamiento.
• tvij: tiempo de viaje desde la salida de i a la llegada de j.
49
• tcij: tiempo que un pasajero emplea en realizar una combinación desde la llegada
de i a j.
• Tmax: instante máximo permitido de la salida de trenes desde sus estaciones
terminales.
• tei: tiempo de viaje empleado en ir desde una estación terminal hasta la llegada a
la estación de combinación i más cercana de la misma línea.
• Tentrada: tiempo empleado por un pasajero en ir desde la puerta de entrada de una
estación hasta el andén.
El parámetro emin, representará el tiempo mínimo que por motivos operacionales, un
tren debe permanecer estacionado para que los pasajeros puedan descender y abordar al
tren.
El parámetro emax, reflejará la calidad de servicio que se desea brindar a los pasajeros, en
cuanto al tiempo de espera en tren. Los pasajeros no estarán detenidos en una estación
de combinación un tiempo superior a emax.
Los tiempos de viaje tvij entre estaciones de combinación serán fijos, y los tiempos de
combinación tcij serán tomados como el máximo tiempo que un persona demora en
realizar una combinación. El tiempo Tentrada, se considera como el máximo empleado por
un pasajero en llegar al andén.
3.3.3 Variables
Las variables utilizadas en el MSTV son las siguientes:
• Xij: 1 si el tren que llega en i puede realizar combinación con el tren de j; 0 si no.
• Yi: 1 si se requiere un viaje extra que pase por i; 0 si no.
• Li: instante de llegada del último tren a i.
• Si: instante de salida del último tren de i.
• Qk: 1 si pasa tren extra por línea k; 0 si no.
50
La variable Xij es una variable binaria que representa la factibilidad de una combinación, es
decir tomará valor 1 si los pasajeros que abordaban en el tren que llegó a i, pueden
realizar la combinación hacia el tren que llegó a j, siempre y cuando (i,j) pertenezca a un
conjunto factible de pares de combinación, es decir, (i,j) є com, y tomará valor 0 en el caso
que el tren que llego a j, se haya iniciado su viaje antes de la llegada del tren a i.
La variable Yi representa los viajes extras que se deben realizar cuando no es posible
realizar un combinación, es decir, si la variable Xij toma valor 0 para (i,j) є com, significa
que aún hay pasajeros que llagaron a i que no han podido realizar combinación con el tren
que llega a j, luego se deberá realizar un viaje extra que llegue a j. En este caso, la variable
Yj tomará valor 1.
Por otra parte las variables Li y Si representan los instantes de llegada y salida de un tren
en una estación de combinación i, permitiendo calcular con ellos el intervalo de tiempo
que un tren permanece estacionado.
La variable Qk, lo que hace es reunir a todos los trenes extras que se decide enviar por una
misma línea k en un solo tren. Es decir, si para una línea k hay dos variables Yi que valen 1,
la variable Qk tomará valor 1 y sólo enviará un tren por esa línea y no dos.
3.3.4 Restricciones
Las restricciones del modelo deben representar básicamente las relaciones mencionadas
anteriormente, más un conjunto de restricciones operativas del modelo.
• Tiempos de viaje.
Se debe establecer que para cualquier par de estaciones de combinación
adyacentes en la red, el tiempo de viaje es fijo y conocido, luego se debe cumplir la
siguiente relación: R� ` �M�� � k� i �o, �� ) ��V �3.13�
51
En donde por razones de consistencia de la ecuación, el par (i,j) debe pertenecer al
conjunto de los pares adyacentes de la red.
• Tiempo mínimo de estacionamiento.
Debe existir un tiempo mínimo de estacionamiento en las estaciones para que
todo pasajero sea capaz de descender de un tren, y abordarlo quienes lo deseen.
La ecuación que contiene esta restricción es la siguiente:
k� ` j$op ' R� i o �3.14�
• Tiempo máximo de estacionamiento.
Esta restricción refleja la calidad de servicio que se desea brindar a los pasajeros,
fijando una cota superior al tiempo de estacionamiento de los trenes en las
estaciones. La restricción está dada por la siguiente ecuación:
k� ` j$�� g R� io �3.15�
• Combinación de un tren a otro.
Como se mencionó en la sección 3.3.3 la variable Xij tomará valor 1 en aquellos
casos en que los pasajeros que vienen de i, pueden realizar la combinación con el
tren que llegó a j. Esta acción sólo tendrá sentido cuando la salida del tren que
llegó a j ocurra después de la llegada del tren a i más el tiempo que demoran los
pasajeros en realizar la combinación, tal como se muestra en el diagrama espacio-
temporal de la Figura 3.10.
Tal representación queda expresada en la siguiente ecuación:
��� � Y g R� � �k� ` �(��# i �o, �� ) (%$ �3.16�
52
En la ecuación, M representa un número lo suficientemente grande como para
superar un instante de salida de cualquier tren a la hora de cierre, que puede
representarse por la diferencia de los parámetros Tm y T del MSTF.
Además, hay que notar que los pares (i,j) que participan en esta restricción son
sólo aquellos que pertenecen al conjunto com, que representa los pares factibles
que realizan alguna combinación en la red.
estación i-1 estación combinación estación j-1
i j
Tiempo de combinación
Tiempo de estacionamiento
línea k línea k’
Figura 3.10: Combinación de un tren a otro.
Analizando la Ecuación 3.16, se observa que el valor de la variable Xij quedará
fijado en 1 cuando el lado derecho de la ecuación tome valor positivo, en otro caso
el valor de dicha variable no queda determinado, por lo tanto se requiere una
ecuación extra para determinar el caso opuesto.
53
• Combinación de trenes infactible.
La siguiente ecuación representa el caso contrario al mostrado en la restricción
anterior, y es cuando no es posible realizar una combinación desde i a j, es decir
cuando el tiempo de salida de j ocurre antes de la llegada de i más el tiempo de
combinación. ��� � Y ' R� � �k� ` �(��# ` Y i�o, �� ) (%$ �3.17�
En este caso, la diferencia R� � �k� ` �(��# tomará un valor negativo, luego la
variable Xij deberá tomar valor 0, para conservar la desigualdad de la ecuación.
Claramente el par (i,j) también debe pertenecer al conjunto de combinaciones
factibles de la red.
• Tren extra.
El modelo debe asegurar que dada la hora de cierre de las puertas de las
estaciones, un pasajero que entró a la estación pueda realizar cualquier viaje en la
red desde un nodo a otro. Para esto debe existir un tren que sea capaz de llevarse
a cualquier usuario desde un lugar al que llegó a hacer combinación hasta
cualquier otro. En caso que el pasajero no pueda realizar la combinación necesaria
debido a que el tren en cuestión ya pasó por esa estación, será necesaria la
asignación de un nuevo tren que pase por ese punto para llevarse a los pasajeros
que esperan ahí.
��� g 1 � �� i�o, �� ) (%$ �3.18�
Como se muestra en la Ecuación 3.18, en caso que los pasajeros que llegaron a i no
puedan realizar la combinación a j, deberá existir un tren que pase por j para poder
llevarse más tarde a estos pasajeros.
Al igual que en las restricciones anteriores, el par (i,j) debe pertenecer a los pares
factibles de combinaciones en la red.
54
• Todas las rutas factibles.
Con las restricciones descritas hasta ahora, todo pasajero puede abordar un tren y
realizar una combinación si lo estima necesario para poder llegar a su destino. Pero
existe un grupo de pares origen-destino que necesitan realizar dos combinaciones
para poder llegar a su destino.
Sea A la línea en donde se encuentra el origen y B la línea donde se encuentra el
destino, y las líneas A y B no tienen punto de combinación entre ellas, a partir de
los supuestos y las características de la red, habrá al menos dos líneas con las que
la línea A puede realizar combinación. Sean C1 y C2 líneas que combinan con A y
además combinan con B, luego el pasajero que entró a A y desea ir a una estación
en B podrá optar por ir de A a C1 y de C1 a B, o de A a C2 y de C2 a B, realizando
dos combinaciones en cada caso.
Lo que pretende este modelo es que el pasajero llegue a la estación ubicada en B
al menos por una de las posibles rutas que posee, es decir, que una de ellas sea
factible. Luego, para que eso se cumpla, bajo las características de este modelo, es
necesario que el tren que se necesita tomar para pasar de A a C1 o de A a C2 no
sea un tren extra. Si se cumple lo anterior, por una de las rutas estará realizando la
primera combinación con los primeros trenes, y la segunda combinación vuelve al
problema de sólo una combinación, la cual puede ser realizada o no con un tren
extra.
Lo descrito aquí se escribe matemáticamente de la siguiente forma:
� ���,�� ) W ' |S| � 1 i S ) �%�� �3.19�
En la ecuación anterior, los conjuntos C representan todos los conjuntos de
variables Yi, para aquellos pares origen-destino que requieren dos combinaciones,
donde Yi representa el tren extra que se debe o no tomar en la primera
55
combinación. Luego si al menos uno de esos trenes no existe, habrá una ruta
factible para el par origen-destino del conjunto C.
• Unión de trenes extras en una misma línea
Un tren extra es necesario en una línea k cuando al menos una de las
combinaciones que usa esa línea lo requiera. De esta forma la salida de un tren
extra se ve forzada por las variables Yi.
� g �� i�, io ) 9 �3.20�
Luego si alguna de las variables Yi tomara valor 1, inmediatamente la variable Qk,
tomaría el mismo valor, independientemente de la cantidad de variables Yi que lo
hagan. En caso de que ninguna de las variables Yi tome valor 1, la variable Qk se
verá forzada a tomar valor 0. Esto se explicará mejor en la Sección 3.3.5.
• Tiempo máximo permitido de la salida de trenes
La resolución de este problema podría entregar muchas soluciones en donde se
respeten todas las restricciones planteadas, pero hasta el momento no se le ha
pedido al modelo que los valores de la solución estén dentro de un tiempo máximo
permitido de operación. Es por esto que las salidas de los últimos trenes desde sus
estaciones terminales deben estar acotadas por un cierto instante, el cual
determinará lo más tarde que un tren puede iniciar un viaje. Analíticamente,
k� � �j� ' &$�� io ) j�� �3.21�
• Instante mínimo permitido para la salida de trenes
56
La restricción anterior no asegura un acotamiento inferior de los tiempos de salida
de los trenes, incluso éstos podría tomar valores negativos y la restricción seguiría
siendo válida. Para dar solución a esto se debe establecer un instante a partir del
cual puedan comenzar a salir estos últimos trenes. En este modelo, el instante t=0
corresponde al horario mínimo permitido para el cierre de puertas, luego
considerando que un pasajero consiguió entrar a la red en ese instante, demorará
un tiempo conocido (Tentrada) en llegar al andén. De esta forma Tentrada
corresponderá al mínimo instante en que un tren podrá iniciar un viaje desde una
estación terminal (comenzando en un instante t=0). Analíticamente,
&hs�-��� ' k� � �j� io ) j�� �3.22�
3.3.5 Función Objetivo
Al igual que en el MSTF, lo que se busca es cumplir con ciertas restricciones incurriendo en
el mínimo costo posible, lo que se traduce en el número mínimo de trenes que se deben
sacar a circulación para cumplir con las exigencias requeridas. En este modelo se trabaja
con el último tren de cada una de las líneas, tren que debe existir para cada línea, por lo
tanto lo que se querrá minimizar es el número de viajes extra que se debe realizar para
poder efectuar las combinaciones posibles en la red. Luego la función objetivo para este
modelo queda representada como sigue.
YZ[ �� �3.23�
Como se planteó en una de las restricciones al estar minimizando la suma de las variables
Qk, en la Ecuación 3.20 cuando todas la variables Yi toman valor cero, la función objetivo
obliga a que el valor de la variable Qk sea 0.
57
3.3.6 Cuadro resumen del MSTV
A continuación se presenta un cuadro resumen del MSTV. YZ[ ����
s.a R� ` �M�� � k� i �o, �� ) ��V k� ` j$op ' R� i o ) Z k� ` j$�� g R� i o ) Z ��� � Y g R� � �k� ` �(��# i �o, �� ) (%$ ��� � Y ' R� � �k� ` �(��# ` Y i�o, �� ) (%$ ��� g 1 � �� i�o, �� ) (%$
� ���,�� ) W ' |S| � 1 i S ) �%��
� g �� i�, io ) 9 �� � �j� ' &$�� io ) j�� &hs�-��� ' �� � �j� io ) j�� ��� ) B0,1F io, � �� ) B0,1F io k� , R� g 0 io Figura 3.11: Modelo de Salida de trenes con Tiempos Variables (MSTV).
Los resultados que se obtienen de este modelo son de suma importancia para el resultado
final buscado por esta tesis. Estos resultados serán utilizados en la formulación del MSTF
tal como se explica en la siguiente sección, donde se finaliza el capítulo con la integración
de los modelos.
58
3.4 Integración de los modelos
En esta sección se explica cómo se realiza la integración de ambos modelos. A partir de la
solución del MSTV, se incorpora nuevas restricciones al MSTF, para así completar el
objetivo de esta tesis.
Como se mencionó, el MSTV a diferencia del MSTF trabaja con todas las líneas de la red en
forma conjunta ajustando los tiempos de salidas de trenes para poder realizar los
trasbordos necesarios a la hora de cierre. Por lo tanto, de los resultados del MSTV se
espera una programación de horarios para los últimos trenes y además para los trenes
extras que sea necesario utilizar.
Estos resultados deben ser llevados al MSTF para cada una de las líneas, identificando en
ellas los instantes de salida desde las estaciones terminales del último tren y del tren extra
si es que existiese.
Los instantes de salida de los últimos trenes desde las estaciones terminales obtenidos
con el MSTV tomarán valores entre Tentrada y Tmax. La forma en que estos valores se
convierten a valores del MSTF es la que se describe a continuación.
3.4.1 Conversión de resultados del MSTV al MSTF
En el MSTV se establece un parámetro Tmax, el cual indica el horario máximo permitido
de salida de los últimos trenes desde sus estaciones terminales. Lo mismo sucede con
Tentrada que condiciona el instante mínimo de salida. Luego, los valores obtenidos en el
MSTV para (li- tei) estarán en el intervalo [Tentrada, Tmax], donde li corresponde a la llegada
de un tren a la primera estación de combinación de una línea k, con i є k, y tei corresponde
al tiempo de viaje entre la estación terminal desde la que sale el tren y la primera estación
de combinación a la que llega.
Por otra parte, en el MSTF se establece un tiempo Te el cual indica el horario mínimo de
cierre de puertas de las estaciones. A partir de este instante se puede conocer el instante
59
mínimo de salida de un último tren desde una estación terminal, el cual está dado por (Te
+ Tentrada) donde Tentrada corresponde al tiempo empleado por un pasajero en ir desde la
entrada de la estación hasta el andén.
Luego, el mínimo instante de salida de un tren desde su estación terminal generado por el
MSTV (li- tei) entre todas las líneas, corresponderá al instante (Te + tentrada) en el MSTF.
El mínimo de los (li- tei) en el MSTV será fijado como el instante inicial de salida de los
últimos trenes (Te + Tentrada) y se podrá recalcular los (li- tei) para cada una de las líneas,
para llevarlos al MSTF.
La misma transformación se debe hacer para los tiempos de salida desde las estaciones
terminales para los trenes extras que son requeridos.
3.4.2 Nuevas restricciones del MSTF
Una vez conocidos los tiempos de salida de los últimos trenes y de los trenes extras desde
las estaciones terminales, el paso siguiente es imponer en el modelo que en esos instantes
de tiempo se debe generar un viaje. Analíticamente, para una estación �� y un tiempo �� ,
��¡� �� � 1 �3.24�
La restricción anterior es válida tanto para los últimos trenes como para los trenes extras.
Además, sean tultimo y textra los tiempos de salida para el último tren y el extra desde una
estación terminal, el intervalo de tiempo r = [tultimo , textra] quedará fuera de la restricción
de intervalo máximo de salida de trenes consecutivos.
Por último el parámetro Tm, parámetro del MSTF que indica el instante de tiempo
después del cual no deben quedar trenes en circulación, corresponderá al máximo (textra +
tvi), entre las dos estaciones terminales de la línea, que corresponde al instante de salida
60
del tren extra más el tiempo empleado en llegar al otro extremo de la línea. En caso de no
ser necesario un tren extra, Tm = max {tultimo + tvi}
En resumen, los pasos a seguir para la obtención del resultado final son los siguientes:
1. Resolución del MSTV.
2. Obtención del mínimo de los (li- tei) entre todas las líneas.
3. Fijar el valor anterior en (Te + Tentrada) y transformar los valores (li- tei) para cada
una de las líneas.
4. Imponer en el MSTF que para algún k la variable Xikt tome valor 1 en los
instantes de tiempo calculados en el paso anterior, para la estación terminal
correspondiente.
5. En caso de haber tren extra, excluir el intervalo de tiempo entre la salida del
último tren y el extra de la restricción de intervalo máximo.
6. Fijar el valor de Tm como el máximo instante de salida de un tren más el
tiempo que utiliza en el viaje.
7. Resolver el MSTF.
Así, se da por finalizada la construcción de los modelos que resuelven la problemática
presentada en esta tesis. En el siguiente capítulo se detalla la resolución de los modelos,
mostrando los resultados obtenidos, aplicados a la red de Metro.
61
4. APLICACIÓN DE LOS MODELOS
En el presente capítulo, se presenta y analiza los resultados obtenidos con los modelos
planteados.
Se comenzará mostrando los tamaños de las instancias a trabajar, luego los resultados de
cada modelo y su integración.
Para finalizar el capítulo se realiza un análisis sobre las soluciones obtenidas, basadas
principalmente en los tiempos de espera de los usuarios. Se concluye con una
comparación de la solución obtenida con la forma actual que utiliza Metro en su
operación.
4.1 Tamaño de las instancias
Se puede determinar el tamaño de los modelos en términos de la cantidad de variables y
restricciones que éstos poseen. A continuación se observa el detalle de cada uno de ellos.
4.1.1 Tamaño del MSTF
Variables Cantidad
Xikt |I|·|K|·|P|
Yikt |I|·|K|·|P|
Wikt |I|·|K|·|P| Tabla 4.1: Cantidad de variables del MSTF.
Restricciones Cantidad
Disponibilidad inicial |K|
Disponibilidad de un tren |I|·|K|·|P|
Desactivación de disponibilidad |I|·|K|·(|P|-1)
Conservación de flujo |I|·|K|·(|P|-tv-m)
Un tren se guarda hasta el día siguiente |I|·|K|·|P|
No se guardan trenes simultáneamente |I|·|P|
Capacidad de las cocheras |I|·|P|
Último tren estacionado |I|·|P|
Todos los trenes deben guardarse 1
62
Intervalo mínimo |I|·|P|
Intervalo máximo |I|·|P|
Satisfacción de demanda |I|·|A|·|P| Tabla 4.2: Cantidad de restricciones del MSTF.
Analizando la instancia para la Línea 1 de la red actual de Metro, los tamaños de los
conjuntos son los siguientes:
• |I| = 2 (estaciones terminales)
• |K| = 22 (trenes en operación)
• |P| = 170 (períodos en cuestión)
• |A| = 23 (arcos de la línea)
Luego, la cantidad de variables binarias del modelo es de 7.480. En cuanto a las
restricciones, se tiene un total de 37.923 restricciones.
4.1.2 Tamaño del MSTV
Variables Cantidad
Xij |I|·|I|
Yi |I|
Li |I|
Si |I|
Qk |K| Tabla 4.3: Cantidad de variables del MSTV
Restricciones Cantidad
Tiempos de viaje |ady|
Estacionamiento mínimo |I|
Estacionamiento máximo |I|
Combinación de trenes |com|
No combinación de trenes |com|
Tren extra |com|
Caminos factibles |doub|
Unión de trenes |K|
Tiempo máximo de salida |ext| Tabla 4.4: Cantidad de restricciones del MSTV.
Tomando la instancia en cuestión, los tamaños de los conjuntos son los siguientes:
63
• |I| = 28 (distintas llegadas a estaciones de combinación)
• |ady| = 18 (pares de estaciones de combinación adyacentes en la red)
• |com| = 40 (pares del conjunto I que poseen combinaciones factibles)
• |doub| = 6 (rutas que requieren dos combinaciones)
• |K|=10 (cantidad de líneas en la red)
• |ext|=10 (subconjunto de I que contiene los i más próximos a cada una de las
estaciones termianles)
De los datos anteriores, el modelo cuenta con un total de 878 variables y 220
restricciones. Se observa que el problema es pequeño en cuanto a cantidad de variables y
restricciones, esto principalmente se debe a la previa eliminación de restricciones y
variables que de antemano se sabía que tomaban valores cero, o que no eran factibles
dentro del modelo. Esto se pudo realizar con la incorporación de varios de los conjuntos
que corresponden a subconjuntos de otros.
4.2 Resolución de los modelos
Los problemas modelados fueron programados en el compilador algebraico GAMS 21.7, y
los modelos fueron resueltos utilizando el solver MIP en CPLEX 9.0. Este paquete de
optimización matemática, contiene un conjunto variado de algoritmos para resolver
diversos tipos de problemas de programación matemática. Para encontrar soluciones
enteras realiza un Branch and Bound, hasta llegar a una solución factible entera dentro del
rango de aceptación dado por el GAP relativo entre la solución entera encontrada y la
mejor de las cotas encontradas en el Branch and Bound, que es por default de un 10%, o
bien, hasta que se acaben sus ramas. El GAP relativo utilizado en la resolución de los
modelos fue cambiado y fijado en un 0%.
En Anexos 2, se encuentra un listado de la notación utilizada para cada estación de la red,
para un mejor entendimiento de los resultados expuestos.
64
4.2.1 Resolución del MSTV
Antes de reportar los resultados obtenidos con el MSTV se presentan los principales
parámetros (y supuestos sobre éstos) utilizados para la resolución del modelo.
4.2.1.1 Parámetros del MSTV
La red actual del Metro de Santiago está compuesta por 5 líneas, luego el conjunto de
líneas planteado para este modelo posee 10 elementos, los cuales se desprenden de las
dos posibles direcciones que puede tomar cada una de las líneas de Metro.
Las estaciones de combinación de la red son 7, y hay cuatro formas de llegar o salir de
cada una ellas, luego el conjunto de llegadas a estaciones de combinación i є I, tendrá 28
elementos. Dichos elementos se presentan en la Figura 4.1. Tal como se muestra en ella,
por ejemplo, la estación de combinación encerrada en el círculo, posee 4 distintas formas
de llegar a ella con i = {9, 10, 11, 12}.
La unidad con que se trabajaron los tiempos fue de 10 segundos. Luego todos los
parámetros y los resultados obtenidos que sean de tiempo se encuentran en esa unidad.
Además, el instante t=0 queda establecido como el instante mínimo de cierre de puertas,
23:00 hrs.
Los valores para los tiempos de estacionamiento mínimo (emin) y máximo (emax) son 2 y
20 respectivamente.
Los valores para los tiempos de combinación entre líneas en una estación terminal (tcij)
fueron todos fijados en 21. El valor del parámetro Tentrada es 18.
En la Tabla 4.5 se presentan los tiempos de viaje entre las estaciones de combinación (tvij
con (i,j) є ady).
En la Tabla 4.6 se presentan los tiempo utilizados en ir desde las estaciones terminales
hasta la primera estación de combinación (i є ext).
65
1 3
Con respecto al parámetro Tmax, que corresponde al instante después del cual todos los
últimos trenes deben haber iniciado su viaje desde las estaciones terminales, el modelo se
hizo correr en base a distintos valores de éste, tal como se detalla más adelante en este
capítulo.
Figura 4.1: Llegadas a las estaciones de combinación.
2 4
5 7
6 8
13 26
15 14
24
16
17 25
20 18
19 27
23 21
22 28
9 11
12 10
66
Dirección i Dirección j Tiempo de viaje tvij
1 7 9
7 16 111
25 8 107
8 4 7
5 9 35
9 13 37
14 10 39
10 6 35
1 11 27
11 23 109
28 12 106
12 2 27
26 18 116
18 21 6
22 19 7
19 15 120
24 20 52
27 17 52 Tabla 4.5: Tiempos de viaje entre estaciones de combinación.
Dirección i Tiempo de viaje tei
1 21
3 83
5 77
14 24
22 78
24 0
25 0
26 0
27 0
28 0 Tabla 4.6: Tiempos de viaje desde las estaciones terminales a las de combinación.
67
4.2.1.2 Resultados del MSTV
La función objetivo de este modelo es minimizar el número de trenes extras que se
necesitan para poder realizar los trasbordos necesarios a la hora de cierre. Para
determinar este número, se trabajó en base a distintos valores de sus parámetros.
Como se explicó en el capítulo anterior, si no fuera por el parámetro Tmax, el problema
podría entregar distintas soluciones con una misma función objetivo. Es por esto que el
problema debe ser acotado con respecto al horario de la salida de trenes, es decir, según
Tmax se define el instante máximo permitido para la salida del último tren desde cada
estación terminal de la red.
En base a los distintos resultados obtenidos se logró identificar tres valores de Tmax en
donde la función objetivo cambiaba de valor. En la Tabla 4.7 se presenta los resultados
obtenidos de acuerdo a los valores de Tmax.
Valores de Tmax Número de Trenes Extras
315 6
326 5
407 4 Tabla 4.7: Número de trenes extras c/r a Tmax.
Para todos los valores de Tmax por debajo de 315, el problema es infactible. Esta
infactibilidad se debe principalmente a la restricción presentada en la Ecuación 3.19 del
capítulo anterior, para la generación de rutas que requieren doble combinación. De lo
contrario en el peor de los casos, el problema hubiese entregado trenes extras para cada
una de las líneas definidas para el MSTV, según fuese necesario.
Para todos los valores incluidos en el intervalo [315,326[, la función objetivo es la misma y
la cantidad de trenes extras requeridos resulta ser 6.
Para los valores incluidos en el intervalo [326,407[, el valor de la función objetivo
corresponde a 5 trenes extras.
68
Para los valores mayores o iguales a 407, el valor fue siempre el mismo y corresponde a 4
trenes extras.
Los parámetros Tmax fueron elegidos como los mínimos valores dentro de cada intervalo
donde la función objetivo era la misma, esto porque para distintos valores de Tmax dentro
de un mismo intervalo, las variables de salida de los trenes se iban ajustando a estos
valores máximos permitidos, con esto se permiten salidas más tardías de trenes, lo que se
traduce en mayores tiempos de espera para los pasajeros. Luego tomando los mínimos
Tmax de cada intervalo, se asegura que los trenes están saliendo de las estaciones
terminales tan pronto como sea necesario.
A partir de los datos de Tmax v/s la cantidad de trenes necesarios, se puede realizar un
análisis del trade-off existente entre la calidad de servicio brindada vs los costos asociados
a la operación. Esto se discute en la Sección 4.3.
A partir de los resultados dados por los distintos Tmax, los horarios establecidos para los
últimos trenes están dados por las variables Si y Li del modelo, y los horarios de los trenes
extras que deben iniciar viaje desde las estaciones terminales quedan determinados según
las llegadas de trenes que necesitan realizar trasbordo con el tren extra. Esto es, sea k la
línea que requiere tren extra, se busca el máximo de los Lj (instante de llegada con
dirección j), con j cualquier llegada tal que (i,j) є com, con i є k, más el tiempo de trasbordo
requerido para ir de j a i, tcji, más el tiempo de viaje desde la estación terminal hasta i.
Así, los horarios de salida desde cada estación terminal de los últimos trenes y de los
trenes extra, según el parámetro Tmax, son los mostrados en las Tablas 4.8 y 4.9
respectivamente.
69
Línea Estación Tmax = 315 Tmax = 326 Tmax = 407
L1 EM 107 77 77
SP 24 24 24
L2 VN 18 18 18
LC 101 101 101
L4 TO 178 178 235
PPA 209 201 301
L4A VM 315 315 407
LC 234 226 298
L5 QN 103 81 199
VV 101 326 398 Tabla 4.8: Instantes de salida de los últimos trenes de las estaciones terminales.
Línea Estación Tmax = 315 Tmax = 326 Tmax = 407
L1 EM 444 436 525
SP 315 361 433
L2 VN 176 419 491
LC 408 408 500
L4 TO - - -
PPA - - -
L4A VM - - -
LC - - -
L5 QN 219 219 -
VV 354 - - Tabla 4.9: Instantes de salida de los trenes extra desde la estaciones terminales.
Se aprecia que los valores mostrados en la Tabla 4.8 están en el intervalo establecido
[Tentrada, Tmax], tomando en los tres casos los valores extremos para la salida desde alguna
estación terminal.
En cuanto a los tiempos de estacionamiento de los últimos trenes, éstos toman valores
entre 2 y 20. El modelo sólo permite decidir estos tiempos en las estaciones de
combinación de la red, adquiriendo el valor mínimo cuando el tren en cuestión no espera
ningún otro tren para realizar trasbordo. En caso de esperar a algún tren que proviene de
otra línea, utiliza el tiempo mínimo requerido con el cual es capaz de esperar al tren de la
otra línea más el tiempo que un pasajero demora en realizar el trasbordo.
70
Con respecto a los tiempos de estacionamiento de los trenes extras, se utilizó el tiempo
mínimo establecido, 2. Esto se debe a que cuando estos trenes pasan, los pasajeros que
los deben abordar ya estarán esperando por ellos, luego ese tiempo sólo permite la subida
de pasajeros y no la espera de la llegada de los pasajeros al tren.
Estos trenes son los que permitirán establecer los tiempos de espera de los pasajeros, ya
que los trenes anteriores estarán cumpliendo las restricciones de intervalos máximos de
salida establecidas en el MSTF. Esos resultados se analizarán en la Sección 4.3.
4.2.2 Resolución del MSTF
Como se mencionó anteriormente, este modelo trabaja con las líneas de la red en forma
independiente. Los parámetros presentados corresponden sólo a la Línea 1 de la red
actual de Metro, no así los resultados obtenidos que se presentan en conjunto para toda
la red.
Además hay que recordar que este modelo utiliza resultados del MSTV para poder llegar a
los resultados finales.
4.2.2.1 Parámetros del MSTF
El MSTF comienza a operar desde las 22:00 hrs. Para poder establecer la ubicación de los
trenes y con esto su disponibilidad en las estaciones terminales, los datos son extraídos
del Programa de Circulación de Metro. En éste se detalla la salida de cada uno de los
trenes bajo la forma actual de operación desde el inicio de actividades hasta la hora de
cierre. Con la información contenida en este programa se puede conocer cual fue el
último viaje que inició cada tren que continúa en operación previo a la hora en que
comienza a operar el modelo.
71
Así, se puede fijar los valores de las variables de disponibilidad de los trenes en 0 hasta el
instante anterior en que los trenes se encuentren disponibles en las estaciones terminales
correspondientes, y cuando el tren ha llegado la variable de disponibilidad toma valor 1.
En el caso de la Línea 1, a las 22:00 hrs. se encuentran 22 trenes en operación.
La unidad de tiempo con la que trabaja este modelo es de 60 segundos. Esta decisión fue
en base a la capacidad de resolución de los problemas, y por las unidades de los
parámetros de demanda trabajados que están dados en múltiplos de 60 segundos.
En la Tabla 4.10 se muestran los períodos t en los cuales las variables de disponibilidad
toman valor 1. Esta es la principal entrada del modelo.
Estación SAN PABLO (SP)
Instante 1 3 6 9 12 15 18 21 24 27 30 33
Estación ESCUELA MILITAR (EM)
Instante 1 4 7 11 14 17 21 24 27 31
Tabla 4.10: Disponibilidad inicial de los trenes en las estaciones terminales.
Con respecto a las cocheras, ambas estaciones terminales funcionan como cocheras y
además se cuenta con una cochera intermedia ubicada a un costado de la estación
Neptuno. De preferencia conviene que los trenes que se estacionan en ese lugar
provengan de la estación terminal San Pablo dada su cercanía. En caso de no ser factible,
se asignará trenes que provengan desde la otra estación terminal, Escuela Militar. Los
parámetros anteriores (coi y capi), los tiempos de viaje empleados en ir desde una
estación terminal a la otra (tvi), y los tiempos empleados en realizar la maniobra en las
estaciones terminales (mi) se muestran en la Tabla 4.11.
72
Parámetros EM (i=1) SP (i=2)
Co 1 1
Cap 5 14
Tv 30 31
M 3 3
Tabla 4.11: Parámetros co, cap, tv y m.
La Línea 1 posee un total de 24 estaciones, luego el conjunto A (arcos entre
interestaciones) tiene 23 elementos. Para cada uno de estos arcos se calculó el tiempo
que demora un tren desde la estación terminal hasta el inicio del arco.
Los períodos fueron divididos en tres intervalos de tiempo. De acuerdo a estos intervalos
los tiempos mínimos y máximos permitidos entre trenes consecutivos, continuando el
crecimiento establecido por los datos de entrada, son los mostrados en la Tabla 4.12.
R tmin Tmax
1 4 5
2 6 8
3 8 12
Tabla 4.12: Tiempos mínimos y máximos entre trenes consecutivos.
En la Línea 1 operan actualmente 7 tipos de trenes conformando un total de 40 trenes
para la operación, de los cuales 22 estarán en funcionamiento después de las 22:00 hrs.
Sus capacidades varían según el tipo de tren y la cantidad de coches que éstos posean. Es
por esto que se trabaja con una capacidad promedio de 1262 personas por tren.
73
Los datos de demanda con los que se trabaja son los datos que se tienen por cada
interestación de la red. Estos datos de obtienen a través de las “Caldas” que corresponden
a estimaciones de la demanda por tren cada 15 minutos en cada una de las
interestaciones de la red. Los gráficos que se presentan a continuación muestran como es
el comportamiento de la demanda a lo largo de la Línea 1 en sus dos direcciones.
Figura 4.2: Gráfico de la demanda en Línea 1 dirección SP-EM.
Figura 4.3: Gráfico de la demanda en Línea 1 dirección EM-SP.
74
De los resultados obtenidos del MSTV, se tiene que para la Línea 1, los datos utilizados en
el MSTF para los instantes de salida de los últimos trenes y de los trenes extra (según el
parámetro Tmax del MSTV) son los mostrados en la Tabla 4.13.
L1 Estación Tmax = 315 Tmax = 326 Tmax = 407
Último EM 77 72 72
SP 64 64 64
Extra EM 134 132 147
SP 112 120 132
Tabla 4.13: Instantes de salida de los últimos trenes y de los trenes extra.
Estos resultados están transformados según la unidad de medida del MSTF y ajustados
para que las 22:00 hrs. corresponda a t=0.
4.2.2.2 Resultados del MSTF
Los resultados mostrados del MSTV permiten agregar las restricciones adicionales al
MSTF, obteniendo los siguientes valores para la función objetivo del problema.
El número de viajes mostrados en la Tabla 4.14 son los que ocurren en el intervalo de
tiempo entre las 22:00 hrs y el máximo valor tomado por el último viaje programado, ya
sea de tren extra o no.
75
Línea Tmax = 315 Tmax =326 Tmax = 407
L1 27 27 27
L2 24 24 24
L4 23 23 25
L4A 27 27 33
L5 25 31 33
Total 126 132 142
Tabla 4.14: Cantidad de viajes por línea.
En cuanto a la frecuencia de salida de los trenes, se obtuvo un comportamiento creciente
en sus intervalos de salida.
Los datos extraídos del Programa de Circulación hasta las 22:00 hrs, tenían un intervalo de
salida de 3 minutos. Los resultados arrojados por el modelo, adquieren intervalos en
forma creciente de 5, 7, 8 y 12 minutos respectivamente, intervalos de tiempo dentro de
las cotas permitidas por Metro.
La relajación del problema, entrega como resultado una solución con variables enteras,
entregando el mismo valor de la función objetivo con el problema no relajado.
4.3 Análisis y experimentos
4.3.1 Horarios de salida
De los resultados obtenidos del MSTV se observa en la Tabla 4.7 que mientras más tarde
se permite la salida de los últimos trenes, menor es la cantidad de trenes extras
necesarios para poder realizar los trasbordos a la hora de cierre.
Por otra parte, al trabajar con los datos obtenidos del MSTV en el MSTF se observa que la
cantidad de viajes totales aumenta al permitir que la salida de los últimos trenes sea más
76
tarde. La razón de esto es que el modelo se ve obligado, por las restricciones de intervalo
máximo, a poner trenes entre viajes establecidos (en este caso entre el último tren y los
viajes anteriores). Luego, la disminución de trenes extras en el MSTV (2 trenes) no se
compensa con la gran diferencia de viajes necesarios que se desprenden del MTSF (16
trenes).
A partir del resultado anterior, el posible trade-off entre calidad de servicio y costos,
asociado al tiempo de espera vs cantidad de trenes, que se desprende el MSTV, se anula al
compararlo con los resultados del MSTF, en donde en conjunto se obtiene un menor
tiempo de espera de los pasajeros por el último tren y además la minimización del número
de viajes realizados (minimización de costos operacionales). A partir de esto se tiene que
el parámetro a utilizar como Tmax queda fijo en 315, lo que en hora real equivale a las
11:52:30 hrs., (los pasajeros que entran a la estación que cierra más tarde sus puertas
toman el tren en ese instante de tiempo).
Así los instantes de salida en hora real para los últimos trenes y los trenes extra desde
cada una de las estaciones terminales son los que se muestran en la Tabla 4.15.
Línea Estación Último Extra
L1 EM 11:17:50 12:14:00
SP 11:04:00 11:52:30
L2 VN 11:03:00 11:29:20
LC 11:16:50 12:08:00
L4 TO 11:29:40 -
PPA 11:34:50 -
L4A VM 11:52:30 -
LC 11:39:00 -
L5 QN 11:17:10 11:36:30
VV 11:16:50 11:59:00 Tabla 4.15: Horarios de salida de los últimos trenes y los trenes extra.
Además se realizó un análisis en cuanto a la variación de los tiempos de estacionamiento
de los trenes en las estaciones de combinación para el MSTV. El tiempo permitido de la
77
solución actual es de 200 segundos de estacionamiento. Ante variaciones del parámetro
emax, se presentan diferencias significativas para valores muy elevados de éste, que se
escapa de lo planteado por Metro en cuanto al tiempo de estacionamiento (entre 4 ó 5
minutos como máximo). El número mínimo de trenes extra que se necesitaría para poder
generar todas las rutas, bajo las características de la red en cuestión, es 3 con un tiempo
de estacionamiento máximo permitido de casi 40 minutos (utilizando el mismo
Tmax=315).
emax [seg] cantidad de trenes extras
0-190 infactible
200-300 6
310-980 5
990-2320 4
2330- 3 Tabla 4.16: Cantidad de trenes extra c/r a emax.
Dados estos valores se mantiene el valor de emax en 200 segundos y el estacionamiento
mínimo emin en 20 segundos, tiempo necesario para que los pasajeros puedan descender
y abordar los trenes.
4.3.2 Generación de rutas
Con los horarios establecidos para los últimos trenes y los trenes extras, se busca que
cada pasajero que tomó el último tren pueda llegar a cualquier punto de la red, pudiendo
realizar los trasbordos requeridos. El modelo asegura que al menos existirá una ruta para
cualquier par origen-destino de estaciones de la red.
Los pares origen-destino, según las características de la red, son clasificados en tres
grupos: aquellos pares que no requieren realizar trasbordos (se encuentran en una misma
línea), aquellos que requieren un trasbordo (estaciones que pertenecen a líneas que se
78
conectan en una estación de combinación), y aquellos que requieren de dos trasbordos
(estaciones pertenecientes a líneas que no tienen estación de combinación).
Para el primer grupo, la ruta queda establecida por la línea en la que se encuentran ambas
estaciones. Para estas rutas se utiliza el último tren.
Para aquellos pares que requieren de un trasbordo, la ruta queda establecida mediante la
utilización de ese único trasbordo, es decir, desde la estación de origen a la estación de
combinación, y desde ésta a la estación de destino. Para estas rutas el tren que se toma
en la estación de origen corresponde al último tren, y el tren con el que combina para
pasar a la línea donde se encuentra la estación de destino, puede ser último o extra.
Para aquellos pares que requieren dos combinaciones se establecen rutas específicas las
cuales aseguran encontrar trenes de trasbordo en ambos puntos de combinación. Las
rutas que conectan dos puntos de la red pueden ser variadas, pero para la hora de cierre
no se podrán realizar todas ellas. Es por esto que las rutas para llegar desde cualquier par
origen-destino que requiera de dos trasbordos (en donde se comience con el último tren)
deben ser como sigue:
Figura 4.4: Rutas L1-L4-L4A y L5-L4-L4A.
79
Figura 4.5: Rutas L2-L4A-L4 y L4-L4A-L2.
Figura 4.6: Rutas L4A-L4-L1 y L4A-L4-L5.
• L1(último tren) – L4(último tren) – L4A(último tren)
• L5 (último tren)– L4(último tren) – L4A(último tren)
• L2 (último tren)– L4A(último tren) – L4(último tren)
• L4 (último tren)– L4A(último tren) – L2(tren extra)
80
• L4A (último tren)– L4(último tren) – L1(tren extra)
• L4A (último tren)– L4(último tren) – L5(tren extra)
Estas secuencias de trenes son las que deben ser las utilizadas para viajar en la red
después de la hora de cierre de puertas, asegurando que cada pasajero llegue a su
destino.
Se observa que la línea 4 y 4A son las más utilizadas. Esto se debe a que son aquellas que
operan hasta más tarde sin la utilización de trenes extras, por lo que favorece que los
trasbordos de la hora de cierre se realicen con los últimos trenes y no con los extras, como
se indica en el modelo.
La generación de estas rutas nace a partir del MSTV a través de la restricción que se
establece en la Ecuación 3.19 en donde para cada par origen-destino que requiere de dos
combinaciones, de todas las rutas posibles al modelo se le exige que por lo menos exista
una factible.
4.3.3 Tiempos de espera
Dados los horarios de trenes para la hora de cierre y las rutas a seguir por los pasajeros se
puede analizar los tiempos de espera de éstos.
Para el primer grupo de nodos (los que pertenecen a una misma línea), el tiempo de
espera por los trenes será el tiempo que demora en pasar el último tren. Estos tiempos
quedan acotados por los parámetros utilizados en las restricciones de intervalo máximo
del MSTF.
En la Tabla 4.17 se muestran los resultados obtenidos del MSTF para los tiempos de
espera por los últimos trenes (en [seg]).
81
L1 L2 L4 L4A L5
EM SP VN LC TO PPA VM LC QN VV
480 720 480 480 720 720 480 720 540 600
Tabla 4.17: Tiempos de espera por último tren.
El segundo grupo de nodos (aquellos que requieren de un trasbordo) se puede dividir en
dos: aquellos que realizan trasbordo con un último tren o aquellos que lo hacen con un
tren extra. Quienes combinan con un último tren, al igual que en el caso anterior los
tiempos de espera de ambos trenes están dados por las restricciones de intervalo
máximo, y dependiendo de la dirección que toman en el trasbordo los tiempos de espera
serán los mostrados en la Tabla 4.17. Para quienes combinan con un tren extra, los
tiempos de espera del primer tren son los de la Tabla 4.17 y los tiempos de espera por los
trenes extras (en [seg]) en las estaciones de combinación, utilizando la notación del
conjunto I mostrada en la Figura 4.1, son los de la Tabla 4.18.
De la Tabla 4.18 se observa, por ejemplo, que el tren extra que sale desde la estación
terminal Quinta Normal (QM) está siendo esperado en dos partes de la red i = {4, 10}. Para
los pasajeros de i=4, el tiempo de espera es cero y para los pasajeros de i=10, el tiempo de
espera es de 520 segundos (8 minutos 40 segundos).
Los tiempos de espera de los trenes que provienen de las estaciones terminales Quinta
Normal (QN) y Vespucio Norte (VN) se consideran razonables, ya que están dentro del
rango de aceptación establecido por la condiciones de intervalos máximos. Por el
contrario, se observa que para las otras estaciones de donde provienen trenes extras, los
tiempos de espera de algunos pasajeros que desean hacer el trasbordo superan los 2000
segundos (más de 30 minutos de espera).
82
QN VN EM
I Te I te i te
4 0 2 0 12 2790
10 520 6 220 15 0
SP LC VV
I te I te i Te
7 2590 17 0 21 0
8 1290 6 2670 22 460
11 2370 2 2650 10 2490
12 1990 4 2490
15 0
Tabla 4.18: Tiempos de espera por trenes extra.
Para la disminución de esos largos tiempos de espera se proponen 2 alternativas:
utilización de trenes intermedios u operación normal hasta trenes extra. Estas alternativas
de describen a continuación.
Utilización de trenes intermedios
Se puede disminuir el tiempo de espera de algunos pasajeros utilizando un tren
intermedio (entre el último tren y el tren extra) que beneficie a los grupos de pasajeros
que más esperan para realizar un trasbordo. De los resultados mostrados en la Tabla 4.18
se podría iniciar viajes con trenes intermedios desde las estaciones terminales EM, SP, LC y
VV beneficiado así a ciertos grupos de pasajeros que presentaban tiempos de espera por
el tren extra muy elevados. Con esto, los tiempos de espera de estos pasajeros se verán
disminuidos, entregando una calidad de servicio adecuada.
83
Los tiempos de salida de estos nuevos trenes deben seguir cumpliendo las restricciones de
capacidad y de intervalos fijados en el MSTF. Luego, el tiempo de salida fue calculado de
tal forma que los pasajeros que llegan entre la salida del último tren y el tren extra,
quienes esperaran más del tiempo máximo establecido (emax) por el tren extra, se suban
al tren intermedio, que se llevará a todos los que se encuentren esperando. En la Figura
4.7 se ilustra la explicación anterior.
último tren tren intermedio tren extra
emin emax
tiempo
llegada de pasajeros
Figura 4.7: Incorporación de trenes intermedios.
Con estos nuevos trenes los tiempos de espera (en [seg]) para los pasajeros quedan como
se muestra en la Tabla 4.19.
84
SP =85 LC = 86 EM = 87 VV = 86
i te I Te i te i te
7 980 6 410 12 700 10 760
8 0 2 380 4 760
11 760
12 590
Tabla 4.19: Tiempos de espera con trenes intermedios.
La incorporación de estos trenes intermedios permite la reducción de los tiempos de
espera entre un 62% y un 100%. De no ser por las restricciones de intervalo mínimo del
MSTF, se podría haber hecho reducciones de tiempo para todas las líneas en un 100% en
al menos una estación.
Con esta solución, la cantidad de viajes en total que se deben realizar en toda la red sube
de 126 a 130.
Operación normal hasta trenes extra
Esta solución transforma los trenes extra en últimos trenes, es decir el MSTF se hace
correr fijando los horarios de los extras como últimos viajes sujeto a todas las restricciones
que se establecen en este. Operando de esta forma, se debe indicar a los pasajeros cual es
el último tren con el que pueden hacer combinaciones para llegar a cada uno de los
destinos de la red, tren que queda determinado por el tren que realiza un viaje en el
horario más próximo (por debajo) del horario establecido anteriormente para el último
tren.
Haciendo correr el MSTF en base a lo anterior, la solución entregada corresponde a un
total de 153 viajes. Con esto se asegura que los tiempos de espera de los usuarios no sean
superiores a los parámetros establecidos para intervalos máximos.
85
1 3
Para aquellos pares de nodos que necesitan dos trasbordos, se presenta en detalle el
seguimiento de la ruta. Para esto, la red ha sido dividida en tramos tal como se muestra
en la Figura 4.8.
Figura 4.8: Tramos de la red.
Las Tablas que se presentan a continuación muestran los tiempos de espera (te), tiempos
de viaje (tv) y tiempos de espera en tren (tet) para cada una de las rutas señaladas en la
sección anterior (todos en [seg]).
a b c d
e
f
g
h
i
j
k
l m
n
86
L1-L4-L4A
origen te tv tet te tv tet te tv tet destino
a 720 1490 40 0
1160 0 0 520 0 h b 720 720 20 0
c 720 370 0 0
d 480 240 0 470 Tabla 4.20: Tiempos en ruta L1-L4-L4A.
L5-L4-L4A
origen te tv tet te tv tet te tv tet destino
l 540 1570 260
0 70 0 0 520 0 h m 540 1360 6
n 540 1090 0 Tabla 4.21: Tiempos en ruta L5-L4-L4A.
L2-L4A-L4
origen te tv tet te tv tet te tv tet destino
i 480 1110 0
0 520 0
0 1200 0 e
j 480 1200 100 0 60 0 f
l 480 2030 120 0 870 20 g Tabla 4.22: Tiempos en ruta L2-L4A-L4.
L4-L4A-L2
origen te tv tet te tv tet te tv tet destino
e 720 1160 0
0 520 0
0 1070 0 i
f 720 70 0 0 1140 20 j
g 720 850 200 0 1960 40 l Tabla 4.23: Tiempos en ruta L4-L4A-L2.
L4A-L4-L1
origen te tv tet te tv tet te tv tet destino
h 720 520 0 0 1200 0
0 1000 40 a
0 740 20 b
0 390 0 c
0 210 0 d Tabla 4.24: Tiempos en ruta L4A-L4-L1.
87
L4A-L4-L5
origen te tv tet te tv tet te tv tet destino
h 720 520 0 0 60 0
0 1060 0 n
0 1330 20 m
0 1520 40 l Tabla 4.25: Tiempos en ruta L4A-L4-L5.
De las tablas anteriores, se puede observar que los tiempos de espera que aparecen en la
segunda columna son los que un pasajero debe esperar por el último tren que proviene de
esa línea en dirección a la estación de combinación.
Los tiempos de espera para realizar los trasbordos (quinta y octava columnas)
correspondientes a trenes extras o últimos son todos cero, menos uno que debe esperar
470 segundos (7 minutos, 50 segundos) tiempo que está dentro del rango de aceptación.
En cuanto a los tiempos de espera en tren, son exactamente los establecidos como el
estacionamiento mínimo que realiza un tren equivalente a 20 segundos en cada estación
de combinación.
Del análisis de los 3 tipos de pares origen-destino, se puede concluir que los tiempos de
espera que deberían ser modificados son sólo aquellos en los que incurren los pasajeros
que realizan una combinación y éstos corresponden a trasbordos con trenes extras. Con la
utilización de los trenes intermedios se logra una solución mejor que con la extensión de
la operación hasta la hora de salida de los trenes extras (una diferencia de 20 viajes entre
ambas soluciones).
Además, dado los bajos tiempos de espera para el tercer tipo de pares de nodos, la
incorporación de trenes intermedios no afecta el comportamiento de aquellos pares.
4.3.4 Análisis de la situación actual
Actualmente la programación de horarios para los trenes se opera en forma
independiente para cada una de las líneas y no asegura que después de la hora de cierre
88
de puertas los pasajeros puedan llegar a cualquier punto de la red. Los horarios de trenes
programados aseguran combinaciones factibles hasta las 22:30 hrs., hora establecida
después de haber obtenidos los programas de circulación para cada línea. A partir de
estos horarios se generan rutas indicando a los pasajeros cuales son los trenes que deben
tomar para poder llegar a los distintos tramos de la red.
Los tiempos de espera actuales (en [seg]) de los pasajeros están dados por los últimos
intervalos de salida de los trenes. Estos se presentan a continuación.
L1 L2 L4 L4A L5
EM SP VN LC TO PPA VM LC QN VV
390 360 420 480 480 480 480 720 420 420
Tabla 4.26: Tiempos de espera actuales por últimos trenes.
Estos tiempos si bien son menores que los establecidos por los últimos trenes de los
modelos planteados en esta tesis, fluctúan entre valores similares, teniendo como cota
superior 12 minutos.
Si se considera el esquema de operación actual de Metro, operando con trenes hasta las
23:05 hrs para las líneas 1, 2, 4 y 5 y hasta las 23:45 hrs para la línea 4A, la cantidad total
de viajes realizados es 120.
Hay que notar que tanto la situación actual como los modelos planteados, tiene una hora
de cierre de puertas posterior a las 23:00 hrs. Ahora, si bien los tiempos de espera de la
situación actual y la cantidad de viajes realizados son menores a los resultados obtenidos
por los modelos, hay que recordar que la situación actual tiene media hora menos que los
modelos planteados de satisfacción de rutas para los pasajeros, situación que si se viera
igualada, manteniendo los patrones de la operación actual, operaría con un total de 150
viajes aprox. Lo anterior se traduce en la generación de 20 viajes más.
89
Si se quisiera igualar el nivel de servicio entregado, con la utilización de los modelos
propuestos se estaría hablando de una reducción de costos operacionales considerable
para Metro.
90
5. SÍNTESIS Y CONCLUSIONES
El objetivo de esta tesis es la programación de los horarios de salida de los último trenes
de las estaciones terminales del Metro con el fin de que cada pasajero que consiguió
entrar a la red, pueda llegar a su destino al menos a través de una ruta.
Para cumplir con lo anterior se trabajó en el desarrollo de dos modelos de programación
lineal, los cuales consistían en la programación horaria de trenes hasta la hora de cierre
(MSTF), y en la coordinación de trasbordos de los últimos trenes (MSTV) respectivamente.
Posteriormente estos modelos fueron integrados para poder obtener el resultado final.
Trabajar con estos dos modelos permite principalmente trabajar con las líneas en
conjunto para poder coordinar los trasbordos de los últimos trenes y esto trasmitirlo a la
generación de horarios de una línea en particular. La forma en que opera Metro
actualmente sólo trabaja con las líneas en forma independiente, y no en conjunto para
coordinar los trasbordos, generando los programas de circulación para cada línea, y a
partir de éstos, se evalúa cuáles son las rutas y combinaciones que se pueden realizar a la
hora de cierre.
El MSTF tenía por objetivo la minimización del número de viajes que se de deben realizar
desde las 22:00 hrs. hasta la hora de cierre de las puertas del Metro. Por su parte, el MSTV
tenía por objetivo la minimización del número de trenes extra (después del último tren)
que son necesarios para que los usuarios puedan llegar a cualquier punto de la red
tomando el último tren de cada línea. Para la integración de los modelos, los resultados
del MSTV fueron agregados en forma de restricciones al MSTF, y finalmente éste fue
resuelto.
El principal resultado obtenido fue la programación horaria de trenes en detalle para cada
línea a partir de las 22:00 hrs. hasta la hora de cierre de puertas (después de las 23:00
hrs.) coordinando los últimos trasbordos con el fin de minimizar la cantidad de trenes
requeridos para la operación. Con esto se pudo establecer los horarios de los últimos
91
trenes que salen desde las estaciones terminales, horario posterior al instante mínimo
establecido para el cierre de puertas.
En cuanto a la calidad de servicio entregada, reflejada principalmente en los tiempos de
espera de los usuarios, está incorporada en forma de restricción en el MSTF acotando los
intervalos de salida de trenes desde sus estaciones terminales. El problema podría haber
sido abordado con una función multi-objetivo en donde se minimizaran costos
operacionales y tiempos de espera. Si se llevara ese problema a una función mono-
objetivo utilizando el método de restricciones (Constraint Method and Goal Programming)
se puede establecer una cota para el tiempo de espera, que fue lo que se hizo a priori para
el desarrollo del MSTF, y resolver la función objetivo minimizando el número de trenes
sujeto a las restricciones de calidad de servicio.
En cuanto al problema de coordinación, no es posible realizar todas las combinaciones
sólo con los últimos trenes desde cada estación terminal para cualquier tipo de red con
más de dos líneas. Es por esto que se deben incorporar trenes extras para recoger a los
pasajeros que aún esperan el tren de trasbordo. El objetivo del segundo modelo era la
minimización de tales trenes, consiguiendo trasbordos factibles para toda la red.
La utilización de trenes extras vs una operación normal hasta la misma hora, permite
claramente una disminución en la realización de viajes ya que éstos trenes están
programados de tal forma que se hacen cargo exclusivamente de las personas que están
esperando en estaciones de combinación y no para la operación normal con frecuencias
de salida constantes.
Con respecto a las rutas generadas según el tipo de par origen-destino, se realizó un
análisis de los tiempos de espera en los que incurrían los pasajeros, observando que
quienes realizaban una combinación debían esperar tiempos muy grandes por los trenes
de trasbordo. Para dar solución a esto se propuso la incorporación de trenes intermedios
en las líneas que lo requiriesen, beneficiando a algunos grupos de pasajeros. La
disminución de estos tiempos fluctuó entre un 62% y 100%.
92
La cantidad de viajes que deben ser realizados en base a la propuesta expuesta
anteriormente es 130, con un funcionamiento de la red de Metro, en que cada una de las
estaciones cierra después de las 23:00 hrs., asegurando que ingresando a esa hora pueden
llegar a cualquier punto de la red.
La forma de operación actual de Metro utiliza 120 viajes, pero sólo asegura caminos
factibles para cualquier par de nodos de la red hasta la 22:30 hrs. Frente a esto, se
propone el resultado obtenido con la generación de 10 viajes más pero asegurando la
llegada al destino de los pasajeros entre las 23:00 y las 23:50 hrs., dependiendo de la
estación en la que se ingrese.
Los resultados obtenidos son satisfactorios. En cuanto al primer modelo (MSTF), el
resultado de la relajación coincide con el resultado del problema entero, lo cual asegura
que se está en el óptimo. En cuanto al segundo, el problema es pequeño y la solución
entera es encontrada rápidamente.
Por otra parte, los supuestos utilizados para la creación de los modelos, limitan
ligeramente la aplicabilidad real de los mismos, principalmente debido a características
que debe comprender la red en estudio, los períodos horarios utilizados y a características
propias de los trenes tales como capacidades y maniobras. Como solución a esto se
propone la extensión de los modelos a una red general y trabajar con los tiempos en
forma más desagregada o en función de los tiempos de operación de cada tren en cada
línea (PESP).
En cuanto a trabajos futuros se propone la utilización de una función multi-objetivo como
se mencionó anteriormente, en donde se optimice una función de costos y otra con
respecto a la calidad de servicio. Utilizando distintos métodos de solución se podría llegar
a soluciones Pareto óptimas, en donde el tomador de decisiones deberá escoger según los
intereses y objetivos de su estudio.
También se propone la utilización de un solo modelo que sea capaz de enfrentar los dos
problemas tratados con distintos modelos en esta tesis, es decir, un modelo que sea capaz
93
de entregar una programación horaria para un conjunto de líneas que conforman una red,
considerando los trasbordos que se realizan en ésta.
94
6. BIBLIOGRAFÍA
[1] M. Abkowitz, R. Josef, J.Tozzi and M.K. Driscoll, Operational Feasibility of Timed
Transfer in Transit Systems. J. Trans. Eng. 113, 168-177, 1987.
[2] J.H. Bookbinder, Transfer Optimization in a Transit Network, Transportation Science,
Vol. 26, No. 2, 1992.
[3] M.R. Bussieck, Optimal Lines in Public Rail Transport. PhD thesis, Technische
Universität Braunschweig, 1998.
[4] M.R. Bussieck, T. Winter and U.T. Zimmermann, Discrete Optimization in Public Rail
Transport .Math. Programming, 1997.
[5] M.S. Chowdhury and S.I. Chien, Optimization of Transfer Coordination for Intermodal
Transit Networks. Transportation Research Board, 80th Annual Meeting, January, 2001.
[6] M.T. Claessens, N.M. van Dijk and P.J. Zwaneveld, Cost optimal allocation of rail
passenger lines. European J. Oper. Res., 110 (3) 474-489, 1998.
[7] C. Giesemann, Periodic Timetable Generation. Seminar on Algorithms and Models for
Railway Optimization, University of Constance, SS 2002.
[8] R. Hall, M. Dessouky and Q. Lu, Optimal Holding Times at Transfer Station, University of
Sourthern California, 2001.
[9] P. Knoppers and T. Muller, Optimized Transfer Opportunities in Public Transport,
Transportation Science, Vol. 29, No. 1, 1995.
[10] K.K.T. Lee and P. Schonfeld, Optimal Slack Time for Timed Transfer at a Transit
Termianl. Journal of Advanced Transportation, Vol. 25, No. 3, pp. 281-308.
[11] T. Lindner, Train Schedule Optimization in Public Rail Transport. PhD thesis,
Technische Universität Braunschweig, 2000.
[12] T. Lindner and U.T. Zimmermann, Cost Optimal PeriodicTrain Scheduling. Technische
Universität Braunschweig, January 14, 2005.
95
[13] M.N. Nielsen, B. Hove and Jeans Clausen, Constructing periodic timetables using MIP
– a case study from DSB S-train. Int. J. Operational Research, Vol. 1, No. 3, 2006.
[14] V. Romero, Modelos de optimización del Tráfico de Trenes, PhD thesis, Universidad
de Chile, 2005.
[15] P. Serafini and W. Ukovich, A mathematical model for periodic scheduling problems.
SIAM J. Disc. Math. 2 (4), 1989.
[16] B. Vaidyanathan, K.C. Jha and R.K. Ahuja, Multicommodity network flow approachto
the rail road crew-scheduling problem. IBM J. RES. & DEV. Vol. 51, No 3, 2007.
[17] A. Vega, F. Robusté, A. Ibeas, J.M. Díaz, P. de la Lastra y J.L. Moura, Un Modelo de
Operación del Transporte Público Colectivo Urbano en Superficie considerando el tráfico en
la Cuidad, © Santander- CIT 2002.
[18] J.C. Villumsen, Construction of Timetables based on Periodic Event Scheduling.
Kongens Lyngby 2006, IMM-Thesis-2006-52.
[19] www.metrosantiago.cl
96
ANEXOS
1. Red de Metro, Diciembre 2007.
Fuente: www.metrosantiago.cl
97
2. Siglas Estaciones de Metro.
LINEA 1 L1
SAN PABLO SP
NEPTUNO NP
PAJARITOS PJ
LAS REJAS LR
ECUADOR EC
ALBERTO HURTADO AH
U DE SANTIAGO US
ESTACIÓN CENTRAL EL
U LATINOAMERICANA LA
REPÚBLICA RE
LOS HÉROES LH
LA MONEDA LM
UNIVERSIDAD DE CHILE CH
SANTA LUCÍA SL
UNIVERSIDAD CATÓLICA UC
BAQUEDANO BA
SALVADOR SA
MANUEL MONTT MM
PEDRO DE VALDIVIA PV
LOS LEONES LE
TOBALABA TO
EL GOLF GO
ALCÁNTARA AL
ESCUELA MILITAR EM
LINEA 2 L2
LA CISTERNA LC
EL PARRÓN EP
LO OVALLE LO
CIUDAD DEL NIÑO CN
DEPARTAMENTAL DE
LO VIAL LV
SAN MIGUEL SM
EL LLANO LL
FRANKLIN FR
RONDIZONNI RO
PARQUE O'HIGGINS PQ
TOESCA TO
LOS HEROES LH
SANTA ANA SA
CAL Y CANTO CA
PATRONATO PT
98
CERRO BLANCO CB
CEMENTERIOS CE
EINSTEIN EI
DORSAL DO
ZAPADORES ZA
AMÉRICO VESPUCIO NORTE VN
LINEA 4 L4
TOBALABA TO
COLÓN CO
BILBAO BI
PRÍNCIPE DE GALES GA
SIMÓN BOLÍVAR SB
PLAZA EGAÑA EG
LOS ORIENTALES OR
ROTONDA GRECIA RG
LOS PRESIDENTES LP
ROTONDA QUILÍN RQ
LAS TORRES LT
MACUL MC
VICUÑA MACKENNA VM
VICENTE VALDÉS VA
ROJAS MAGALLANES RM
TRINIDAD TR
LOS QUILLAYES LQ
ELISA CORREA EA
HOSP. SÓTERO DEL RÍO HS
PROTECTORA DE LA INF PI
LAS MERCEDES ME
PLAZA PUENTE ALTO PPA
LINEA 4A L4A
VICUÑA MACKENNA VM
SANTA JULIA JU
LA GRANJA LG
SANTA ROSA SR
SAN RAMÓN RN
LA CISTERNA LC
99
LINEA 5 L5
QUINTA NORMAL QN
CUMMING RC
SANTA ANA SA
PLAZA DE ARMAS PZ
BELLAS ARTES BE
BAQUEDANO BQ
PARQUE BUSTAMANTE PB
SANTA ISABEL SI
IRARRÁZAVAL IR
ÑUBLE UN
RODRIGO DE ARAYA RA
CARLOS VALDOVINOS CV
CAMINO AGRÍCOLA AG
SAN JOAQUÍN SJ
PEDREROS PE
MIRADOR AZUL MA
LA FLORIDA LF
VICENTE VALDÉS VV