Optimal Scheduling of Urban Transit Systems Using Genetic Algorithms
Publication: Journal of Transportation Engineering
Volume 121, Issue 6
Abstract
Scheduling of urban transit network can be formulated as an optimization problem of minimizing the overall transfer time (TT) of transferring passengers and initial waiting time (IWT) of the passengers waiting to board a bus/train at their point of origin. In this paper, a mathematical programming (MP) formulation of the scheduling problem at one transfer station is presented. The MP problem is large and nonlinear in terms of the decision variables, thereby making it difficult for classical programming techniques to solve the problem. We apply genetic algorithms (GAs)—search and optimization methods based on natural genetics and selection—to solve the scheduling problem. The main advantage of using GAs is that the problem can be reformulated in a manner that is computationally more efficient than the original problem. Further, the coding aspect of GAs inherently takes care of most of the constraints associated with the scheduling problem. Results from a number of test problems demonstrate that the GAs are able to find optimal schedules with a reasonable computational resource. The paper concludes by presenting a number of extensions to the present problem and discusses plausible solution techniques using GAs. The success of GAs in this paper suggests their efficacy as a solution tool for similar optimization problems arising in transportation systems.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Bookbinder, J. H., and Désilets, A.(1992). “Transfer optimization in a transit network.”Transp. Sci., 26(2), 106–118.
2.
Davis, T., and Principe, J. C. (1991). “A simulated annealing like convergence theory for the simple genetic algorithm.”Proc., 4th Int. Conf. on Genetic Algorithms, R. K. Belew and L. B. Booker, eds., Morgan Kaufman, San Mateo, Calif., 174–181.
3.
Deb, K. (1993). “Genetic algorithms in engineering design optimization.”Proc., Advanced Study Inst. on Computational Methods for Engrg. Analysis and Design, J. N. Reddy et al., eds., Indian Inst. of Technol., Madras, India, 12.1–12.25.
4.
Eshelman, L. J., and Schaffer, J. D. (1993). “Real-coded genetic algorithms and interval-schemata.”Foundations of genetic algorithms II, D. Whitley, ed., Morgan Kaufman, San Mateo, Calif., 187–202.
5.
Glover, F.(1975). “Improved linear integer programming formulations of nonlinear integer problems.”Mgmt. Sci., 22(4), 455–460.
6.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning . Addison-Wesley, Reading, Mass.
7.
Goldberg, D. E., Deb, K., and Korb, B. (1990). “Messy genetic algorithms revisited: nonuniform size and scale.”Complex Systems, Vol. 4, 415–444.
8.
Grefenstette, J. J., and Fitzpatrick, J. M. (1985). “Genetic search with approximate function evaluations.”Proc. of an Int. Conf. on Genetic Algorithms and Their Applications, J. J. Grefenstette, Lawrence Erlbaum, Hillsdale, N.J., 112–120.
9.
Holland, J. H. (1975). Adaptation in natural and artificial systems . University of Michigan Press, Ann Arbor, Mich.
10.
Kargupta, H., Deb, K., and Goldberg, D. E. (1992). “Ordering genetic algorithms and deception.”Parallel problem solving from nature II, R. Manner and B. Manderick, eds., North Holland, Amsterdam, The Netherlands, 47–56.
11.
Kikuchi, S., and Parameswaran, J. (1993). “Solving a schedule coordination problem using a fuzzy control technique.”Proc., Intelligent Scheduling Systems Symp., ORSA-TIMS, San Francisco, Calif.
12.
Proc., 1st Int. Conf. on Genetic Algorithms. (1985). J. J. Grefenstette, ed., Lawrence Erlbaum, Hillsdale, N.J.
13.
Proc., 2nd Int. Conf. on Genetic Algorithms. (1987). J. J. Grefenstette, ed., Lawrence Erlbaum, Hillsdale, N.J.
14.
Proc., 4th Int. Conf. on Genetic Algorithms. (1991). R. Belew and L. B. Booker, eds., Morgan Kaufman, San Mateo, Calif.
15.
Radcliffe, N. J. (1993). “Genetic set recombination.”Foundations of genetic algorithms II, D. Whitley, ed., North Holland, Amsterdam, The Netherlands, 203–220.
16.
Rapp, M. H., and Gehner, C. D. (1976). “Transfer optimization in an interactive graphic system for transit planning.”Transp. Res. Rec. 619, Transp. Res. Board (TRB), Washington, D.C., 27–33.
17.
Reklaitis, G. V., Ravindran, A., and Ragsdell, K. M. (1983). Engineering optimization—methods and applications . Wiley, New York, N.Y.
18.
Schaffer, J. D. (1984). “Some experiments in machine learning using vector evaluated genetic algorithms.”Dissertation Abstracts Int., Vol. 46.
19.
Vose, M. D. (1993). “Modeling simple genetic algorithms.”Foundations of genetic algorithms II, D. Whitely, ed., Morgan Kaufman, San Mateo, Calif. 63–73.
20.
Wright, A. H. (1991). “Genetic algorithms for real parameter optimization.”Foundations of genetic algorithms, G. J. E. Rawlins, ed., Morgan Kaufman, San Mateo Calif., 205–218.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 121 • Issue 6 • November 1995
Pages: 544 - 553
Copyright
Copyright © 1995 American Society of Civil Engineers.
History
Published online: Nov 1, 1995
Published in print: Nov 1995
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.