Time Scheduling of Transit Systems With Transfer Considerations Using Genetic Algorithms

@article{deb98time, abstract = {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.}, author = {Deb, Kalyanmoy and Chakroborty, Partha }, citeulike-article-id = {1572336}, journal = {Evolutionary Computation}, keywords = {algorithms, computer\_science, genetic\_algorithms}, number = {1}, pages = {1--24}, posted-at = {2007-08-29 20:52:53}, priority = {2}, title = {Time Scheduling of Transit Systems With Transfer Considerations Using Genetic Algorithms}, url = {http://citeseer.ist.psu.edu/deb98time.html}, volume = {6}, year = {1998} }

TY - JOUR ID - deb98time L3 - citeulike-article-id:1572336 TI - Time Scheduling of Transit Systems With Transfer Considerations Using Genetic Algorithms JF - Evolutionary Computation VL - 6 IS - 1 SP - 1 EP - 24 N2 - 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. KW - algorithms KW - computer_science KW - genetic_algorithms AU - Deb, Kalyanmoy AU - Chakroborty, Partha PY - 1998/// UR - http://citeseer.ist.psu.edu/deb98time.html ER -