Time Scheduling of Transit Systems With Transfer Considerations Using Genetic Algorithms

作     者：Deb, Kalyanmoy Chakroborty, Partha 

作者机构：Indian Inst Technol Dept Mech Engn Kanpur 208016 Uttar Pradesh India Indian Inst Technol Dept Civil Engn Kanpur 208016 Uttar Pradesh India 

出 版 物：《EVOLUTIONARY COMPUTATION》 (调优计算)

年 卷 期：1998年第6卷第1期

页      面：1-24页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Genetic algorithms mixed-integer programming reliability time scheduling transfer time transit system 

摘      要：Scheduling of a bus transit system must be formulated as an optimization problem, if the level of service to passengers is to be maximized within the available resources. In this paper, we present a formulation of a transit system scheduling problem with the objective of minimizing the overall waiting time of transferring and nontransferring passengers while satisfying a number of resource- and service-related constraints. It is observed that the number of variables and constraints for even a simple transit system (a single bus station with three routes) is too large to tackle using classical mixed-integer optimization techniques. The paper shows that genetic algorithms (GAS) are ideal for these problems, mainly because they (i) naturally handle binary variables, thereby taking care of transfer decision variables, which constitute the majority of the decision variables in the transit scheduling problem;and (ii) allow procedure-based declarations, thereby allowing complex algorithmic approaches (involving if then-else conditions) to be handled easily. The paper also shows how easily the same GA procedure with minimal modifications can handle a number of other more pragmatic extensions to the simple transit scheduling problem: buses with limited capacity, buses that do not arrive exactly as per scheduled times, and a multiple-station transit system having common routes among bus stations. Simulation results show the success of GAS in all these problems and suggest the application of GAS in more complex scheduling problems.