ABSTRACT Title of Thesis: BUS NETWORK SCHEDULING WITH GENETIC ALGORITHMS AND SIMULATION Name of Degree Candidate: Park, Seong Jae Degree and Year: Master of Science, 2005 Thesis Directed By: Professor Paul M. Schonfeld Department of Civil and Environment Engineering This thesis investigates the costs associated with a bus scheduling problem in an urban transit network for both deterministic and stochastic arrival processes and proposes computerized models for each. A simple genetic algorithm (SGA) with some problem-specific genetic operators is developed for the deterministic arrival process and a simulation-based genetic algorithm (SBGA) is developed for the stochastic arrival process. The new models are applied to an artificial bus network to test their efficiency. Several sensitivity analyses and a goodness test are conducted for each arrival process. The results show that the SGA model can find the optimized solution very quickly when it uses problem-specific operators such as the coordinated headway generator, coordinated headway crossover and coordinated headway mutation. They also show that the SBGA model can find a good solution even though it uses general genetic operators. BUS NETWORK SCHEDULING WITH GENETIC ALGORITHMS AND SIMULATION By Park, Seong Jae Thesis submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Master of Science 2005 Advisory Committee: Professor Paul M. Schonfeld Professor Gang-Len Chang Assistant Professor Kelly Clifton ? Copyright by Park, Seong Jae 2005 ii Dedication TO MY MOTHER, WIFE, AND DAUGHTER FOR THEIR UNDITIONAL LOVE iii Acknowledgements I wish to thank many people that have given me their help and support for this work. I sincerely hope not to leave anyone out, but for those not mentioned I wish to extend my gratitude. First, I wish to gratefully thank my advisor, Dr. Paul M. Schonfeld, for his support and guidance thorough the development of this thesis. His technical and editorial advice was essential to the completion of this thesis. Secondly, thanks are due to the other members of my advisory committee: Dr. Gang-Len Chang and Dr. Kelly Clifton for their invaluable comments and suggestions on this thesis. To my colleagues, and friends, thank you for their understanding, and help during my study. To my mother, wife, and daughter, thank you for your endless love, support, and encouragement. iv Table of Contents Dedication..................................................................................................................... ii Table of Contents......................................................................................................... iv List of Tables ............................................................................................................... vi List of Figures............................................................................................................. vii Chapter 1: Introduction.................................................................................................1 1.1 Problem Statement.......................................................................................... 1 1.2 Research Objectives........................................................................................ 3 1.3 Scope............................................................................................................... 4 1.4 Organization.................................................................................................... 4 Chapter 2: Literature Review........................................................................................ 5 2.1 Quantitative studies of bus scheduling problems............................................ 5 2.2 Genetic algorithm applications for transit network problems......................... 9 2.3 Summary....................................................................................................... 12 Chapter 3: Model Formulation.................................................................................... 13 3.1 Deterministic Arrival Process....................................................................... 18 3.1.1 Analytic Approach............................................................................. 18 3.1.2 Headway Optimization Model........................................................... 21 3.2 Stochastic Arrival Process ............................................................................ 26 3.2.1 Analytic Approach............................................................................. 26 3.2.2 Slack Time Optimization Model........................................................ 33 Chapter 4: Genetic Algorithm..................................................................................... 36 4.1 Initial Population........................................................................................... 38 v 4.2 Fitness Function............................................................................................ 39 4.3 Reproduction................................................................................................. 40 4.4 Crossover ...................................................................................................... 41 4.4.1 Simple Crossover............................................................................... 42 4.4.2 Two-point Crossover ......................................................................... 43 4.4.3 Coordinated Headway Crossover ...................................................... 44 4.5 Mutation........................................................................................................ 44 4.5.1 Uniform Mutation .............................................................................. 45 4.5.2 Coordinated Headway Mutation........................................................ 45 4.6 Elitism........................................................................................................... 46 Chapter 5: Case Study and Analysis........................................................................... 47 5.1 Deterministic Case........................................................................................ 51 5.1.1 Numerical Results and Sensitivity Analysis...................................... 51 5.1.2 Goodness Test.................................................................................... 60 5.2 Stochastic Case ............................................................................................. 62 5.2.1 Numerical Results and Sensitivity Analysis...................................... 62 5.2.2 Goodness Test.................................................................................... 73 Chapter 6: Conclusions and Recommendations ........................................................ 76 6.1 Conclusions................................................................................................... 76 6.2 Recommendations for Further Research....................................................... 79 References................................................................................................................... 81 vi List of Tables Table 3.1 Variable definitions 16 Table 3.2 Example of stochastic effect on simple network 34 Table 4.1 Example of a scaling window 40 Table 5.1 Baseline parameter values for numerical analysis 50 Table 5.2 O/D demand ratio matrix for example network 50 Table 5.3 Genetic parameters of SGA for the example network 51 Table 5.4 Results of SGA model for the case study 52 Table 5.5 Resulting components of the total cost for the deterministic case 53 Table 5.6 Genetic parameters and operators in other scenarios 54 Table 5.7 Results of scenario 1 55 Table 5.8 Results of scenario 2 55 Table 5.9 Optimized headways and total costs for different vehicle operating costs 57 Table 5.10 Optimized headways and total costs for different waiting time values 58 Table 5.11 Optimized headways and total costs for different demand ratio 59 Table 5.12 Parameters of SBGA for the example network 64 Table 5.13 Results of SBGA model for the case study 65 Table 5.14 Resulting components of the optimized total cost for the stochastic case 66 Table 5.15 Transfer cost for different slack times of s9 67 Table 5.16 Optimized slack times and total costs for different ratio of standard deviation 70 vii List of Figures Figure 3.1. Structure of total cost for coordinated network operation........................ 15 Figure 3.2 Waiting times at transfer center................................................................. 20 Figure 3.3 Noisiness of the total system cost function ............................................... 22 Figure 3.4 Basic network configuration for SGA....................................................... 24 Figure 3.5 SGA implementation procedure................................................................ 25 Figure 3.6 Inter-cycle waiting time at transfer center................................................. 28 Figure 3.7 Cases of missed connections with common headways ............................. 29 Figure 3.8 Cases of dispatching delay with common headways ................................ 31 Figure 3.9 Simple bus route for the example of the effect of stochastic process ....... 34 Figure 3.10 SBGA implementation procedure ........................................................... 35 Figure 4.1 Stochastic universal sampling ................................................................... 41 Figure 4.2 Simple crossover ....................................................................................... 42 Figure 4.3 Two-point crossover.................................................................................. 43 Figure 5.1 Network configuration for case study 1 .................................................... 48 Figure 5.2 Network configuration for case study 2 .................................................... 49 Figure 5.3 Minimum total cost through successive generations in SGA.................... 53 Figure 5.4 Optimized headways vs. vehicle operating costs ...................................... 57 Figure 5.5 Optimized headways vs. waiting time values............................................ 58 Figure 5.6 Optimized headways vs. demand ratio...................................................... 59 Figure 5.7 Distribution of total cost for the random sample by SGA......................... 61 Figure 5.8 Slack times in the example network.......................................................... 63 viii Figure 5.9 Minimum total cost through successive generations in SBGA................. 66 Figure 5.10 Transfer costs vs. slack time s9 ............................................................... 68 Figure 5.11 Optimized mean slack time and total cost vs. standard deviation ratio... 71 Figure 5.12 Slack time vs. standard deviation ratio on link 3..................................... 72 Figure 5.13 Distribution of total cost for the random sample by SBGA .................... 73 Figure 5.14 Normal probability plot for the random sample by SBGA ..................... 74 1 Chapter 1: Introduction 1.1 Problem Statement In urban areas the demand for buses is unevenly distributed over space and time. It is usually impractical to directly connect all origin-destination pairs with bus routes due to limited economic and social resources. In such cases a bus transit network with limited accessibility and mobility is effective in serving the demand and consists of several bus routes and transfer centers. In a bus network there is an additional transfer time at transfer centers in addition to in-vehicle time and waiting time at bus stops. In operating a bus network, headway is a key factor to consider in bus scheduling, and the safety factor built into schedules, called ?slack time?, is another key factor when vehicle arrival process is stochastic, since both (headway and slack time) are crucial decision variables affecting total system cost. The headway of a route directly affects the waiting time of passengers at bus stops and the time spent at transfer terminals. Several studies show that coordination of headways among routes can minimize the total system cost of bus operation, which includes operator cost and user cost. Slack time can help reduce the probability of missed connections and reduce expected waiting time at transfer centers. However, excess slack time in a route schedule can worsen travel time and increase total waiting time. It is known from the previous research that slack time is sensitive to the demand, the distribution of 2 headways (e.g. normal distribution, exponential distribution, etc) and their standard deviation. 14, 23 As a result, it is also very important to optimize slack times in bus network scheduling in order to minimize connection (or waiting) time among routes and total system cost. Several methods in previous research have been proposed to solve bus network scheduling problem. The main objective of previous methods can be summarized as finding optimized headways and slack times, and thus minimizing the total system cost. Even though the past methods had their own strong points, they also had limitations because there are many sources of complexity on the bus scheduling problem such as non-linearity of the cost functions, computation complexity of objective function, which is usually based on network scale, and various stochastic vehicle arrival processes. This thesis aims to relax some limitations of previous research and to introduce two new models for the bus scheduling problem. The models proposed in this study can reflect dynamic arrival effects resulting from stochastic arrival processes, allow different slack times in each direction of a route at transfer centers, and analyze a multiple transfer network mixed with fully-coordinated, semi- coordinated, and off-phased transfer. To develop new models for the bus scheduling problem this research uses genetic algorithms (GAs) and computer simulation. A simple genetic algorithm (SGA) with some problem-specific genetic operators is used in deterministic arrival process and a simulation-based genetic algorithm (SBGA) in stochastic arrival process. In SGA genetic operators are focused on searching for optimized headways. 3 On the other hand, in SBGA genetic operators are used to optimize slack times and computer simulation is used to calculate statistical estimators of headway distributions under stochastic arrival processes, which are the key elements to evaluate fitness function of SBGA. As a result, two computerized models, SGA and SBGA, are introduced in this study to search for optimized solutions of the bus scheduling problem. 1.2 Research Objectives The objective of this study is to develop new computerized optimization models for the bus scheduling problem in a coordinated bus network, namely, new models to find optimized bus headways and slack times. In the new models bus headways are optimized first under the deterministic arrival process, and then slack times are introduced to optimization problem for the stochastic arrival processes with a dispatching strategy that a bus arriving at transfer center earlier than its departure time leaves on time, regardless of the arrival time of passengers transferring from other routes. The objective function of the proposed models is the minimization of total system cost which is the combination of operator cost and user cost. Operator cost is determined from the fleet size and travel time of a vehicle, and user cost consisting of user in-vehicle and waiting time cost is a function of the in-vehicle travel time and headways of buses. 4 1.3 Scope The scope of this study is limited to developing two computerized models for optimization of bus scheduling. Two models, SGA and SBGA, using GAs and computer simulation are applied to this study, which are designed to optimize bus scheduling under deterministic and stochastic arrival processes, respectively. Some of genetic operators are exclusively used for just one model and others are for both models, based on the properties of the problem. 1.4 Organization The remainder of this thesis is divided into five chapters. Chapter 2 reviews the literature on bus scheduling problem characteristics and methodologies and on GA applications to transit network. Chapter 3 defines the formulation for measuring and evaluating the systemic performance of the transit network and develops new computerized models (SGA and SBGA) using genetic algorithms and computer simulation. Chapter 4 introduces GAs and some genetic operators including problem- specific operators. Chapter 5 presents numerical results obtained when the new models are applied to an artificial transit network and explores their sensitivity to the changes in decision variables. A goodness test for the solution is also shown in this chapter. Finally, Chapter 6 presents the conclusions of this study and recommends further research directions. 5 Chapter 2: Literature Review The literature reviewed in this section is divided into the two following categories: quantitative studies of the bus scheduling problem and GA applications for transit network problems. 2.1 Quantitative studies of bus scheduling problems For the past decades, many studies have analyzed the bus scheduling problem and many optimization models have been proposed. Relatively recent studies have focused on the joint analysis of optimized headways and slack times, usually minimizing a total system cost function. Newell (1971) analyzed the dispatching policies for a transit route which a given number of vehicles might be dispatched at any times and the arrival rate of passengers was a given smooth function of time, typically having one or more peaks. He showed that if the capacity of vehicles was sufficiently large to serve all waiting passengers and the number of vehicles was large, then the optimal flow rate of vehicles and the number of passengers served per vehicle, both varied with time approximately as the square root of the arrival rate passengers. If the vehicles had limited capacity, their dispatch schedule would be distorted so that certain vehicles were dispatched as soon as they were full. Salzborn (1972) proposed a mathematical model for the bus scheduling problem. For a given passenger arrival rate, the problem was to determinate the bus 6 departure rate as a function of time. The primary objective of the study was to minimize the number of buses and a secondary criterion was the minimization of the passenger waiting time. The results showed that during the peak period loads represented actual passengers, but at off-peak times the actual loading was much lower. Thus, it was often desirable to reduce the number of buses that was in operation during off-peak periods. Salzborn (1980) also investigated some rules for scheduling a bus system consisting of an inter-town route linking a string of interchanges each of which was the center of a set of feeder routes. He presented the requirements for the inter-town route and feeder route scheduling under pre-determined parameters. Hall (1985) developed a model for scheduling vehicle arrivals at transportation terminals where vehicles were randomly delayed en route and evaluated the optimal slack time when vehicles were delayed according to an exponential probability distribution. The results showed that coordinating arrivals with departures was most important when the headway was large relative to average vehicle delay. Abkowitz et al. (1986) proposed headway control strategies as methods for correcting transit service irregularities and reducing passenger wait times at stops and addressed a particular strategy which could be implemented on high frequency route (headways under 10-12 minutes), in which buses were held at a control stop to a threshold headway. They developed an algorithm which yielded the optimal control stop location and optimal threshold headway with respect to a system wait function. They concluded that the headway variation did not increase linearly along a route and 7 that the location of the optimal control stop and threshold value were sensitive to the passenger boarding profile. ?zekici (1987) formulated an analytic model for analyzing and exploiting the relation between the arrival and service processes, with emphasis on the impact of this relation on average waiting times. The results showed that, when a timetable of the scheduled services is available, the arrival pattern of passengers was not stationary and passengers chose an optimal time to arrive at the bus stop based on the information they had about the timetable and their observation on the service performance. Banks (1990) studied multi-route transit systems to determine net-benefit maximizing headways, which were subjected to constraints on vehicle capacity, subsidy, and fleet size. Conditions of optimality were derived for the unconstrained case and the various constrained cases. The relation between optimality conditions based on the assumption of fixed demand and those based on the assumption of variable demand was expressed with terms incorporating the elasticity of demand with respect to frequency of service. The results showed that the magnitude of discrepancies between the true conditions of optimality and their fixed-demand approximations depended on the elasticity of demand and on the distribution of ridership and cycle times among the various routes of the system. Lee and Schonfeld (1991) developed a numerical model for optimizing slack times for simple systems with transfers between one bus route and one rail line which could work with arrival distributions. Some analytic results were derived for empirical discrete and Gumbel distributions of bus arrival times. Relations between 8 the optimal slack times and headways, transfer volumes, passenger times values, bus operating cost, and standard deviations of bus and train arrivals were also developed numerically using normally distributed arrivals. The results provided some guidelines on desirable slack times and showed that schedule coordination between the two routes was not worth attempting when standard deviations of arrivals exceeded certain levels. Bookbinder and Desilets (1992) analyzed the variation of waiting time of transfer passengers using simulation for the various travel time situations and used mean disutility function to evaluate the inconvenience under random bus travel times. The results showed that it was very important to take randomness of travel times into account when optimizing transfers and that bus travel times could optimize transfers according to various objective functions and under various holding policies. Knoppers and Muller (1995) investigated the possibility and limitations of coordinated transfers in public transit using the minimization of passenger?s transfer time as the objective function. The results showed that optimal transfer times could be defined only if fluctuations in passenger arrival times at the boarding point could be contained within certain time limits and that coordination of timetables was only worthwhile when the punctuality of standard deviation on the feeder line at the transfer point was less than 40% of the connecting line. Ting (1997) studied complex transfer coordination problems by employing basic calculus and optimization algorithms. A total system cost function was used to evaluate the performance of the coordination. Two optimization algorithms were developed for transfer coordination with deterministic and stochastic travel time cases. 9 The author proposed that a common headway search algorithm was applicable for transit networks in which the headways on different routes should be fairly similar and that an integer-ratio headway search approach based on integer multiples of a base cycle was applicable for networks whose headways should be significantly different. 2.2 Genetic algorithm applications for transit network problems There are many GAs applied to various parts of transportation research since it was introduced in 1975, and it is expanding more and more its boundary. Most recent studies using GAs in transit network problem can be found for optimization of route network design in which bus scheduling is usually a part of route optimization function. Chakroborty et al. (1995) investigated the mathematical programming formulation of the bus scheduling problem at one transfer station, whose objective was to minimize the total waiting time, the sum of transfer time of transferring passengers at transfer center and initial waiting time of the passengers waiting to board a bus at their point of origin. The authors also pointed out the limitations of classical programming techniques to solve the problem and developed an optimization model using genetic algorithms with binary coding for decision variables. They assumed that bus arrival times were deterministic. The results showed that the GA-based models were able to find optimal schedules without excessive computational resources. Chakroborty et al. (1998) expanded the mathematical programming 10 formulation of the bus scheduling problem to the multi-transfer network and analyzed the computational complexity of the mathematical formulation that was a NLP problem. They used genetic algorithms to search for the optimal values of bus scheduling on the multi-transfer network under the assumption that bus capacity was much greater than the demand and that bus arrival times were deterministic. Chakroborty et al. (1998) developed a procedure using a GA for designing efficient transit routes forming a transit route network (or route set) for a given road network. The authors showed that the transit route network design problem was a discrete, NP-hard, combinatorial problem with a difficult-to-calculate objective function - features which posed almost unsurmountable difficulties in obtaining a solution through traditional optimization techniques. The results showed that the GA- based method performed substantially better than the existing procedures. Ngamchai (2000) investigated the major components and constraints in bus transit route design and proposed a new model for optimizing bus transit route configuration and service frequencies on each bus route. Three major components were used to obtain an efficient solution; those were route generation algorithm, route evaluation model and route improvement algorithm. The objective function of his paper was to minimize the total system cost, and the author included results of bus scheduling as a part of objective function. He assumed that each route could only be coordinated at one transfer point, thus classified transfer centers into the priority order according to the volume of demand. The author applied GA to the model to search for the optimal routes and introduced many problem-specific genetic operators to facilitate search. 11 Bielli et al. (2002) proposed a heuristic approach based on GA to solve transportation bus network optimization problems. The method involved genetic operators and a number of additional ingredients which allowed to compute fitness function values aggregating the values of a number of performance indicators. They used results of the bus scheduling problem as the performance indicators such as average number of transfers, average waiting time, average traveling time, and average walking time. Chakroborty (2003) summarized the effectiveness of procedures based on genetic algorithm in solving the urban transit network design problem (UTNDP) consisting of two sub-problems, namely, the transit routing problem and the transit scheduling problem and presented the limitations of traditional methods in solving the UTNDP. He suggested that traditional methods had difficulty in solving the transit routing and scheduling problems since the UTNDP had discrete decision variables, and it was a constrained non-linear optimization problem, which was by nature not easily amenable to mathematical programming formulations. To show the effectiveness of GA-based models, the author compared GA-based results with those of some previous researchers for transit routing problem and analyzed five different scenarios using GA for transit scheduling problem V. M. Tom and S. Mohan (2003) proposed a GA-based model, simultaneous route and frequency coded model (SRFC), to solve transit route network design (TRND) problem. SRFC adopted a new coding scheme that incorporated the frequency of the route as a variable in addition to the route details. Some results of the bus scheduling problem in their paper were reused for performance measures: 12 average in-vehicle travel time, average waiting time, and average generalized travel time Jitendra Agrawal et al. (2004) applied GA to TRND problem and proposed two parallel genetic algorithm models. The first was global parallel virtual machine (PVM) parallel GA model where the fitness evaluation was done concurrently in a parallel processing environment using PVM libraries. The second was a global message passing interface (MPI) parallel GA model where an MPI environment substituted for the PVM libraries. They also used results of the bus scheduling problem to evaluate the performance of new models. 2.3 Summary After a review of the above studies, it appears that optimization methods for bus scheduling have already been well developed analytically. However, computerized models for bus scheduling have not been widely introduced. Some models using computer simulation have been applied to simple network scheduling problems or single transfer center optimization problems. Also, in most GA-based network optimization models, the bus scheduling was used just as a part of objective function for route network design problem within the boundary of the previous research. Therefore, this research focused on extending the methodology to more complex situations (e.g. introduction of slack times for all directions at transfer centers), and developing computerized optimization models for the bus scheduling problem using GA and computer simulation. 13 Chapter 3: Model Formulation The methodology in this chapter includes the introduction of analytical formulas and the development of their application models. Analytical approaches are used to formulate cost functions incorporating deterministic and probabilistic vehicle arrival processes, and application models are used to develop computerized models which are intended to search for the optimized solution of the total cost function. Analytical formulas in this study are based on the framework introduced by Ting (1997), and application models are developed using GAs and computer simulation. For application models, simple genetic algorithm (SGA) and simulation- based genetic algorithm (SBGA) are introduced. Both analytical approaches and application models are constructed for coordinated network operation because previous research already showed that the coordinated operation is the best way to minimize the total system cost on the common urban transit network system. Therefore, this study is limited to coordinated networks. Solving the bus scheduling problem means finding the optimized headways for deterministic vehicle arrivals and the optimized headways and slack times (if applicable) for stochastic arrivals. SGA is devised to solve the problem for the deterministic case, and SBGA for the stochastic case. SBGA uses computer simulation to evaluate statistical estimators in the stochastic process. SBGA using computer simulation is slightly problematic because simulation is not only time consuming but also has a variance problem. However, computer simulation can imitate the complex stochastic process and provide estimators in real time, which is 14 the most important point in a computerized optimization model. It is assumed that this work applies to a predetermined network of urban transit (bus) routes. All assumptions of Ting (1997) are also applied to this study as stated below: 1. The present analysis does not consider the issue of route location, stop spacing, and service for particular routes and time periods. 2. The origin-destination matrix is given, and is assumed to be (1) independent of transit service quality, (2) deterministic and uniformly distributed over time during the specific time period. 3. Passenger arrivals are random and uniformly distributed over time at each bus stop. 23 In the next two sections, the methodology for deterministic and stochastic bus arrival processes is presented. Figure 3-1 shows the structure of the total cost for the coordinated network operation. Total cost includes non-transfer and transfer cost. Non-transfer cost includes vehicle operating cost, passenger waiting cost, passenger in-vehicle cost and layover cost, and transfer cost includes inter-cycle delay cost, slack time cost, missed connection cost, and dispatching delay cost. Table 3-1 shows the notation for variables used in this chapter. 15 Figure 3.1. Structure of total cost for coordinated network operation Total Cost Non-Transfer Cost Transfer Cost Vehicle Operating Cost User Waiting Cost User in-vehicle Cost Inter-cycle Delay Cost Slack Delay Cost Missed Connection Cost Layover Cost Dispatching Delay Cost 23 16 Table 3.1 Variable definitions Variables Descriptions Units a k fixed vehicle operating cost of route k $/min. b k variable vehicle operating cost of route k $/min. B k vehicle operating cost $/min. C d connection delay cost of transfer passengers $/min. C f transfer cost $/min. C l layover time cost $/min. C m missed connection cost for transfer passengers $/min. C o operating cost $/min. C p inter-cycle transfer delay cost due to unequal integer-ratio headway $/min. C s slack delay cost $/min. C Tdet total system cost in deterministic arrival headways $/min. C Tsto total system cost in stochastic arrival headways $/min. C v in-vehicle cost $/min. C w waiting cost $/min. D mk number of passengers already on board at transfer center m on the direction  of route k passengers/min. f(t k ) probability density function of arrival time on the direction  of route k F mk transfer demand to direction  of route k at transfer center m passengers/min. g jk greatest common divisor of  j and  k h k headway of route k min. h kmax maximum headway of route k min. h kmin minimum headway of route k min. i index of link j, k index of route k l max maximum load factor of route k N(c) set of transfer nodes m index of transfer center 17 q jk transfer demand from route j to route k passengers/min. q jk transfer demand from the direction  of route j to the direction  of route k passengers/min. Q i demand of link i passengers/min. Q k demand of route k passengers/min. Q km maximum demand on route k passengers/min. S k vehicle size of route k seats s mk slack time at the transfer center m on the direction  of route k min. s mkmax maximum slack time at the transfer center m on the direction  of route k min. s mkmin minimum slack time at the transfer center m on the direction  of route k min. t i travel time on link i min. t i travel time on the direction  of link i min. t j arrival time on the direction  of route j at transfer center t jk average transfer waiting time from route j to k min. t jk average transfer waiting time from the direction  of route j to the direction  of route k min. t k arrival time on the direction  of route k at transfer center T k round trip time of route k min. t kl layover time of route k min. t kl layover time change of route k min. w k transfer waiting time on route k min. y base cycle min. ,  direction of bus on round trip (0, forward direction; 1, backward direction)  j integer for headway of route j on base cycle (=h k /y)  mk 1, if transfer station m is on route k; 0, otherwise  k 2 variance of headway on route k ? unit waiting time cost passengers/min.  unit in-vehicle cost passengers/min. 18 3.1 Deterministic Arrival Process Under the deterministic arrival process, the link travel times and route headways are deterministic and all buses arrive at the stop on schedule. In this case it doesn?t need to introduce slack times to bus scheduling. The objective is to find the optimized headways in the network to minimize the total system cost which includes bus operating cost, user waiting cost, user in-vehicle cost, user transfer cost and layover cost. 3.1.1 Analytic Approach In this deterministic situation it is assumed that the travel times of two links connecting two nodes are equal. The round trip time at each route k is the summation of travel times of all the links on route k. = )(kAi ik tT (3.1) The linear vehicle operating cost function and the vehicle capacity constraint used here are given by: kkkk SbaB += (3.2) k kk k l hQ S = (3.3) The average operating cost of route k is the product of the needed fleet size and the unit operating cost. The total operating cost is determined as: 19 = k k kk o h TB C (3.4) It is assumed that passengers arrive at stops randomly and uniformly, so the average waiting time at the origin stop is half of the route headway. The total waiting cost is = k k kw h QC 2 ? (3.5) The in-vehicle cost of link i is the product of passenger demand and in-vehicle time on each link. The total in-vehicle cost is = i iiv tQC  (3.6) The transfer waiting cost is the summation of transfer demand times transfer waiting times at the transfer centers. It is assumed that the average transfer time from route j to route k is t jk . The total transfer cost is computed as: = jk k jkjk j f tqC ? (3.7) In a transit network a passenger can transfer multiple times. For simplicity the maximum number of transfers is limited in this study to three times per one-way passenger trip. Figure 3.2 shows examples of the average transfer waiting times when using one, two and three transfers. 20 h 1 h 1 j t jk from j to k = h 1 /2 2 h 1 k (h: headway) a) Using one transfer (A) from route j to k h 1 h 1 h 1 j 3/2 h 1 3/2 h 1 k t jk from j to k = h 1 /2 3h 1 l t jl from j to l = h 1 b) Using two transfers (A, B) from route j to l h 1 h 1 h 1 h 1 j 4/3 h 1 4/3 h 1 4/3 h 1 k t jk from j to k = h 1 /2 2 h 1 2 h 1 l t jl from j to l = h 1 4 h 1 m t jm from j to m = 3h 1 /2 c) Using three transfers (A, B, C) from route j to m (h: headway, s: slack time, Transfer center: A(j-k), B(k-l), C(l-m)) Figure 3.2 Waiting times at transfer center 21 For the coordination among bus headways at the transfer center, the layover time of route k (t kl ) is assumed, which is the extra service time at the end stop of route k. The total layover cost is = k k kl kl h t BC (3.8) In the deterministic arrival process, the total system cost is the sum of equations (3.4)-(3.8). lfvwoT CCCCCC ++++= det (3.9) 3.1.2 Headway Optimization Model It is difficult to solve equation (3.9) with traditional optimization methods for the networks of realistic size. Therefore, heuristic algorithms have usually been used to search for the optimized headways in most previous studies. Figure 3.3 demonstrates the ?noisiness? of the total system cost function which has many local optimal solutions in a simple one-way bus network. There are two bus routes on the example network which consists of two origins (1&2) and destinations (A&B). Total system costs are evaluated numerically for the all integer values within the range (from minimum to maximum) of headways. The maximum and minimum headways of this study are computed as: )2,max( max max km k k Q lS h = (3.10) )2, 4 max( max min k k h h = (3.11) 22 B 1 A 2 a) Network geometrics for two one-way routes b) Total costs vs. headways for two one-way routes Figure 3.3 Noisiness of the total system cost function Demand: 1-A (160), 1-B(40) 2-A (40), 2-B(60) Travel Time (min): 1-A(60), 2-B(50) Optimum Solution (min): (12,12) 23 For the deterministic arrival process this study uses a GA to develop a headway optimization model, called a simple genetic algorithm (SGA). This SGA has seven steps in its procedure: initialization, population, reproduction, crossover, mutation, next population, and stopping criteria. The initialization proceeds as follows: 1. Optimize headways independently for each route. 2. Rank the routes by sorting them in the order of increasing headway. 3. Identify the main route which has the most transfer centers along it, or which has the lowest optimum headway, if needed to break ties. 4. Classify each transfer center as a fully coordinated transfer center, a semi- coordinated transfer center, or a general transfer center. - Fully coordinated transfer center: where the largest number of routes meets, or where the main route meets the second route in the sorted order if the number of routes crossing at transfer centers is same. - Semi-coordinated transfer center: where the main route meets other routes - General transfer center: where routes than the main one meet (usually, off-phased transfer center) 5. Assign travel demand on the links according to the shortest path on the basic network. Figure 3.4 shows basic network configuration for the SGA model and figure 3.5 illustrates the procedure of the SGA implementation. The genetic algorithm and GA operators used in this study will be explained in detail in chapter 4. 24 Figure 3.4 Basic network configuration for SGA 1 6 5 3 4 2 Route I Route II Route III [9] ( , ) [8] ( , ) [7] ( , ) [4] ( , )[1] ( , ) [2] ( , ) [5] ( , ) [3] ( , )[6] ( , ) ::: : A ::: : B ::: : C Legend : Demand on Origin 1,2,3,4,5,6: Origin or Destination number [1](15,1.2): Link number, Link travel time, Standard deviation ::: : A , ::: : B , ::: : C : Transfer center 25 Figure 3.5 SGA implementation procedure Population Reproduction Crossover Mutation Next population Stop ? End Begin No Yes Initialization 26 3.2 Stochastic Arrival Process In the stochastic case, the vehicle operating cost, passenger waiting cost, and in-vehicle cost are the same as in the deterministic case. However, the transfer cost is different because slack time is introduced in the stochastic case. Slack time is the additional dwelling time of a bus at a transfer center to facilitate passenger transfer and to reduce the probability of missed connections. Thus it can reduce the expected waiting time at transfer and decrease the total cost. It is sensitive to passenger demand and the distribution of bus arrival pattern, so its value differs among routes, among bus stops on a route and among directions of routes at a transfer center. Therefore, the total transfer cost function includes all cost components that result from the slack time and headway. Those are the slack delay cost, inter-cycle delay cost, missed connection cost, and dispatching delay cost. There is also layover time change cost in stochastic process for the change of layover time by the addition of the slack time. 3.2.1 Analytic Approach The slack delay cost includes the user time cost of passengers on board and supplier cost for slack time. The slack delay cost is given by: ++= k mkmk k k mkmk cNm s s h B FDC ?  )( )( (3.12) The first term is the slack time delay cost to passengers already on board and the second term is the waiting cost for transfer passengers to route k. The last part is the increased vehicle operating cost for the slack time. 27 In a stochastic process, the average waiting time includes the difference of the slack time between two routes, thus the average transfer waiting time between routes involved in a transfer is a little different from the deterministic case. Figure 3.5 illustrates examples of the average transfer waiting time when using one, two, or three transfer centers. It is assumed that the average transfer waiting time from the direction  of route j to the direction  of route k is t jk . The inter-cycle delay cost is the summation of all the routes connecting at the transfer centers.  ? jkjk jk kj p tqC = (3.13) Only one dispatching strategy is considered at the transfer center, which is that vehicles do not wait for other vehicles arriving behind schedule, and vehicle arrivals are independent among routes. It is also assumed that passengers can transfer to the coordinated receiving vehicle at transfer center when bus routes have not only common but also integer-ratio headways between them, and that the link travel times on a route are independent. The probability of missed connections includes following two cases: (1) the feeder vehicle j arrives late while the receiving vehicle k is not late and (2) both vehicles are late, but feeder vehicle j arrives after receiving vehicle k leaves. 23 Figure 3.6 shows two cases of the missed connections from route j to k with common headways. 28 (h: headway, s: slack time, Transfer center: A(j-k), B(k-l), C(l-m)) t jk from route j to k = 1/2 h 1 + s 1 - s 2 (through one transfer center A) t jl from route j to l = h 1 + s 1 - s 3 (through two transfer centers A and B) t jm from route j to m = 3/2 h 1 + s 1 - s 4 (through three transfer centers A, B, and C) Figure 3.6 Inter-cycle waiting time at transfer center F(t) F(t) F(t) F(t) h 1 h 1 h 1 h 1 j tim tim tim tim s 1 4/3 h 1 4/3 h 1 4/3 h 1 s 2 s 3 s 4 2 h 1 2 h 1 4 h 1 k l m 29 Figure 3.7 Cases of missed connections with common headways F(t) F(t) F(t) F(t) time k time j time s mk k h k times mj j h j s mk s mj h k s mk h j s mj t j s mj s mk +t j -s mj s mk 30 The missed connection cost, C m , can be classified into two cases (i.e., common and integer headways between route j and k), and it is determined as:   +  ++ +=       ? mkmjj mk j mj mk k j mj sst s jjkkmkmjjk h s s h jjkkmjjmkk h s mkmjjk jk kjcNm m dttfdttfssth dttfdttfstshqC ])()()( )()()([ )( (3.14 a) for common headways, and   +  ++ +=       ? mkmjj mk kj mj mk k j mj sst s jjkkmkmjjk hh s s h jjkkmjjmkk h s mkmj k jk jk jk kjcNm m dttfdttfssth dttfdttfstsh h yg qC ])()()( )()()([ ],min[ )( (3.14 b) for integer-ratio headways. The connection delay cost, C d , is the additional waiting cost of passengers who arrive at transfer center before the departure time of the connecting bus but the connecting bus arrives behind schedule. The probability of dispatching delay includes the following two cases regarding the two vehicles involved in a connection: (1) the feeder vehicle j arrives early while the receiving vehicle k is late and (2) both vehicles are late, but feeder vehicle j arrives before the receiving vehicle k. 23 Figure 3.7 shows the cases of the dispatching delay with common headways at the transfer center. 31 Figure 3.8 Cases of dispatching delay with common headways F(t) F(t) F(t) F(t) time j time k time j h j time k h k h j h k s mj s mj s mk s mk s mj t j s mj s mk s mk +t j -s mj s mk 32 The dispatching delay cost is given by:   ++  ++ = k mjmkj j mj mj j k mk h sst jjkkmkjmjk h s s h kkjjmkk h s mkmjjk jk kjcNm d dttfdttfstst dttfdttfstqC      ? ])()()( )()()([ )( (3.15a) for common headways, and   ++  ++ = k mjmkj kj mj mj j k mk h sst jjkkmkjmjk hh s s h kkjjmkk h s mkmj k jk jk jk kjcNm d dttfdttfstst dttfdttfst h yg qC      ? ])()()( )()()([ ],min[ )( (3.15 b) for integer-ratio headways. The layover time change cost, C l , accounts for the change of layover time at the end of a route which is occurred by the addition of slack time, and it can be a negative or positive value according to the size of slack time. The layover time change cost is given by:  =  k k kl kl h t BC (3.16) In the stochastic arrival process, the total system cost is the sum of equations (3.12)-(3.16): ldmpslvwoTsto CCCCCCCCCC  ++++++++= (3.17) 33 3.2.2 Slack Time Optimization Model The total system cost function (Eq. 3.17) is too complex for finding the optimized solution (i.e., the optimized headways and slack times) with an analytical approach. Ting (1997) used a numerical integration method to compute transfer delays, but that method also cannot be easily transferred to a computerized model which has to be able to evaluate the results of stochastic arrival process in real time. The second computerized optimization model, called a simulation-based genetic algorithm (SBGA), is developed using computer simulation and a genetic algorithm. Computer simulation is used here because it can provide statistical estimators resulting from the complex stochastic arrival process in real time. To illustrate the complexity/effect of stochastic arrival process, figure 3.8 shows a simple bus route with four links whose travel times and standard deviations are the same on all links and normally distributed. Table 3.2 shows the results of the average arrival time (M) at the end of each link and its standard deviation (SD) with the various slack times applied. Even when the slack time is 0, average arrival times at the bus stops B, C, and D are not just the sum of the link travel times because a bus arrival before the departure time has to wait to depart on time. At 0 slack time, the average arrival times and their standard deviations are increasing when the buses approach the last stop (D) of the route although the link travel times are independent. As slack time increases the average arrival times at each bus stop also increase due to the additional delay from the slack time, but standard deviations are diminishing because slack times can help buses depart on-time. As the slack time increases, the 34 average arrival time at a stop approaches the sum of link travel times and slack times, and its standard deviation becomes the same as the standard deviation at all bus stops. That situation starts to occur when the slack time reaches 2 minutes in table 3.2. Figure 3.9 Simple bus route for the example of the effect of stochastic process Table 3.2 Example of stochastic effect on simple network Bus Stop A B C D Slack Time (min) M SD M SD M SD M SD 0.0 20.00 1.001 40.40 1.158 60.68 1.303 80.91 1.434 0.5 20.00 1.000 40.70 1.083 61.30 1.140 81.86 1.183 1.0 20.00 1.001 41.08 1.033 62.11 1.049 83.12 1.055 2.0 20.00 0.999 42.01 1.002 64.01 1.002 86.01 1.004 Situations become much more complex when the bus network is large, many transfer centers are located in the network, and each route has a different slack time for each direction at a transfer center. Therefore, computer simulation is applied here in spite of its limitations to simulate those situations. 1(20, 1) 1) (20, 1) 3 (20, 1) 4 (20, 1) 1) Link number (Link travel time (min), Standard deviation) A B C DO 35 The results of SGA (i.e., headways) are used as the basic parameters for SBGA to search for optimized slack times because example tests showed that the stochastic vehicle arrival process does not change the optimized headways from SGA. Simulation is applied to evaluate the missed connection and dispatching delay time in coordinated transfer, and transfer delay time in off-phased transfer within SBGA. Figure 3.9 shows the procedure of the SBGA implementation. Figure 3.10 SBGA implementation procedure Population Reproduction Crossover Mutation Next population Stop ? Begin End Fitness function computation Slack times & Headways Simulation Total Cost Yes No 36 Chapter 4: Genetic Algorithm A Genetic Algorithm (GA) may be described as a mechanism that imitates the genetic evolution of species. It was first introduced by Holland in 1975 and getting increasingly powerful since then. Now, it is the most widely known type of evolutionary computational methods. GA is a local search algorithm, which works starting from an initial collection of strings (or a population) representing possible solutions of the problem. Each string of the population is called a chromosome, and has associated a value called fitness function that contributes in the generation of new populations by means of genetic operators (denoted reproduction, crossover and mutation, respectively). At each generation, the algorithm uses the fitness function values to evaluate the survival capacity of each string i of the population using simple operators in order to create a new population which try to improve on the current fitness function values by using pieces of the oldest ones. Maurizio et al. (2002) described the differences between GA and other local search techniques as follows: 1. GA operates with codes of the parameter set and not with the parameters themselves; 2. GA searches for a population of points and not a single point; 3. GA uses objective function information and not derived or auxiliary knowledge; 4. GA uses probabilistic transition rules and not deterministic ones. 15 37 These particular aspects make this method applicable in a very general way, without the limitations imposed by other local search methods (i.e., continuity, derivative existence, uni-modality). Moreover, it makes possible exploiting consequent information from more points in the dominion of the solutions, reducing the probability of finding false peaks, i.e., traps or local optima. Chakroborty et al. (1998) pointed out that the bus scheduling problem was a nonlinear, mixed-integer program and that the traditional algorithms for solving nonlinear, mixed-integer programming problems were rare and not efficient, especially when the number of variables and constraints was large. They suggested that the number of variables and constraints in the original NLP formulation was O(sr 2 n 2 ) for a transit network having s transfer stations, r routes passing through each station, and n transit vehicles plying on each route. 5 From the previous studies, we can find that methods to solve bus scheduling problems in multi transfer network are very limited by the complexity of the problems. In this study, there are many sources of complexity in the bus scheduling problem, such as nonlinearity, noisiness, discreteness, and non-convexity of the objective functions (i.e., Eq. 3.9 & 3.17). As a result, a straightforward mathematical programming approach cannot achieve satisfactory results. In previous studies, most optimization models for the bus scheduling problem in multiple transfer networks used heuristics based on artificial intelligence. There are several well-known heuristic methods in artificial intelligence, such as tabu search, simulated annealing, genetic algorithms, and neural networks. Each of them has its inherent strengths and weaknesses (e.g., excessive computing time in simulation annealing) and limitations 38 for application to a specific problem. Therefore, it is very desirable to choose a method which is suitable for the properties of the problem considered. Based on the strengths and weaknesses of the potential methods, a GA was selected here for the bus scheduling optimization. It should also be noted that previous related studies (Tom & Mohan, Ngamchai & Lovell) have chosen the GA approach for similar problems. The application of GA to a specific problem includes several steps. The procedure of SGA and SBGA using GA are shown in figure 3.4 and 3.9 in chapter 3. In the next six sections, GA components such as initial population, fitness function, reproduction, crossover, mutation, and elitism will be presented. 4.1 Initial Population Generating initial population is to construct an initial collection of strings of which individual is a chromosome, a set of headways or slack times. A chromosome should in some way contain information about the solution it represents. For coding of a chromosome this study uses integer values (a set of headways) in SGA and multiples of 0.25 (a set of slack times) in SBGA. The initial population is randomly generated within the range of slack time in SBGA, but in SGA it is coordinated with the headway of the main route which has the largest passenger demand among bus routes on a bus network and several transfer centers on the route. The initial population in SGA is a set of integer multiples of the main route headway. For example, consider two individuals with 5 values (headways or slack times) each: 39 1. Coordinated headways with first value (or headway of route 1) - Individual 1 5 10 15 10 15 - Individual 2 3 3 6 9 9 2. Randomly generated slack times - Individual 1 0.25 0.5 1.0 0.0 0.75 - Individual 2 0.5 0.0 1.5 0.25 0.75 4.2 Fitness Function The fitness function evaluates the fitness of each individual i in the population. We used scaling window method as a fitness function. It transforms the objective function value into a measure of relative fitness, as follows: == )())(()( iii xfxfgxh (4.1) where  = a constant, usually the minimum of f(x) x i = the phenotypic value of individual i . f = the objective function before scaling g = transform the value of the objective function to a non-negative number h = the resulting relative fitness. The individual fitness after scaling, )( i xF , is computed as the individual?s performance, g(f(x i )), relative to the whole population: 40 ))(( ))(( )( )( )( 1 = == N i i i i i i xfg xfg xh xh xF (4.2) where N = the population size. The following table 4.1 shows an example of a scaling window. Table 4.1 Example of a scaling window Before scaling (=0) After scaling (=50) i f(x i ) P(f(x i )) 1) h(x i ) F(x i ) 1 53 0.25 3 0.20 2 54 0.25 4 0.27 3 58 0.27 8 0.53 4 50 0.23 0 0.00 Total 215 1.00 15 1.00 1) P(f(x i )): Percentage of the objective function before scaling 4.3 Reproduction The principle behind GA is essentially Darwinian natural selection. Reproduction (or selection) provides the driving force in GA. With too much force, genetic search will terminate prematurely; with too little force, evolutionary progress will be slower than necessary. Typically, a lower selection pressure is indicated at the start of a genetic search in favor of a wide exploration of the search space, while a higher selection pressure is recommended at the end to narrow the search space. 41 This study uses stochastic universal sampling for reproduction, which is a single-phase sampling algorithm and uses N equally spaced pointers where N is the number of selections required. The population is shuffled randomly and a single random number, P, in the range [0 (Sum of fitness function) /N] is generated. The N individuals are chosen by generating the N pointers spaced by 1, [P 1 , P 2 , ?, P N ], and selecting the individuals whose fitness span the positions of the pointers. To illustrate this selection process, consider the situation shown in figure 4.1. Figure 4.1 Stochastic universal sampling In the above figure, when N=6, the sum of fitness function=1, and P=0.07, a new population 1, 2, 2, 4, 5, and 6 is selected. 4.4 Crossover Crossover operates on selected values from parent chromosomes and creates new offspring. Simple (or one-point) crossover and two-point crossover are used in SBGA and coordinated headway crossover is used in SGA. 0.20 0.49 0.53 0.66 0.86 1 : 1 : 2 : 3 : 4 : 5 : 6 P 1 P 2 P 3 P 4 P 5 P 6 42 4.4.1 Simple Crossover In simple crossover, one crossover position k[1, 2, ..., N-1], N of the number of variables (or slack times) of an individual, is selected uniformly at random. After that, the variables are exchanged between the individuals about this point, and two new offspring are produced. For example, consider the following two individuals with 5 slack times each: - Individual 1 0.25 0.75 1.25 2.25 2.50 - Individual 2 0.75 0.25 0.25 1.75 2.25 When the chosen crossover position, k, is 3, the new individuals are created: - Offspring 1 0.25 0.75 1.25 | 1.75 2.25 - Offspring 2 0.75 0.25 0.25 | 2.25 2.50 Figure 4.2 illustrates this process. Figure 4.2 Simple crossover (Parents) (Children) 43 4.4.2 Two-point Crossover For two-point crossover, 2 crossover positions k i [1,2,...,N-1], i=1 and 2, are chosen at random with no duplicates and sorted in ascending order. Then, the variables between successive crossover points are exchanged between the two parents to produce two new offspring. The section between the first variable and the first crossover point is not exchanged between individuals. For example, consider the following two individuals with 5 slack times each: - Individual 1 0.25 0.75 1.25 2.25 2.50 - Individual 2 0.75 0.25 0.25 1.75 2.25 When the chosen crossover positions, k, is 2 and 4, the new individuals are created: - Offspring 1 0.25 0.75 | 0.25 1.75 | 2.50 - Offspring 2 0.75 0.25 | 1.25 2.25 | 2.25 Figure 4.3 illustrates this process. Figure 4.3 Two-point crossover (Parents) (Children) 44 4.4.3 Coordinated Headway Crossover Coordinated headway crossover is the combination of simple crossover and coordinated headway generator. At first, one crossover position k is selected and the variables are exchanged between the individuals about this point as the case of simple crossover. Secondly, it is checked whether the headways of other routes are multiples of the main route (e.g. route 1). If any route is not coordinated with the main route a new headway is generated for that route as a coordinated value with the main route. For example, consider the following parents with 5 headways each: - Individual 1 2 2 6 6 8 - Individual 2 3 6 9 6 9 When the chosen crossover position, k, is 2, the new individuals are created: - Offspring 1 2 2 | 8 6 6 - Offspring 2 3 6 | 6 6 9 4.5 Mutation The mutation operator plays a secondary role with respect to reproduction and crossover operators. Nevertheless, mutation is needed to prevent an irrecoverable loss of potentially useful information which occasionally reproduction and crossover can cause. Mutation is an occasional random alteration, with small probability, of the headway or slack time. Uniform mutation is used in SBGA and coordinated headway mutation used in SGA. 45 4.5.1 Uniform Mutation In uniform mutation a gene (or slack time), x i , of a chromosome is changed to a new one within its range. A gene is selected for mutation if a random number ( 1 ) is less than the probability of mutation (e.g. 0.2 in SBGA) and a new gene is produced as follows, minminmax2 ))1/)((( iiiinew xxxfx +?+=  (4.4) where x inew = a new slack time of x i  1 ,  2 = a random number  = gap of slack time (=0.25) f = a function for round-down to integer x imin , x imax = the lower and upper bound of the slack time, respectively. For example, consider the following individual with 5 slack times: - Individual x 0.25 0.75 1.25 2.25 2.50 When the chosen mutation position is third (x i =3),  2 is 0.5, x imin is 0, and x imax is 3, the new offspring is created: - New offspring 0.25 0.75 1.5 1) 2.25 2.50 1) f(0.5*(3/0.25+1))*0.25+0 = f(6.5)*0.25 = 1.5 4.5.2 Coordinated Headway Mutation Coordinated headway mutation is developed to facilitate the search for the optimized headways, based on the fact that the optimized headways are integer 46 multiples of the main route headway. A gene (or headway) selected for uniform mutation is changed into a new gene, which is one of the integer multiples of the main route headway. For example, consider the following individual with 5 headways: - Individual x 3 3 6 6 9 When the chosen mutation position is third, x main is 3, x imin is 2, and x imax is 11, the candidates for x inew are 3, 6, and 9 and the third headway is changed from 6 to 3. - New offspring 3 3 3 6 9 where x imax , x imin = the upper and lower bound of headway, x i , respectively x main = the headway of the main route x inew = a new headway of x i . 4.6 Elitism Once a new population has been produced by reproduction, crossover and mutation of individuals from the old population, the fitness of the individuals in the new population may be determined. However, there is no guarantee that the best fitness of the new population is better than that of parents. Elitism is used for the best individual in the previous generation to be deterministically allowed to propagate through successive generations. Therefore, the least fit individual in the new population is replaced by the best fit individual in the previous generation. 47 Chapter 5: Case Study and Analysis The objective of this chapter is to illustrate the applicability and reasonableness of the new models. Two computerized models, SGA and SBGA, developed in chapter 3 are applied to an artificial bus network for case study. Deterministic case of bus arrival process is presented in section 5.1 and stochastic case in section 5.2. At each section, numerical results and sensitivity analysis are presented first and a goodness test for the best solution resulted from the new model is then conducted. The goodness tests used in this chapter follow the method proposed by Jong (1998). The network configurations for the case study are shown in figure 5.1 and figure 5.2. Figure 5.1 displays a six-route system with a loop and shows link travel times, their standard deviations and route numbers. Figure 5.2 shows link and node numbers, names of transfer centers, and travel demand of passengers (passengers/hr) at the each node (or origin). In this study it is assumed that the travel time of a link is equal in both directions and independent from the travel times of other links. It is usually impossible to coordinate all routes at all transfer centers in multi-transfer network. Therefore, in this study all routes are fully coordinated at transfer center C because C is the busiest transfer center, and at other transfer centers other routes are coordinated to the forward direction of the route 1. Table 5.1 shows the baseline parameter values for the numerical analysis, which are estimated by linear regression of the values from the previous studies. The demand ratio matrix between origins and destinations (O/D) for the example network is shown in table 5.2. 48 Figure 5.1 Network configuration for case study 1 I II III IV V VI 17 [0.9] 13 [0.6] 25 [1.1] 26 [1.1]16 [0.8] 32 [1.1] 17 [0.9]21 [1.0] 19 [1.0] 22 [1.0] 23 [1.1] 18 [0.9] 21 [1.0] 23 [1.0] 29 [1.1] 24 [1.0] 17 [0.9] Route numbers: I, II, ? Link travel time and standard deviation: 21 [1.0], ? 49 Figure 5.2 Network configuration for case study 2 60 1 7 2 3 4 5 6 8 9101112 : 11 : 10 : 17 : 5C E DA B : 1 : 2 : 3 : 4 : 6 : 7 : 8 : 9 : 12 : 13 : 14 : 15 : 16 80 120 80 100 250 11010010090100 230 Transfer centers: A, B, C, D, E Demands: in box (230, 60, ?) Link numbers: : 1 , : 2 , ? Node numbers: 1, 2, ? 50 Table 5.1 Baseline parameter values for numerical analysis B k Vehicle operating cost ($/bus-min.) 1.33 ? Unit waiting time cost ($/passenger-min.) 0.4  Unit in-vehicle cost ($/passenger-min.) 0.2 Table 5.2 O/D demand ratio matrix for example network (Ratio of travel demand from origin to destination) D O 1 2 3 4 5 6 7 8 9 10 11 12  1 0 0.04 0.05 0.10 0.15 0.02 0.22 0.12 0.10 0.08 0.05 0.07 1.00 2 0.15 0 0.10 0.06 0.05 0.02 0.15 0.08 0.09 0.07 0.06 0.17 1.00 3 0.18 0.10 0 0.08 0.05 0.03 0.16 0.06 0.07 0.05 0.15 0.07 1.00 4 0.12 0.05 0.06 0 0.12 0.05 0.20 0.09 0.12 0.07 0.08 0.04 1.00 5 0.12 0.04 0.05 0.11 0 0.05 0.26 0.15 0.10 0.05 0.04 0.03 1.00 6 0.13 0.03 0.03 0.07 0.17 0 0.25 0.05 0.13 0.09 0.03 0.02 1.00 7 0.20 0.02 0.03 0.08 0.12 0.06 0 0.25 0.11 0.05 0.04 0.04 1.00 8 0.12 0.04 0.04 0.10 0.18 0.05 0.25 0 0.10 0.05 0.04 0.03 1.00 9 0.13 0.04 0.04 0.15 0.10 0.07 0.21 0.08 0 0.1 0.05 0.03 1.00 10 0.15 0.03 0.05 0.05 0.12 0.07 0.23 0.06 0.12 0 0.07 0.05 1.00 11 0.21 0.08 0.15 0.07 0.08 0.04 0.16 0.05 0.05 0.03 0 0.08 1.00 12 0.25 0.11 0.08 0.06 0.05 0.02 0.17 0.07 0.09 0.02 0.08 0 1.00  1.76 0.58 0.68 0.93 1.19 0.48 2.26 1.06 1.08 0.66 0.69 0.63 51 5.1 Deterministic Case 5.1.1 Numerical Results and Sensitivity Analysis With the above baseline values, we test the deterministic case in which the link travel times are constants (i.e., their standard deviations are zero). SGA developed in chapter 3 is applied to the example network. The parameters for the proposed SGA are summarized in table 5.3. The population size and maximum number of generations in SGA are 30 and 30, respectively. Both are much lower than those in SBGA (see section 5.2.1) since problem-specific genetic operators used in SGA such as coordinated headway generator, coordinated headway crossover, and coordinated headway mutation can lead to good solutions within fewer generations. Table 5.3 Genetic parameters of SGA for the example network Parameters Value Population size 30 Maximum number of generation 30 Percentage of crossover 0.9 Percentage of mutation 0.2 Although the problem-specific genetic operators can accelerate SGA?s search for the optimized solution, the SGA model is probabilistic and we cannot guarantee the best solution from SGA is the global optimum for the problem. We run the model 52 10 times. All ten runs have same headways and the results from 10 runs are given in table 5.4. This means that the genetic operators developed for SGA model work very well in searching for the optimized solution. Table 5.4 Results of SGA model for the case study Headways (min) Run H1 H2 H3 H4 H5 H6 Total Cost ($) 1~10 8 16 16 16 16 8 515.1824 The detailed components of the lowest total cost from SGA are shown in table 5.5. The in-vehicle cost (C v ) accounts for a large fraction of the total cost and the vehicle operating cost (C o ) is second. The waiting time cost (C w ), the transfer cost (C f ), and the layover time cost (C l ) are listed in the order, respectively. It is important to note that the transfer cost is a little higher although the bus routes in the example network are coordinated with each other at most transfer centers. The reason for this situation is that a considerable portion of the transfer cost comes from the additional waiting time at the off-phased transfer centers. Therefore, it is very important to decide how to operate the off-phased centers in a network with multiple transfer stations. The additional waiting time cost in the example network is $7.6027, which accounts for 44% of the transfer cost. 53 Table 5.5 Resulting components of the total cost for the deterministic case C Tdet ($) C o C w C v C f C l 515.1824 87.6138 57.0667 350.0810 17.0960 3.3250 In order to visualize the evolution of the model (SGA) using coordinated headway generator, coordinated headway crossover, and coordinated headway mutation, we plot the minimum objective value (or total cost) in each generation and the generation number in figure 5.3. The figure shows that total cost reaches its best value, which is $515.1824 at the 13 th generation, and that problem-specific genetic operators can find a good solution within fewer generations. Figure 5.3 Minimum total cost through successive generations in SGA Generation M i ni m um t ot a l c os t ( $) 54 To assess the efficiency of problem-specific genetic operators developed for SGA model we conduct an analysis to examine the influence of different types of operators on the solution. We use general (or conventional) genetic operators for different scenarios. Table 5.6 shows the genetic parameters and operators used in each scenario. Scenario 1 has the same population size and maximum number of generations as in the SGA model, but different genetic operators, such as random headway generator, simple crossover, and uniform mutation. Scenario 2 is just different from scenario 1 in the maximum number of generations. Table 5.6 Genetic parameters and operators in other scenarios Scenario Population size Max. number of generation Initial population Crossover Mutation 1 30 30 Randomly generated Simple crossover Uniform mutation 2 30 100 Randomly generated Simple crossover Uniform mutation Tables 5.7 and 5.8 show the results of scenarios 1 and 2, respectively. In 10 runs the best value is $517.3694 in scenario 1 and $515.1824 in scenario 2. The resulting values in scenario 1 have never reached the optimized value ($515.1824) found by SGA and those in scenario 2 have only reached that optimized value 3 times. Those results show how well problem-specific genetic operators in SGA work. 55 Table 5.7 Results of scenario 1 Headways (min) Run H1 H2 H3 H4 H5 H6 Total Cost ($) 1 7 7 16 14 14 7 532.9610 2 8 16 8 16 10 8 526.3800 3 8 8 8 12 8 8 521.5835 4 8 16 16 8 8 16 519.4515 5 8 16 8 16 12 8 525.5563 6 8 16 16 8 8 8 517.3694 7 8 16 8 8 12 16 529.3017 8 8 12 10 16 8 8 525.6023 9 8 8 10 8 8 8 522.8950 10 8 8 16 12 7 8 530.6744 Table 5.8 Results of scenario 2 Headways (min) Run H1 H2 H3 H4 H5 H6 Total Cost ($) 1 7 14 14 14 14 7 521.7030 2 8 16 16 16 16 8 515.1824 3 8 16 8 16 8 8 518.1982 4 8 16 16 12 8 8 520.5126 5 8 16 16 16 8 8 515.3702 6 8 16 16 16 8 8 515.3702 7 8 8 16 16 8 8 517.3118 8 8 16 16 16 16 8 515.1824 9 8 16 16 8 8 8 517.3694 10 8 16 16 16 16 8 515.1824 56 For sensitivity analysis we choose three factors affecting the total cost in deterministic case: bus operating cost, passengers waiting time cost, and travel demand. Table 5.9 and figure 5.4 show the optimized headways for the operation on the example network at different vehicle operating costs. As expected, the optimized headways increase as the operating cost increases. When the vehicle operating costs varies from 0.5 to 0.75 $/vehicle-min all routes have the same headways, 8 minutes. However, the headways of route 2 to 5 and headway 6 increase to twice the headway of route 1 from 1.33 and 2.5 $/vehicle-min, respectively. Table 5.10 and figure 5.5 show the optimized headways and total costs at different waiting time values. In this case the optimized headways decrease as the waiting time cost increases. The headway of route 1 is half the headway of other routes at 0.1 and 0.2 $/passenger-min, but route 6 becomes to the same headway of route 1 at 0.3 $/passenger-min and other routes at 0.5 $/passenger-min. Common headways are preferable from the value of 0.5 $/passenger-min. Table 5.11 and figure 5.6 show the optimized headways at various demand levels (ratio value 1 is the base demand). The results show that the headways roughly decrease as the demand ratio increases. When the ratio is 0.4 and 0.7 the headways of all routes are same headways, but from the ratio 1 the integer-ratio headways become preferable. The headways of routes 2 to 5 are twice the headways of the routes 1 and 6 at the ratio 1, and the headway of route 6 also becomes twice the headway of route 1 at the ratio 1.5. 57 Table 5.9 Optimized headways and total costs for different vehicle operating costs Headways (min) Cost ($/min) H1 H2 H3 H4 H5 H6 Total cost ($) 0.50 8 8 8 8 8 8 441.25 0.75 8 8 8 8 8 8 464.50 1.33 8 16 16 16 16 8 515.18 1.80 8 16 16 16 16 8 547.32 2.50 8 16 16 16 16 16 591.74 3.00 8 16 16 16 16 16 622.61 ? ? ? ?? ?? ?? ???? ???? ???? ???? ???? ???? ???????{?????????{????{??????? ??? ?????????{?????? ?{????????? H1 H2~H5 H6 Figure 5.4 Optimized headways vs. vehicle operating costs 58 Table 5.10 Optimized headways and total costs for different waiting time values Headways (min) Values ($/min) H1 H2 H3 H4 H5 H6 Total cost ($) 0.1 8 16 16 16 16 16 454.03 0.2 8 16 16 16 16 16 475.85 0.3 8 16 16 16 16 8 496.64 0.4 8 16 16 16 16 8 515.18 0.5 8 8 8 8 8 8 529.61 1.0 8 8 8 8 8 8 585.44 ? ? ? ?? ?? ?? ??? ??? ??? ??? ??? ??? ? ??????{??? ?{??????{????????????? ??? ????????{??????? {????????? H1 H2~H5 H6 Figure 5.5 Optimized headways vs. waiting time values 59 Table 5.11 Optimized headways and total costs for different demand ratio Headways (min) Demand Ratio H1 H2 H3 H4 H5 H6 Total cost ($) 0.4 21 21 21 21 21 21 243.87 0.7 12 12 12 12 12 12 386.49 1.0 8 16 16 16 16 8 515.18 1.5 5 10 10 10 10 10 744.37 2.0 4 8 8 8 8 8 942.44 2.5 3 6 6 6 6 6 1,1760.00 ? ? ?? ?? ?? ?? ??? ??? ??? ??? ??? ??? ? ?? ???{????? ?????????{?????? ?{????????? H1 H2~H5 H6 Figure 5.6 Optimized headways vs. demand ratio 60 5.1.2 Goodness Test Although the solution found with the proposed SGA model seems reasonable, it is hard to prove its optimality because SGA cannot guarantee finding the global optimum. Therefore, we design an experiment to statistically test the goodness of the algorithm. This goodness test follows the method used by Jong (1998). The experiment is initialized by randomly generating solutions to the problem. For each of them we then evaluate its objective value. This procedure is a sampling process. To maximize the generality and satisfy the statistical requirements, the sample must be created in such a way that the solutions are representative and independent of each other. The next step in the experiment is to fit a distribution to the objective values for the random sample. The fitness of the distribution can be checked with the Chi-Square or K-S tests. Since the sample is randomly generated, the fitted distribution should be able to reflect the actual distribution of the objective value for the real population. Based on this distribution, we can compare the solution found the proposed model and calculate the cumulative probability of the solution in the distribution. The lower the probability, the better the solution. 12 For the goodness test, we first create a random sample of 10,000 observations. Total cost of the best solution is $532.1268 and the objective value of the worst solution is $720.5057. The sample mean is $604.5817 and the standard deviation is $33.6372. Figure 5.7 shows the distribution of the random sample and the relative position of the best solution found by SGA. The distribution of the random sample is bimodal and seems unfamiliar. The number of observations of the total cost around 61 650 is relatively much less than the numbers of 590?s and 670?s. We do not find a known statistical distribution for the random sample. However, figure 5.7 shows that the total cost ($515.1824) of the best solution found by SGA is much less than the lowest total cost ($532.1268) of the random sample. This confirms that SGA is a good model for solving the bus scheduling problem with a deterministic arrival process. Figure 5.7 Distribution of total cost for the random sample by SGA Total Cost Number of observation Optimum of SGA (515.1824) 62 5.2 Stochastic Case 5.2.1 Numerical Results and Sensitivity Analysis On the same example network used for the deterministic case, we test the stochastic case in which the link travel times are not constants but variables (i.e., their standard deviations are not zero). The second model, SBGA, is applied to the example network. To analyze the stochastic arrival process, slack times are introduced to transfer centers to reduce the probability of missing transfer. Figure 5.8 shows the slack times in the example network. There are 22 slack times at five transfer centers and two slack times of a route at a transfer center are different from each other because there are two travel directions (e.g., s1 and s3 at transfer center A on the figure). Table 5.12 shows the parameters for SBGA. The population size is set at 60 and the maximum number of generations is set at 100. Both are much larger than those of SGA (see section 5.1.1). We cannot develop problem-specific genetic operators for SBGA since it is very difficult to estimate the relation between slack times and cost functions in a complex network. Instead, we use general genetic operators in stochastic case such as stochastic universal sampling, one-point or two- point crossover, uniform mutation, and elitism. For computer simulation 5,000 random variables are used and that number is decided by the trade-off between the simulation error and running time. The maximum value of slack time is limited to 3 minutes because more than 3 minutes of slack time is generally unrealistic. 63 Figure 5.8 Slack times in the example network I s1 II III IV V VI s2 s3 s4 s5 s6 s7 s8 s9 s10 s11 s12 s13 s14 s15 s16 s17 s18 s19 s20 s21 s22 :::: A :::: B :::: C :::: D :::: E 64 Table 5.12 Parameters of SBGA for the example network Parameters Value Population size 60 Maximum number of generation 100 Percentage of crossover 0.9 Percentage of mutation 0.2 Number of random variables for simulation 5,000 Range of slack time (minutes) 0 ~ 3 As with SGA in the deterministic case, the SBGA model is probabilistic and cannot guarantee finding the global optimum. We run the model 10 times in the stochastic case, which requires 32,987 seconds (9 hour 10 min.) of CPU time on Pentium 4 CPU 3.06Ghz, 512 MB of RAM, Notebook Computer. Table 5.13 shows the results of SBGA model. On the 10 runs the average total cost and its standard deviation are $545.2004 and $0.81, and the average slack time and its standard deviation are 1.10 and 0.79, respectively. From the results, we can infer that it is difficult to estimate the change pattern of the total cost from the variation of single slack time at a transfer center since the total cost is the result of the combination of slack time, link travel time, layover time, transfer volume and coordination method. The best solution is found at the 5 th run, and total cost and average slack time are $543.8844 and 1.02. Table 5.14 shows the detailed components of the total cost of the 5 th run, and figure 5.9 illustrates the minimum total cost through successive generations in SBGA, which reached the best solution at the 70 th generation. 65 Table 5.13 Results of SBGA model for the case study Run S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 S16 S17 S18 S19 S20 S21 S22 Mean Total Cost 1 0.75 1.5 1 2 1.5 3 0 2.75 2.25 2 1.25 0.75 2.75 1.5 0.5 1.5 1.5 0.75 0.25 0 0.5 0.25 1.28 544.0900 2 1.25 2 0 2 1.25 1.25 0.5 2.5 0.5 1.5 0.75 0.75 2 1.25 1.75 0.5 0.25 0.75 0 0 3 0 1.08 544.4400 3 0.25 3 0.5 1.5 1 1.5 0 1 1 0.5 1.75 2.25 1 1.5 0.25 0 0.25 0 0.75 0 1.25 1.5 0.94 545.2500 4 0.25 2.5 0 1.25 1 1 0.5 2 1.75 1.75 1 1.25 2 1.75 0.75 0.75 1 0 2.5 0 0.5 1.75 1.13 545.4400 5 0.5 1.75 0.25 1.75 1.25 1 0 1.25 1.5 1.5 0.75 1.75 1.75 2.25 1 1.5 0.75 0.25 0.25 0.25 1.25 0 1.02 543.8844 6 0.5 0.75 0 0 0 1 0.25 0.25 2 1.75 1.5 1 2.25 1.25 0.5 1.75 1 0.75 1.5 0.25 2.75 1 1.00 546.0200 7 0.5 1 0 1.25 2.25 1.25 0.5 2.25 1.25 2 2.75 1 1 1.25 1 2 1.75 0.5 0.5 0.5 2.75 1 1.28 545.6400 8 0.5 2.75 0.5 1 1 1.75 0 1.5 1.75 1 1 1.5 2 1.25 0.75 1.25 1 0.25 0 1 2.5 0.5 1.13 545.4700 9 0 1 0 1.5 1 1 0 0 2.5 0.5 1 0.75 2.75 2.0 1.25 0 0.25 1.75 1.75 1.75 1.25 2 1.08 546.3600 10 0 2 0.25 1.75 1 1.25 0.25 0.75 1.25 1 0 1.25 2 2.75 1 0.75 0 0.25 1.75 1.75 1.25 0 1.01 545.4100 Mean 0.45 1.83 0.25 1.40 1.13 1.35 0.23 1.43 1.58 1.35 1.18 1.23 1.95 1.68 0.88 1.00 0.73 0.53 0.93 0.55 1.70 0.80 1.10 545.2004 Std. 1) 0.37 0.77 0.33 0.59 0.56 0.67 0.22 0.94 0.60 0.57 0.73 0.49 0.60 0.51 0.43 0.71 0.58 0.52 0.88 0.71 0.96 0.76 0.81 - 1) Std: Standard deviation 66 Table 5.14 Resulting components of the optimized total cost for the stochastic case C Tsto ($) C o C w C v C l 543.8844 87.6138 57.0667 350.0810 3.3250 C s C p C m C d C l 16.6202 23.8746 6.1203 0.5644 -1.3816 Figure 5.9 Minimum total cost through successive generations in SBGA To investigate the changes in the components of transfer cost, we select a slack time, s9, which is located on the main route (route 1) and the busiest transfer center (C) in the example network. s9 is varied from 0 to 3 at intervals of 0.25 and all other slack times are fixed. Generation M i ni m um t ot a l c os t ( $) 67 Table 5.15 and figure 5.10 show the transfer cost (C f ) for different slack times of s9 and its components. As expected, the slack time delay cost (C s ) increases linearly, and the missed connection cost (C m ) and the dispatching delay cost (C d ) are decreasing as s9 increases. However, the inter-cycle transfer delay cost (C p ) varies more dynamically as s9 increases. It increases slightly at first when s9 increases, but it decreases at 1 and 1.25 minutes of s9. It increases again after 1.5 minutes of s9. The transfer cost roughly decreases until s9 reaches 1.5 minutes and, after that, it increases. The optimized slack time of s9 in the detail investigation is 1.5 minutes, which is the same value from SBGA. Table 5.15 Transfer cost for different slack times of s9 Transfer cost (C f ) s9 C s C p C m C d Sum (C f ) 0.00 14.68 25.56 10.22 0.88 51.33 0.25 15.00 25.89 9.40 0.79 51.08 0.50 15.33 26.29 8.29 0.72 50.62 0.75 15.65 26.73 7.72 0.66 50.76 1.00 15.97 26.74 7.08 0.62 50.41 1.25 16.30 25.33 6.53 0.59 48.74 1.50 16.62 23.94 6.10 0.57 47.22 1.75 16.94 24.12 5.76 0.55 47.37 2.00 17.27 24.59 5.52 0.54 47.92 2.25 17.59 25.08 5.35 0.54 48.56 2.50 17.91 25.51 5.27 0.54 49.23 2.75 18.24 25.92 5.18 0.53 49.87 3.00 18.56 26.30 5.16 0.53 50.55 68 ? ?? ?? ?? ?? ?? ?? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ???? ?????{??? ?{???? ????????{????{? ? ? ? ? ? ? ? ? ? ? ? Figure 5.10 Transfer costs vs. slack time s9 As a factor for sensitivity analysis of the stochastic arrival process we choose the slack time since its variation directly affects the transfer cost and the total cost. Table 5.16 shows the optimized slack times and total costs for different standard deviation ratios, and figure 5.11 shows the mean value of slack times and total cost at various standard deviations. The ratio of standard deviations in the example network is increased from 0 to 3 at intervals of 0.25 where the ratio value 1 is the base standard deviation. The mean value of slack times is 0 minutes at ratio 0 (i.e., the deterministic arrival process) and increases as the ratio increases to 0.75. Afterwards, it decreases and stays around 0.35 minutes after the ratio 1.5. The peak of the mean Optimum 69 slack time is 1.13 minutes at the ratio 0.75. It is important to note in the figure that the mean slack time does not reach 0 minutes even when the standard deviation ratio is relatively large and that the mean slack time at transfer center C (a fully coordinated transfer center) stays around 0.3 minutes after the ratio 1.5. In most previous research, the mean slack time usually reaches 0 minutes at a fully coordinated independent transfer center when the standard deviation goes beyond a threshold. This means that, in a network with multiple transfer centers, a combination of some slack times can still reduce the total cost at the system level even at the relatively large standard deviations, and that in the total cost the reduction due to the slack time combination exceeds the cost increase due to the introduction of the slack times. This indicates that the combination of slack times can affect the layover time of a route and the transfer waiting time of passengers at transfer centers. For the comparison of the total costs between optimized and 0 slack times, the total costs are inserted in the last two columns of table 5.16. 70 Table 5.16 Optimized slack times and total costs for different ratio of standard deviation S R 1) S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 S16 S17 S18 S19 S20 S21 S22 Total Cost TC (S=0 2) ) 0.00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 515.18 515.18 0.25 0.75 1 0 0.25 0.5 0.5 0.75 1.5 0.5 1.25 0.75 0.5 1 0.25 0.25 0.75 0.5 0.25 1.75 0 0.5 0.5 532.30 546.85 0.50 0.25 2 0.5 0.75 0.5 0.5 0 0.25 1.25 2.25 1 1.75 2.25 1.5 1.25 1.25 0.25 0.5 0.5 0.5 1.75 0.5 537.91 547.29 0.75 0.75 1.25 1 1.5 0.75 2.25 0.5 0.75 1 1.5 1 1.5 2 1.25 1.25 1 0 1 1 0.75 2.5 0.25 541.19 547.96 1.00 0.5 1.75 0.25 1.75 1.25 1 0 1.25 1.5 1.5 0.75 1.75 1.75 2.25 1 1.5 0.75 0.25 0.25 0.25 1.25 0 543.88 548.50 1.25 0.25 3 0 0 0.25 0 0 0 0 1.75 1 1 1.5 2 0.75 0.5 0.75 0.25 0.25 0 2 0 547.53 549.01 1.50 0.25 2.25 0 0 0.75 0 0 0 0 0 0 0 1 0.75 0 0 0.75 0.5 0.25 0.25 2.5 0 548.41 549.51 1.75 0.25 2.25 0 0 0.75 0 0 0 0 0 0 0 1.5 0 0 1 0.5 0.5 0.25 0 0 0 548.55 550.07 2.00 0 2.25 0 2.5 0.5 0 0 0 0 0 0 0 1 0.25 0 0.5 0 0 0.5 0.5 0 0 548.68 550.57 2.25 0 2 0 1.5 1 0 0.5 0 0 0 0 0 1 0.25 0 1.75 0.25 0.25 0 0.75 0 0 548.89 551.13 2.50 0 1.75 0 1.5 1.5 0 0 0 0 0 0 0 1 1.5 0 0.25 0 0 0 0 0 0 550.01 551.55 2.75 0 2.25 0 0 0.5 0 0 0 0 0 0 0 1 2 0 0 0.25 0 0 0 0 0 550.98 552.10 3.00 0 2 0 0 0.25 0 0 0 0 0 0 0 1 1.5 0 0 0.5 0 0 0 0 0 551.25 552.34 - 1) S R : Ratio of standard deviation, - 2) S=0: All slack times are 0 71 0 0.2 0.4 0.6 0.8 1 1.2 1.4 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 Standard deviation ratio M e a n s l a c k t i m e ( m i n ) 510 520 530 540 550 560 T o t a l c o s t ( $ ) mean(s) Total cost Figure 5.11 Optimized mean slack time and total cost vs. standard deviation ratio To examine more closely the variation of slack time, we select the six slack times (s9 to s14) at the busiest transfer center (C), at which all routes are fully coordinated. Only the standard deviation on link 3 is changed from 0 to 3 at intervals of 0.25 or 0.5 where a ratio value 1 is the base standard deviation of the travel time on link 3. All other slack times are fixed at the best solution found by SBGA besides two slack times (s15 & s17) which are directly related to s9. Figure 5.12 shows the changes in slack times at transfer center C. Slack time s9 is 0 minutes at the ratio 0, reaches the peak (1.75 minutes) at the ratio 0.25, and stays at the peak for ratios between 0.25 and 0.75. Afterwards, it decreases and drops 72 to 1.25 minutes at the ratio 2. In this case, s9 also does not reach 0 minutes at the relatively large ratio of standard deviation. If the transfer center C is a fully coordinated independent transfer center, s9 drops to 0 minutes when the ratio goes beyond a threshold. The mean of other slack times (s10 ~ s14) at transfer center C increases slightly at first and reaches the peak at the ratios 0.5 and 1.5. It decreases after that, but does not reach 0 minutes. This shows that change of the standard deviation of a link travel time has a limited influence in changing the slack times. ? ??? ??? ??? ??? ? ??? ???? ??? ???? ? ??? ? ??? ? ????????{?????????{?????{??{????{? ?????{????{???????? ? s9 mean (s10-s14) Figure 5.12 Slack time vs. standard deviation ratio on link 3 73 5.2.2 Goodness Test As in the experiment design introduced in section 5.1.2, a set of representative and independent solutions is randomly generated. After creating a random sample of 10,000 solutions, we observe that the best solution of the sample yields an objective value $548.1219 and the worst is $567.8093. The mean of the objective values is $556.9689 and the standard deviation is $2.7086. Figure 5.13 illustrates the distribution of the random sample and the relative position of the best solution found by SBGA. The distribution of the random sample has a bell shape. Figure 5.13 Distribution of total cost for the random sample by SBGA Number of observation Total Cost Optimum of SBGA (543.8844) 74 A normality test for the random sample was conducted with the statistical package Minitab. Figure 5.14 shows the normal probability plot resulting from the normality test. The more the black points in the figure match the straight line (i.e. red line), the more the random sample approaches to a normal distribution. Thus, figure 5.14 demonstrates that the normal distribution fits well the random sample in spite of some slight differences at both ends. Actually, the P-value of the normality test is 0.0884, which is higher than the minimum criterion (0.05) for a normal distribution. Figure 5.14 Normal probability plot for the random sample by SBGA The following normal distribution was fitted to the random sample. Total Cost = Normal (556.9689, 7.3365) (5.1) Total Cost P r oba bi l i t y 75 With the normal distribution (Eq. 5.1) we can calculate the cumulative probability of the best solution found by SBGA. The cumulative probability of the best solution ($548.1219) in the above normal distribution is 0005.0)27.3() 2.7086 556.9689548.1219 2.7086 556.9689 ()1219.548( ==    = zP TC PTCP This means that the best solution from SBGA dominates more than 99.95% of the solutions in the distribution and that the solution is excellent when compared to other possible solutions to the problem. Such results give us confidence in the proposed model. 76 Chapter 6: Conclusions and Recommendations 6.1 Conclusions It is difficult to solve the bus scheduling problem with traditional local search methods in an urban transit network of realistic size due to the complexities of the objective function and its constraints (e.g. non-linearity, noisiness, computational complexity from large number of variables and constraints). Therefore, heuristic algorithms have usually been used to search for the optimized headways and slack times. The use of simulation for the bus scheduling problem has been also limited to simple transit networks. In this study two computerized models, SGA and SBGA, using genetic algorithms and computer simulation are developed in chapter 3. We focus on extending the previous methods to more complex situations and finding an optimized solution quickly. The genetic algorithm and operators used in this study are described in chapter 4. In chapter 5 new models are applied to an artificial bus network for numerical results and sensitivity and goodness test. The conclusions of this research can be summarized as follows: 1. The first model (SGA) developed for the deterministic arrival process can find the optimized solution very quickly when joined with problem- specific genetic operators such as coordinated headway generator, coordinated headway crossover and coordinated headway mutation. 77 2. Under the deterministic arrival process, common or integer-ratio headways among bus routes are the favored way to minimize the total system cost in coordinated operation. It is also important to determine how to operate the off-phased transfer centers since a considerable portion of transfer cost in the deterministic case results from the additional passengers waiting time at those centers. 3. A sensitivity test for deterministic case shows that common headways are preferable when operating cost is relatively low, but integer-ratio headways are more suitable when operating cost increases, as shown in table 5.9. 4. When passenger waiting time cost is relatively low, integer-ratio headways are preferable, but common headways are favored when the waiting cost increases, as shown in table 5.10. 5. When travel demand is relatively low, common headways are preferable, but integer-ratio headways are preferred when travel demand increases, as shown in table 5.11. 6. The goodness test shows that the new model (SGA) can find a good solution for the bus scheduling problem under the deterministic arrival process, as shown in figure 5.7, even though this study does not find a suitable statistical distribution for the random sample. 7. Under the stochastic arrival process, the total cost is the result of the complex combination among slack times. Thus, it is difficult to predict the variation of the total cost from the change of some slack times. 78 8. Transfer cost (C f = C s + C p + C m + C d ) under the stochastic case accounts for a much larger fraction of total cost than in the deterministic case, as shown in table 5.14. 9. In the stochastic case the slack time delay cost, the inter-cycle transfer delay cost, and the missed connection cost are the dominant factors in the transfer cost. The slack time delay cost is a linear function, but the inter- cycle transfer delay cost and the missed connection cost are non-linear functions, as shown in figure 5.10. 10. As the standard deviation increases, the mean slack time increases at first but decreases beyond some threshold. Unlike for a fully coordinated independent transfer center, the mean slack time does not drop to zero even when the standard deviation increases to relatively large values, as shown in figure 5.11. 11. The goodness test for the stochastic arrival process verifies that the best solution from SBGA is an excellent one when compared to other solutions generated randomly for the problem. 12. This study used the total system cost as an objective function for the bus scheduling problem and developed two new models, SGA and SBGA, to optimize it. However, the new models can be applied to various objective functions (e.g., mean transfer waiting time) and other scenarios (e.g., different passengers arrival distribution at bus stops, or different travel time pattern of buses) with small changes in the models. 79 13. Only an artificial bus network was analyzed using the new models in this study. However, these models can be applied to optimize schedules for other transportation systems such as intercity bus networks with feeder buses, general urban transit networks including rail and bus routes, and hub-spoke aviation networks. 6.2 Recommendations for Further Research This study could be extended in the following aspects: 1. In this study we assume that the passenger demand is known and fixed, without considering the diverted demand sensitive to the change of bus headway and travel time. Improved models should consider how changes in travel time or headway would affect demand. 2. This study also assumes that passengers choose the route with the shortest travel time. In reality, some users may prefer a route which is less crowded or requires fewer transfers. A new model could analyze various passenger travel preferences regarding travel times and transfers. 3. The fleet in this study has a single type of bus with pre-specified characteristics. However, many kinds of buses run on real transit networks because that may be often economical or beneficial to the users. Therefore, mixed fleets of buses could be considered in future models. 4. This study is limited to analyzing bus operations for one dispatching strategy in which vehicles do not wait for other vehicles arriving behind 80 schedule at a transfer center. However, there are some other strategies to maximize social benefit or minimize total system cost on the bus operation (e.g., real-time dispatching strategy). Advanced new strategies for the bus operation could be included in future studies. 5. The SBGA model developed in this study uses general genetic operators due to limitations in analyzing relations among decision variables and total cost under the stochastic arrival process. Slack times in a stochastic case result from the interaction among headways, passenger demand, transfer strategy, number of transfers, coordination method and bus arrival process. Thus, further research should analyze the effect of those factors in detail and develop problem-specific genetic operators. 6. This study developed two separate models for deterministic and stochastic cases. In future studies, joining two such models into an integrated one should be considered to search for jointly optimized solutions (headways and slack times). 81 References 1. Abkowitz, M., Eiger, A. and Engelstein, I., "Optimal Control of Headway Variation on Transit Routes", Journal of Advanced Transportation, Vol. 20, No. 1, pp. 73-88, 1986. 2. Banks, J. H., "Optimal Headways for Multiroute Transit Systems", Journal of Advanced Transportation, Vol. 24, No. 2, pp. 127-155, 1990. 3. Bookbinder, J. H., "Transfer Optimization in a Transit Network", Transportation Science, Vol. 26, No. 2, pp. 106-118, 1992. 4. Chakroborty, P., "Genetic Algorithms for Optimal Urban Transit Network Design", Computer-Aided Civil and Infrastructure Engineering, Vol. 18, pp. 184-200, 2003. 5. Chakroborty, P., Deb, K. and Srinivas, B., "Network-wide Optimal Scheduling of Transit Systems Using Genetic Algorithms", Computer-Aided Civil and Infrastructure Engineering, Vol. 13, pp. 363-376, 1998. 6. Chakroborty, P., Deb, K. and Surbrahmanyam, P. S., "Optimal Scheduling of Urban Transit Systems Using Genetic Algorithms", Journal of Transportation Engineering, Vol. 121, No.6, pp. 544-553, 1995. 7. Jin, G., "Genetic Algorithm and its Application", Kyowoo Press, 2004. 8. Hall, R. W., "Vehicle Scheduling at a Transportation Terminal with Random Delay en Route", Transportation Science, Vol. 19, No. 3, pp. 308-320, 1985. 9. Im, J., "Matlab?s Power", Ajin Press, 2002. 10. Devore, J. L., "Probability and Statistics", Thomson Brooks/Cole, 2004. 82 11. Jitendra, A., Tom, V. M. and A. M. A. ASCE, "Transit Route Network Design using Parallel Genetic Algorithm", Journal of Computing in Civil Engineering, Vol. 18, No. 3, pp. 248-256, 2004. 12. Jong, J-C, "Optimization Highway Alignment with Genetic Algorithm", Ph.D. dissertation, Civil Engineering Department, University of Maryland, College Park, 1998. 13. Konppers, P. and Muller, T., "Optimized Transfer Opportunities in Public Transport", Transportation Science, Vol. 29, No. 1, pp. 101-105, 1995. 14. Lee, K. T. and Schonfeld, P., "Optimal Slack Time for Timed Transfers at a Transit Terminal", Journal of Advanced Transportation, Vol. 25, No. 3, pp. 281-308, 1991. 15. Maurizio, B., Massimiliano, C. and Pasquale, C., "Genetic Algorithms in Bus Network Optimization", Transportation Research Part C 10, pp. 19-34, 2002. 16. Mitsuo, G. and Runwei, C., "Genetic Algorithms & Engineering Optimization", Wiley Interscience, 2000. 17. Newell, G. F., "Dispatching Policies for a Transportation Route", Transportation Science, Vol. 5, No. 1, pp. 91-105, 1971. 18. Ngamchai, S. and Lovell, D. J., "Optimal Time Transfer in Bus Transit Route Network Design Using a Genetic Algorithm", Journal of Transportation Engineering, Vol. 129, No. 5, pp. 510-521, 2003. 19. ?zekici, S., "Average Waiting Time in Queues with Scheduled Batch Services", Transportation Science, Vol. 21, No. 1, pp. 55-61, 1987. 20. Salzborn, F. J. M., "Optimal Bus Scheduling", Transportation Science, Vol. 6, No. 2, pp. 137-148, 1972. 83 21. Salzborn, F. J. M., "Scheduling Bus Systems with Interchanges", Transportation Science, Vol. 14, No. 3, pp. 211-231, 1980. 22. Ross, S. M., "Simulation", Academic Press, 2002. 23. Ting, C. J., "Transfer Coordination in Transportation Networks", Ph.D. dissertation, Civil Engineering Department, University of Maryland, College Park, 1997. 24. Tom, V. M. and Mohan, S., "Transit Route Network Design Using Frequency Coded genetic Algorithm", Journal of Transportation Engineering, Vol. 129, No. 2, pp. 186- 195, 2003.