Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems

Urban Transit Scheduling Problem (UTSP) considers the process of creating timely transit schedules that includes bus and drivers assignment based on the users' and operators’ requirements. This thesis studies multiobjective UTSP consisting of frequency setting, timetabling, simultaneous bus and driver scheduling by applying Multiple Tabu Search (MTS) algorithm. Metaheuristic methods have been widely applied to solve UTSP which is a NP-hard problem. However, there is no applications of MTS in UTSP are known to date. Therefore, MTS is developed from TS with some additional features such as systematic neighbourhood evaluation procedure to reach the near optimal solutions quickly. The ability of MTS approach to exploit and explore the solution space effectively with adaptive memory property makes it more suitable to be used in UTSP. The implementation of MTS begins with the frequency optimization procedure which determines the service frequencies and fleet sizes with the objectives of minimizing the operational cost, passengers’ waiting times at nodes and the overcrowding in the buses. A mixed integer programming models are formulated to represent the objectives. Then, timetabling process is performed to identify a set of departure times at both origin and destination based on predefined parameters. The multiobjective set covering model is used by including some real-world restrictions to find number of buses and drivers as it can represent the problem clearly for implementation. The MTS algorithm is coded in ANSI-C language and tested on benchmark data from Mandl's Swiss Network and Mumford's larger data. Nondominated solutions are produced for every dataset to mark the tradeoff between the conflicting objectives studied in this research. Additionally, the MTS algorithm is also implemented in parallel computing to produce parallel MTS for generating comparable solutions in shorter computational times. The major contribution of this research is to propose MTS method for solving UTSP in both sequential and parallel approach and it is shown that the algorithms are able to produce comparable results for most of the cases from literature and the computational times can be reduced significantly for more than 80% by the parallel execution. As a future work, the research can be extended to find the departure times at every bus stops, provided the number of passengers at each stops