Parallel Multiple Tabu Search for Multiobjective Urban Transit Scheduling Problem

• 作者: Hsin Vonn Seow Lai Soon Lee Nor Aliza Abd Rahmin Vikneswary Uvaraja
• 来源期刊: 电脑和通信(英文)
• 学科: 数学
• 关键词: Urban TRANSIT Scheduling MULTIPLE Tabu Search PARALLEL Frequency SETTING TIMETABLING Big Data
• 年，卷（期）: dnhtxyw_2020,（5）
• 页码范围: 14-54
• 页数: 41页
• 分类号: O17

摘要

Urban Transit Scheduling Problem (UTSP) is concerned with determining reliable transit schedules for buses and drivers by considering the preferences of both passengers and operators based on the demand and the set of transit routes. This paper considered a UTSP which consisted of frequency setting, timetabling, and simultaneous bus and driver scheduling. A mixed integer multiobjective model was constructed to optimize the frequency of the routes by minimizing the number of buses, passenger’s waiting times and overcrowding. The model was further extended by incorporating timeslots in determining the frequencies during peak and off-peak hours throughout the time period. The timetabling problem studied two different scenarios which reflected the preferences of passengers and operators to assign the bus departure times at the first and last stop of a route. A set covering model was then adopted to minimize the number of buses and drivers simultaneously. A parallel tabu search algorithm was proposed to solve the problem by modifying the initialization process and incorporating intensification and diversification approaches to guide the search effectively from the different feasible domain in finding optimal solutions with lesser computational effort. Computational experiments were conducted on the well-known Mandl’s and Mumford’s benchmark networks to assess the effectiveness of the proposed algorithm. Competitive results are reported based on the performance metrics, as compared to other algorithms from the literature.