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...

Full description

Saved in:

Bibliographic Details
Main Author:	Uvaraja, Vikneswary
Format:	Thesis
Language:	English
Published:	2018
Subjects:	Urban transportation Transportation - Planning Local transit
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!

id	my-upm-ir.83718
record_format	uketd_dc
spelling	my-upm-ir.837182022-01-05T02:38:17Z Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems 2018-12 Uvaraja, Vikneswary 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. Urban transportation Transportation - Planning Local transit 2018-12 Thesis http://psasir.upm.edu.my/id/eprint/83718/ http://psasir.upm.edu.my/id/eprint/83718/1/FS%202019%2038%20-%20ir.pdf text en public masters Universiti Putra Malaysia Urban transportation Transportation - Planning Local transit Lee, Lai Soon
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English
advisor	Lee, Lai Soon
topic	Urban transportation Transportation - Planning Local transit
spellingShingle	Urban transportation Transportation - Planning Local transit Uvaraja, Vikneswary Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
description	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.
format	Thesis
qualification_level	Master's degree
author	Uvaraja, Vikneswary
author_facet	Uvaraja, Vikneswary
author_sort	Uvaraja, Vikneswary
title	Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
title_short	Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
title_full	Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
title_fullStr	Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
title_full_unstemmed	Sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
title_sort	sequential and parallel multiple tabu search algorithm for multiobjective urban transit scheduling problems
granting_institution	Universiti Putra Malaysia
publishDate	2018
url	http://psasir.upm.edu.my/id/eprint/83718/1/FS%202019%2038%20-%20ir.pdf
_version_	1747813411473850368

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

Similar Items