Algoritmo de generación de columnas para la asignación de tareas en el sistema Metrobus-Q / Elizabeth Carolina Zúñiga Riofrío

By: Zúñiga Riofrío, Elizabeth Carolina
Contributor(s): Torres Carvajal, Luis Miguel [Director]
Material type: Mixed materialsMixed materialsQuito : EPN, 2015Description: 113 hojas : ilustraciones, 29 x 21 cm + CD-ROM 6171Subject(s): Algoritmos | Modelos matemáticosOther classification: T-FCM/ Online resources: Texto completo
Contents:
LA BIBLIOTECA CENTRAL NO DISPONE DE ESTA TESIS EN FORMATO PAPEL
Dissertation note: FACULTAD DE CIENCIAS Pregrado Tesis (Ingeniero Matemática). -- Escuela Politécnica Nacional. 2015 Summary: Resumen .- En el presente proyecto se aborda el problema de asignación de conductores, en el contexto del sistema de transporte público masivo Trolebús. Se presenta un modelo de programación lineal entero, basado en un modelo de particionamiento de conjuntos. Este modelo tiene por objetivo reducir al mínimo el tiempo de inactividad total de los conductores en las terminales, respetando los acuerdos laborales y buscando ocupar el menor número de buses. Se propone el uso del método de generación de columnas para enfrentar el problema. Como subproblema resultante, se obtienen problemas de caminos más cortos con restricciones, uno para cada tipo de tarea. Debido al gran número de variables que se presentan en la asignación de conductores, se hace uso de la estrategia de fijación de variables. Por último, se formula un modelo de emparejamiento máximo para unir las jornadas laborales que se puedan realizar en una misma secuencia, en un día. Se reportan los resultados computacionales, para instancias reales, que cubren hasta 1400 viajes programados.Summary: Abstract .- In this project, the duty scheduling problem will be addressed in the context of the Trolebús mass transit system. An integer linear programming model based on a set partitioning formulation is presented. This model aims at minimizing the total idle time of drivers in the terminals, while complying to labor agreements and minimizing the number of buses used in the solution. A column generation method is proposed to address the problem. The solution scheme involves solving shortest paths problems with resource constraints, one different subproblem for each type of task path. Due to the large number of variables, we make use of a variable fixing strategy. Finally, a maximum matching model is formulated to join duties that can be done in one block, in a day. Computational results for real instances, covering up to 1400 scheduled trips, are reported.
Tags from this library: No tags from this library for this title.
    Average rating: 0.0 (0 votes)

FACULTAD DE CIENCIAS Pregrado Tesis (Ingeniero Matemática). -- Escuela Politécnica Nacional. 2015

Bibliografía : páginas 99 - 101.

LA BIBLIOTECA CENTRAL NO DISPONE DE ESTA TESIS EN FORMATO PAPEL

Resumen .- En el presente proyecto se aborda el problema de asignación de conductores, en el contexto del sistema de transporte público masivo Trolebús. Se presenta un modelo de programación lineal entero, basado en un modelo de particionamiento de conjuntos. Este modelo tiene por objetivo reducir al mínimo el tiempo de inactividad total de los conductores en las terminales, respetando los acuerdos laborales y buscando ocupar el menor número de buses. Se propone el uso del método de generación de columnas para enfrentar el problema. Como subproblema resultante, se obtienen problemas de caminos más cortos con restricciones, uno para cada tipo de tarea. Debido al gran número de variables que se presentan en la asignación de conductores, se hace uso de la estrategia de fijación de variables. Por último, se formula un modelo de emparejamiento máximo para unir las jornadas laborales que se puedan realizar en una misma secuencia, en un día. Se reportan los resultados computacionales, para instancias reales, que cubren hasta 1400 viajes programados.

Abstract .- In this project, the duty scheduling problem will be addressed in the context of the Trolebús mass transit system. An integer linear programming model based on a set partitioning formulation is presented. This model aims at minimizing the total idle time of drivers in the terminals, while complying to labor agreements and minimizing the number of buses used in the solution. A column generation method is proposed to address the problem. The solution scheme involves solving shortest paths problems with resource constraints, one different subproblem for each type of task path. Due to the large number of variables, we make use of a variable fixing strategy. Finally, a maximum matching model is formulated to join duties that can be done in one block, in a day. Computational results for real instances, covering up to 1400 scheduled trips, are reported.

Elizabeth Carolina Zúñiga Riofrío cedido 2015/08/27 $ 0.20 Ej. 1 Biblioteca Central 42098

There are no comments on this title.

to post a comment.
Share

Powered by Koha