
small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


INSTITUTE OF TRANSPORTATION STUDIES UNIVERSITY OF CALIFORNIA, BERKELEY A Dynamic Holding Strategy to Improve Bus Schedule Reliability and Commercial Speed Yiguang Xuan, Juan Argote, and Carlos F. Daganzo WORKING PAPER UCB ITS VWP 2011 1 March 2011 1 A Dynamic Holding Strategy to Improve Bus Schedule Reliability and Commercial Speed Yiguang Xuan, Juan Argote, and Carlos F. Daganzo Institute of Transportation Studies University of California, Berkeley, CA 94720 ( March 18, 2011) Abstract Bus systems are naturally unstable. Without control, the slightest disturbance to bus motion can cause buses to bunch, reducing schedule reliability. Holding strategies can eliminate this instability. However, the conventional schedule based holding method requires too much slack time, which slows buses. This delays on board passengers and increases operating costs. This paper studies a family of dynamic holding strategies that use the current state of all buses, as well as a virtual schedule. The virtual schedule is introduced whether the system is run with a published schedule or not. We found that with this control method, which we term general control method, buses can both closely adhere to schedule and maintain regular headways without too much slack. Thus the general control idea is applicable to bus lines with both long and short headways. Although the optimal set of control parameters can be found numerically, a oneparameter version of the control method can be optimized in closed form. This simple method was shown to be near optimal. To put it in practice, one only needs the arrival times of the current bus and the preceding bus relative to the virtual schedule. This simple method was found to outperform alternative control methods ( i. e., require less slack for the same headway variance). While the paper mostly focuses on recurrent small disturbances under quasi deterministic demand, it also shows that the proposed control method can deal with large disturbances. Keywords: bus bunching, bus schedule reliability, headway variance, commercial speed, dynamic holding, control method. 1 Introduction Bus schedule reliability is an essential attribute of a bus system, and is consistently ranked as one of the major concerns by passengers ( Paine et al., 1967; Golob et al., 1972; Wallin et al., 1974). Unfortunately, bus systems are naturally unstable, and buses tend to fall off schedule without intervention. This instability is due to the fact that the loading time of a bus at a station1 is a non decreasing function of the headway between buses. As first explained by Newell & Potts ( 1964), early buses encounter and serve fewer passengers, and tend to catch up with the buses in front of them, while late buses tend to fall further behind. The tendencies result in the so called 1 To avoid confusion, we use bus stations to mean locations where buses stop to pick up or drop off passengers. Stop is only used as a verb. 2 “ bus bunching” phenomenon, which annuls the schedule and increases the average waiting time of passengers. Bus holding strategies may eliminate this problem. They are characterized by embedding slack time in the schedule, and holding buses at each control station for a period of time before their scheduled departure. A bus is generally held longer if it is ahead of schedule and shorter ( or not even held) if it is behind schedule, so that the instability can be neutralized. The most common form of holding is the “ schedule based” method, in which drivers are instructed never to depart a control station ahead of a pre published schedule. Among the literature that analytically addresses the bus bunching problem with holding methods, most of the studies ( Osuna and Newell, 1972; Newell, 1974; Barnett, 1974; Hickman, 2001; Eberlein et al, 2001; Zhao et al, 2006) try to minimize passenger time ( either waiting time at the station only or both waiting at the station and riding time on board). Problems based on this objective are difficult, and most of these studies only discuss problems with one bus line, a single control station, and either one or two buses. 2 Some use “ rolling horizon” heuristics. Many more studies resort to simulations ( Koffman, 1978; Turnquist & Bowman, 1980; Abkowitz et al., 1986; Vandebona & Richardson, 1986; Senevirante, 1990; Adamski & Turnau, 1998) due to the difficult nature of the problem. There is also a literature that uses control theory. Daganzo ( 2009b) approached the bus bunching problem from a different angle: instead of minimizing passenger waiting time, the paper proposed a headway based dynamic holding strategy to reduce the amount of slack time in the schedule, subject to a headway variability constraint. The idea was to increase the commercial speed of buses3 while compensating for the effects of small disturbances ( e. g., due to traffic). With this new objective, the paper analytically addressed a much broader range of problems: systems with many buses, many control stations, and stochastic cruising time. The article proposed a general form for this family of dynamic holding strategies by defining a convolution kernel. However, it only studied in depth a particular case: a headway based control in which buses were held based only on the expected demand and their forward headway ( the headway between the current bus and the bus in front) for systems where a schedule is not published. It was shown that headways could be regularized with less slack than required by the schedulebased control method. Unfortunately, as explained in the reference, the method cannot always compensate for large disturbances, such as those due to bus breakdown. To alleviate this problem, Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) proposed a cooperative control method in which bus speed was regulated based on the expected demand and the spacings between the current bus and the preceding and following buses. This method was able to compensate for large disturbances. 4 More recently, a holding method in 2 The exception is Eberlein et al ( 2001) which addresses an arbitrary number of buses. But the study does not model the cruising time between two stations stochastically. 3 The commercial speed of buses is the total distance traveled divided by total time taken ( including scheduled holding). 4 The Eulerian version of the method in Daganzo and Pilachowski ( 2009, 2011) is used here, in which holding times would be based on the forward and backward headways ( the headway between the current bus and the bus behind). 3 which the holding times are based only on the backward headway, independent of demand, has been proposed ( Bartholdi, 2011). The method is appealing because it is very simple and it has been tested successfully with an experiment for a case with low demand. It is claimed that this approach can also compensate for large disturbances ( Bartholdi, 2011). The results about to be described build on Daganzo ( 2009b). A general control method is proposed that uses both the arrival times of all buses at stations and a virtual schedule. As such, the method includes as special cases all three existing models in the control genre. The virtual schedule is different from the published schedule, and is used even if there is no published schedule, as occurs in bus lines with short headways. Unlike the existing methods, we found that with this general control method, buses can not only maintain regular headways but also stick to their schedule. This is important because the control method then can be applied to bus lines with both long and short headways. The optimal parameters of the general control method, i. e. those which provide the maximum commercial speed for a given schedule/ headway reliability level are also identified. It turned out that a one parameter version of the method, which only requires information on the current bus and its leading bus, is near optimal and outperforms other existing control alternatives. While this paper focuses on small disturbances to the bus operation, the case of large disturbances is also addressed. The paper is organized as follows. Section 2 presents the assumptions and the bus motion laws under the general control method. Section 3 proves that with this method buses are able to adhere to their schedule with only minor random deviations. Section 4 demonstrates that a simple version of the general control method is near optimal, and that it outperforms the other existing methods. Sections 5 and 6 discuss how to handle large disturbances and highly stochastic demand. Finally Section 7 summarizes the main findings. 2 Assumptions and Bus Motion Formulation 2.1 Assumptions The same assumptions are made as in Daganzo ( 2009b): ( a) the number of bus dispatches and stations in the system can be as high as desired; ( b) buses are always dispatched on time with equal headways from the first station; ( c) the bus capacity for passengers is unlimited; ( d) buses do not pass each other; ( e) vehicle running times between adjacent stations are modeled as independent random variables; ( f) demand is stochastic but its contribution to the variance of the running time between stations is assumed to be negligible compared with the variance due to traffic ( we call this quasi deterministic demand); ( g) the bus loading time is dominantly affected by boarding passengers; ( h) only those passengers arriving during the inter arrival time will board the bus, and holding is then applied after the boarding process; ( i) there exists enough slack to ensure that the holding time never runs short; ( j) buses stop at all stations and holding is also applied at all stations. Assumption ( a) makes the analysis comparable to a situation with a finite number of buses but enough layover time, so that buses are always dispatched on time. Assumptions ( b) and ( c) 4 are reasonable if the operational design problem for a bus line ( i. e., to choose proper dispatching headways, fleet size, and vehicle size for a given route) has already been addressed. Assumption ( d) is reasonable if the system is well managed. But even if passing is allowed, we can renumber the buses and results will not change much. Assumption ( f) is relaxed in Section 6 to account for highly stochastic demand. Assumption ( g) is appropriate for bus systems, where boardings and alightings occur simultaneously and the alighting time per passenger is much smaller than the boarding time per passenger. Assumption ( h) greatly simplifies the formulation with only negligible effect, since the loading and holding times are much shorter compared with the interarrival time. Assumption ( i) makes the formulation linear and the problem tractable, as will soon be shown. Assumption ( j) can be relaxed ( see Appendix A). 2.2 Bus Motion with a Control Law Let us use n ( n = 0, 1, 2, …) to denote the bus number ( the buses dispatched first have smaller numbers) and s ( s = 0, 1, 2 …) to denote the station number ( increasing s in the traveling direction). The notation follows Daganzo ( 2009b): • tn, s is the scheduled arrival time of bus n at station s. The tn, s’s form the virtual schedule for buses; they are not the published schedule to passengers. A published schedule can be obtained by shifting the virtual schedule earlier in time to ensure that buses never depart ahead of the published schedule. • an, s is the actual arrival time of bus n at station s. • εn, s = an, s – tn, s is the deviation from scheduled arrival time of bus n at station s. • hn, s = an, s – an 1, s is the time headway between bus n and its leading bus at station s. • H is the scheduled headway. • cs is the average cruising time from station s to s+ 1, which includes the time to accelerate and decelerate, but does not include the dwell time to serve passengers. • υn, s+ 1 is the random noise in the cruising time of bus n between station s to s+ 1, whose mean is zero and variance is σn, s+ 1 2. • Dn, s is the holding time applied to bus n at station s. 5 • ds is the amount of slack time in the virtual schedule at station s ( i. e., the holding time if the bus arrives when expected). • β s is a dimensionless measure for the demand rate at station s, where the demand rate ( in passengers/ hour) is normalized by the passenger boarding rate ( also in passengers/ hour). This implies that the passenger loading time at station s increases by β s if headway increases by one unit of time. Typical values of β s range from 10 2 to 10 1. With the above notation, the scheduled arrival times can be formulated as: n, s 1 n, s s s s , t = t + H + d + c + β ( 1a) , , 1, t t H n s n s = + − ( 1b) 5 In reality, we recommend holding buses en route by slowing them down shortly after departing the station and by providing drivers with adequate real time information. This unnerves passengers less, and releases station capacity in those cases where the station is also used by other bus lines as well. 5 with n s s s t + β H + d , being the scheduled departure times. The actual arrival times obey: . , + 1 , , , , + 1 = + + + + n s n s s n s n s s n s a a β h D c υ ( 2) By combining equations ( 1) and ( 2), it is possible to express the motion of buses in terms of εn, s: ( ) ( ). n, s 1 n, s s n, s n 1, s n, s 1 n, s s = + − + + D − d + − + ε ε β ε ε υ ( 3) It is assumed that Dn, s is a linear function of the arrival times of all buses at station s, ai, s, or equivalently as a function of the deviations from the schedule, the εi, s. 6 It is convenient to write this function as: [( 1 ) ] , , , 1, , Σ − − = − + − + n s s s n s s n s i i n i s D d β ε β ε f ε ( 4a) because plugging ( 4a) into ( 3), yields the simple relation: . , + 1 − , , + 1 = Σ + n s i i n i s n s ε f ε υ ( 4b) To define a specific control method one needs to specify the slack times ds at each station and all the control coefficients {…, f 1, f0, f1, …}. All three holding strategies in the control genre mentioned in the introduction are special cases of this general control method. For example, if we set f0 = 1 + βs, f1 = – βs and fi = 0 ∀ i∉{ 0, 1}, we obtain the case with no control, because then Dn, s = ds = 0. In this case, the bus motion is governed by ( 1 ) . , + 1 , − 1, , + 1 = + − + n s s n s s n s n s ε β ε β ε υ ( no control) ( 5) The conventional schedule based control method is the case with fi = 0 ∀ i. In this case, the drivers are instructed not to depart the control station before the scheduled departure time. If there is enough slack time in the schedule as per assumption ( i), the buses can always depart the control station on schedule, i. e., n s s n s n s n s s s a + β h + D = t + β H + d , , , , . Therefore, it follows that [ ( )], n, s s n, s s n, s n 1, s D d − = − ε + β ε − ε ( sch. control) ( 6a) and . , + 1 , + 1 = n s n s ε υ ( sch. control) ( 6b) The method in Daganzo ( 2009b), which is based on the forward headway is: ( )( ). , , D d h H n s s s n s = − α + β − ( forward headway) ( 7a) This can be expressed as a function of the deviation from the schedule as: ( )( ). n, s s s n, s n 1, s D d − = − α + β ε − ε ( forward headway) ( 7b) 6 The arrival times of the current bus and the buses in front, ai, s’s for i ≤ n, are readily available when bus n arrives at station s. But the arrival times of the buses behind, ai, s’s for i > n, can only be predicted. For now, we will assume that we have perfect information, i. e., we know all ai, s’s. We will demonstrate later that this assumption is acceptable. 6 This is the special case of ( 4a) with f0 = 1 – α, f1 = α, fi = 0 ∀ i∉{ 0, 1}, where 0 < α < 1, and ( 4b) becomes: ( 1 ) . , + 1 , − 1, , + 1 = − + + n s n s n s n s ε α ε αε υ ( forward headway) ( 7c) Similarly, the Eulerian version7 of the ( Lagrangian) method in Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) , which is based on both the forward and backward headways, is obtained by setting f 1 = f1 = α, f0 = 1 – 2α, fi = 0 ∀ i∉{ 1, 0, 1}, where 0 < α < 1/ 2. This yields: ( ) ( )( ), , 1, , D d h H h H n s s n s s n s = + − − + − + α α β ( two way headway) ( 8a) ( 2) ( ) , n, s s n 1, s s n, s s n 1, s D d + − = + αε − β + α ε + β + α ε ( two way headway) ( 8b) and ( 1 2 ) . + 1, + 1, , − 1, , + 1 = + − + + n s n s n s n s n s ε αε α ε αε υ ( two way headway) ( 8c) Finally, a demand independent method based on the backward headway alone ( Bartholdi, 2011) is obtained by setting f 1 = α, f0 = 1 + βs – α, f1 = – βs and fi = 0 ∀ i∉{ 1, 0, 1}. This results in: ( ), , 1, 1, D h H h H n s n s n s = = + − + + α α α ( backward headway) ( 9a) ( ) , n, s n 1, s n, s s n, s n 1, s D H d + + = α + ε − ε = − αε + αε ( backward headway) ( 9b) and ( 1 ) . , + 1 + 1, , − 1, , + 1 = + + − − + n s n s s n s s n s n s ε αε β α ε β ε υ ( backward headway) ( 9c) 3 Stability Analysis This section shows that with the general control method, buses are able to adhere to their schedule with bounded deviations. Of course, this means that they can also maintain regular headways. As in Daganzo ( 2009b), we first express the summation term in ( 4b) as the convolution ( denoted with *) of two vectors: the bus deviations from the schedule εs = [… ε n  1, s εn, s ε n + 1, s …] T and the kernel of the convolution ( the set of control coefficients) f = [… f 1 f0 f1 …] T. The nth element of the convolution is: [ ] Σ − = s n k n k k s f , f * ε ε . If we also define s υ = [… 7 The control method introduced in Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) is consistent with a Lagrangian specification of the buses system, while the proposed general control in this paper is based on an Eulerian specification. Daganzo ( 2006) demonstrates the close connection between Lagrangian and Eulerian coordinates in the context of automobile motion. 7 υ n  1, s υn, s υ n + 1, s …] T as the vector of disturbances, then the vector form of ( 4b) is 1 1 * + + = + s s s ε f ε υ . Now apply the convolution iteratively, so that the ε. terms can be expressed as a function of the control coefficients f and the noise terms υ. . This yields: * * ( * ) * * * ... 1 1 1 1 1 1 = + = + + = + + = s+ s+ s s+ s s− s+ s s− ε υ f ε υ f υ f ε υ f υ f f ε . Next define  j f to be the jth self convolution of f ( i. e.,   1 * − = j j f f f , where  0 f = [… 0 1 0 …] T). Since assumption ( b) states that buses are always dispatched from the first station on time ( ε = 0 0 ), the above expression becomes: * , 1 0 s 1 j s s+ j= j + − ε = Σ f υ ( 10a) which expands to [ * ] . , 1 0 1 0 , 1 Σ Σ Σ + = + − = − + − = = s j i i j n i s j s n s j j s j n ε f υ f υ ( 10b) It is now possible to see that the following is true. Lemma: Define = Σ i i F f , then j i i j Σ f ≤ F  . Proof: Σ Σ Σ Σ Σ Σ( Σ ) Σ − − − − − − − = ≤ = = i i j i k k j i k i k k j i k k k j i i k k k j f f f f f f f F f   1  1  1  1 ... ... .  2 2 j k k j ≤ ≤ F Σ f ≤ ≤ F − □ Proposition: If 1 and M n s ≤ , + 1 υ , then n, s+ 1 ε is bounded above by M /( 1− F) Proof: Σ Σ Σ Σ + = − + − = − + − = ≤ s j i i j n i s j s n s j i i j n i s j f f , 1 0  , 1 0  , 1 ε υ υ ( since ) 0  1 M f M n, s s j i i j ≤ ≤ = + Σ Σ υ ( as per Lemma) 0 Σ = ≤ s j M F j ( since 1). 1 1 1 1 < − → − = − + F F M F M F s □ Corollary: If n, s+ 1 ε is bounded, then h H n s − , + 1 is also bounded. Proof: , + 1 , + 1 − 1, + 1 , + 1 − 1, + 1 − = − ≤ + n s n s n s n s n s h H ε ε ε ε . □ 8 Any method with F < 1 will exhibit bounded deviations from a schedule, εn, s+ 1, and from the average headway, hn, s+ 1 – H. Bounded deviations from a schedule are important for systems with long headways in which passenger arrivals are not uniform in time, but adjust to the schedule. Bowman and Turnquist ( 1981) showed that if passengers choose their arrival times to minimize their wait, then their average waiting time is proportional to the buses’ average deviations from their schedule; see also Daganzo ( 1997a). Unfortunately, none of the headway based methods, ( 7), ( 8) and ( 9), satisfy the condition F < 1. It will be shown in Section 4 that the variances of their deviations from a schedule are unbounded. 4 Optimal control It is proposed to choose the control coefficients f that minimize the slack time ds required to avoid negative holding times while guaranteeing a maximum standard deviation from the schedule: i. e., a given level of schedule reliability. This proposal is reasonable because slack is inversely related to commercial speed. Let us define 2 ( f, n, s) ε σ as the function that returns var( ) n, s ε given f, n and s. From equation ( 10), we have Σ Σ − = − − = 1 , 0  , s n s j i i j n i s j ε f υ . If we assume that the noise terms are independent and identically distributed ( i. i. d.) with variance σ 2 , then var( ) ( ) . 1 0 2  2 , Σ Σ − = = s n s j i i j ε σ f ( 11a) Since all the terms in this summation are non negative, an upper bound to the variance of n, s ε is: ( , , ) ( ) lim var( ) ( ) , 0 2  2 , 2 2 Σ Σ ∞ = →∞ →∞ ≤ ≡ = n s j i i j s n σ n s σ ε σ f ε ε f f ( 11b) which will be our measure of schedule reliability. Theorem: If Σ = 1 =− n i n i f and = 0 i f for all other i then the right hand side of equation ( 11b) is unbounded. Proof: Let us first show that if Σ = 1 i i f then f 1, j. i i j Σ = ∀ ( 12a) If we assume that Σ = 1 i i f , the following is true: , 0.   1  1  1  1 Σ = Σ Σ = Σ Σ = Σ = Σ ∀ > − − − − − − f f f f f f f j i i j i k i k k j k k j i i k k k j i i j 9 The first equality is the definition of convolution; the second is obtained by interchanging the order of the summation; the third follows from the assumption; and the fourth by relabeling the dummy subscript index. When j = 1, Σ ≡ Σ i i j i i f f  by definition. Therefore 1  Σ = i i j f if j = 1. Thus by induction, f j i i j Σ = 1,∀  . Using this result, it is possible to show that Σ Σ ∞ = 0 2  ( ) j i i j f is unbounded. Notice that the index of the nonzero terms of the nth convolution must be in the interval [– nj, nj]. Thus Σ( ) Σ ( ) =− = nj i i j i nj i j f 2 f 2 , which consists of 2nj + 1 terms. A lower bound to Σ ( ) =− nj i nj i j f 2 is obtained by choosing the fi j values that minimize Σ ( ) =− nj i nj i j f 2 , subject to Σ = 1 =− nj i nj i j f as per ( 12a). The minimum arises when all the terms in these summations are equal, i. e., when f nj nj i nj i j = 1 ( 2 + 1) ,∀ − ≤ ≤ . ( ) ( ) ( ) . 2 1 1 2 1 2 1 2 2 2 + = + Σ = Σ ≥ + =− nj nj f f nj nj i i j i nj i j ( 12b) Since the sum Σ ∞ = 0 2 + 1 1 j nj diverges because it is a special case of the general harmonic series, so does ( 11b). □ Note that all the headway based control methods discussed in this paper, ( 7), ( 8) and ( 9), satisfy the conditions of this theorem. Therefore as mentioned in Section 3, σε 2( f) = ∞ and the methods cannot maintain a schedule. We also define 2 ( , n, s) h σ f as the function that returns the headway variance var( ) n, s h given f, n and s. Because the headway hn, s can be expressed as n s n s n s h H , , − 1, = + ε − ε , we have ( ) . 1 , 0  1 , Σ Σ − = − − − = + − s n s j i i j i j n i s j h H f f υ ( 13a) The headway variance again can be expressed as a sum of non negative terms, and is thus bounded above by the limiting case: ( , , ) ( ) lim var( ) ( ) . 0 2  1 2 , 2 2 Σ Σ ∞ = − →∞ →∞ ≤ ≡ = − n s j i i j i j s n h h σ f n s σ f h σ f f ( 13b) Methods ( 7) and ( 8) have been shown to have a bounded headway variance ( Daganzo, 2009a, 2009b; Daganzo and Pilachowski, 2009, 2011). Numerical calculations of ( 13b) show that the demand independent method ( 9) only produces bounded headway variances for low to medium demand levels, if the control coefficient is carefully chosen ( α ≈ 0.5). However, these high values of α result in long slack times, and therefore low commercial speeds. 8 8 Refer to ( 9a) and note that the slack time is αH. 10 To obtain the slack times ds that avoid negative holding times, we combine equations ( 4a) and ( 10), so that the holding time is expressed as a function of the control coefficients and noise terms: [( 1 ) ] . [( 1 ) ] 1 0  1  1 , , , 1, , Σ Σ Σ − = − + − − − − = − + − − = − + − − s s j i s i j s i j i j n i s j n s s s n s s n s k k n k s d f f f D d f β β υ β ε β ε ε ( 14a) Under the assumption of i. i. d. noise, the variance of the holding time Dn, s is the sum of many independent random variables, which as before is bounded above by the limiting case; i. e.: var( ) ( , ) lim var( ) [( 1 ) ]. 0 2  1  1 2 , 2 , Σ Σ ∞ = − + →∞ →∞ ≤ ≡ = + − − n s j i s i j s i j i j s n n s D s D σ f β D σ β f β f f ( 14b) According to the central limit theorem, Dn, s is approximately normal. Therefore, to ensure that the holding time is rarely negative, i. e., Pr{ 0} 0 , < ≈ n s D , we shall choose ( , ) 3 ( , ), s s D s d f β = σ f β ( 14c) so that the assumption is true 99.87% of the time. The optimization problem with J control stations is then the following mathematical program, where sε is the guaranteed standard deviation from the schedule. s. t. ( ) . ( MP1) min ( , ) 1 ε ε σ β s d J s s s ≤ Σ = f f f The functions in ( MP1) are given by ( 11b), ( 14b) and ( 14c), and can be calculated numerically. 4.1 Homogeneous Case Note that in ( MP1) the dimensionless demand rates, βs, at different stations ( from 1 to J) can be different; and so can the slacks, ds. But for demonstration purposes, it is assumed here that the demand rate is uniform ( βs = β) along the bus line. Now the slack time will also be the same ( d1 = d2 = ...) at all the stations. Thus the subscript s is now dropped, and ( MP1) becomes: s. t. ( ) . ( MP2) min ( , ) ε ε σ β s d f ≤ f f Appendix A shows that it is sometimes better to introduce holding times at control points spaced every few stations, and how to choose such spacing. Figure 1 shows the contour lines of σε( f) = sε and d( f, β) = d, when β = 0.1 for two methods that have two nonzero control coefficients. In Figure 1a, all fi = 0 except for f0 and f1, and in Figure 1b, only f0 and f 1 are nonzero. The interior of the dashed squares in the figures are the regions where the condition = Σ < 1 i i F f holds. We see that in either case, both σε( f) and d( f, β) are quasi convex functions of f within the stability region Σ < 1 i i f . Clearly the optimal control coefficient values for any sε are at the point where its σε = sε contour is tangent to a d 11 contour, with the two gradients pointing against each other. Figure 1 shows the loci of optimal control coefficients for different σε/ σ levels by means of dark diamonds. Since contours are convex, the solutions were obtained with a local gradient search. See Appendix B for the derivation of the gradients. This method works well with up to 7 nonzero control coefficients, which we have tested. Note from Figure 1 that the schedule based control method ( with fi = 0 ∀ i) is actually among the optimal solutions. Indeed, it provides the best possible schedule reliability ( always departing on time), though it requires much slack ( d/ σ = 3.4). ( a) ( b) Figure 1. The iso σε/ σ and iso d/ σ contours and the optimal control f* with two coefficients, β = 0.1. ( a) All fi = 0 except for f0 and f1; ( b) all fi = 0 except for f0 and f 1. Dotted lines within the square are the contours with equal σε/ σ value and solid lines are the contours with equal d/ σ value. The dashed square is the stability region. We also observe that the optimal control coefficients in both cases are very close to the f0 axis. This indicates that the optimal f1 * and f 1 * are very small, and that the performance of a control method with a single nonzero coefficient ( f0 ≠ 0) may be comparable with that with two or more nonzero coefficients. Table 1 confirms this guess. It shows the optimal slack time ( in units of σ) for β = 0.1. Different demand rates yield similar results. Table 1. Effect of the number of nonzero control coefficients on d*/ σ when β = 0.1. d* / σ σε / σ = 1 σε / σ = 1.2 σε / σ = 1.5 σε / σ = 2 fi = 0 ∀ i, except for f0 3.314 1.989 1.657 1.527 fi = 0 ∀ i, except for f 1, f0, f1 3.314 1.978 1.637 1.463 fi = 0 ∀ i, except for f 2, f 1, f0, f1, f2 3.314 1.978 1.637 1.463 Figure 2 shows the optimal control coefficients f 2 *, f 1 *, f0 *, f1 *, and f2 * for different β and σε / σ. Note that the optimal control coefficients are almost insensitive to changes in the dimensionless demand rate, β. This is good news, because in reality we may not know the demand rate very well. Also note that the values of f 2 *, f 1 *, f1 * and f2 * are roughly negligible ( absolute values less than 12 0.05 in Figure 2). 9 We did not show the other control coefficients because they are even smaller. So, the performance of a control method with only one nonzero coefficient ( f0 ≠ 0), which we call the “ simple control” method, should be near optimal. Figure 2. Optimal values of f 2 *, f 1 *, f0 *, f1 *, and f2 * with different demand rate and schedule reliability. This result is nice for both implementation and theoretical analysis. From the implementation point of view, only the arrival times of the current bus and its leading bus, as well as the virtual schedule, are needed to decide the holding time of the current bus at a given station. From an analysis point of view, the simple control method is helpful because formulas simplify and ( MP1) can be solved in closed form. The control law, bus motion, and metrics of interest are re derived below, with f0 being the only decision variable. For the system to be stable: F = f0 < 1 . Note that ( ) ( )  0 f f j i i j = δ , where δ ( i) is the discrete unit impulse function. In this case, the reader can verify that equations ( 4a), ( 4b), ( 11b), ( 13b), ( 14b), and ( 14c) reduce to: [( 1 ) ], n, s s s 0 n, s s n 1, s D d f − = − + β − ε − β ε ( 15a) , , + 1 0 , , + 1 = + n s n s n s ε f ε υ ( 15b) ( ) ( 1 2 ), 0 2 0 σ 2 f = σ − f ε ( 15c) ( ) 2 ( 1 2 ), 0 2 0 2 f f h σ = σ − ( 15d) 9 With perfect information on future bus arrival times, the elements f 2 * and f 1 * are already close to zero. In reality, information will be imperfect and transit agencies will probably rely less on the future bus arrival times, leading to the use of even smaller values for f 2 * and f 1 *. 13 [ ], 1 ( 1 ) ( , ) 2 0 2 2 0 2 0 2 f f f D − + − + = σ β β σ β ( 15e) and ( , ) 3 ( , ). 0 0 d f β σ f β D = ( 15f) Note that σε 2( f0) > σ2 if the system is stable ( f0 2 < 1). The optimal solution of ( MP1) is obtained by minimizing ( 15e) such that ( 15c) is bounded above by sε 2, where sε > σ. Clearly, ( 15c) must be binding. Thus in the optimal solution the actual variance σε 2 matches the target sε 2. Therefore, the optimal coefficient for the simple control method is: * 1 ( 2 / 2 ), where 2 2 , 0 σ σ σ σ ε ε f = − > ( 15g) and * 3 1 1 ( / ) 2 . 2 σ β σ 2 σ 2 β ε ε + ⎟⎠ ⎞ ⎜⎝ ⎛ d = + − − ( 15h) 4.2 Comparison with Other Control Methods Figure 3 plots ( 15h); it shows how the simple control method performs for different values of β. Note that it requires much less slack time than the schedule based control method, which is represented by the five points with σε / σ = 1. Curves like those shown in Figure 3 cannot be constructed for the headway based control methods discussed in this paper, because as we have demonstrated, σε 2( f) = ∞ in these cases; i. e., because their deviations from schedule εn, s grow unbounded as s grows. Figure 3. Slack time d vs. schedule reliability σε for the simple control method. Schedule based control method is represented by the points with σε / σ = 1. 14 To further compare the simple control method with the headway based methods, Figure 4 plots d / σ vs. the dimensionless headway standard deviations σh / σ that are allowed. Figure 4 shows that the simple control method behaves better than the forward headway based method given by ( 7), the two way headway based method given by ( 8), and the backward headwaybased method given by ( 9). In all three cases, the reduction in slack time is considerable. Note that the headway based methods cannot achieve σh / σ below 1.5 for any slack whatsoever, while the simple control method can. The improved results should not be surprising given that headway based methods are just special cases of the general control method, and that the simple method is near optimal. ( a) ( b) ( c) Figure 4. Slack time d vs. headway reliability σh to compare the simple control method with headway based control methods relying on: ( a) forward headway only; ( b) forward and backward headways; and ( c) backward headway only. 4.3 Balancing Schedule Reliability and Slack Time Previously, we have chosen to minimize slack time ( maximize commercial speed) subject to a schedule reliability constraint. This was appealing because it did not require knowledge of the passenger origin destination table. Here we assume that the average user trip length l is known and show how to balance the two metrics by minimizing the sum of the average passenger waiting and riding times. We will focus on bus lines operating with short headways and compare the five control methods ( schedule based, forward headway based, backward headway based, 15 two way headway based and the simple method). For bus lines with long headways, headwaybased control methods are not applicable, and the performance comparison of the schedule based and the simple control method would favor the latter even more. It is assumed that: ( i) the average bus cruising speed is vc ( i. e., including acceleration and deceleration due to the stops); ( ii) station spacing S is uniform; ( iii) demand β is uniform; ( iv) passengers value their waiting time γ ( γ > 1) times as much as their riding time; and ( v) control is applied at all stations. The passenger waiting time is: H 2 2 ( 2H) h + σ . The passenger riding time is l v H d l S c + ( β + ) . The weighted sum of the two can be expressed as the sum of a fixed component T0 and a variable component ΔT that depends on the control method: 2 , 0 T H l v H l S c = γ + + β ( 16a) T 2 ( 2H) d l S . h Δ = γ σ + ( 16b) Note T0 includes waiting, line haul riding and loading time under ideal conditions. It is the minimal possible travel time, and is achievable only if the bus system had no disturbances. The added term ΔT includes the extra time penalty passengers suffer due to non uniform headways and the slack time. The parameters σh 2 and d can be calculated as a function of their control coefficients with equations ( 13b), ( 14b) and ( 14c) for the four considered methods. For each method the control coefficients that minimize ( 16b) are obtained. Figure 5 shows the ratio ΔT/ T0 for the optimized control methods, as a function of the demand rates β and the dimensionless trip lengths l/ S. The following parameter values were used: S = 400 meters, H = 5 minutes, vc = 20 km/ hr, γ = 2 and σ = 10 seconds. For low demand rates ( 0.01 < β < 0.05), all the headway based methods and the simple method perform much better than the schedule based method. The ΔT/ T0 ratios in this situation are 4 11% for the backwardheadway based method, 5 10% for the forward headway based method and only 3 7% for the two way headway based method and the simple method. As demand increases, the backwardheadway based method becomes unstable and the simple method also outperforms the rest of methods with a maximal ΔT/ T0 ratio of 15% at β = 0.2 and l/ S = 25. Finally, note that the twoway headway based method and the simple method are practically indistinguishable. Both methods achieve such similar results because the optimization procedure leads to values of α ( the two way headway based control coefficient) which are practically zero. 16 Figure 5. Ratio of variable travel time over fixed travel time ( ΔT/ T0) for different control methods with various demand rates β and dimensionless trip lengths l/ S. 4.4 Sensitivity to the Control Coefficients Numerical calculation shows that control coefficients that do not differ much from the optimal control coefficients do not increase the required slack time much. Figure 6 shows the ratio of d/ d* when β = 0.1 and the general control method has two nonzero coefficients. In this figure, d is the slack time of the non optimal control coefficients at the indicated point and d* is the optimal slack time with the same σε value. We see that within a small neighborhood around the optimal coefficients f*, the ratio is close to 1 but large deviations can result in inefficiency. ( a) ( b) Figure 6. Sensitivity to control coefficients when β = 0.1. ( a) All fi = 0 except for f0 and f1; ( b) all fi = 0 except for f0 and f 1. The contour lines show the ratio of the non optimal slack time d* over the optimal slack time d with the same σε value. 17 5 Robustness to Large Disturbances When the system is subject to a large disturbance, such as a bus breakdown, the holding times as in ( 4a) may become negative and buses may bunch if nothing is done. It is proposed in this case to abandon the published schedule ( if one is provided) and to focus on regularizing headways. To do this, the virtual schedule is reformulated so it can absorb the effect of the disturbance. This will enable buses to recover from the effect of the large disruption and still provide service with regular headways. To demonstrate the idea, we next show how to modify the virtual schedule in two situations: ( i) when a bus is so far behind schedule that it cannot catch up by itself and ( ii) when a bus in the system goes out of service unexpectedly. Other situations can be handled similarly. Only the simple control method is studied. 5.1 Bus Far Behind Schedule According to assumption ( i), the holding time Dn, s as in ( 15a) will almost always be nonnegative. But when there is an unexpected large disturbance, the assumption can be violated, and Dn, s as calculated from ( 15a) may turn out to be negative. A negative Dn, s means that the control, instead of holding the bus back, would want to push it forward. This is an indication that the bus cannot keep up with the schedule by itself. To remedy this situation, the current virtual schedule can be shifted forward in time by the smallest possible Δt, so that the critical bus n0 at s0 ( and therefore all other buses) will be able to keep up with the new schedule by themselves. If we use primes to denote variables under the new virtual schedule, the changes are: ' , , , , , t t t n s n s n s = + Δ ∀ ( 17a) ' ' , , , , , , , a t t n s n s n s n s n s ε = − = ε − Δ ∀ ( 17b) ' [( 1 ) ' ' ] ( 1 ) , , . , 0 , 1, , 0 D d f D f t n s n s s s n s s n s n s = − + − − = + − Δ ∀ − β ε β ε ( 17c) However, adding too much slack time decreases the commercial speed. Therefore, only the necessary amount of Δt would be added in order to keep the holding time of the critical bus 0 , 0 ' n s D close to but greater than zero, i. e.: ( ) /( 1 ), 0 , 0 0 t D f n s Δ = − − ( 17d) where n0 , s0 D is given by ( 15a). In reality, ( 17d) can be modified to include an extra buffer time δ > 0: Δ = (− ) /( 1− ) + δ 0 , 0 0 t D f n s . Doing this ensures that the procedure does not have to be repeated too often, but delays all the buses a bit more. Note, this process ensures that the system returns to stability and that the process is repeatable, i. e., whenever we find the holding time Dn, s for a bus as in ( 15a) to be negative, the virtual schedule can be shifted forward again using the same method. 18 5.2 Bus Breakdown Now imagine there are N buses running on a loop and one bus suddenly breaks down. We will define a new virtual schedule so that the remaining N 1 buses can adhere to it and maintain regular headways, while keeping their commercial speed as fast as possible. As shown in Figure 7, we number the buses in a way that bus N breaks down, with bus 1 behind it. The headway in the original schedule is H, and the original schedule satisfies tn+ 1, s = tn, s + H ( for ∀ s, n = 1 to N 2). Under the new schedule, the loss of one bus results in a slightly larger equilibrium headway H’ ≈ NH/( N 1). 10 Thus the new schedule satisfies t’n+ 1, s = t’n, s + H’ ( for ∀ s, n = 1 to N 2). We assume that the schedule of bus 1 is shifted backward by a time Δt to be found ( Δt < 0 if shifted forward), i. e., t’ 1, s = t1, s – Δt. The schedules of the other buses are shifted to maintain the new headway H’: , , 1 to 1, 1 ' ( 1)( ' ) 1 , , , ∀ = − − = − Δ + − − = − Δ + − H s n N N t t t n H H t t n n s n s n s ( 18a) , , , , ' ' 1 , 1 to 1. n s n s n s n s 1 a t t n H sn N N ε = − = ε + Δ− − ∀ = − − ( 18b) Figure 7. Illustration of virtual schedule change when bus N is suddenly out of service. We assume that at the time of bus breakdown, the current ( or closest upstream) station of bus n is s( n). Under the new virtual schedule, the holding times for the given Δt would be: 10 This approximation is good if the cycle time of buses does not change much after the breakdown. The exact expression for the new headway is H'= H[( c + d) N][( c + d)( N − 1) − βH], where c is the average cruising time between stations, d is the slack time per station, and β is the dimensionless demand rate, in the homogeneous case. 19 , 1 1 ( 1 )( ) ( 1 ) 1 [( 1 ) ] ' [( 1 ) ' ' ] ( for 2 to  1) 0 0 ( ) ( ) ( ) 0 , ( ) ( ) 1, ( ) , ( ) ( ) ( ) 0 , ( ) ( ) 1, ( ) − + − − − Δ + − − = − + − − = − + − − = − − N H H N f t f n d f D d f n N s n s n s n n s n s n n s n n s n s n s n n s n s n n s n β β ε β ε β ε β ε ( 19a) . 1 ( 1 )( ) 2 [( 1 ) ] ' [( 1 ) ' ' ] ( for 1) 0 ( 1) ( 1) ( 1) 0 1, ( 1) ( 1) 1, ( 1) 1, ( 1) ( 1) ( 1) 0 1, ( 1) ( 1) 1, ( 1) H N f t N d f D d f n s s s s s N s s s s s s N s − − − Δ − − = − + − − = − + − − = − − β β ε β ε β ε β ε ( 19b) As in the last subsection, negative holding times indicate that the corresponding buses cannot keep up with the schedule. Thus Δt is found by solving: { } s. t. ' ( ) 0 1 to 1. ( MP3) arg min min ' ( ) , ( ) , ( ) Δ ≥ ∀ = − Δ = Δ D t n N t D t n s n n n s n Note that each non negativity constraint imposes an upper bound on Δt, and the solution for Δt is the minimum of these upper bounds. Thus the solution always exists. In reality, the transit agency may add a little buffer δ to Δt to ensure that the remaining N 1 buses do not experience frequent disturbances. The system can then be run with the simple control method, and the process in Section 5.1 can be used to account for other disturbances. 6 Control Law with Real Time Information on Demand So far, we have assumed that demand is quasi deterministic and known, but this may not always be realistic. In this section, we discuss how to relax our assumption on quasi deterministic demand by exploiting real time information on passenger boarding. We assume that the arrival of passengers follows a Poisson process, with the average demand at station s, βs, known. We also assume that the actual number of passengers to board bus n at station s, Xn, s, is stochastic. Thus if the headway is given, [  ] / , n, s n, s s n, s b E X h = β h t ( 20a) var(  ) / , n, s n, s s n, s b X h = β h t ( 20b) where tb is the average time needed to board a passenger. Although Xn, s is a random variable, we assume that its realization is observable when bus n finishes boarding at station s. 11 We will show that with this real time information, the control law can be slightly modified to achieve similar performance as in the quasi deterministic case. 11 This is possible because the number of boarding passengers can be measured either by a person at the station, or by an automatic passenger counter system. 20 The scheduled arrival times satisfy the same equation ( 1a). Average demand βs is used for the schedule, since real demand is unknown yet. n, s 1 n, s s s s . t = t + H + d + c + β ( 21a) The actual motion of buses is affected by the real demand: . , + 1 , , , , + 1 = + + + + n s n s b n s n s s n s a a t X D c υ ( 21b) Then, the deviations from schedule can be obtained by subtracting the previous two equations, ( 21a) from ( 21b): ( ) . , + 1 , , , , + 1 = + − + − + n s n s b n s s n s s n s ε ε t X β H D d υ ( 22a) Real time demand information is used to decide the holding time. This is feasible because boarding occurs before holding, and the realization of Xn, s is known when holding time is calculated. We propose the following instead of ( 4a): ( ) , , , , . n s s b n s s n s i i n i s D d tX H f β ε ε − = − − + − Σ ( 22b) Now if we combine ( 22a) and ( 22b), the evolution equation for the deviations from schedule as shown in ( 23) is the same as equation ( 4b): , 1 , , 1 . n s i i n i s n s ε fε υ + − + = Σ + ( 23) Thus with real time demand information, the motion of buses under the new control law will not change. The stability analysis and the expression for σε and σ h still hold. Only the expression for the slack time ds is slightly different, and is derived in Appendix C. The final result is that: d 3 2 t H. s D s b = σ + β ( 24) where σD 2 is calculated using ( 14b). Figure 8 compares the slack time required vs. schedule reliability under various demand rates, with parameters H = 5 minutes, tb = 4 seconds, and σ = 10 seconds. Slack times under quasi deterministic and stochastic situations are calculated by ( 14c) and ( 24) respectively. Clearly, the slack time has to be increased, but only significantly if β s tbH is large compared with σD 2. Therefore, the only changes needed to rigorously account for random demand fluctuations are to use ( 22b) instead of ( 4a) for the holding time, and ( 24) instead of ( 14c) for the slack time ds. 21 Figure 8. Comparison of slack time d vs. schedule reliability σε under various quasi deterministic and stochastic demand rates for the simple control method. 7 Conclusion In this paper, we studied a general control method, which is a family of dynamic holding strategies, to improve bus schedule reliability while providing the service with the fastest possible commercial speed. We have four main findings: • First, the general control method allows buses not only to maintain regular headways but also to adhere to their schedule. None of the existing adaptive methods can achieve this feat. Thus the proposed method is applicable to bus lines with both long and short headways. • Second, a simple control method, which is a one parameter version of the general control method, is found to be near optimal. It outperforms alternative control methods, but only requires information of the current bus and its leading bus. • Third, in case of large disturbances, buses can still maintain regular headways, by adapting the virtual schedule. This schedule adaptation method guarantees the robustness of the control method under any circumstance. • Finally, highly stochastic demand can be taken into account by slightly modifying the proposed general control method to incorporate real time demand information. References Abkowitz, M., Eiger, A., & Engelstein, I. ( 1986). Optimal control of headway variation on transit routes. Journal of Advanced Transportation, 20( 1), 73 88. Adamski, A., & Turnau, A. ( 1998). Simulation support tool for real time dispatching control in public transport. Transportation Research Part A: Policy and Practice, 32( 2), 73 87. 22 Barnett, A. ( 1974). On controlling randomness in transit operations. Transportation Science, 8( 2), 102 116. Bartholdi, J. ( 2011). ( private communication). Bowman, L. A., & Turnquist M. A. ( 1981). Service frequency, schedule reliability and passengers wait times at transit stops. Transportation Research Part A: General, 15( 6), 465 471. Daganzo, C. F. ( 1997a). Passenger waiting time: advertised schedules. In: Daganzo C. F. ( ed.), Fundamentals of transportation and traffic operations. Elsevier, New York, NY, 291 292. Daganzo, C. F. ( 1997b). Schedule instability and control. In: Daganzo C. F. ( ed.), Fundamentals of transportation and traffic operations. Elsevier, New York, NY, 304 309. Daganzo, C. F. ( 2006). On the variational theory of the traffic flow: well posedness, duality and applications. Networks and Heterogeneous Media, 1( 4), 601 619. Daganzo, C. F. ( 2009a). A cheap and resilient way to eliminate bus bunching. The 4th International Conference on Future Urban Transport, Gothenburg, Sweden. Daganzo, C. F. ( 2009b). A headway based approach to eliminate bus bunching: Systematic analysis and comparisons. Transportation Research Part B: Methodological, 43( 10), 913 921. Daganzo, C. F., & Pilachowski J. ( 2009). Reducing bunching with bus to bus cooperation. Working Paper UCB ITS VWP 2009 12, U. C. Berkeley Center for Future Urban Transport. Daganzo, C. F., & Pilachowski, J. ( 2011). Reducing bunching with bus to bus cooperation. Transportation Research Part B: Methodological, 45( 1), 267 277. Eberlein, X. J., Wilson, N. H. M., & Bernstein, D. ( 2001). The holding problem with real time information available. Transportation Science, 35( 1), 1 18. Golob, T. F., Canty, E. T., Gustafson, R. L., & Vitt, J. E. ( 1972). An analysis of consumer preferences for a public transportation system. Transportation Research, 6( 1), 81 102. Hickman, M. D. ( 2001). An analytic stochastic model for the transit vehicle holding problem. Transportation Science, 35( 3), 215 237. Koffman, D. ( 1978). A simulation study of alternative real time bus headway control strategies. Transportation Research Record 663, 41 46. Newell, G. F., & Potts, R. B. ( 1964). Maintaining a bus schedule. Proceedings of the 2nd Australian Road Research Board, 2, 388 393. Newell, G. F. ( 1974). Control of pairing of vehicles on a public transportation route, two vehicles, one control point. Transportation Science, 8( 3), 248 264. 23 Osuna, E. E., & Newell, G. F. ( 1972). Control strategies for an idealized public transportation system. Transportation Science, 6( 1), 52 72. Paine, F. T., Nash, A. N., Hille, S. J., & Brunner, G. A. ( 1967). Consumer conceived attributes of transportation: An attitude study. College Park: University of Maryland. Senevirante, P. N. ( 1990). Analysis of on time performance of bus services using simulation. Journal of Transportation Engineering, 116( 4), 517 531. Turnquist, M. A., & Bowman, L. A. ( 1980). The effects of network structure on reliability of transit service. Transportation Research Part B: Methodological, 14( 1 2), 79 86. Vandebona, U., & Richardson, A. J. ( 1986). Effect of checkpoint control strategies in a simulated transit operation. Transportation Research Part A: General, 20( 6), 429 436. Wallin, R. J., & Wright, P. H. ( 1974). Factors which influence modal choice. Traffic Quarterly, 28( 2), 271 289. Zhao, J., Dessouky, M., & Bukkapatnam, S. ( 2006). Optimal slack time for schedule based transit operations. Transportation Science, 40( 4), 529 539. Appendix A: A Method for Locating Control Stations We have assumed during the analysis that the proposed control method is applied at each station, but this is not always desirable. As shown in Daganzo ( 1997b, 2009), it is often beneficial to space out the control points more widely. In this spirit, it is assumed here that control stations are located every N stations, and N is treated as a decision variable. The demand rate β is assumed to be uniform throughout the bus line and such that β << 1. We will first transform the equations of bus motion from station to station into similar equations describing the bus motion from control station to control station, as if there were no intermediate stations. It will be shown that when β << 1, one may simply replace β and σ with β’ = Nβ and σ '= σ N + N( N − 1) β to model the bus motion in this manner. The variance of the noise between control stations ( σ’) 2 is simply given by ( 11a) using the { fi j} of the uncontrolled case and replacing s by N. Recall that for the uncontrolled situation, [ ] T f = L, 1 + β , − β , L . It can be seen from the binomial formulas that ( 1 ) ( ) .  m j m m j m j f − − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = β β ( A1) Thus, 24 [, 1 , , 0, ]. ( 1 ) ( ) , 2 , ( 1 ) , ( 1 ) 1 ( ), 2 2  T T j j j j j j j j L L L L β β β β β β β ≈ + − ⎥⎦ ⎤ ⎢⎣ ⎡ − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ f = + + − − − ( A2) The last approximation works because β << 1 and thus we can neglect terms of order β 2 and higher. Equation ( A2) can now be inserted in ( 11a) to yield: ( ( 1) ). ( 1 2 ) ( 1 ) ( ) ( ') ( ) 2 1 0 2 1 0 2 2 1 0 2  2 2 σ β σ β σ β β σ σ = + − ≈ + ⎥⎦ ⎤ ⎢⎣ ⎡ − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = = Σ Σ Σ Σ Σ − = − = − − = N N N j m j f N j N j m m j m N j m m j ( A3) It should also be clear from ( A2) that when j = N and β << 1, the dimensionless demand between control stations is β’ = Nβ. By setting β’ = Nβ and σ '= σ N + N( N − 1) β , we can treat the bus motion as if there were only stations at the control stations and apply ( MP2) with these new parameters. The number of stations between control stations, N, is however, a decision variable in the new version of ( MP2). Consideration of ( 11b) and ( 14b) reveals that this new mathematical program is: ' ( 1) . s. t. ' ( ) ( MP4) min ' ( , ) , β σ σ σ σ σ β σ σ ε ε = + − ≤ N N N s N d N N f f f This MP can be solved numerically as in Section 4.1, or analytically if we adopt the simple control method. Appendix B: Derivation of the Gradients for Greedy Search In developing Figure 1, we solved the following optimization problem, which is equivalent to ( MP2): s. t. ( ) . ( MP5) min ( , ) 2 2 2 ε ε σ σ β s D f ≤ f f From equations ( 11b) and ( 14b), we find the following expressions for σε 2( f) and σD 2( f, β), whose gradients we seek: 25 ( ) ( ) , 0 2  2 2 Σ Σ ∞ = = j i i j σ σ f ε f ( , ) [( 1 ) ]. 0 2  1  1 2 2 Σ Σ ∞ = − + = + − − D j i i j i j i j σ f β σ β f βf f Using generating functions, one can find the following expression for fi j: . ! ! ! ! 1 0 1 0 0 1 1 0 1 1 , , 0 1 1 0 1 1  Σ = = − − Σ Σ = − = − = − − rk i k j k k k k m k k m i j m r r m r r m f f f m k k k f j L L L ( B1) Since ,  −  − 1 ∂ ∂ = i j r i r j f f jf ( B2) The partial derivatives of σε 2( f) and σD 2( f, β) with respect to fr can be expressed as: 2 ( )( ), 0   1 2 2 Σ Σ ∞ = − − = ∂ ∂ j i i j i r j r f jf f σ σ ε ( B3) and [ ] [( 1 ) ( 1)]. 2 ( 1 )  1 1 1  0  1  1 2 2 i r j i r j i r j j i i j i j i j r D jf jf j f f f f f − − − − − − ∞ = − + + − − + = + − − ∂ ∂ Σ Σ β β σ β β σ ( B4) Appendix C: Derivation of the Slack Time Formula for the Control Law with Real Time Demand Information Recall that it is assumed that Pr{ 0} 0 , < ≈ n s D , i. e., [ ] 3 var( ). n, s n, s E D = D ( C1) It is first shown that the expectation of Dn, s is ds: [( )] [ ] [ ( ) ] . ( 1 ) ( 1 ) [ ] [ (  .,.)] 1 0  1  1 , , 1, , , , , , , s s s j i s i j s i j i j n i s j s s n s s n s i i n i s s s n s s n s i i n i s n s X n s d d E f f f d E f E d h H f E D E E D = = − + − − = − + − − = − − + − = Σ Σ Σ Σ − = − + − − − − − β β υ β ε β ε ε β β ε ε υ υ υ υ υ ( C2) Now, consider the law of total variance: 26 var( ) [ var(  .,.)] var( [  .,.]), , , , υ υ n s υ X n s υ X n s D = E D + E D ( C3) where [ var(  .,.)] [ var(  .,.)] [ ] , , , , E D E t X E t h t H X n s X b n s v s b n s s b υ υ β β υ υ = − = = ( C4) and ( [ ]) ([ ]) ( ) { ( ) } . var ( 1 ) var ( ) var ( ) var[ (  .,.)] var 2 1 0  1  1 , , 1, , , , 1, , , , , , , D s j i s i j s i j i j n i s j s n s n s n s i i n i s s s n s n s n s i i n i s X n s s s n s s n s i i n i s f f f f d f E D d h H f σ β β υ β ε ε ε ε β ε ε ε ε υ β β ε ε υ υ υ υ υ = = + − − = − + − = − − + − = − − + − Σ Σ Σ Σ Σ − = − + − − − − − − − ( C5) Thus it follows that var( ) [ var(  .,.)] var( [  .,.]) 2 , , , , D E D E D t H n s X n s X n s D s b υ υ σ β υ υ = + = + where σD 2 is calculated using ( 14b). Now according to ( C1): d 3 2 t H. s D s b = σ + β ( C6)
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  A dynamic holding strategy to improve bus schedule reliability and commercial speed 
Subject  TA1001.C795 no. 20111; Bus linesTimetablesMathematical models.; BusesSpeedMathematical models.; SchedulingMathematical models. 
Description  Performed by UC Berkeley Center for Future Urban Transport.; "A Volvo Center of Excellence."; "March 2011."; Includes bibliographical references (leaves 2123). 
Creator  Xuan, Yiguang. 
Publisher  Institute of Transportation Studies, University of California, Berkeley 
Contributors  Argote, Julian.; Daganzo, Carlos.; UC Berkeley Center for Future Urban Transport.; University of California, Berkeley. Institute of Transportation Studies. 
Type  Text 
Language  eng 
Relation  Also available online.; http://www.its.berkeley.edu/publications/UCB/2011/VWP/UCBITSVWP20111.pdf; http://worldcat.org/oclc/710154049/viewonline 
DateIssued  [2011] 
FormatExtent  26 leaves : charts ; 28 cm. 
RelationIs Part Of  Working paper ; UCBITSVWP20111; Working paper (UC Berkeley Center for Future Urban Transport) ; UCBITSVWP20111. 
Transcript  INSTITUTE OF TRANSPORTATION STUDIES UNIVERSITY OF CALIFORNIA, BERKELEY A Dynamic Holding Strategy to Improve Bus Schedule Reliability and Commercial Speed Yiguang Xuan, Juan Argote, and Carlos F. Daganzo WORKING PAPER UCB ITS VWP 2011 1 March 2011 1 A Dynamic Holding Strategy to Improve Bus Schedule Reliability and Commercial Speed Yiguang Xuan, Juan Argote, and Carlos F. Daganzo Institute of Transportation Studies University of California, Berkeley, CA 94720 ( March 18, 2011) Abstract Bus systems are naturally unstable. Without control, the slightest disturbance to bus motion can cause buses to bunch, reducing schedule reliability. Holding strategies can eliminate this instability. However, the conventional schedule based holding method requires too much slack time, which slows buses. This delays on board passengers and increases operating costs. This paper studies a family of dynamic holding strategies that use the current state of all buses, as well as a virtual schedule. The virtual schedule is introduced whether the system is run with a published schedule or not. We found that with this control method, which we term general control method, buses can both closely adhere to schedule and maintain regular headways without too much slack. Thus the general control idea is applicable to bus lines with both long and short headways. Although the optimal set of control parameters can be found numerically, a oneparameter version of the control method can be optimized in closed form. This simple method was shown to be near optimal. To put it in practice, one only needs the arrival times of the current bus and the preceding bus relative to the virtual schedule. This simple method was found to outperform alternative control methods ( i. e., require less slack for the same headway variance). While the paper mostly focuses on recurrent small disturbances under quasi deterministic demand, it also shows that the proposed control method can deal with large disturbances. Keywords: bus bunching, bus schedule reliability, headway variance, commercial speed, dynamic holding, control method. 1 Introduction Bus schedule reliability is an essential attribute of a bus system, and is consistently ranked as one of the major concerns by passengers ( Paine et al., 1967; Golob et al., 1972; Wallin et al., 1974). Unfortunately, bus systems are naturally unstable, and buses tend to fall off schedule without intervention. This instability is due to the fact that the loading time of a bus at a station1 is a non decreasing function of the headway between buses. As first explained by Newell & Potts ( 1964), early buses encounter and serve fewer passengers, and tend to catch up with the buses in front of them, while late buses tend to fall further behind. The tendencies result in the so called 1 To avoid confusion, we use bus stations to mean locations where buses stop to pick up or drop off passengers. Stop is only used as a verb. 2 “ bus bunching” phenomenon, which annuls the schedule and increases the average waiting time of passengers. Bus holding strategies may eliminate this problem. They are characterized by embedding slack time in the schedule, and holding buses at each control station for a period of time before their scheduled departure. A bus is generally held longer if it is ahead of schedule and shorter ( or not even held) if it is behind schedule, so that the instability can be neutralized. The most common form of holding is the “ schedule based” method, in which drivers are instructed never to depart a control station ahead of a pre published schedule. Among the literature that analytically addresses the bus bunching problem with holding methods, most of the studies ( Osuna and Newell, 1972; Newell, 1974; Barnett, 1974; Hickman, 2001; Eberlein et al, 2001; Zhao et al, 2006) try to minimize passenger time ( either waiting time at the station only or both waiting at the station and riding time on board). Problems based on this objective are difficult, and most of these studies only discuss problems with one bus line, a single control station, and either one or two buses. 2 Some use “ rolling horizon” heuristics. Many more studies resort to simulations ( Koffman, 1978; Turnquist & Bowman, 1980; Abkowitz et al., 1986; Vandebona & Richardson, 1986; Senevirante, 1990; Adamski & Turnau, 1998) due to the difficult nature of the problem. There is also a literature that uses control theory. Daganzo ( 2009b) approached the bus bunching problem from a different angle: instead of minimizing passenger waiting time, the paper proposed a headway based dynamic holding strategy to reduce the amount of slack time in the schedule, subject to a headway variability constraint. The idea was to increase the commercial speed of buses3 while compensating for the effects of small disturbances ( e. g., due to traffic). With this new objective, the paper analytically addressed a much broader range of problems: systems with many buses, many control stations, and stochastic cruising time. The article proposed a general form for this family of dynamic holding strategies by defining a convolution kernel. However, it only studied in depth a particular case: a headway based control in which buses were held based only on the expected demand and their forward headway ( the headway between the current bus and the bus in front) for systems where a schedule is not published. It was shown that headways could be regularized with less slack than required by the schedulebased control method. Unfortunately, as explained in the reference, the method cannot always compensate for large disturbances, such as those due to bus breakdown. To alleviate this problem, Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) proposed a cooperative control method in which bus speed was regulated based on the expected demand and the spacings between the current bus and the preceding and following buses. This method was able to compensate for large disturbances. 4 More recently, a holding method in 2 The exception is Eberlein et al ( 2001) which addresses an arbitrary number of buses. But the study does not model the cruising time between two stations stochastically. 3 The commercial speed of buses is the total distance traveled divided by total time taken ( including scheduled holding). 4 The Eulerian version of the method in Daganzo and Pilachowski ( 2009, 2011) is used here, in which holding times would be based on the forward and backward headways ( the headway between the current bus and the bus behind). 3 which the holding times are based only on the backward headway, independent of demand, has been proposed ( Bartholdi, 2011). The method is appealing because it is very simple and it has been tested successfully with an experiment for a case with low demand. It is claimed that this approach can also compensate for large disturbances ( Bartholdi, 2011). The results about to be described build on Daganzo ( 2009b). A general control method is proposed that uses both the arrival times of all buses at stations and a virtual schedule. As such, the method includes as special cases all three existing models in the control genre. The virtual schedule is different from the published schedule, and is used even if there is no published schedule, as occurs in bus lines with short headways. Unlike the existing methods, we found that with this general control method, buses can not only maintain regular headways but also stick to their schedule. This is important because the control method then can be applied to bus lines with both long and short headways. The optimal parameters of the general control method, i. e. those which provide the maximum commercial speed for a given schedule/ headway reliability level are also identified. It turned out that a one parameter version of the method, which only requires information on the current bus and its leading bus, is near optimal and outperforms other existing control alternatives. While this paper focuses on small disturbances to the bus operation, the case of large disturbances is also addressed. The paper is organized as follows. Section 2 presents the assumptions and the bus motion laws under the general control method. Section 3 proves that with this method buses are able to adhere to their schedule with only minor random deviations. Section 4 demonstrates that a simple version of the general control method is near optimal, and that it outperforms the other existing methods. Sections 5 and 6 discuss how to handle large disturbances and highly stochastic demand. Finally Section 7 summarizes the main findings. 2 Assumptions and Bus Motion Formulation 2.1 Assumptions The same assumptions are made as in Daganzo ( 2009b): ( a) the number of bus dispatches and stations in the system can be as high as desired; ( b) buses are always dispatched on time with equal headways from the first station; ( c) the bus capacity for passengers is unlimited; ( d) buses do not pass each other; ( e) vehicle running times between adjacent stations are modeled as independent random variables; ( f) demand is stochastic but its contribution to the variance of the running time between stations is assumed to be negligible compared with the variance due to traffic ( we call this quasi deterministic demand); ( g) the bus loading time is dominantly affected by boarding passengers; ( h) only those passengers arriving during the inter arrival time will board the bus, and holding is then applied after the boarding process; ( i) there exists enough slack to ensure that the holding time never runs short; ( j) buses stop at all stations and holding is also applied at all stations. Assumption ( a) makes the analysis comparable to a situation with a finite number of buses but enough layover time, so that buses are always dispatched on time. Assumptions ( b) and ( c) 4 are reasonable if the operational design problem for a bus line ( i. e., to choose proper dispatching headways, fleet size, and vehicle size for a given route) has already been addressed. Assumption ( d) is reasonable if the system is well managed. But even if passing is allowed, we can renumber the buses and results will not change much. Assumption ( f) is relaxed in Section 6 to account for highly stochastic demand. Assumption ( g) is appropriate for bus systems, where boardings and alightings occur simultaneously and the alighting time per passenger is much smaller than the boarding time per passenger. Assumption ( h) greatly simplifies the formulation with only negligible effect, since the loading and holding times are much shorter compared with the interarrival time. Assumption ( i) makes the formulation linear and the problem tractable, as will soon be shown. Assumption ( j) can be relaxed ( see Appendix A). 2.2 Bus Motion with a Control Law Let us use n ( n = 0, 1, 2, …) to denote the bus number ( the buses dispatched first have smaller numbers) and s ( s = 0, 1, 2 …) to denote the station number ( increasing s in the traveling direction). The notation follows Daganzo ( 2009b): • tn, s is the scheduled arrival time of bus n at station s. The tn, s’s form the virtual schedule for buses; they are not the published schedule to passengers. A published schedule can be obtained by shifting the virtual schedule earlier in time to ensure that buses never depart ahead of the published schedule. • an, s is the actual arrival time of bus n at station s. • εn, s = an, s – tn, s is the deviation from scheduled arrival time of bus n at station s. • hn, s = an, s – an 1, s is the time headway between bus n and its leading bus at station s. • H is the scheduled headway. • cs is the average cruising time from station s to s+ 1, which includes the time to accelerate and decelerate, but does not include the dwell time to serve passengers. • υn, s+ 1 is the random noise in the cruising time of bus n between station s to s+ 1, whose mean is zero and variance is σn, s+ 1 2. • Dn, s is the holding time applied to bus n at station s. 5 • ds is the amount of slack time in the virtual schedule at station s ( i. e., the holding time if the bus arrives when expected). • β s is a dimensionless measure for the demand rate at station s, where the demand rate ( in passengers/ hour) is normalized by the passenger boarding rate ( also in passengers/ hour). This implies that the passenger loading time at station s increases by β s if headway increases by one unit of time. Typical values of β s range from 10 2 to 10 1. With the above notation, the scheduled arrival times can be formulated as: n, s 1 n, s s s s , t = t + H + d + c + β ( 1a) , , 1, t t H n s n s = + − ( 1b) 5 In reality, we recommend holding buses en route by slowing them down shortly after departing the station and by providing drivers with adequate real time information. This unnerves passengers less, and releases station capacity in those cases where the station is also used by other bus lines as well. 5 with n s s s t + β H + d , being the scheduled departure times. The actual arrival times obey: . , + 1 , , , , + 1 = + + + + n s n s s n s n s s n s a a β h D c υ ( 2) By combining equations ( 1) and ( 2), it is possible to express the motion of buses in terms of εn, s: ( ) ( ). n, s 1 n, s s n, s n 1, s n, s 1 n, s s = + − + + D − d + − + ε ε β ε ε υ ( 3) It is assumed that Dn, s is a linear function of the arrival times of all buses at station s, ai, s, or equivalently as a function of the deviations from the schedule, the εi, s. 6 It is convenient to write this function as: [( 1 ) ] , , , 1, , Σ − − = − + − + n s s s n s s n s i i n i s D d β ε β ε f ε ( 4a) because plugging ( 4a) into ( 3), yields the simple relation: . , + 1 − , , + 1 = Σ + n s i i n i s n s ε f ε υ ( 4b) To define a specific control method one needs to specify the slack times ds at each station and all the control coefficients {…, f 1, f0, f1, …}. All three holding strategies in the control genre mentioned in the introduction are special cases of this general control method. For example, if we set f0 = 1 + βs, f1 = – βs and fi = 0 ∀ i∉{ 0, 1}, we obtain the case with no control, because then Dn, s = ds = 0. In this case, the bus motion is governed by ( 1 ) . , + 1 , − 1, , + 1 = + − + n s s n s s n s n s ε β ε β ε υ ( no control) ( 5) The conventional schedule based control method is the case with fi = 0 ∀ i. In this case, the drivers are instructed not to depart the control station before the scheduled departure time. If there is enough slack time in the schedule as per assumption ( i), the buses can always depart the control station on schedule, i. e., n s s n s n s n s s s a + β h + D = t + β H + d , , , , . Therefore, it follows that [ ( )], n, s s n, s s n, s n 1, s D d − = − ε + β ε − ε ( sch. control) ( 6a) and . , + 1 , + 1 = n s n s ε υ ( sch. control) ( 6b) The method in Daganzo ( 2009b), which is based on the forward headway is: ( )( ). , , D d h H n s s s n s = − α + β − ( forward headway) ( 7a) This can be expressed as a function of the deviation from the schedule as: ( )( ). n, s s s n, s n 1, s D d − = − α + β ε − ε ( forward headway) ( 7b) 6 The arrival times of the current bus and the buses in front, ai, s’s for i ≤ n, are readily available when bus n arrives at station s. But the arrival times of the buses behind, ai, s’s for i > n, can only be predicted. For now, we will assume that we have perfect information, i. e., we know all ai, s’s. We will demonstrate later that this assumption is acceptable. 6 This is the special case of ( 4a) with f0 = 1 – α, f1 = α, fi = 0 ∀ i∉{ 0, 1}, where 0 < α < 1, and ( 4b) becomes: ( 1 ) . , + 1 , − 1, , + 1 = − + + n s n s n s n s ε α ε αε υ ( forward headway) ( 7c) Similarly, the Eulerian version7 of the ( Lagrangian) method in Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) , which is based on both the forward and backward headways, is obtained by setting f 1 = f1 = α, f0 = 1 – 2α, fi = 0 ∀ i∉{ 1, 0, 1}, where 0 < α < 1/ 2. This yields: ( ) ( )( ), , 1, , D d h H h H n s s n s s n s = + − − + − + α α β ( two way headway) ( 8a) ( 2) ( ) , n, s s n 1, s s n, s s n 1, s D d + − = + αε − β + α ε + β + α ε ( two way headway) ( 8b) and ( 1 2 ) . + 1, + 1, , − 1, , + 1 = + − + + n s n s n s n s n s ε αε α ε αε υ ( two way headway) ( 8c) Finally, a demand independent method based on the backward headway alone ( Bartholdi, 2011) is obtained by setting f 1 = α, f0 = 1 + βs – α, f1 = – βs and fi = 0 ∀ i∉{ 1, 0, 1}. This results in: ( ), , 1, 1, D h H h H n s n s n s = = + − + + α α α ( backward headway) ( 9a) ( ) , n, s n 1, s n, s s n, s n 1, s D H d + + = α + ε − ε = − αε + αε ( backward headway) ( 9b) and ( 1 ) . , + 1 + 1, , − 1, , + 1 = + + − − + n s n s s n s s n s n s ε αε β α ε β ε υ ( backward headway) ( 9c) 3 Stability Analysis This section shows that with the general control method, buses are able to adhere to their schedule with bounded deviations. Of course, this means that they can also maintain regular headways. As in Daganzo ( 2009b), we first express the summation term in ( 4b) as the convolution ( denoted with *) of two vectors: the bus deviations from the schedule εs = [… ε n  1, s εn, s ε n + 1, s …] T and the kernel of the convolution ( the set of control coefficients) f = [… f 1 f0 f1 …] T. The nth element of the convolution is: [ ] Σ − = s n k n k k s f , f * ε ε . If we also define s υ = [… 7 The control method introduced in Daganzo and Pilachowski ( 2009, 2011) and Daganzo ( 2009a) is consistent with a Lagrangian specification of the buses system, while the proposed general control in this paper is based on an Eulerian specification. Daganzo ( 2006) demonstrates the close connection between Lagrangian and Eulerian coordinates in the context of automobile motion. 7 υ n  1, s υn, s υ n + 1, s …] T as the vector of disturbances, then the vector form of ( 4b) is 1 1 * + + = + s s s ε f ε υ . Now apply the convolution iteratively, so that the ε. terms can be expressed as a function of the control coefficients f and the noise terms υ. . This yields: * * ( * ) * * * ... 1 1 1 1 1 1 = + = + + = + + = s+ s+ s s+ s s− s+ s s− ε υ f ε υ f υ f ε υ f υ f f ε . Next define  j f to be the jth self convolution of f ( i. e.,   1 * − = j j f f f , where  0 f = [… 0 1 0 …] T). Since assumption ( b) states that buses are always dispatched from the first station on time ( ε = 0 0 ), the above expression becomes: * , 1 0 s 1 j s s+ j= j + − ε = Σ f υ ( 10a) which expands to [ * ] . , 1 0 1 0 , 1 Σ Σ Σ + = + − = − + − = = s j i i j n i s j s n s j j s j n ε f υ f υ ( 10b) It is now possible to see that the following is true. Lemma: Define = Σ i i F f , then j i i j Σ f ≤ F  . Proof: Σ Σ Σ Σ Σ Σ( Σ ) Σ − − − − − − − = ≤ = = i i j i k k j i k i k k j i k k k j i i k k k j f f f f f f f F f   1  1  1  1 ... ... .  2 2 j k k j ≤ ≤ F Σ f ≤ ≤ F − □ Proposition: If 1 and M n s ≤ , + 1 υ , then n, s+ 1 ε is bounded above by M /( 1− F) Proof: Σ Σ Σ Σ + = − + − = − + − = ≤ s j i i j n i s j s n s j i i j n i s j f f , 1 0  , 1 0  , 1 ε υ υ ( since ) 0  1 M f M n, s s j i i j ≤ ≤ = + Σ Σ υ ( as per Lemma) 0 Σ = ≤ s j M F j ( since 1). 1 1 1 1 < − → − = − + F F M F M F s □ Corollary: If n, s+ 1 ε is bounded, then h H n s − , + 1 is also bounded. Proof: , + 1 , + 1 − 1, + 1 , + 1 − 1, + 1 − = − ≤ + n s n s n s n s n s h H ε ε ε ε . □ 8 Any method with F < 1 will exhibit bounded deviations from a schedule, εn, s+ 1, and from the average headway, hn, s+ 1 – H. Bounded deviations from a schedule are important for systems with long headways in which passenger arrivals are not uniform in time, but adjust to the schedule. Bowman and Turnquist ( 1981) showed that if passengers choose their arrival times to minimize their wait, then their average waiting time is proportional to the buses’ average deviations from their schedule; see also Daganzo ( 1997a). Unfortunately, none of the headway based methods, ( 7), ( 8) and ( 9), satisfy the condition F < 1. It will be shown in Section 4 that the variances of their deviations from a schedule are unbounded. 4 Optimal control It is proposed to choose the control coefficients f that minimize the slack time ds required to avoid negative holding times while guaranteeing a maximum standard deviation from the schedule: i. e., a given level of schedule reliability. This proposal is reasonable because slack is inversely related to commercial speed. Let us define 2 ( f, n, s) ε σ as the function that returns var( ) n, s ε given f, n and s. From equation ( 10), we have Σ Σ − = − − = 1 , 0  , s n s j i i j n i s j ε f υ . If we assume that the noise terms are independent and identically distributed ( i. i. d.) with variance σ 2 , then var( ) ( ) . 1 0 2  2 , Σ Σ − = = s n s j i i j ε σ f ( 11a) Since all the terms in this summation are non negative, an upper bound to the variance of n, s ε is: ( , , ) ( ) lim var( ) ( ) , 0 2  2 , 2 2 Σ Σ ∞ = →∞ →∞ ≤ ≡ = n s j i i j s n σ n s σ ε σ f ε ε f f ( 11b) which will be our measure of schedule reliability. Theorem: If Σ = 1 =− n i n i f and = 0 i f for all other i then the right hand side of equation ( 11b) is unbounded. Proof: Let us first show that if Σ = 1 i i f then f 1, j. i i j Σ = ∀ ( 12a) If we assume that Σ = 1 i i f , the following is true: , 0.   1  1  1  1 Σ = Σ Σ = Σ Σ = Σ = Σ ∀ > − − − − − − f f f f f f f j i i j i k i k k j k k j i i k k k j i i j 9 The first equality is the definition of convolution; the second is obtained by interchanging the order of the summation; the third follows from the assumption; and the fourth by relabeling the dummy subscript index. When j = 1, Σ ≡ Σ i i j i i f f  by definition. Therefore 1  Σ = i i j f if j = 1. Thus by induction, f j i i j Σ = 1,∀  . Using this result, it is possible to show that Σ Σ ∞ = 0 2  ( ) j i i j f is unbounded. Notice that the index of the nonzero terms of the nth convolution must be in the interval [– nj, nj]. Thus Σ( ) Σ ( ) =− = nj i i j i nj i j f 2 f 2 , which consists of 2nj + 1 terms. A lower bound to Σ ( ) =− nj i nj i j f 2 is obtained by choosing the fi j values that minimize Σ ( ) =− nj i nj i j f 2 , subject to Σ = 1 =− nj i nj i j f as per ( 12a). The minimum arises when all the terms in these summations are equal, i. e., when f nj nj i nj i j = 1 ( 2 + 1) ,∀ − ≤ ≤ . ( ) ( ) ( ) . 2 1 1 2 1 2 1 2 2 2 + = + Σ = Σ ≥ + =− nj nj f f nj nj i i j i nj i j ( 12b) Since the sum Σ ∞ = 0 2 + 1 1 j nj diverges because it is a special case of the general harmonic series, so does ( 11b). □ Note that all the headway based control methods discussed in this paper, ( 7), ( 8) and ( 9), satisfy the conditions of this theorem. Therefore as mentioned in Section 3, σε 2( f) = ∞ and the methods cannot maintain a schedule. We also define 2 ( , n, s) h σ f as the function that returns the headway variance var( ) n, s h given f, n and s. Because the headway hn, s can be expressed as n s n s n s h H , , − 1, = + ε − ε , we have ( ) . 1 , 0  1 , Σ Σ − = − − − = + − s n s j i i j i j n i s j h H f f υ ( 13a) The headway variance again can be expressed as a sum of non negative terms, and is thus bounded above by the limiting case: ( , , ) ( ) lim var( ) ( ) . 0 2  1 2 , 2 2 Σ Σ ∞ = − →∞ →∞ ≤ ≡ = − n s j i i j i j s n h h σ f n s σ f h σ f f ( 13b) Methods ( 7) and ( 8) have been shown to have a bounded headway variance ( Daganzo, 2009a, 2009b; Daganzo and Pilachowski, 2009, 2011). Numerical calculations of ( 13b) show that the demand independent method ( 9) only produces bounded headway variances for low to medium demand levels, if the control coefficient is carefully chosen ( α ≈ 0.5). However, these high values of α result in long slack times, and therefore low commercial speeds. 8 8 Refer to ( 9a) and note that the slack time is αH. 10 To obtain the slack times ds that avoid negative holding times, we combine equations ( 4a) and ( 10), so that the holding time is expressed as a function of the control coefficients and noise terms: [( 1 ) ] . [( 1 ) ] 1 0  1  1 , , , 1, , Σ Σ Σ − = − + − − − − = − + − − = − + − − s s j i s i j s i j i j n i s j n s s s n s s n s k k n k s d f f f D d f β β υ β ε β ε ε ( 14a) Under the assumption of i. i. d. noise, the variance of the holding time Dn, s is the sum of many independent random variables, which as before is bounded above by the limiting case; i. e.: var( ) ( , ) lim var( ) [( 1 ) ]. 0 2  1  1 2 , 2 , Σ Σ ∞ = − + →∞ →∞ ≤ ≡ = + − − n s j i s i j s i j i j s n n s D s D σ f β D σ β f β f f ( 14b) According to the central limit theorem, Dn, s is approximately normal. Therefore, to ensure that the holding time is rarely negative, i. e., Pr{ 0} 0 , < ≈ n s D , we shall choose ( , ) 3 ( , ), s s D s d f β = σ f β ( 14c) so that the assumption is true 99.87% of the time. The optimization problem with J control stations is then the following mathematical program, where sε is the guaranteed standard deviation from the schedule. s. t. ( ) . ( MP1) min ( , ) 1 ε ε σ β s d J s s s ≤ Σ = f f f The functions in ( MP1) are given by ( 11b), ( 14b) and ( 14c), and can be calculated numerically. 4.1 Homogeneous Case Note that in ( MP1) the dimensionless demand rates, βs, at different stations ( from 1 to J) can be different; and so can the slacks, ds. But for demonstration purposes, it is assumed here that the demand rate is uniform ( βs = β) along the bus line. Now the slack time will also be the same ( d1 = d2 = ...) at all the stations. Thus the subscript s is now dropped, and ( MP1) becomes: s. t. ( ) . ( MP2) min ( , ) ε ε σ β s d f ≤ f f Appendix A shows that it is sometimes better to introduce holding times at control points spaced every few stations, and how to choose such spacing. Figure 1 shows the contour lines of σε( f) = sε and d( f, β) = d, when β = 0.1 for two methods that have two nonzero control coefficients. In Figure 1a, all fi = 0 except for f0 and f1, and in Figure 1b, only f0 and f 1 are nonzero. The interior of the dashed squares in the figures are the regions where the condition = Σ < 1 i i F f holds. We see that in either case, both σε( f) and d( f, β) are quasi convex functions of f within the stability region Σ < 1 i i f . Clearly the optimal control coefficient values for any sε are at the point where its σε = sε contour is tangent to a d 11 contour, with the two gradients pointing against each other. Figure 1 shows the loci of optimal control coefficients for different σε/ σ levels by means of dark diamonds. Since contours are convex, the solutions were obtained with a local gradient search. See Appendix B for the derivation of the gradients. This method works well with up to 7 nonzero control coefficients, which we have tested. Note from Figure 1 that the schedule based control method ( with fi = 0 ∀ i) is actually among the optimal solutions. Indeed, it provides the best possible schedule reliability ( always departing on time), though it requires much slack ( d/ σ = 3.4). ( a) ( b) Figure 1. The iso σε/ σ and iso d/ σ contours and the optimal control f* with two coefficients, β = 0.1. ( a) All fi = 0 except for f0 and f1; ( b) all fi = 0 except for f0 and f 1. Dotted lines within the square are the contours with equal σε/ σ value and solid lines are the contours with equal d/ σ value. The dashed square is the stability region. We also observe that the optimal control coefficients in both cases are very close to the f0 axis. This indicates that the optimal f1 * and f 1 * are very small, and that the performance of a control method with a single nonzero coefficient ( f0 ≠ 0) may be comparable with that with two or more nonzero coefficients. Table 1 confirms this guess. It shows the optimal slack time ( in units of σ) for β = 0.1. Different demand rates yield similar results. Table 1. Effect of the number of nonzero control coefficients on d*/ σ when β = 0.1. d* / σ σε / σ = 1 σε / σ = 1.2 σε / σ = 1.5 σε / σ = 2 fi = 0 ∀ i, except for f0 3.314 1.989 1.657 1.527 fi = 0 ∀ i, except for f 1, f0, f1 3.314 1.978 1.637 1.463 fi = 0 ∀ i, except for f 2, f 1, f0, f1, f2 3.314 1.978 1.637 1.463 Figure 2 shows the optimal control coefficients f 2 *, f 1 *, f0 *, f1 *, and f2 * for different β and σε / σ. Note that the optimal control coefficients are almost insensitive to changes in the dimensionless demand rate, β. This is good news, because in reality we may not know the demand rate very well. Also note that the values of f 2 *, f 1 *, f1 * and f2 * are roughly negligible ( absolute values less than 12 0.05 in Figure 2). 9 We did not show the other control coefficients because they are even smaller. So, the performance of a control method with only one nonzero coefficient ( f0 ≠ 0), which we call the “ simple control” method, should be near optimal. Figure 2. Optimal values of f 2 *, f 1 *, f0 *, f1 *, and f2 * with different demand rate and schedule reliability. This result is nice for both implementation and theoretical analysis. From the implementation point of view, only the arrival times of the current bus and its leading bus, as well as the virtual schedule, are needed to decide the holding time of the current bus at a given station. From an analysis point of view, the simple control method is helpful because formulas simplify and ( MP1) can be solved in closed form. The control law, bus motion, and metrics of interest are re derived below, with f0 being the only decision variable. For the system to be stable: F = f0 < 1 . Note that ( ) ( )  0 f f j i i j = δ , where δ ( i) is the discrete unit impulse function. In this case, the reader can verify that equations ( 4a), ( 4b), ( 11b), ( 13b), ( 14b), and ( 14c) reduce to: [( 1 ) ], n, s s s 0 n, s s n 1, s D d f − = − + β − ε − β ε ( 15a) , , + 1 0 , , + 1 = + n s n s n s ε f ε υ ( 15b) ( ) ( 1 2 ), 0 2 0 σ 2 f = σ − f ε ( 15c) ( ) 2 ( 1 2 ), 0 2 0 2 f f h σ = σ − ( 15d) 9 With perfect information on future bus arrival times, the elements f 2 * and f 1 * are already close to zero. In reality, information will be imperfect and transit agencies will probably rely less on the future bus arrival times, leading to the use of even smaller values for f 2 * and f 1 *. 13 [ ], 1 ( 1 ) ( , ) 2 0 2 2 0 2 0 2 f f f D − + − + = σ β β σ β ( 15e) and ( , ) 3 ( , ). 0 0 d f β σ f β D = ( 15f) Note that σε 2( f0) > σ2 if the system is stable ( f0 2 < 1). The optimal solution of ( MP1) is obtained by minimizing ( 15e) such that ( 15c) is bounded above by sε 2, where sε > σ. Clearly, ( 15c) must be binding. Thus in the optimal solution the actual variance σε 2 matches the target sε 2. Therefore, the optimal coefficient for the simple control method is: * 1 ( 2 / 2 ), where 2 2 , 0 σ σ σ σ ε ε f = − > ( 15g) and * 3 1 1 ( / ) 2 . 2 σ β σ 2 σ 2 β ε ε + ⎟⎠ ⎞ ⎜⎝ ⎛ d = + − − ( 15h) 4.2 Comparison with Other Control Methods Figure 3 plots ( 15h); it shows how the simple control method performs for different values of β. Note that it requires much less slack time than the schedule based control method, which is represented by the five points with σε / σ = 1. Curves like those shown in Figure 3 cannot be constructed for the headway based control methods discussed in this paper, because as we have demonstrated, σε 2( f) = ∞ in these cases; i. e., because their deviations from schedule εn, s grow unbounded as s grows. Figure 3. Slack time d vs. schedule reliability σε for the simple control method. Schedule based control method is represented by the points with σε / σ = 1. 14 To further compare the simple control method with the headway based methods, Figure 4 plots d / σ vs. the dimensionless headway standard deviations σh / σ that are allowed. Figure 4 shows that the simple control method behaves better than the forward headway based method given by ( 7), the two way headway based method given by ( 8), and the backward headwaybased method given by ( 9). In all three cases, the reduction in slack time is considerable. Note that the headway based methods cannot achieve σh / σ below 1.5 for any slack whatsoever, while the simple control method can. The improved results should not be surprising given that headway based methods are just special cases of the general control method, and that the simple method is near optimal. ( a) ( b) ( c) Figure 4. Slack time d vs. headway reliability σh to compare the simple control method with headway based control methods relying on: ( a) forward headway only; ( b) forward and backward headways; and ( c) backward headway only. 4.3 Balancing Schedule Reliability and Slack Time Previously, we have chosen to minimize slack time ( maximize commercial speed) subject to a schedule reliability constraint. This was appealing because it did not require knowledge of the passenger origin destination table. Here we assume that the average user trip length l is known and show how to balance the two metrics by minimizing the sum of the average passenger waiting and riding times. We will focus on bus lines operating with short headways and compare the five control methods ( schedule based, forward headway based, backward headway based, 15 two way headway based and the simple method). For bus lines with long headways, headwaybased control methods are not applicable, and the performance comparison of the schedule based and the simple control method would favor the latter even more. It is assumed that: ( i) the average bus cruising speed is vc ( i. e., including acceleration and deceleration due to the stops); ( ii) station spacing S is uniform; ( iii) demand β is uniform; ( iv) passengers value their waiting time γ ( γ > 1) times as much as their riding time; and ( v) control is applied at all stations. The passenger waiting time is: H 2 2 ( 2H) h + σ . The passenger riding time is l v H d l S c + ( β + ) . The weighted sum of the two can be expressed as the sum of a fixed component T0 and a variable component ΔT that depends on the control method: 2 , 0 T H l v H l S c = γ + + β ( 16a) T 2 ( 2H) d l S . h Δ = γ σ + ( 16b) Note T0 includes waiting, line haul riding and loading time under ideal conditions. It is the minimal possible travel time, and is achievable only if the bus system had no disturbances. The added term ΔT includes the extra time penalty passengers suffer due to non uniform headways and the slack time. The parameters σh 2 and d can be calculated as a function of their control coefficients with equations ( 13b), ( 14b) and ( 14c) for the four considered methods. For each method the control coefficients that minimize ( 16b) are obtained. Figure 5 shows the ratio ΔT/ T0 for the optimized control methods, as a function of the demand rates β and the dimensionless trip lengths l/ S. The following parameter values were used: S = 400 meters, H = 5 minutes, vc = 20 km/ hr, γ = 2 and σ = 10 seconds. For low demand rates ( 0.01 < β < 0.05), all the headway based methods and the simple method perform much better than the schedule based method. The ΔT/ T0 ratios in this situation are 4 11% for the backwardheadway based method, 5 10% for the forward headway based method and only 3 7% for the two way headway based method and the simple method. As demand increases, the backwardheadway based method becomes unstable and the simple method also outperforms the rest of methods with a maximal ΔT/ T0 ratio of 15% at β = 0.2 and l/ S = 25. Finally, note that the twoway headway based method and the simple method are practically indistinguishable. Both methods achieve such similar results because the optimization procedure leads to values of α ( the two way headway based control coefficient) which are practically zero. 16 Figure 5. Ratio of variable travel time over fixed travel time ( ΔT/ T0) for different control methods with various demand rates β and dimensionless trip lengths l/ S. 4.4 Sensitivity to the Control Coefficients Numerical calculation shows that control coefficients that do not differ much from the optimal control coefficients do not increase the required slack time much. Figure 6 shows the ratio of d/ d* when β = 0.1 and the general control method has two nonzero coefficients. In this figure, d is the slack time of the non optimal control coefficients at the indicated point and d* is the optimal slack time with the same σε value. We see that within a small neighborhood around the optimal coefficients f*, the ratio is close to 1 but large deviations can result in inefficiency. ( a) ( b) Figure 6. Sensitivity to control coefficients when β = 0.1. ( a) All fi = 0 except for f0 and f1; ( b) all fi = 0 except for f0 and f 1. The contour lines show the ratio of the non optimal slack time d* over the optimal slack time d with the same σε value. 17 5 Robustness to Large Disturbances When the system is subject to a large disturbance, such as a bus breakdown, the holding times as in ( 4a) may become negative and buses may bunch if nothing is done. It is proposed in this case to abandon the published schedule ( if one is provided) and to focus on regularizing headways. To do this, the virtual schedule is reformulated so it can absorb the effect of the disturbance. This will enable buses to recover from the effect of the large disruption and still provide service with regular headways. To demonstrate the idea, we next show how to modify the virtual schedule in two situations: ( i) when a bus is so far behind schedule that it cannot catch up by itself and ( ii) when a bus in the system goes out of service unexpectedly. Other situations can be handled similarly. Only the simple control method is studied. 5.1 Bus Far Behind Schedule According to assumption ( i), the holding time Dn, s as in ( 15a) will almost always be nonnegative. But when there is an unexpected large disturbance, the assumption can be violated, and Dn, s as calculated from ( 15a) may turn out to be negative. A negative Dn, s means that the control, instead of holding the bus back, would want to push it forward. This is an indication that the bus cannot keep up with the schedule by itself. To remedy this situation, the current virtual schedule can be shifted forward in time by the smallest possible Δt, so that the critical bus n0 at s0 ( and therefore all other buses) will be able to keep up with the new schedule by themselves. If we use primes to denote variables under the new virtual schedule, the changes are: ' , , , , , t t t n s n s n s = + Δ ∀ ( 17a) ' ' , , , , , , , a t t n s n s n s n s n s ε = − = ε − Δ ∀ ( 17b) ' [( 1 ) ' ' ] ( 1 ) , , . , 0 , 1, , 0 D d f D f t n s n s s s n s s n s n s = − + − − = + − Δ ∀ − β ε β ε ( 17c) However, adding too much slack time decreases the commercial speed. Therefore, only the necessary amount of Δt would be added in order to keep the holding time of the critical bus 0 , 0 ' n s D close to but greater than zero, i. e.: ( ) /( 1 ), 0 , 0 0 t D f n s Δ = − − ( 17d) where n0 , s0 D is given by ( 15a). In reality, ( 17d) can be modified to include an extra buffer time δ > 0: Δ = (− ) /( 1− ) + δ 0 , 0 0 t D f n s . Doing this ensures that the procedure does not have to be repeated too often, but delays all the buses a bit more. Note, this process ensures that the system returns to stability and that the process is repeatable, i. e., whenever we find the holding time Dn, s for a bus as in ( 15a) to be negative, the virtual schedule can be shifted forward again using the same method. 18 5.2 Bus Breakdown Now imagine there are N buses running on a loop and one bus suddenly breaks down. We will define a new virtual schedule so that the remaining N 1 buses can adhere to it and maintain regular headways, while keeping their commercial speed as fast as possible. As shown in Figure 7, we number the buses in a way that bus N breaks down, with bus 1 behind it. The headway in the original schedule is H, and the original schedule satisfies tn+ 1, s = tn, s + H ( for ∀ s, n = 1 to N 2). Under the new schedule, the loss of one bus results in a slightly larger equilibrium headway H’ ≈ NH/( N 1). 10 Thus the new schedule satisfies t’n+ 1, s = t’n, s + H’ ( for ∀ s, n = 1 to N 2). We assume that the schedule of bus 1 is shifted backward by a time Δt to be found ( Δt < 0 if shifted forward), i. e., t’ 1, s = t1, s – Δt. The schedules of the other buses are shifted to maintain the new headway H’: , , 1 to 1, 1 ' ( 1)( ' ) 1 , , , ∀ = − − = − Δ + − − = − Δ + − H s n N N t t t n H H t t n n s n s n s ( 18a) , , , , ' ' 1 , 1 to 1. n s n s n s n s 1 a t t n H sn N N ε = − = ε + Δ− − ∀ = − − ( 18b) Figure 7. Illustration of virtual schedule change when bus N is suddenly out of service. We assume that at the time of bus breakdown, the current ( or closest upstream) station of bus n is s( n). Under the new virtual schedule, the holding times for the given Δt would be: 10 This approximation is good if the cycle time of buses does not change much after the breakdown. The exact expression for the new headway is H'= H[( c + d) N][( c + d)( N − 1) − βH], where c is the average cruising time between stations, d is the slack time per station, and β is the dimensionless demand rate, in the homogeneous case. 19 , 1 1 ( 1 )( ) ( 1 ) 1 [( 1 ) ] ' [( 1 ) ' ' ] ( for 2 to  1) 0 0 ( ) ( ) ( ) 0 , ( ) ( ) 1, ( ) , ( ) ( ) ( ) 0 , ( ) ( ) 1, ( ) − + − − − Δ + − − = − + − − = − + − − = − − N H H N f t f n d f D d f n N s n s n s n n s n s n n s n n s n s n s n n s n s n n s n β β ε β ε β ε β ε ( 19a) . 1 ( 1 )( ) 2 [( 1 ) ] ' [( 1 ) ' ' ] ( for 1) 0 ( 1) ( 1) ( 1) 0 1, ( 1) ( 1) 1, ( 1) 1, ( 1) ( 1) ( 1) 0 1, ( 1) ( 1) 1, ( 1) H N f t N d f D d f n s s s s s N s s s s s s N s − − − Δ − − = − + − − = − + − − = − − β β ε β ε β ε β ε ( 19b) As in the last subsection, negative holding times indicate that the corresponding buses cannot keep up with the schedule. Thus Δt is found by solving: { } s. t. ' ( ) 0 1 to 1. ( MP3) arg min min ' ( ) , ( ) , ( ) Δ ≥ ∀ = − Δ = Δ D t n N t D t n s n n n s n Note that each non negativity constraint imposes an upper bound on Δt, and the solution for Δt is the minimum of these upper bounds. Thus the solution always exists. In reality, the transit agency may add a little buffer δ to Δt to ensure that the remaining N 1 buses do not experience frequent disturbances. The system can then be run with the simple control method, and the process in Section 5.1 can be used to account for other disturbances. 6 Control Law with Real Time Information on Demand So far, we have assumed that demand is quasi deterministic and known, but this may not always be realistic. In this section, we discuss how to relax our assumption on quasi deterministic demand by exploiting real time information on passenger boarding. We assume that the arrival of passengers follows a Poisson process, with the average demand at station s, βs, known. We also assume that the actual number of passengers to board bus n at station s, Xn, s, is stochastic. Thus if the headway is given, [  ] / , n, s n, s s n, s b E X h = β h t ( 20a) var(  ) / , n, s n, s s n, s b X h = β h t ( 20b) where tb is the average time needed to board a passenger. Although Xn, s is a random variable, we assume that its realization is observable when bus n finishes boarding at station s. 11 We will show that with this real time information, the control law can be slightly modified to achieve similar performance as in the quasi deterministic case. 11 This is possible because the number of boarding passengers can be measured either by a person at the station, or by an automatic passenger counter system. 20 The scheduled arrival times satisfy the same equation ( 1a). Average demand βs is used for the schedule, since real demand is unknown yet. n, s 1 n, s s s s . t = t + H + d + c + β ( 21a) The actual motion of buses is affected by the real demand: . , + 1 , , , , + 1 = + + + + n s n s b n s n s s n s a a t X D c υ ( 21b) Then, the deviations from schedule can be obtained by subtracting the previous two equations, ( 21a) from ( 21b): ( ) . , + 1 , , , , + 1 = + − + − + n s n s b n s s n s s n s ε ε t X β H D d υ ( 22a) Real time demand information is used to decide the holding time. This is feasible because boarding occurs before holding, and the realization of Xn, s is known when holding time is calculated. We propose the following instead of ( 4a): ( ) , , , , . n s s b n s s n s i i n i s D d tX H f β ε ε − = − − + − Σ ( 22b) Now if we combine ( 22a) and ( 22b), the evolution equation for the deviations from schedule as shown in ( 23) is the same as equation ( 4b): , 1 , , 1 . n s i i n i s n s ε fε υ + − + = Σ + ( 23) Thus with real time demand information, the motion of buses under the new control law will not change. The stability analysis and the expression for σε and σ h still hold. Only the expression for the slack time ds is slightly different, and is derived in Appendix C. The final result is that: d 3 2 t H. s D s b = σ + β ( 24) where σD 2 is calculated using ( 14b). Figure 8 compares the slack time required vs. schedule reliability under various demand rates, with parameters H = 5 minutes, tb = 4 seconds, and σ = 10 seconds. Slack times under quasi deterministic and stochastic situations are calculated by ( 14c) and ( 24) respectively. Clearly, the slack time has to be increased, but only significantly if β s tbH is large compared with σD 2. Therefore, the only changes needed to rigorously account for random demand fluctuations are to use ( 22b) instead of ( 4a) for the holding time, and ( 24) instead of ( 14c) for the slack time ds. 21 Figure 8. Comparison of slack time d vs. schedule reliability σε under various quasi deterministic and stochastic demand rates for the simple control method. 7 Conclusion In this paper, we studied a general control method, which is a family of dynamic holding strategies, to improve bus schedule reliability while providing the service with the fastest possible commercial speed. We have four main findings: • First, the general control method allows buses not only to maintain regular headways but also to adhere to their schedule. None of the existing adaptive methods can achieve this feat. Thus the proposed method is applicable to bus lines with both long and short headways. • Second, a simple control method, which is a one parameter version of the general control method, is found to be near optimal. It outperforms alternative control methods, but only requires information of the current bus and its leading bus. • Third, in case of large disturbances, buses can still maintain regular headways, by adapting the virtual schedule. This schedule adaptation method guarantees the robustness of the control method under any circumstance. • Finally, highly stochastic demand can be taken into account by slightly modifying the proposed general control method to incorporate real time demand information. References Abkowitz, M., Eiger, A., & Engelstein, I. ( 1986). Optimal control of headway variation on transit routes. Journal of Advanced Transportation, 20( 1), 73 88. Adamski, A., & Turnau, A. ( 1998). Simulation support tool for real time dispatching control in public transport. Transportation Research Part A: Policy and Practice, 32( 2), 73 87. 22 Barnett, A. ( 1974). On controlling randomness in transit operations. Transportation Science, 8( 2), 102 116. Bartholdi, J. ( 2011). ( private communication). Bowman, L. A., & Turnquist M. A. ( 1981). Service frequency, schedule reliability and passengers wait times at transit stops. Transportation Research Part A: General, 15( 6), 465 471. Daganzo, C. F. ( 1997a). Passenger waiting time: advertised schedules. In: Daganzo C. F. ( ed.), Fundamentals of transportation and traffic operations. Elsevier, New York, NY, 291 292. Daganzo, C. F. ( 1997b). Schedule instability and control. In: Daganzo C. F. ( ed.), Fundamentals of transportation and traffic operations. Elsevier, New York, NY, 304 309. Daganzo, C. F. ( 2006). On the variational theory of the traffic flow: well posedness, duality and applications. Networks and Heterogeneous Media, 1( 4), 601 619. Daganzo, C. F. ( 2009a). A cheap and resilient way to eliminate bus bunching. The 4th International Conference on Future Urban Transport, Gothenburg, Sweden. Daganzo, C. F. ( 2009b). A headway based approach to eliminate bus bunching: Systematic analysis and comparisons. Transportation Research Part B: Methodological, 43( 10), 913 921. Daganzo, C. F., & Pilachowski J. ( 2009). Reducing bunching with bus to bus cooperation. Working Paper UCB ITS VWP 2009 12, U. C. Berkeley Center for Future Urban Transport. Daganzo, C. F., & Pilachowski, J. ( 2011). Reducing bunching with bus to bus cooperation. Transportation Research Part B: Methodological, 45( 1), 267 277. Eberlein, X. J., Wilson, N. H. M., & Bernstein, D. ( 2001). The holding problem with real time information available. Transportation Science, 35( 1), 1 18. Golob, T. F., Canty, E. T., Gustafson, R. L., & Vitt, J. E. ( 1972). An analysis of consumer preferences for a public transportation system. Transportation Research, 6( 1), 81 102. Hickman, M. D. ( 2001). An analytic stochastic model for the transit vehicle holding problem. Transportation Science, 35( 3), 215 237. Koffman, D. ( 1978). A simulation study of alternative real time bus headway control strategies. Transportation Research Record 663, 41 46. Newell, G. F., & Potts, R. B. ( 1964). Maintaining a bus schedule. Proceedings of the 2nd Australian Road Research Board, 2, 388 393. Newell, G. F. ( 1974). Control of pairing of vehicles on a public transportation route, two vehicles, one control point. Transportation Science, 8( 3), 248 264. 23 Osuna, E. E., & Newell, G. F. ( 1972). Control strategies for an idealized public transportation system. Transportation Science, 6( 1), 52 72. Paine, F. T., Nash, A. N., Hille, S. J., & Brunner, G. A. ( 1967). Consumer conceived attributes of transportation: An attitude study. College Park: University of Maryland. Senevirante, P. N. ( 1990). Analysis of on time performance of bus services using simulation. Journal of Transportation Engineering, 116( 4), 517 531. Turnquist, M. A., & Bowman, L. A. ( 1980). The effects of network structure on reliability of transit service. Transportation Research Part B: Methodological, 14( 1 2), 79 86. Vandebona, U., & Richardson, A. J. ( 1986). Effect of checkpoint control strategies in a simulated transit operation. Transportation Research Part A: General, 20( 6), 429 436. Wallin, R. J., & Wright, P. H. ( 1974). Factors which influence modal choice. Traffic Quarterly, 28( 2), 271 289. Zhao, J., Dessouky, M., & Bukkapatnam, S. ( 2006). Optimal slack time for schedule based transit operations. Transportation Science, 40( 4), 529 539. Appendix A: A Method for Locating Control Stations We have assumed during the analysis that the proposed control method is applied at each station, but this is not always desirable. As shown in Daganzo ( 1997b, 2009), it is often beneficial to space out the control points more widely. In this spirit, it is assumed here that control stations are located every N stations, and N is treated as a decision variable. The demand rate β is assumed to be uniform throughout the bus line and such that β << 1. We will first transform the equations of bus motion from station to station into similar equations describing the bus motion from control station to control station, as if there were no intermediate stations. It will be shown that when β << 1, one may simply replace β and σ with β’ = Nβ and σ '= σ N + N( N − 1) β to model the bus motion in this manner. The variance of the noise between control stations ( σ’) 2 is simply given by ( 11a) using the { fi j} of the uncontrolled case and replacing s by N. Recall that for the uncontrolled situation, [ ] T f = L, 1 + β , − β , L . It can be seen from the binomial formulas that ( 1 ) ( ) .  m j m m j m j f − − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = β β ( A1) Thus, 24 [, 1 , , 0, ]. ( 1 ) ( ) , 2 , ( 1 ) , ( 1 ) 1 ( ), 2 2  T T j j j j j j j j L L L L β β β β β β β ≈ + − ⎥⎦ ⎤ ⎢⎣ ⎡ − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ f = + + − − − ( A2) The last approximation works because β << 1 and thus we can neglect terms of order β 2 and higher. Equation ( A2) can now be inserted in ( 11a) to yield: ( ( 1) ). ( 1 2 ) ( 1 ) ( ) ( ') ( ) 2 1 0 2 1 0 2 2 1 0 2  2 2 σ β σ β σ β β σ σ = + − ≈ + ⎥⎦ ⎤ ⎢⎣ ⎡ − + ⎟ ⎟⎠ ⎞ ⎜ ⎜⎝ ⎛ = = Σ Σ Σ Σ Σ − = − = − − = N N N j m j f N j N j m m j m N j m m j ( A3) It should also be clear from ( A2) that when j = N and β << 1, the dimensionless demand between control stations is β’ = Nβ. By setting β’ = Nβ and σ '= σ N + N( N − 1) β , we can treat the bus motion as if there were only stations at the control stations and apply ( MP2) with these new parameters. The number of stations between control stations, N, is however, a decision variable in the new version of ( MP2). Consideration of ( 11b) and ( 14b) reveals that this new mathematical program is: ' ( 1) . s. t. ' ( ) ( MP4) min ' ( , ) , β σ σ σ σ σ β σ σ ε ε = + − ≤ N N N s N d N N f f f This MP can be solved numerically as in Section 4.1, or analytically if we adopt the simple control method. Appendix B: Derivation of the Gradients for Greedy Search In developing Figure 1, we solved the following optimization problem, which is equivalent to ( MP2): s. t. ( ) . ( MP5) min ( , ) 2 2 2 ε ε σ σ β s D f ≤ f f From equations ( 11b) and ( 14b), we find the following expressions for σε 2( f) and σD 2( f, β), whose gradients we seek: 25 ( ) ( ) , 0 2  2 2 Σ Σ ∞ = = j i i j σ σ f ε f ( , ) [( 1 ) ]. 0 2  1  1 2 2 Σ Σ ∞ = − + = + − − D j i i j i j i j σ f β σ β f βf f Using generating functions, one can find the following expression for fi j: . ! ! ! ! 1 0 1 0 0 1 1 0 1 1 , , 0 1 1 0 1 1  Σ = = − − Σ Σ = − = − = − − rk i k j k k k k m k k m i j m r r m r r m f f f m k k k f j L L L ( B1) Since ,  −  − 1 ∂ ∂ = i j r i r j f f jf ( B2) The partial derivatives of σε 2( f) and σD 2( f, β) with respect to fr can be expressed as: 2 ( )( ), 0   1 2 2 Σ Σ ∞ = − − = ∂ ∂ j i i j i r j r f jf f σ σ ε ( B3) and [ ] [( 1 ) ( 1)]. 2 ( 1 )  1 1 1  0  1  1 2 2 i r j i r j i r j j i i j i j i j r D jf jf j f f f f f − − − − − − ∞ = − + + − − + = + − − ∂ ∂ Σ Σ β β σ β β σ ( B4) Appendix C: Derivation of the Slack Time Formula for the Control Law with Real Time Demand Information Recall that it is assumed that Pr{ 0} 0 , < ≈ n s D , i. e., [ ] 3 var( ). n, s n, s E D = D ( C1) It is first shown that the expectation of Dn, s is ds: [( )] [ ] [ ( ) ] . ( 1 ) ( 1 ) [ ] [ (  .,.)] 1 0  1  1 , , 1, , , , , , , s s s j i s i j s i j i j n i s j s s n s s n s i i n i s s s n s s n s i i n i s n s X n s d d E f f f d E f E d h H f E D E E D = = − + − − = − + − − = − − + − = Σ Σ Σ Σ − = − + − − − − − β β υ β ε β ε ε β β ε ε υ υ υ υ υ ( C2) Now, consider the law of total variance: 26 var( ) [ var(  .,.)] var( [  .,.]), , , , υ υ n s υ X n s υ X n s D = E D + E D ( C3) where [ var(  .,.)] [ var(  .,.)] [ ] , , , , E D E t X E t h t H X n s X b n s v s b n s s b υ υ β β υ υ = − = = ( C4) and ( [ ]) ([ ]) ( ) { ( ) } . var ( 1 ) var ( ) var ( ) var[ (  .,.)] var 2 1 0  1  1 , , 1, , , , 1, , , , , , , D s j i s i j s i j i j n i s j s n s n s n s i i n i s s s n s n s n s i i n i s X n s s s n s s n s i i n i s f f f f d f E D d h H f σ β β υ β ε ε ε ε β ε ε ε ε υ β β ε ε υ υ υ υ υ = = + − − = − + − = − − + − = − − + − Σ Σ Σ Σ Σ − = − + − − − − − − − ( C5) Thus it follows that var( ) [ var(  .,.)] var( [  .,.]) 2 , , , , D E D E D t H n s X n s X n s D s b υ υ σ β υ υ = + = + where σD 2 is calculated using ( 14b). Now according to ( C1): d 3 2 t H. s D s b = σ + β ( C6) 



B 

C 

I 

S 


