Due to the steady increased in public transportation demand, there is a need to provide more desirable and user-friendly transit systems. Typically, the public transportation timetables are modeled as an assignment problem, which often has objectives such as reducing the cost of operation, minimizing waiting time between transfer points or improving the quality of performance. This research considers the problem of developing synchronized timetables for bus transit systems with fixed routes when a waiting time limit exist at each transfer stops, for the passengers making connections. The objective of this research is to have maximum number of simultaneous arrivals. Different to previous studies, a simultaneous arrival' has been defined as an arrival of buses of different routes at a transfer point such that the time between these arrivals do not exceed the passenger waiting time range associated with the transfer stop. In other words, at each node, an upper bound and a lower bound are set for the arrivals of two buses and these buses are run within this allowable window. The heuristic developed has been modeled as a mixed integer linear programming problem and applied to some real life problems to evaluate the outcomes. The total number of synchronizations obtained by the model was compared to the maximum possible simultaneous arrivals at each node. Results show that a larger number of simultaneous arrivals are obtained when the waiting time ranges are relaxed. Finally some important applications of the proposed model compared to the existing models are presented.

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

This dissertation investigates the influencing factors on timetable quality, not only from a data quality perspective, but also from an information quality perspective which takes into account the quality of the business processes involved in creating the timetable. The Nelson Mandela Metropolitan University was used as a case study for assessing the quality of the timetable process, the quality of the source data, and the quality of the final timetable produced. A framework for managing the data quality during the timetabling process is proposed. The framework is based on reviews done on data quality management best practices and data quality aspects. Chapter 1 introduces the current Nelson Mandela Metropolitan University timetable, and motivates why data quality management is essential to its success. The scope and research objectives are presented for this dissertation. Chapter 2 covers a literature study on business process and data quality management best practices. The common thread through all the management methodologies investigated, was top management involvement and commitment to continuously improving the quality of data. Chapter 3 discusses various characteristics of data quality. Quality is determined to be whether the end result meets the quality requirements for which it was intended. Hence each system could have quality aspects that are unique to it. Chapter 4 explains various research designs and which were followed for this dissertation. The combination of literature studies, a questionnaire and a case study were used. Chapter 5 is a case study of the data quality and timetabling processes used at the Nelson Mandela Metropolitan University and is based on the research design described in chapter 4. The current business processes followed in setting up the current timetable are presented, as well as the proposed timetabling process that should produce a better quality timetable for the Nelson Mandela Metropolitan 4 University. The data quality aspects most pertinent to the Nelson Mandela Metropolitan University are determined, being timeliness, accountability, integrity and consistency, as well as the most probable causes for bad timetable quality, like uniform technology, processes, ownership and using a common terminology. Chapter 6 presents a framework for managing timetable data quality at the Nelson Mandela Metropolitan University using an Information Product Map approach that will ensure a better quality timetable. Future research is also proposed. It is evident from this dissertation that data quality of source data as well as the quality of the business process involved is essential for producing a timetable that satisfies the requirements for which it was intended. The management framework proposed for the Nelson Mandela Metropolitan University timetabling process can potentially be used at other institutions as well.

This thesis reports on research into the applicability of intelligent agents in the airline scheduling environment. The methodology employed was to look at intelligent agent research and then, based on this, to build models that can be used to solve some of the airline scheduling problems. The following was done: · An agent-based model was developed that can assist airline schedulers in the maintenance of a disrupted schedule. The agent model consists of a hybrid approach combining elements of machine learning and expert systems. · A multiagent model was developed that can generate a profitable and flyable schedule. The multiagent model developed extends the traditional control structures of the hierarchical agent organisation to a matrix structure. This new model can be extended to any problem domain that deals with resource allocation and capacity management. To guide the thinking behind this research, a few questions were posed regarding the problem to be solved: Q1. Can intelligent agents play a role in the airline industry, with specific focus on the scheduling creation and maintenance process? Q2. What will the design of the agent models be if the scheduling needs of an airline have to be addressed? Q3. If the models as envisioned in question 2 can be created, what will the practical implications be? At a conceptual level the research produced three results: R1. No references were found to multiagent technology in the production or maintenance of airline schedules. This theoretical research into agent systems shows that there is applicability in the scheduling environment, with specific reference to schedule maintenance and generation. R2. An agent model was created that combines declarative knowledge with empirical learning to assist human schedulers in the day-to-day maintenanceof the schedule. Multiple solutions to a scheduling problem are generated by the agent using embedded scheduling rules. The agent then uses the Qlearning algorithm to learn the preferences of the human scheduler. This approach combines the best of expert systems and machine learning. To solve the problem of schedule generation, a multiagent system with a matrix governance model was introduced. Aircraft and airports were modelled as buying and selling agents. The business manager agent that assigns individual aircrafts to specific routes was defined. This was accomplished by matching individual aircraft capacity to origin-destination demand. The agent model was then expanded to show how the inclusion of a resource manager agent can handle system capacity management. This is a matrix governance model, as an aircraft agent is managed by a business manager agent, as well as by a resource manager agent. The initial results from the prototype show that this model can generate profitable and flyable schedules. The multiagent model developed extends the traditional hierarchical agent organisation to that of a matrix structure. The contract net protocol used for typical multiagent coordination was adapted to work in this new control structure. This new model can be extended to any problem domain that deals with resource allocation and capacity management. R3. A few airlines use expert systems to handle schedule disruptions. By introducing machine learning, a flexibility is achieved that is currently not available. The approach proposed for schedule generation is not guaranteed to provide optimal results like traditional operations research techniques, but it is useful for high-level analysis, long-term planning, new hub or alliance planning and research. It also has potential as a catalyst for integrated planning. Keywords: Multiagent systems, airline scheduling / Ehlers, E.M., Prof.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Civil Engineering, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / by Mordechai Porath. / M.S.

