Schedule determination of a multiple route transit system

1. By Pranamesh Chakraborty Sharath M N Department of Civil Engineering Indian Institute of Technology Kanpur India 1 st of March, 2013 Schedule Determination of a Multiple- Route Transit System

2. Introduction Transit system plays a very important role in handling the high travel demand and simultaneously reducing the problem of congestion and pollution in any urban area. A public transport system can be made efficient by scheduling it in such a manner so that the waiting time for passengers as well as transfer time from one route to another is minimized.

3. Problem Statement Route 2 Route 1 Route 3 Route 6 Route 5 Route 4 Fig 1. Typical Transit Network The solid lines represent the routes and the circled intersections represent transfer stations The problem is to determine the schedule such that waiting time for the passengers is minimized which includes Initial Waiting Time (IWT) as well as Transfer Time (TT).

4. Mathematical Formulation The objective function is First term represents the total transfer time while the second term represents the total waiting time.

5. Constraints ( Chakroborty , P., Das, A .,2003) The transit unit should stop for a certain minimum period as physical transfer of passengers takes some time and at the same time, the transit unit cannot stop at a stop for a very long time. The constraints g 1 and g 2 will take care of these aspects . Constraint g 3 states that transferring of passengers cannot happen to transit units that have departed the transfer stations before the arrival of passenger at that transfer point . A person can transfer to only one transit unit and it is dictated by the constraint g 4 . . The time headway between any two successive vehicles must be positive and must be less than the policy headway. It is governed by constraints g 5 and g 6 . No transferring passenger shall wait for more than a certain period of time and it is being dictated by g 7 . The arrival time of a transit unit is dependent on arrival time of a transit unit at a stop previous to transfer stop and also on the travel time between those two stops; constraints g 8 and g 9 state this . The constraint g 10 states the minimum fleet size for each route while g 11 states that the total fleet size of all the routes is to be equal to N.

6. Constraints

7. where

8. Solution Technique The scheduling problem formulated is a mixed integer nonlinear programming problem. The objective function and the constraint g 7 are nonlinear whereas the variable is a 0-1 binary variable and the other variables are real. It is difficult to solve such a formulation problem using traditional optimization techniques. Hence Genetic Algorithms (GA) are used to solve such problems.

9. Genetic Algorithms Genetic algorithms are optimization algorithms based on the principles of natural genetics and natural selection. GAs are generally used to solve maximization problems. For minimization problems, the objective function (referred as Fitness function Ƒ(x) in GA problems) can be transformed into an equivalent function to be maximized. .

10. The design variables are first coded randomly in string structures. The length of the string depends on desired level of accuracy. Then the fitness value of each string is evaluated. The population is then operated by three main operators- reproduction , crossover and mutation thus forming a new population set. Genetic Algorithms

11. Genetic Algorithms Reproduction The good strings are selected and reproduced with a probability (p i ) proportional to its fitness value . Crossover Two strings are chosen at random from the population and some portion of the strings is exchanged between the pair. The crossover is done with a small probability of p c (i.e. 100p c % of the strings are used in crossover ). Mutation The mutation operator changes randomly a particular bit of a string from 1 to 0 or vice versa with a small mutation probability p m .

12. Revised Formulation (considering only one transfer stop) The new decision variables , and n i are introduced where, = Headway between the k th and the (k—l) th bus of the i th route ; = Stopping time of the k th bus of the i th route ; The bounds for the variable is provided by constraint g 1 and g 2 . The upper bound for is provided by g 5 , lower bound by g 6. The variables is also not required because the schedule encoded in a string is known and thus it is simple to find which transfers were made. Thus constraints g 3 and g 4 are also eliminated . The constraint g 11 is used to eliminate one of the n i variables . Thus we are left with only g 7 . This revised formulation can be used to determine the optimal solution using Penalty methods in satisfying the constraints ( Chakroborty , Deb, & Sharma, 2001).

13. String A string is concatenation of several substrings There will be as many substrings as number of variables Number of bits in a string is governed by level of accuracy required The upper bound and lower bound of substrings can be defined

14. String n 1 is the first substring s 1 is the second substring The third substring is s i = for all k Number of variables is r is the number of routes No substring for is required

15. n i , s i and strings are decoded n i is checked for its range Only first n i number of are decoded and rest are ignored Last head way for each route is computed based on sum of all headway which should be equal to scheduling period and checked if it is in permissible range Thus the entire schedule can be determined The objective function and rest of constraints can be calculated If a constraint is not satisfied, a heavy penalty is assigned to the string Evaluation of Strings

16. Example ( Chakroborty , Deb, & Sharma, 2001) Scheduling is done for a single transfer station Number of routes, r=3 Total fleet size, N=30 Scheduling time period, H=240 minutes Minimum fleet size=5 Policy headway is assumed to be proportional to demand Percentage of total demand Policy headway ( mins ) 5-15 56 15-25 47 25-45 40 45-60 35 >60 31

17. Example (contd.) Minimum stopping time=2mins Maximum stopping time=5mins Headway range=32mins Maximum transfer time=30mins =300, for all routes Arrival pattern is triangular with =0.8

18. GA parameters Population size =800 Maximum number of generations =800 Cross over probability = 0.95 Mutation probability = 0.005 Example (contd.) Variable Number of bits Fleet size 4 Headway 5 Stopping time 2

19. Example (contd.) Objective function with only IWT term Case 1 Equal Demand on all routes Theoretical optimum fleet size for each route is 10 Theoretical global optimum objective function value=3456mins Source: ( Chakroborty , Deb, & Sharma, 2001)

20. Example (contd.) Case 2 Demand ratio among routes=1:4:9 Theoretical fleet size allocation should be in the ratio 1:2:3 Optimum objective function value=13825mins Source: ( Chakroborty , Deb, & Sharma, 2001)

21. Objective function with both IWT and TT This problem can not be solved by using traditional optimisation techniques Case 1 Demand ratio is 1:4:4 Example (contd.) Source: ( Chakroborty , Deb, & Sharma, 2001)

22. Case 2 Demand ratio 1:4:9 Example (contd.) Source: ( Chakroborty , Deb, & Sharma, 2001)

23. Example (contd.) Variables IWT+TT IWT only Fleet size distribution 8:11:11 7:12:11 Number of matches 8 1 Comparison for Demand ratio 1:4:4 Variables IWT+TT IWT only Fleet size distribution 7:11:12 6:10:14 Number of matches 7 2 Comparison for Demand ratio 1:4:9

24. Chakroborty P , Das. A. (2003). Principles of Transportation Engineering. New Delhi: Prentice Hall of India. Chakroborty , P., Deb, K., & Sharma, R. K. (2001). Optimal fleet size distribution and scheduling of transit systems using genetic algorithms. Transportation Planning and Technology , 24.3 , 209-225. Chakroborty , P., Deb, K., & Subrahmanyam , P. S. (1995). Optimal Scheduling of Urban Transit Systems using Genetic Algoritms . Journal of Transportation Engineering , 544-553. Deb, K. (2006). Optimization for Engineering Design. New Delhi, India: Prentice Hall of India Private Limited. References

25. Thank You