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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/83718/1/FS%202019%2038%20-%20ir.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|