A dissertation submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science in Engineering. University of the Witwatersrand, Johannesburg, 2016 / Given a flight schedule with fixed departure times and cost, solving the fleet assignment problem assists airlines to find the minimum cost or maximum revenue assignment of aircraft types to flights. The result is that each flight is covered exactly once by an aircraft and the assignment can be flown using the available number of aircraft of each fleet type. This research proposes a novel, non-linear integer programming fleet assignment model which differs from the linear time-space multi-commodity network fleet assignment model which is commonly used in industry. The performance of the proposed model with respect to the amount of time it takes to create a flight schedule is measured. Similarly, the performance of the time-space multicommodity fleet assignment model is also measured. The objective function from both mathematical models is then compared and results reported. Due to the non-linearity of the proposed model, a genetic algorithm (GA) is used to find a solution. The time taken by the GA is slow. The objective function value, however, is the same as that obtained using the time-space multi-commodity network flow model. The proposed mathematical model has advantages in that the solution is easier to interpret. It also simultaneously solves fleet assignment as well as individual aircraft routing. The result may therefore aid in integrating more airline planning decisions such as maintenance routing. / MT2017

Wong Chi Wing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 105-106). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Literature Review --- p.3 / Chapter 1.3 --- Thesis Outline --- p.5 / Chapter 2 --- The Timetable Synchronization Problem --- p.7 / Chapter 2.1 --- Underlying Assumptions --- p.7 / Chapter 2.2 --- The Timetable Synchronization Problem (TTSP) --- p.10 / Chapter 2.2.1 --- Time-Horizon Boundary Concerns --- p.10 / Chapter 2.2.2 --- Transfer Waiting-times Declaration --- p.11 / Chapter 2.2.3 --- Set Declarations --- p.13 / Chapter 2.2.4 --- Parameter Declarations --- p.14 / Chapter 2.2.5 --- Variable Declarations --- p.16 / Chapter 2.2.6 --- Model Description --- p.17 / Chapter 2.3 --- Alternative Formulation --- p.22 / Chapter 2.4 --- Summary --- p.24 / Chapter 3 --- Solution Approach --- p.25 / Chapter 3.1 --- Computation Comparison of the Two Formulation --- p.25 / Chapter 3.2 --- CPLEX Parameter Settings --- p.26 / Chapter 3.3 --- Optimization-based Heuristic Method (OHM) --- p.26 / Chapter 3.3.1 --- Why Modify? - Sharper LP-Relaxation --- p.28 / Chapter 3.3.2 --- How to Predict and Release --- p.30 / Chapter 3.4 --- Performance of the OHM --- p.31 / Chapter 3.5 --- Summary --- p.32 / Chapter 4 --- Case Study of the MTR in HK --- p.33 / Chapter 4.1 --- Problem Settings --- p.33 / Chapter 4.1.1 --- Train Routes --- p.33 / Chapter 4.1.2 --- Cross-platform Times --- p.34 / Chapter 4.1.3 --- Testing Horizon --- p.35 / Chapter 4.1.4 --- Number of Trains --- p.35 / Chapter 4.1.5 --- Allowable Adjustments to Operational Parameters --- p.36 / Chapter 4.2 --- Solution Quality --- p.37 / Chapter 4.2.1 --- Average Transfer Waiting-times --- p.37 / Chapter 4.2.2 --- Possible Maximum Transfer Waiting-times --- p.37 / Chapter 4.2.3 --- """Just Miss""" --- p.38 / Chapter 4.3 --- Summary --- p.39 / Chapter 5 --- Solution Quality in Different Settings --- p.40 / Chapter 5.1 --- Optional Operational Constraints I - Improve Regularity --- p.41 / Chapter 5.1.1 --- Regularity of Dwell-times --- p.41 / Chapter 5.1.2 --- Regularity of Headway --- p.43 / Chapter 5.2 --- Cases Analysis I --- p.44 / Chapter 5.2.1 --- Case Analysis 1 - l Steps to Use the System --- p.45 / Chapter 5.2.2 --- Case Analysis 2 - Varying Run-times --- p.47 / Chapter 5.2.3 --- Case Analysis 3 - Non-rush Hour --- p.49 / Chapter 5.2.4 --- Case Analysis 4 - Varying Regularity of Dwell-times . . --- p.52 / Chapter 5.3 --- Cases Analysis II --- p.55 / Chapter 5.3.1 --- Optional Operational Constraints II - Increasing Dwell-times (1) --- p.55 / Chapter 5.3.2 --- Case Analysis 5 - Adding Special Dwell-times Bounds . --- p.56 / Chapter 5.4 --- Case Analysis III --- p.58 / Chapter 5.4.1 --- Optional Operational Constraints III - Increasing Dwell-times (2) --- p.58 / Chapter 5.4.2 --- Case Analysis 6 - Adding Modified Special Dwell-times Bounds --- p.59 / Chapter 5.5 --- Future Work --- p.61 / Chapter 6 --- Timetable-Synchronization System --- p.62 / Chapter 6.1 --- Hierarchy of the Timetable-Synchronization System --- p.64 / Chapter 6.2 --- Use of the Component Software Tools --- p.66 / Chapter 6.2.1 --- ILOG CPLEX 7.5 --- p.66 / Chapter 6.2.2 --- Microsoft Visual Basic. Net 2003 --- p.66 / Chapter 6.2.3 --- Microsoft Office XP - Excel --- p.67 / Chapter 6.2.4 --- Microsoft Office XP - Access --- p.68 / Chapter 6.3 --- Summary --- p.69 / Chapter 7 --- Conclusions --- p.70 / Chapter 7.1 --- Summary and Further Studies --- p.70 / Appendix --- p.72 / Chapter A --- The MTR System in HK --- p.73 / Chapter B --- Abbreviation of Routes --- p.74 / Chapter C --- Abbreviation of Interchange Stations --- p.75 / Chapter D --- Passenger Groups --- p.76 / Chapter E --- Average Transfer Waiting-times (08:00-ج09:00) --- p.78 / Chapter F --- Maximum Transfer Waiting-times (08:00-ج09:00) --- p.79 / Chapter G --- Using the Timetable-Synchronization System --- p.80 / Chapter G.l --- Steps to Use the System --- p.82 / Chapter H --- Timetable-Synchronization System Problem Generator --- p.85 / Chapter H.1 --- "Use of the ""Timetable-Synchronization System Problem Gen- erator""" --- p.85 / Chapter H.2 --- "Hierarchy of the ""Timetable-Synchronization System Problem Generator""" --- p.86 / Chapter H.3 --- "Using the ""Timetable-Synchronization System Problem Gen- erator""" --- p.87 / Chapter I --- Transfer Waiting-time Calculator --- p.94 / Chapter I.1 --- Use of Transfer Waiting-time Calculator --- p.94 / Chapter I.2 --- Using the Transfer Waiting-time Calculator --- p.95 / Chapter J --- Database Structure in Microsoft Access --- p.97 / Chapter J.1 --- Operational Parameters --- p.98 / Chapter J.1.1 --- Use of Operational Parameters --- p.98 / Chapter J.1.2 --- Structure of the Tables --- p.98 / Chapter J.2 --- Current Timetable --- p.102 / Chapter J.2.1 --- Use of Current Timetable --- p.102 / Chapter J.2.2 --- Structure of the Tables --- p.102 / Chapter J.3 --- Patronage --- p.103 / Chapter J.3.1 --- Structure of the Table --- p.104 / Bibliography --- p.106

published_or_final_version / Transport Policy and Planning / Master / Master of Arts in Transport Policy and Planning