### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Public Transportation CE 574

UI

GPA 3.54

### View Full Document

## 6

## 0

## Popular in Course

## Popular in Civil Engineering

This 6 page Class Notes was uploaded by Savanna Cruickshank on Friday October 23, 2015. The Class Notes belongs to CE 574 at University of Idaho taught by Michael Kyte in Fall. Since its upload, it has received 6 views. For similar materials see /class/227774/ce-574-university-of-idaho in Civil Engineering at University of Idaho.

## Reviews for Public Transportation

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/23/15

n3 C3 4 39 Research Record 1780 Paper No 010442 Designing Synchronization into Bus Timetables Avishai Cedar and Ofer Tel r addressed Synchronization means a fit between the arrival time of one L J r r r sit schedulers and is addressed intuitively The scheduler in fact attempts to create the departure times in the timetable while complying with the a a I fl the scheduler in creating timetables These procedures attempt to maximime the number L r ml n MAIquot 39 39 39 39 ranch I llu ulers appreciate the importance of creating a timetable with maximum v L to another with minimum wait time at transfer nodes El cient proce quot quot quot to create 39 39 39 39 u c A major role of transit schedulers is to create timetables for the routes of a given bus networkl Three parameters need to be selected and addressed before the actual scheduling in constructing such timetables 2 1 Type of headway even or uneven 2 Method for setting the frequencies maximum load or load profile and Oneor quot quot 39 quot quotquot 4 uling Will39 39 39 quot 39 r cum while p10quot viding adequate service minimizing operator and user cost through weighing factors Maximum synchronization the focus of this study is important from the operator39s and the user s perspectives because it involves creating timetables that will maximize the number of simultaneous arrivals of buses at the connection transfer nodes Any route design at the network x quot 39 of transfer points because of their adverse effect on the user I A tradeoff exists between eliminating many transfer points and the ef ciency of the bus route network from the operating cost perspective To allow for an adequate bus level of service schedulers in facing the synchronization task want to ensure maximum switching in the transfer of passengers from one route to another without wait time is task 39 quot 39 39 l 39 in wait time iur passengers requiring connections In accomplishing this objective quot es a mm 39 at generates an opportunity for increasing ridership Transportation Research Institute Civil Engineering Faculty Technionlsrael Institute of Technology Haifa 32000 lsrael is the most dif cult task of the transit scheduler 39 39 39 quot in fart attempts to create departure times in the timetable while complying with the n L L 1 t a Ap J r p r lllllt llt sculed for the application of maximum synchronization as a useful tool for the scheduler in creating timetables The synchronization problem has not been dealt with exten sively in the literature Voss formulated the problem of minimiz ing the waiting time of passengers at transfer nodes as a mathe matical programming quadratic assignment problem for c39ases in which each bus route is jointed by a set ni of possible depar ture times 3 The problem was modi ed to a case with different routes partly using the same tracks implying that security dis tances must be observed Desilet and Rousseau describe a differ ent model which selects a starting time for each route from a set of iblc v time TL 39 39 39 39 39 penaltyassociated with transfers from one line to another The penalty function which can be calculated in various ways accounts for the randomness of travel times Daganzo presents the problem of coordinating a network with only one node at which inbound and outbound routes intersect 5 Procedures are presented to enable transit schedulers to set restrictions on headways for each route introduce different frequencies for every route and apply other constraints The objective is to maximize the number of simultaneous bus arrivals in the network The departure times are set accordingly Two heuristic procedures are presented that solve the problem Examples are given in which the heuristic procedures are compared with optimal solutions HEURISTIC PROCEDURES The resaarch report of this study formulated the problem as a large 39 quot5 lineal niobium 6 Running small net works ve routes ve nodes using General Algebraic Modeling System GAMS software on an IBM PC required hours even da S 7 39 quot e pit in titate 39 39 39 r of heuristic procedures that would solve such problems in a reason able time Two heuristic procedures were implemented in Turbo Pascal and many examples were checked and compared39with the optimal solutions obtained by using GAMS 7 8 The rst proce dure is based on the selection of nodes in a network In each step the next node is selected provided that not all the departure times have been determined for that node After the departure time is resolved all l 39 rm are t T r cedure attempts to improve the solution through possible shifts in the departure times 39nd Tal blem notations are the following amiing horizon departure times of the buses can be set val 0 T which is a discrete interval number of bus routes in the network number of transfer nodes in the network y um vu maxk maximum headway policy headway permitted een two adjacent bus departures on route k 1 S k S M Fk number of departures to be scheduled for route k during terva10T1SkSM TH travel time from the starting point of route k to node j V M 1 S j S N travel times considered to be deterministic canbe referred to as mean travel times a Vditlon the following should be noted I o The rst departure in each route k must take place in the inter val 0 Hmax k a M I he problem is impractical unless the following constraints hold for each k Paper No 01 0442 29 Hman Z Hmink T2 Fk lHmink TS Ft Hman 39 The ease of a route k that does not pass through a node j is represented by Tki l Procedure l De nition 7 A node is de ned as possible if At least one bus route passes through the node and not all the departure times for that route are set 39 More simultaneous arrivals can be created at the node De nition 2 A node is de ned as new if no arrival times have been set for it Procedure 1 uses several components as shown in the owchart in Figure 1 INITIALIZATION CHOOSE FIGURE 1 Procedure I flowchart SELECT THE NEXT NODE NO IS NO ANEW NODE 80 Paper No 070442 Step 1 Initialization check whether the problem is feasible and create the data structures Mark all nodes as possible Step 2 Select the next node NO from the possible nodes Step 3 If NO is new perform component FIRST otherwise perform component MIDDLE Step 4 If there is any possible node go to Step 2 if there are any more routes perform component CHOOSE and go to Step 2 otherwise stop Step 1 contains a check of whether the problem is feasible and two data structures are built 1 A structure called route for each bus route 1 which includes Hmin Hmaxi F the number of nodes the route passes through and the departure times that have already been set A structure called node for each node n which includes the number of routes passing through the node the route with the maxi mum l 39 quot quot 39 39 39 at the node at each time point in the interval 0 T maqu where the maximum is over all i j All the nodes are marked possible m In Step 2 the next node NO is selected from among the possible nodes Node NO must satisfy the following conditions i The number of different bus arrival times at the node is max imum in such a node there is a greater probability that another bus departure can be set so that it will arrive at NC by any one of the already Set arrival times 2 Among the nodes satisfying the preceding condition NO is that through which a maximum number of routes pass in such a node there is a greater potential for simultaneous arrivals 3 Among the nodes satisfying the preceding condition NO minimizes the maximum travel time of all routes from their origin to the node after the departure times of buses are set to meet at NO there is still a potential for simultaneous arrivals at distant nodes A distinction is made in Step 3 between a new node and another node For a new node component FIRST attempts to set the depar ture times of buses that pass through it such that the buses will arrive ML 4 t in continue to be created at the node according to the Hmin Hmax of the routes For example for buses on Routes 2 and 3 that arrive simultaneously at a certain node at time to if the next departure time mi L t a a minntPc from the last departure time of the route for all I l 2 and 3 maxHmin S d S minHmax there will be additional simultaneous arrivals at the node at time to d Component FIRST nds the minimal d possible If parameter d cannot be set Hmin gt Hmaxp the next departure times of buses on these routes will not be resolved at this step For a node that is not new an attempt is made to set the bus departure times on routes passing through it such that the buses will arrive at the node at the earliest time among all the arrival times already set in that node If no more simultaneous arrivals are avail able at the node the node is marked as not possible This component is called MIDDLE Step 4 tests whether any more nodes are possible If not there may be routes on which not all the bus departure times were set In such cases the route that passes through the maximum number Transportation Research Record 1780 of nodes is chosen and its next departure time is Set by using the difv ference Hmin from the last departure In such a way the algorithm sets additional bus arrivals for the maximum number of nodes pos sible All the nodes through which route 139 passes are marked possi ble and the procedure returns to Step 2 This component is called CHOOSE Procedure ll The results of Procedure I certainly could be improved by allowing a shifting of the timetable obtained by Procedure I That is for each node and for each two time points t1 and t t lt 12 at which buses arrive at the node an attempt can be made to introduce a shift in all r 39 ior 39 39 the node at It so that they quot 39 39 Ifrhi n pelvic 39 quot ineg and the number of simultaneous arrivals increases It should be noted that to shift a single bus departure time the following must be checked 1 After the shifting is done the constraints on Hmin and Hmax must still hold Otherwise additional departure times on the route should be shifted 2 As a result of shifting the departure time of bus 139 its arrival time for all the nodes passed through is changed Therefore the departure time of each bus that arrives simultaneously with bus i at any node mu t Lquot Fm L i 39 L 39 on Hmin and Hmax must be checked and so on This process is recursive and an attempt to shift a single departure time may cause the shifting of all the network departure times 3 A shift of At minutes in the departure time of bus i may result in changing other departure times which ultimately will lead to changing the departure time of bus i by more than At A check must eliminate this situation LJJJ 1L u ung r ponents MERGE and MOVE and a process TRY MOVE as shown in Figure 2 Component MERGE 39nmpmn m i 39 V II and 1 t lttz to a given node NO and delivers to component MOVE three ele ments the bus routes arriving at 1 and t2 and the required shift value t2 t1 FIGURE 2 Procedure ll flowchart II TRY MOVE Cedar and Tel Camponent MOVE The MOVE component attempts to shift t by At t2 t1 where t is c anged by route number This component also contains the num ber of buses that need to be shifted and a bus array with all possible buses that need to be checked for shifting Each bus is identi ed by route number and bus code Component MOVE uses the process TRYMOVE which allows for individual shifts to be checked TRYvMC T39 r r L A L time of a given bus and provides MOVE with successful or false This TRY MOVE process checks if the required new departure time is within 0 Tand that the resultant headway does not exceed Hmax Combined Procedures Procedures I and II can be combined to shift Procedure 1 results Also the rst selected node NO can change N times N0 1 2 N that is to run Procedure I N times These N runs over different NOs can also be combined with Procedure 11 Four aria39inn in the c r Procedure I N runs of Procedure I rst node vari s Procedure II and shifts in the results of N runs of Procedure I The complexity running time as a function of network size of each variation is certainly not the same Procedure I has the lowest complexity followed by N runs of Procedure I which is less com plex than Procedure 11 The most complex run is the one with N changes of the rst node while running Procedure Ill 1 EXAMPLES Three examples of bus networks are described Two examples are presented in detail for the sake of clarity An optimal procedure with the linear programming software GAMS was applied to each example for comparison purposes 7 Detailed Examples Figure 3 presents a simple network example combining two trans fer points with two routes The numbers on the arcs are travel times in minutes A demonstration of Procedure I follows Step 7 The data given for the example in Figure 3 i Hmin Hmax F No of Nodes I 5 15 4 2 II 8 20 3 Z l 5 Rle 7 ROUTE I 1 0 l 2 ROUTE II FIGURE 3 Example 1 basic network Paper No 010442 31 Node n No ofRouter Route with mail 1 2 II 2 2 11 These data comply with the three constraints Hmaxr 2 Hmim TZFk 1Hmink TS Ft Hman Step 2 39quotL quot 39 t he alerted NC 39 39 39 max imum routes crossing and minimum and maximum travel time from the origin to NO Thus the number of departure arrival times equals 0 for both nodes The number of crossing routes equals 2 for both nodes The maximum travel time for Node 2 is 17 27 27 The maximum travel time for Node 1 is 7 l2 12 the minimum travel time for Node 1 is 12 27 12 The selected NO is therefore Node 1 Step 3 The earliest time possible is set for Node ll Continuing in this node the synchronization is based on max 5 8 S d lt min 15 20 gt d 8 This is the FIRST component which gives the following results Departure Time Route I Route II Meeting Time 5 0 12 13 8 20 21 16 28 where meeting refers to a simultaneous arrival The number of departures of Route 11 complies with F2 3 Step 4 Because Node 2 has yet to be examined Step 2 is selected Step 3 Because Node 2 is not new component MIDDLE is applied Fl 4 gt 3 currently created thus one more departure time of Route 1 is set based on the already created departure times of Route 11 at O 8 16 such that the synchronization is made at Node 2 The results are the additional departure time for Route I at 26 which meets the Route 11 bus39s departure at 16 Step 4 quot quottoexamine quot 39 quot witht ue nal results as follows Departure Tim Meeting Time M Total Route I Route 11 At Node 1 At Node 2 Meetings 5 0 12 I3 8 20 4 21 16 28 26 43 Certainly in this simple example the optimal and heuristic procedures coincide 32 Paper No 01 0442 Transportation Research Record 1780 FIGURE 4 Example 2 basic network Detailed Example 2 Figure 4 presents the second example with a case of 11min gt Hmaxj for a tworoute fournode network This example is used for Procedures 1 and II The data for Example 2 are as follows Hminl gt Hmaxz l Hmini Hmax F T Route I 6 10 4 30 Route II 3 5 6 Using Procedure Step 1 The data given for the example in Figure 4 Node 1 No ofRoures Route with maxTin l 2 II 2 2 II 3 2 II 4 2 I II Step 2 NO is selected such that 39 The number of departure arrival times equals 0 for all nodes 0 The number of crossing routes equals 2 for all nodes 0 Maximum travel times for the nodes are 10 16 20 and 2 percent respectively 0 The minimum travel time is 10 so NO equals 1 Step 3 Component FIRST is applied The rst meeting time possible at Node 1 is 10 The component cannot set the parameter d Therefore Component FIRST results in only the rst departure time of each route as follows Departure Time Route I Route 1 Meeting Time 3 0 10 Step 4 m J q i i r 1 a r 7 Step 2 The number of arrival times is 1 2 2 and Z respee tively for nodes 1 2 3 and 4 N0 2 maximum travel time 16 is minimum Step 3 Component MIDDLE sets a new meeting at Node 2 at time 27 by setting the third departure time of Route I to 15 and the fourth departure time of Route 11 to 11 Steps 2 3 N0 3 Component MIDDLE sets new meetings at Node 3 at times 28 and 34 by setting the second departure time of Route I to 9 the third departure time of Route II to 8 and the fth departure time of Route 11 to 14 Steps 2 3 N0 4 No meetings are possible The procedure continues to perform Component MIDDLE until it ends with the following results Departure Time Meeting Time Total Route I Route 11 A Node 1 At Node 2 At Node 3 Meetings 3 O 10 9 3 28 15 8 27 34 5 21 11 28 I4 18 The meeting time is indicated in the same row of its associated departure for Route 1 Using Procedure II Components MERGE and MOVE check with the TRYMOVE pos sible shiftings The only successful shifting is the Second departure of Route 11 from 3 to 5 The optimal solution is six meetings using Procedure II Departure Time Meeting Time Total Route I Route II A Node 1 At Node 2 At Node 3 Meetings 3 0 l0 9 5 21 28 15 8 27 34 6 2i 1 1 28 14 18 Example 3 Figure 5 exhibits the Example 3 the following data apply i Hmin Hmaxl F T Route I 3 8 20 Route 11 4 7 Combinations 20 Route III 5 12 see Table 1 Route I Route II FlGURE 5 Example 3 basic network Cedar and Ta Paper No 070442 33 TABLE 1 Maximum Number of Meetings Attained by Four Variations of Procedures I and II with 20 Combinations of Bus Frequencies Combination No F1 F2 F3 Procedure Variation Optimal l lN runs ll IlN runs with shi s l l l l 2 2 2 2 Z 2 l l 2 2 2 2 2 3 3 l 2 l 3 3 3 3 3 4 l 2 2 3 3 4 4 4 5 2 l l 2 3 2 3 3 6 2 l 2 2 3 3 4 4 7 2 2 l 3 3 3 4 4 8 2 2 2 4 4 5 5 5 9 3 l I 2 3 2 3 3 ll 3 I 2 3 3 3 4 4 l l 3 2 l 3 3 3 4 4 12 3 Z 2 4 5 5 6 6 13 3 3 l 4 4 4 5 5 14 3 3 2 5 5 6 6 7 1 5 3 l 3 3 4 3 4 4 16 3 2 3 4 5 6 7 7 l7 3 4 4 7 7 10 10 10 8 4 4 4 8 8 1 l l l l 1 l9 5 5 5 8 8 8 8 8 20 6 6 5 4 7 4 7 7 m t J This third example was examined with four procedure varia tions Procedure I Procedure I with N changes of the rst node Procedure 11 and Procedure 11 with N changes of the rst node The results of these four variations were compared with the optimal results Table 1 The table also includes the 20 combinations of frequencies F 1 F2 and F3 for Routes 111 and 111 respectively The results in Table 1 are as follows 1 For the most complex variation with Procedure 11 and N changes in the rst node of Procedure I there are3918 out of 20 optimal results 2 Procedure I and Procedure I with N runs have 13 same results That is the rst node in Procedure I was the best selection in 13 out of 20 cases 3 0n the basis of Example 3 it is not obvious that Procedure 11 provides better results than Procedure 1 N runs CONCLUSIONS The problem of maximum synchronization in creating bus timeta bles was addressed Maximum synchronization equals the most number of simultaneous bus arrivals at transfer nodes in a bus net work For 1 O 1 o Y LI 4 L I J 39 n by using software and thus heuristic procedures were developed m 7 J Mb Pascal programs and achieved good results compared with the opti 1 39 7 Thissiudy quot 1 39 39 pinh lem in Israel for the procedures developed 6 In this problem there are 14 bus routes with 28 actual transfer nodes The best result using all four variations is 240 meetings using Procedure I with N changes for 39 T l quot becheck against the optimal solution because of its large size K gt01 sit schedUIer in one of the most dif cult scheduling tasks The more transit connections that can be created the better and more reliable LL 39m I L r a vuul ontime performance of the transit vehicles The latter is expected to I I SW A J 39 39 All gether the procedures presented may be one step forward in chang ing the image of transit services and ultimately in view of increasing traf c congestion leading to increased ridership REFERENCES 1 Coder A Methods for Creating Bus Timetables Transportation Research A Vol 21 No 1 1986 pp 59433 Cedar A and N H M Wilson Bus Network Design Transportation Research B Vol 20 No 4 1986 pp 331 344 Voss S Network Design Formulation in Schedule Synchronization In Computer Aided Transit Scheduling M Desrochers and l u seau eds SpringerVerlag BerlinHeidelberg 1992 pp 137 152 4 Desilet A and l Rousseau Syncro A ComputeroAssisted Tool for the 39 39 39 39 39 I quot Aided o N 11 61 H A I JiRnnceaiindl Berlin and Heidelberg 1992 pp 153 166 Daganzo C F Coordination of Inbound and Outbound Schedules at Transportation Terminals Proc 11th Intenmtiomll Symposium on Trans pomztion and Tm z c Theory Elsevier Science Publishing Company New 39 York 1990 pp 379 390 Ta Ceder and B Golany Maximal Synchronization in Plan ning Bus Timetables Research Re ort 91169 Transportation escarch Institute Technion Israel Institute of Technology Haifa Israel 1991 Brooke A D Kendrick and A Meeraus GAMS A User s Guide Sci enti c Press Redwood Calif 1988 8 Borland International Turbo Pascal Version 50 Scotts Valley Ca1if 989 157 V 9 gt1 Publication of this paper sponsored by Committee on Bus Transit Systems

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.