NBSIR 78-1426

Comparison of the

Performance of Three

Algorithms for Use in an

Automated Transit Information

System (ATIS)

Judith F. Gilsinn

Elizabeth L. Leyendecker

Douglas R. Shier

Institute for Basic Standards

Applied Mathematics Division

National Bureau of Standards

Washington, D C 20234

March 1978

Final Report

Technical Report To: Office of Socio-Economic and Special Projects

Urban Mass Transportation Administration

Department of Transportation

Washington, D.C. 20590

NBSIR 78-1426

COMPARISON OF THE

PERFORMANCE OF THREE

ALGORITHMS FOR USE IN AN

AUTOMATED TRANSIT INFORMATION

SYSTEM (ATIS)

Judith F. Gilsinn

Elizabeth L. Leyendecker

Douglas R. Shier

Institute for Basic Standards

Applied Mathematics Division

National Bureau of Standards

Washington, D.C. 20234

March 1978

Final Report

Technical Report To: Office of Socio-Economic and Special Projects

Urban Mass Transportation Administration

Department of Transportation

Washington, D.C. 20590

U.S. DEPARTMENT OF COMMERCE, Juanita M. Kreps, Secretary

Dr. Sidney Harman, Under Secretary

Jordan J. Baruch, Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director

ABSTRACT

This paper compares the performance of three algorithms for

computing trip itineraries for use in an automated transit information

system. One of the approaches (TIMEXD) is based on a time-expanded

network. The other two both compute paths in a bipartite route/ stop

network; one algorithm (LABCOR) is based on the label-correcting approach and the other (LABSET) on the label-setting approach. The transit

networks upon which the performance comparison is based are of two types:

a grid network with specified, possibly non-uniform, distances between

streets, and a spider web type of network. TIMEXD is fastest on all the

larger networks, but it requires most computer storage and outputs paths

with more transfers. LABCOR is the slowest, but is guaranteed to produce the best routing, since it always outputs an optimal path with

fewest transfers. Computation time estimates extrapolated to large transit

networks indicate times of 1.5 to 2.5 seconds per itinerary for TIMEXD

and LABSET respectively, well within the acceptable range for such networks.

Key Words : Algorithms; algorithm testing; mass transit; routing; shortest

paths; transit; transit information systems; transit routing; transportation

urban transportation.

TABLE OF CONTENTS

Page

1. Introduction 1 2. Algorithm Descriptions 3 2.1 Bipartite Route/Stop Algorithms 3

2.1.1 Label- Correcting Bipartite Route/Stop Algorithm

(LABCOR) 6

2.1.2 Label-Setting Bipartite Route/Stop Algorithm (LABSET).. 7

2.2 Time-Expanded Network Algorithms 8

2.2.1 Departure-Oriented Algorithm (TIMEXD) 11

2.2.2 Arrival-Oriented Algorithm (TIMEXA) 12

3. Test-problem Generation 13

4. Analysis of Algorithm Performance 17

4.1 Analysis of the Path Output l 8

4.2 Computer Storage Required by the Algorithms 28

4.3 Comparison of Computation Times 30

4.4 Additional Analyses 44

5. Conclusion and Recommendations 50

6 . References 52

Appendix A. Documentation of Programs for Test-Problem Generation

and Itinerary-Finding 53

A.l Program RAD 56

A. 1.1 Variables and Arrays Used in RAD 56

A. 1.2 Program Input 59

A . 1 . 3 Program Output 6l

A. 1.4 Subroutine LOCAL 6l

A.l. 5 Subroutine EXPRES 6l

A. 1.6 Variables and Arrays Used in LOCAL and EXPRES 6l

A.l. 7 Subroutine RSCHED 63

A.l. 8 Variables and Arrays Used in RSCHED 63

A. 2 Program XGRID 64

A. 2.1 Variables and Arrays Used in XGRID, GRID, and XPRESS ...65

A. 2. 2 Program Input 66

A. 2. 3 Program Output 67

A. 2. 4 Subroutine GRID 67

A. 2. 5 Variables and Arrays Used in GRID 67

A. 2. 6 Subroutine XPRESS 68

A. 2. 7 Variables and Arrays Used in XPRESS 68

A. 2. 8 Subroutine XTRANS 70

A. 2. 9 Variables and Arrays Used in XTRANS 70

A. 2.10 Subroutine XSCHED 71

A. 2. 11 Variables and Arrays Used in XSCHED 71

A. 2. 12 Subroutine TRANS 72

A. 2. 13 Variables and Arrays Used in TRANS 72
TABLE OF CONTENTS (Continued)

A. 3 Program TRA 72

A. 3*1 Variables and Arrays Used in TRA 72

A. 3.2 Program Input 73

A. 3. 3 Program Output 73

A. 4 Program ACYCLE 73

A. 4.1 Variables and Arrays Used in ACYCLE 74

A.h. 2 Program Input 75

A. 4. 3 Program Output 75

A. 5 Program LABCOR 75

A. 5.1 Variables and Arrays Used in LABCOR 75

A. 5-2 Program Input 77

A. 5 • 3 Program Output 77

A. 6 Program LABSET 77

A. 6.1 Variables and Arrays Used in LABSET 77

A. 6. 2 Program Input 79

A. 6. 3 Program Output 79

A. 7 Program TIMEXD 79

A. 7.1 Variables and Arrays Used in TIMEXD 80

A. 7- 2 Program Input 8l

A. 7* 3 Program Output 8l

A. 8 Program TIMEXA 8l

A. 8.1 Variables and Arrays Used in TIMEXA 82

A. 8. 2 Program Input 83

A. 8. 3 Program Output 83

A. 9 Program REMOVE 84

A. 9-1 Variables and Arrays Used in REMOVE 84

A. 9-Program Input 85

A. 9. 3 Program Output 85

A. 10 File Formats 85

A. 10.1 Format for File SDATA (Unit 7) 85

A. 10.

Format for File TDATA (Unit 8 ) 86

A. 10.

3

Format for File NDATA (Unit 9) 86

A. 10.

Format for File ADATA (Unit 10 ) 86

A. 10.

5

Format for File TRIPS (Unit 11 ) 86

A. 10 .

6

Format for File TMIN (Unit 12) 86

Appendix B. Listings of Programs for Test-Problem Generation and

Itinerary-Finding 87

B. l Program RAD 88

B. 1.1 Subroutine LOCAL 91

B.l.

Subroutine EXPRES 95

B.l. 3 Subroutine RSCHED 99

B.2 Program XGRID 100

B.2.1 Subroutine GRID 102

B.2.

Subroutine XPRESS 105

B.2.

3

Subroutine XTRANS 112

B.2.

Subroutine XSCHED Il4

B.2.

5

Subroutine TRANS 117

B.3 Program TRA 119

B.4 Program ACYCLE 121

B.4.1 Subroutine S0RTP 125
TABLE OF CONTENTS (Continued)

B.5 Program LABCOR 129

B.6 Program LABSET 134

B.T Program TIMEXD lUo

B.8 Program TIMEXA 145

B.9 Program REMOVE 150
LIST OF FIGURES

Page

1. Illustrative Bipartite Route/Stop Network )i

2. Illustrative Route Schedule 3

3. Illustrative Time-Expanded Network 9

U. Example of a Grid Network lii

5 . Example of a Radial Network 13

6. Example of Overtake 23

y. Overtake Occurrences in the Test Runs 26

A.l Flowchart of the Transit Program System 5^
LIST OF TABLES

Page

1. Number of Transfers in Each Path 19 -2k

2. Comparison of Paths for TIMEXD Using First Path Encountered to a Node Versus Last Path to that Node 27

3. Algorithm Timings for Each Path 31-36

4. Comparison of Timings of the Three Algorithms 38

5. Correlation of Timings and Network Size Parameters 39

6. Linear Regression Coefficients for the Fit of Timing as a Function

of the Number of Nodes 4l

7. Algorithm Timings (Milliseconds) for LABCOR and LABSET

on 40 x 40 Grid Network 43

8. Descriptions of the Networks for the Tests 45-46

9- Influence of Transfer Time 47

10. Influence of Ratio of Express to Local Speed 49

L - INTRODUCTION

Most larger transit systems operate a telephone transit information

center to provide prospective riders with itineraries for potential

trips. Usually transit system staff provide these itineraries by using

maps, schedules and routing information to piece together manually a trip to meet the caller's request. The largest systems may have as many

as 80 people involved in answering telephoned requests for transit

information. Consideration is currently being given to automating the

route-finding portion of the transit information activity. Transit

system staff would still be required to interpret the caller's request

and relay the computer-produced itinerary to the patron. It is expected

that automation of the route-finding portion of a call would significantly reduce the longer calls and could result in an overall average

reduction of about 20 percent in call length. Other benefits resulting

from automation include repeatability of response and lessened requirements for training of telephone-answering staff in city geography and

transit system routes. Analysis of the costs and benefits of an automated

transit information system is given in [3].

At the heart of an automated system is a procedure (mathematical

algorithm) for finding trip itineraries in a transit network. Such an algorithm would have available to it computerized descriptions of

transit stops, routes and schedules, as well as trip origin and destination and either a desired departure or a desired arrival time. Using

these data the algorithm would produce an optimal trip itinerary, "optimal" in the sense of describing either a trip which arrived soonest > having departed at or after the desired departure time, or a trip which departed latest to arrive at or before the desired arrival time. In

addition to the route-finding algorithm, the computer would also have a procedure for identifying geographically the caller's trip origin and

destination and appropriate transit stops accessible to these points.

The itinerary produced by the route-finding algorithm would specify

boarding time and stop, transfer stops and the arrival and boarding

times at such stops whenever transferring is required, arrival stop and

time, and routes for each segment. An example of such an itinerary

follows

Board Route RED at 5TH AND ELM at 9=00 A.M.

,

Arrive at 5TH AND OAK at 9:15 A.M.

Board Route BLUE at 5TH AND OAK at 9:17 A.M.

,

Arrive at 10TH AND OAK at 9:25 A.M.

Further discussion of the data structures, programs and procedures

involved in an automated transit information system is presented in [lj.

Also included in an appendix to that report are the descriptions of

three specific route-finding algorithms which are the subject of the

analysis presented below. The main objective of [l] was to assess the

feasibility of designing algorithms which could compute itineraries fast

enough to improve the information system's response to the caller. With

feasibility established, the current analysis turns to the choice of
algorithm as it relates to the characteristics of a transit system, such

as the size and complexity of network structure, the regularity of

departures, transfer times, relative speeds of express and local service,

and various patterns of preferential service.

Section 2 below contains descriptions, excerpted from [ 1 J , of the

three algorithms which are compared in the present analysis. Section 3

contains descriptions of the two network-generation programs used to

produce transit-like networks on which the algorithms were tested. The

results are discussed in Section 4, and recommendations for choice are provided in Section 5. Program documentation and listings appear in

appendices

.

The results of the analyses described in Section 4 may be summarized as follows. The label-correcting bipartite route/stop algorithm

(LABCOR) provides the most desirable trip output of the three algorithms,

since it always produces, from among those trips arriving at the same time (under the departure-oriented criterion), that trip requiring

fewest transfers. However, LABCOR is significantly slower than the other

two algorithms. The time-expanded network algorithm (TIMEXD) is fastest

on the test networks, and its speed increases with network size at the

lowest rate of the three algorithms. However, TIMEXD requires significantly more storage than the other two algorithms, mainly because of the

need to store explicitly each possible transfer. The third algorithm,

the label-setting bipartite route/stop approach (LABSET), is slower than

TIMEXD but faster than LABCOR. Path output from LABSET has more transfers than that from LABCOR, but not as many as from TIMEXD. Although

T.ABSET requires somewhat more storage than LABCOR, both require significantly less than TIMEXD. Computation times for all three algorithms depend mainly on the number of stops in the transit network. Other factors

which have some effect include the number of transfers required, the

average transfer time and its variability, and the relative speeds of

express and local service.

- 2-
2. ALGORITHM DESCRIPTIONS

Descriptions of the three algorithms were given in an appendix to

[l] but are repeated here to make this report more self-contained. The

algorithms rely for their efficiency on specialized representations of

the transit data base of stops, routes and schedules. The three algorithms which are analyzed in Section 4 all use the "departure-oriented"

optimality criterion for finding a best path} and thus produce a trip

which arrives soonest while departing at or after the desired departure

time. We include below (and in the appendix) the description of one of

the algorithms, the time-expanded algorithm, programmed for the arrivaloriented case. We expect no difference in the performance between

departure- and arrival-oriented algorithms and have therefore focussed

in the analysis on the departure-oriented criterion.

2 . 1 Bipartite Route/Stop Algorithms

The nodes of the bipartite route/stop network are of two types, one representing the geographical transit stops and the second representing

individual transit routes. Network arcs are also of two types: for

each transit stop an arc connects it to those lines stopping there, and

for each route an arc connects it to the stops along that route. (The arcs associated with a route appear in the order of the stops along the

route.) Thus the network described here is bipartite in the usual

graph-theoretic sense that the nodes of the network may be partitioned

into two sets in such a manner that arcs connect a node in one set with

a node in the other set but do not connect nodes in the same set.

Figure 1 displays an example of such a network. Note that a dummy route

was introduced for a walk transfer link connecting two other routes. A

path in this network is an alternating list of stops and routes, beginning with the origin stop and ending with the destination stop. The

route node appearing between each pair of stops specifies the route

which should be taken between them. The number of transfers is thus one

less than the number of routes appearing in the list, or alternatively,

since each stop other than the origin and destination represents a transfer, two less than the number of stops in the path.

The network as described above does not have associated with it the

time data specifying each discrete departure. The arcs connecting the

routes to the stops actually represent a whole list of scheduled vehicle

trips along the route, to be fetched during the course of the algorithm

as needed. An example of such a list for one route is given in Figure 2.

Each column gives times at a stop and each row represents one transit

vehicle's trip along the route. Thus if the arcs emanating from a route

node are listed in the order of the stops along the route, a row of

Figure 2 represents arrival times at the arc endpoints in order. We

will describe two computational schemes based on this network, one using

the basic label-correcting procedure and a sequence list ordered by

cardinality distance (in this case the number of vehicles used) and the

second using the label-setting procedure and a list ordered by temporary

label (in this case trip arrival time). A more detailed description of

- 3-
FIGURE 1

Illustrative Bipartite Route/Stop Network

V

T

8, 9

6 , 8

9 Nodes

9 Arcs

B1PARTE ROUTE/STOP NETWORK

32 Arcs (Each Connection is Two-way)

-h-
FIGURE 2

Illustrative Route Schedule

Stop 1 Stop 2 Stop j Stop

7:00 7:10 7:15 7 : 30

7:30 7:45 7:55 8:10

8:00 8:15 8:25 8:40

8:30 8:40 8:45 8:55

10:00 10:05 10:09 10:15

12:00 12:07 12:15 12:25

2:00 2:05 2:09 2:15

4:00 4:07 4:15 4:25

4:30 4 : 40 4:50 5:05

5:00 5:15 5:25 5:40

5:30 5:45 5:52 6:05

6:00 6:10 6:15 6:25

6:30 6:40 6:45 6:55

8:00 8:05 8:09 8:15

10:00 10:05 10:08 10:13

- 5 -
the basic label-correcting and label-setting procedures can be found in

[2]. The following notation will be used in describing the schemes.

R

r the set of all transit routes

a particular route

S

s the set of all transit stopsa particular transit stop

ORG the origin transit stop

DST the destination transit stop

N R U S, the nodes of the whole bipartite network

T(i)

P(i)

arrival time at stop i via best path from ORG, for ieS

node preceding i in best path from ORG. (Note that if

i^R then P(i)eS, while if ieS then P(i)eR.)

L(k) sequence list of nodes in S, developed by the scheme,

indicating the order in which they are to be fanned out

from. In the label-correcting method L is maintained in

cardinality distance order; in the label-setting method,

it is ordered by arrival time.

F(i) position of node i in sequence list L

u current position in the sequence list

V last position filled in the sequence list

END last entry in sequence list L

2.1.1 LABEL-CORRECTING BIPARTITE ROUTE/STOP ALGORITHM (LABCOR)

A computational scheme LABCOR for a label-correcting procedure for use with the bipartite route/stop network is given below.

Initialization : Set T(i) = 00 for all i # ORC and set T(ORG) = desired departure time. Set P(i)=0 and F(i)=°° for all ieN.

Set u=0 and v=0.

Step 1: Let i=ORG. Let r be the first listed route stopping at i

Step 2: Search the schedule for route r for the first departure

from i at or after T(i). Let s be the first stop occurring after

i in route r.

Step 3 : Compare the arrival time at s of the scheduled vehicle

found in Step 2 with the current value of T(s). If it is not less

go to Step 6; if it is less, set P(s)=r and P(r)=i.

- 6-
-7-

Step 4 : If T(s) = 00

, go to Step 5- Otherwise let k=F(s). If

k>0, remove s from its previous position by setting L(k)=0.

Step 5 : Set T(s)= the time of arrival of route r at node s. Let v=v+l.

If v>END, set v=l. Set L(v)=s and F(s)=v.

Step 6 : Let s be the next stop on route r, and go to Step 3. If

there are no more stops on r, let r be the next route stopping

at i and go to Step 2. If there are no more routes stopping at

i , set F(i )=0.

Step 1 : If u=v, stop. Otherwise let u=u+l. If u>END, let u=l.

Let i=L(u). If i=0, repeat Step 7- Otherwise let r be the first

route stopping at i and go to Step 2.

These computations do actually maintain the sequence list L in

cardinality distance order. Note that successive path segments are always by different routes, so that cardinality distance is associated

with the number of different routes used in a path. ("Actual" cardinality length of a path in this network is twice the number of routes

used since paths consist of an alternating stop-route sequence. However

since L contains only stops, it can be used in obtaining directly the

number of routes used. ) If it is desired to consider only paths

using no more than some maximum number of routes, say r , then the

computational scheme given above can be modified easilym

fo accommodate

this additional constraint, utilizing two additional pointers:

m the cardinality distance (actually the number of routes)

used in the current path from ORG to node i.

j the position in L of the last node of cardinality distance m.

Both m and j are initialized at 0. The computational scheme is modified

by the addition of a Step 6 .5 between Steps 6 and 7 above.

Step 6.5: If u=j, let m=m+l. If m=r , stop. Otherwise,

set j=v.

2.1.2 LABEL-SETTING BIPARTITE ROUTE/STOP ALGORITHM (LABSET)

A label-setting scheme LABSET for use with the bipartite route/stop

network is similar to that given above, but the sequence list L is kept

ordered by arrival time at each node. The length of L is determined by

M, one plus the maximum arc length. See [2] for a more complete discussion of the label-setting procedure. Since for transit networks the

transferring time must be included in M, it is perhaps easiest to set M

at some reasonable trip length level (say 3 hours, or if desired 2h

hours )

.

-7 -
Initialization : Set T(i)=°° for all nodes i ^ ORG and T(ORG) = desired departure time. Set P(i)=0 for all $odes i. Let u be one plus the desired departure time (mod M).

Step 1 : Let i=ORG. Let r be the first route stopping at i.

Step 2 : Search the schedule of route r for the first departure

from i at or after T(i). Let s be the first stop occurring after

i in route r.

Step 3 : Compare the arrival time at s of the scheduled vehicle

found in Step 2 with the current value of T(s). If it is equal or greater, go to Step 5; if it is less, replace the old T with the new value and set P(s)=r and P(r)=i.

Step h : Let k=T(s) (mod M). Store s in position k+1 of L. Step 5 : Let s be the next stop on route r and go to Step 3. If

there are no more stops on r, let r be the next route stopping

at i, and go to Step 2. If there are no more routes stopping at

i, continue to Step 6.

Step 6 : Let u=u+l. If u>M, let u=l. If L(u)=DST, stop. Otherwise, let i=L(u). If i=0, repeat Step 6. Otherwise let r be the

first route stopping at i and go to Step 2.

Note that termination occurs when DST is the node to be fanned out from.

Thus if DST is fairly close to ORG the label-setting procedure requires

much less calculation than the label-correcting procedure, which terminates only after best paths to all nodes have been found.

2 . 2 Time-Expanded Network Algorithms

Nodes in the time-expanded network are defined by a pair of entities, the geographical transit stop (a separate node for each route) and

a time of day. Thus the geographical node Sixteenth and K Street will

become several nodes, one for each time a transit vehicle stops there.

The network arcs become transit trips departing one stop at a particular

time and arriving at another stop at a different (later) time. Transfer

arcs, representing allowable transfers (i.e., those obeying minimum

transfer times), must be coded directly. An example of such a network is

depicted in Figure 3. In this example there are four transit stops and

three bus lines: a local stopping at each stop (its two daily runs are represented by the paths l-*-3-*6-»-8 and 12-KL6-KL7+20 ) , a faster vehicle

starting at the second stop of the first route and proceeding directly

to the last stop of that route (with four runs: 5^7) 9^10, lU-*15,

and 18-KL9), and one coming from the last stop of the first route

By X(mod M) is meant the remainder when X is divided by M. Its calculation is usually available in FORTRAN through the function M0D(X,M).

- 8 -
GEOGRAPHICAL STOP

-9-
- 10-

back to the next-to-last stop of that route (Us runs are represented by

£*», 11+13* and 21 *22 ). Two transfer axes, 5*9 and ll*-*l8, have been

included. Note that in the left transfer, one Is prevented by a minimum

transfer time restriction from making the earliest vehicle on the second

1 ins.

The Tour stop network has been transformed into one with 22 nodes

arid 1^ arcs. In general, time- expanding the network greatly increases

the number of nodes, in fact by a factor equal to the average number of

transit vehicle departures per geographical node. Generally It Is desirable to decrease rather than Increase network glxe, but the fact

that the resulting time-expanded network is acyclic means that the

Increase Is likely to be beneficial. On an acyclic network the network

nodes can be numbered at the outset in such a way that for each arc (l,

j), i'J. That is. In the numbering, arcs always lead from lower

numbered nodes to those with higher numbers. Of course a similar property a) so holds true of paths. This limits the search for path ex- tensions to nodes whose numbers are greater than nodes already in the

path, so that nodes can be interrogated in the order of their numbering.

The nude order assumed below is the one determined entirely by the time

component of node Identity, except for "ties" which cause no trouble

unless some arc requires no time to traverse. If only major stops are included this situation Is unlikely to occur, but if it were, procedures

exist to number nodes having Identical time components.

The node numbering procedure al lows the network to be broken up

into pieces (which will be called pages) so that the computational

scheme only needs one of them at a time and can finish with the current

one before needing the next.

The computational schemes proposed for computing transit paths In such a network appear below and rely on the basic label -correct l ng

scheme. We will use the following notation:

n( 1 ) the geographical transit node associated with the network

node numbered 1

t(l) the time associated with network node numbered I

ORG geographical node of transit origin

DST geographical node of transit destination

P(D the network node preceding i in a best path from Ohli to

the network node numbered I

•A network is acyclic If there are no pallia containing more than one node

and beginning and ending at the same node. Since all arcs in the timeexpanded network go forward in time, no path can return to a node once it

has left that node, so this network is acyclic.

- 10-
DONE the first node associated with DST encountered (i.e.

the one for which t is minimum) in a path starting at

a node associated with ORG

2.2.1 DEPARTURE-ORIENTED ALGORITHM (TIMEXD)

The computational scheme proceeds through the following steps:

Initialization : DONE = P(i) = 0 for each node i.

Step 1 : Scan the arc list starting with the first node i for which

t(i) is not less than the desired departure time. Let i he the

first node encountered with n(i)=ORG.

Step 2 : Let a=(i,j) he the first arc originating at node i. If

there are none, go to Step 6.

Step 3 : If P(j)^0, go to Step 5- Otherwise set P(j)=i.

Step U : If n(j)^DST, go to Step 5. Otherwise set DONE=min (DONE, j).

Step 3 : Let a=(i,j) he the next arc originating at node i, if

there is one, and go to Step 3. Otherwise continue.

Step 6 : Let i=i+l. Stop if i=DONE.

Step 7 - if P(i)=0 and n(i)#ORG, go back to Step 6. Otherwise

go to Step 2.

It is clear from this description that only the nodes numbered

between the first departure from ORG after the desired departure time

(which we shall call i' ) and the node DONE are examined as arc origin

nodes. In most instances this should he considerably fewer than the

total number of nodes in the network. To take advantage of this fact, one may store information about node i in position i-i'+l in the P array.

The algorithm described above requires only one pass through the

nodes, and only a subset of the nodes at that. No sorting or sequencing

of nodes is necessary, since nodes are examined in numerical order.

Since arcs are stored sorted by origin, only that portion of the network

originating at nodes i* through DONE need be referenced for this path

calculation. An arc in this application only requires identification of

its origin and destination nodes since the t and n pointers describe the

relevant arc characteristics.

- 11-
2.2.2 ARRIVAL-ORIENTED ALGORITHM (TIMEXA)

For the arrival-oriented criterion a modified version of the above

scheme may be applied, using the same network and examining the nodes in reverse order starting from the last node associated with DST whose time

is before the desired arrival time. This scheme will be described

below. Use of two schemes has the advantage that only one copy of the

network, the forward star form, need be stored to handle both the departure oriented and arrival oriented criteria. This is particularly

necessary for the time-expanded network because of its large size.

Different schemes are then applied to the network for the two criteria,

the one above for the departure oriented criterion and the one below for

the arrival oriented criterion. The following array and variable will

be used in describing the scheme, together with the arrays n and t and

variables ORG and DST listed above:

S(i) the network node succeeding i in a best path from the network

node numbered i to DST

FIN the first node associated with ORG encountered (i.e., the

one for which t is maximum) in a path ending at a node

associated with DST.

The computational scheme proceeds through the following steps:

Initialization: FIN=0; S(i)=0 for all i.

Step 1 : Scan the arc list backwards, starting with the last

node i for which t(i) is at most the desired arrival time. Let

i be the first node encountered with n(i)=DST. Set S(i)=i. Go

to Step 6.

Step 2 : Let a=(i,j) be the first arc originating at i. If

there are none, go to Step 6.

Step 3 : If S(j)=0, go to Step 5- Otherwise set S(i)=j.

Step U : If n(i)/ORG, go to Step 5- Otherwise set FIN=max(FIN,i )

.

Step 5 : Let a=(i,j) be the next arc originating at node i, if

there is one, and go to Step 3. Otherwise continue.

Step 6 : Let i=i-l. Stop if i=FIN.

Step 7 : If n(i)^DST, go to Step 2. Otherwise, set S(i)=i and

go back to Step 6.

In the runs described in Section U, only the algorithms using the

departure-oriented criterion, LABCOR, LABSET and TIMEXD, were tested.

Runs of TIMEXA and TIMEXD suggested that the two algorithms performed

similarly. In addition, the symmetry of the criteria and algorithms

suggest that the two criteria should be equally efficient to process.

-12-
3. TEST-PROBLEM GENERATION

Two network generation programs have been written to produce the

route and schedule information for the algorithm testing described in

Section 4. One program generates a p by q grid network in which routes

run either horizontally or vertically and transferring is possible at

any intersection. Every trip requires at least one transfer, as long as the origin and destination are not on the same horizontal or vertical

route. Subsets of the horizontal and vertical streets may be designated

as main streets. Express routes begin and end at the outside of the

grid, run along main streets, and stop only at intersections of other

main streets. An example of such a network is shown in Figure 4, with

express routes indicated by the wider lines and stops on express routes

as blackened disks.

A second program generates a spider web radial type of network in

which routes run inward or outward along radials from a central node and

also clockwise or counterclockwise along beltways or partial beltways

connecting the radials. Other routes may run from the center out along

a radial, diverging from the radial at some point along it. As with the

grid network, radials and beltways may be designated as major arteries

along which express routes run. The express routes only stop at intersections

of other express routes. Any node in the network is accessible from

any other node either by traveling to the center along one radial and

out along another, or else by traveling around one of the beltways. At

least one transfer is required if the origin and destination are not on the same radial or on the same beltway. Figure 5 displays an example of

a radial network, with express routes shown as wider lines and stops on express routes as blackened disks.

Schedule information for both types of networks is given by providing the initial run's departure time, the number of runs and the headways for each time period and route. Several routes may be grouped

together if they have the same headways and numbers of runs. Distances

between grid elements are provided as input to the grid type networks.

Distances of nodes out from the center along the radials are input to

the radial network generator, as are the angles between radials. Distances

along beltway sections are then calculated as circular arc approximations. Using the arc distances, run departure times, and speed factors

for either local or express routes, stop times at later nodes along each

route can be calculated.

Output from the network generation programs consists, for each

route, of the stops along that route and, for each departure along the

route, the time it reaches each of the stops.

The networks generated by these programs clearly represent idealizations of transit system structure, but examination of several transit

system maps has indicated that many systems have an underlying grid or radial structure or a combination of the two. Any undue simplification

-13-
FIGURE b

Example of a Grid Network

-lU-
rri

"

FIGURE 5

Example of a Radial Network

- 15-
associated with the topological regularity implicit in the grid and ra- dial structures is counteracted somewhat by the variability in the ser- vice availability. In fact, since almost all trips calculated for the

analyses in Section 4 required at least one transfer, whereas most transit

systems are designed so that many frequently-made trips require no transfer, the pure grid and radial network structures may actually be a more difficult test case than would be real networks of the same size. Post

facto justification for using idealized networks in the tests is the

finding, reported in Section 1+, that the particular network structure is

less important in determining algorithm performance than are various

measures of the complexity and variability of network parameters.
-17-

U. ANALYSIS OF ALGORITHM PERFORMANCE

The network generation programs described in the previous section were used to produce transit networks with specified characteristics for use in testing the three algorithms, LABCOR, LABSET and TIMEXD. Twentysix different situations were generated, with a particular test network

characterized by the network generator used (i.e., grid or radial), the

minimum transfer times required, and the network input parameters such

as size (number of nodes and runs), frequency of service, and speeds of

express and local vehicles. For each test, twenty-five itineraries were

calculated, with their origin-destination pairs and times of day chosen to

represent "reasonable" trips. The 0-D pairs were not formally chosen by

any random process and probably overrepresent the longer and more com- plicated trips, just those which are more difficult and more timeconsuming to calculate. In some cases, no trip was found within the

desired time period. In order to ascertain that no trip existed, the

algorithms had to process some data; timings for such situations have

therefore been included in the analysis.

The tests were run on the UNIVAC 1108 at the National Bureau of

Standards (NBS) under the EXEC 8 operating system. The programs were

all coded in FORTRAN V, UNIVAC' s enhanced version of FORTRAN IV. Care was taken to insure that the programs were coded without utilizing

special peculiarities of the UNIVAC 1108 and its FORTRAN compiler. The

algorithms were coded to make them as comparable as possible. Timings

include only the algorithm calculation portion of each of the programs;

they do not include any input /output operations. All problems were core-size

problems, that is, the data base for each problem was sized so that it

could be accommodated in the main memory of the computer. This simplified programming and eliminated one possible source of bias or var- iability in performance.

The analyses described below investigate the comparative performance of the three algorithms LABCOR, LABSET, and TIMEXD on small transit

networks containing from U0 to 225 nodes. One test example used a grid

network containing l600 nodes, which is similar in size to the transit

system in a medium size city. The runs were made primarily to test

algorithm performance on a variety of types of networks with varying

characteristics. The network generation programs were designed to allow

input control of several different network parameters including network

size as measured by the numbers of nodes and vehicle runs, network shape

as measured by the number of horizontal and vertical routes in a grid or the geometry of a radial network, the variability of schedules, and the

relative speeds of express and local service. By careful selection of

appropriate input parameters, scenarios representing a variety of rea- sonable network types can be simulated and variations on these networks

can be evaluated. The tests and analyses performed to date do not exhaust

all possible tests which could be informative, but they were designed to

reveal the general performance of the algorithms across the spectrum of

likely input situations.

- 17-
4.1 Analysis of the Path Output

In comparing the itineraries output by the three algorithms for a given trip, it was necessary to choose the most desirable. When all had

the same number of segments, the main difference was usually whether the

traveler waited at the origin or at an intermediate stop, a choice with

neither alternative always being preferable. When there was a difference

in the number of transfers, however, it was believed that the trip with

fewer transfers should always be considered preferable. Table 1 displays,

therefore, the number of transfers required by each of the three algorithms for each of the 25 requested itineraries in each of the 26 test

networks. As noted in the descriptions of the algorithms, LABCOR always

produces that trip which arrives first while departing at or after the

desired departure time and which also has the fewest transfers. The

other two algorithms will produce trips arriving at the same time, but

these trips may require more transfers. In fact, 9 percent of LABSET

trips and l4 percent of TIMEXD trips required more transfers than LABCOR

trips

.

One type of situation in which a routing algorithm may provide

extra transfers occurs when an express vehicle overtakes a local vehicle. This is illustrated in Figure 6. The soonest arrival time for a trip from node 1 to node 5 departing at or after 5:00 is 5:35* Two

different itineraries with the same arrival time are possible: The first

starts out at 5:00 on the local and arrives at stop 3 at 5:20, transfers

to the express at 5:25 and arrives at node 5 at 5:35* The second waits

15 minutes to board the express at node 1 at 5:15 and takes the express

direct to the destination at 5:35- Taking the express is preferable

since it does not involve a transfer. Examples of the overtake situation occurring in the test runs are shown in Figure T- In each case the routing produced by LABCOR (and in these cases also by LABSET) waits

at an intermediate node for an express route, while TIMEXD takes the

local route which is the first vehicle leaving and transfers to the

express just before it overtakes the local.

In an attempt to avoid so many transfers by TIMEXD, we tried

varying the choice criterion for trips which arrive at the same timeexpanded node (that is, trips which arrive at the same geographical node

at the same time). Table 2 shows the results of using two criteria, one which always picks the first trip encountered, which is also the trip whose

last segment starts earliest, and a second which picks the trip whose

final segment starts latest. Although the latter criterion might seem

to correct the difficulties encountered in an overtake situation, it

does not always produce trips with fewer transfers as can be seen in

Table 2 . These results were obtained for network number 2, which had

no express routes and may thus make the second criterion appear less

desirable than is actually the case. However, neither criterion seems to reduce appreciably the incidence of extra transfers using TIMEXD.

-18-
TABLE I

IF

OF

TRANSFERS

IN

EACH

PATH

Transfers

for

LABCOR -19-

indicates

no

trip

was

found. Q

indicates

no

transfers,

i.e. a

iirect

trip.
TABLE

1

(Continued)

Transfers

for

LABCOR

-20-
TABLE

1

(Continued)

Transfers

for

LABSET

-21
TABLE

1

(Continued)

Transfers

for

LABSET

vo

cm WHHHWHHHHHWHHriWHHWHHWHHWH

(M HHHHCMHHHHHCMHHCMHHHCMHHCMOHCMCM

cm WHHHWHHHHHWHHHWHrlWrlrlW H H CO CM

00

CM CMHCMHCMHHHCMHCMHHCMCMHHCMCMHCMCMCMHCM

CM

CM HrlHHCMrlr|r|rlH(\IHrH(MHrlr|CMrlHCMC\IHCMCM

rH

OJ HCMCMHCMHr—IOCM i—IHHCMHCMHHCMCMHH r—lr—IHH

O

CM r—lr—IrHHHHOrlr—IrHHr—Irlr—lOr-Hr-Hr-Hr-HCMr—ICMCMOO

CT\ HrICMrlr—lr—lr—ICMr—ICMCnCMrHr|r—lr—ICMOOrlOrlOr

rH i—

OO

rH CMCMOCMHCMHOHHHHCMOHHHHHCMHHHOH

-J-CMOOHHOOH-^J-HHOHHHHOOOCMHHHHCMCMO

VO HHHCMHHHCMCMHHHHHCMHHCMCMHHCMHHH

HCMHHHHHCMHHHCMHHHHHHHOHHHCMCM

, O rl CM 004 IAVO 1-00 0\0 rl CM (0 4- IA rlWOjIAVOhCOONrlHHHHrlrlrlrlrlCMCMCMWWW

- 22-
TABLE

1

(Continued)

Transfers

for

TIMEXD

-23'
TABLE

1

(Continued)

Transfers

for

TIMEXD

-2b-
Local Times Express Times

No Transfer Express

5:15 5:35

One Transfer

1

5:00

Local Express

5 : 20 , 5:25

55:35

FIGURE 6

Example of Overtake

- 25-
oM

ft

to§«p

to

<u

d> PPc

•H

(0

<u

CJ

Pi

CJ

CJ O

<u ap

Pi

QJ>O o o

t— VD

co

H

a

rV OJ P

to

co

<uU Ov

rH ** LTV VOPC—

CVJ VO C— «* p- LTV VO

irv C

to «

ITS ON

-3-

co

irv icv t— t— p- i—1 VO

C— t- irv c—

CO to t— CO

to I to to , t QJ i <u <U 1 i Pi Ov f u co L P o f f ft-tf ftp- f ft LTV 1 X 1 X 1 X

d> (U <u 1 co t— ' H o

_=J- VO irv VO t- t— t— t—

rH «• on t—UN

H 1 1—

1, rH I rH

cd

L cd

A cdA cd o vo P o Ov f o vo f O rH O o CVJ O CVJ O CO H • H rH 1 rH

CVJ ' vo CO p LTV CVJ t— C— tOv •» LTV •* t— *s P o VO CO rH CO p LTV | CVJ 1

*“

A 1 t—

cvj

r

p ff i—

f P CVJ | p 1 P 1 P

CVJ CO OV VO GO 1—

CVJ CVJ VD P rH CVJ t- t— t—

vo co

Ov rH VO pt— PO

dJo3Po

Pi ft

co

<u •H

Pi

cd

Pi

d)c

to

co

<uP<£co

<u *

CO rH

LT\ LTV

ON « O

CJ CO

cvj cvi t—

rn CVI VO

OV VO VO -HO

O

t- VO

CO

CO

0)0)

(O prH VO f— «> VO CO

CO I—

rH CVJ OV rH VO PI—

• <L> Pi S

ft cd -P op

co

U . d) QJ i p p p t Ph 3 g 1

cd £ O 3 1 ft B

Ph

a ' <D # rH ft -P o r\ p • <D

co Pi

B

Pi , Pi • h

(LI dJ 1 P P T

cd P 3 S I o 3 1 • Pi a P

ft Pi o cd d> p ft B

to d> -H P P 6

PiO

CD pG

•HP

dJ P

CO

<U

Picd

co

<u •H

Pi

cd

Pi

<l> c

•HPM* -26-
TABLE 2

Comparison of Paths for TIMEXD Using First Path Encountered

to a Node Versus Last Path to That Node

TRIP

Number oe I'kAlM seers LABCOR TIMEXD TIMEXD

(last arrival) (first arrival)

1 1 3 1

2 1 3 1

3 1 1 1

b 1 1 1

5 1 1 2

6 1 1 2

7 1 k k

8 1 b b

9 1 1 2

10 1 1 2

11 1 3 1

12 1 3 1 13 1 3 1 lU 1 3 1 15 1 1 2

16 1 1 2

17 1 1 b 18 1 1 b 19 1 1 3

20 1 1 3 21 1 1 1 22 1 1 1

23 1 1 l

2b 1 1 1 25 1 1 1

Average 1.0 1.68 i.88

-27-
In conclusion, LABCOR provides the most desirable path output since

it always produces an itinerary with the minimum number of transfers.

The other two algorithms output a small but significant number of trips

with extra transfers (9 percent for LABSET and lh percent for TIMEXD).

When the overtake problem occurs, using TIMEXD may lead to an extra transfer

from a local to an express because the express starts later than the

local and passes it enroute, arriving first at the destination. Varying

the criterion for choosing between ties does not result in a decrease in

the number of extra transfers for TIMEXD.

4 . 2 Computer Storage . Required by the Algorithms

The storage required by the algorithms is largely a function of the

size and configuration of the network and schedules. The particular

form in which the algorithms have been coded for this study does not

attempt to optimize use of storage of the basic network data. For instance, in LABCOR and LABSET the routes are stored in a doubly indexed

array, ROUTE (i,j), in which the entry for i,j is the jth stop on route i. Thus the size of the array is the number of routes by the

maximum number of stops per route. If one or a few routes are long

while all others are short, this wastes much storage. The compensating

benefit is that of easier reference to a desired piece of data. More

efficient storage would involve more complicated indexing than was used

in the programming. The decision in favor of the simpler representation

was made in the interest of facilitating quick coding. In addition, it

is the LABCOR and LABSET algorithms which are most severely affected by

this decision, and they require less storage than does TIMEXD for the same network. Since we intended to run all three algorithms on the same problems, we were less concerned with wasting storage space in programming LABCOR and LABSET.

In estimating the storage required by LABCOR and LABSET we will use the following notation:

R number of routes

S number of stops

L maximum number of stops per route

K maximum number of routes per stop

D number of vehicle departures

T number of possible time intervals (e.g. lhkO minutes per day)

Then the storage required by algorithm LABCOR is approximately:

3R + 8S + (R+D)L + S-K.

Similarly the storage required by the algorithm LABSET is:

3R + 10S + (R+D)L + S-K + T.

-28-
Additional storage is required for printing paths, but these expressions

contain the major elements requiring computer space.

Notation used in estimating the storage for TIMEXD follows:

N number of time-expanded nodes

A number of arcs in the time-expanded network

T number of possible time intervals (as above)

D number of vehicle departures

£ average number of stops per route

k average number of routes per stop.

The algorithm requires

5N + 2A + T

storage locations, exclusive of path printing and incidentals. To

relate this to the other two algorithms we approximate N and A as follows

N = D-

£

A = D-£ + N-k = D-£(k+l).

Assuming each vehicle arrival gives rise to a new node, we arrive at an overestimate to the number of nodes. Arcs are of two kinds, those which

represent vehicle trips—whose number is the number of vehicle departures

times one less than the number of stops per route (approximated as

DJI) — , and transfer arcs, whose number is the number of routes stopping

at a node times the number of nodes, under the assumption that all

possible transfers at each node are available and reasonable. The total

requirement then becomes

6D£ + 2D£k + T.

These approximations overestimate storage requirements but are useful

for comparison purposes.

In a square grid network of size P x P:

S = P

2 r - Up

L = £ = P

K ~ k = U

so the storage required by LABCOR is

12P + 16P

2 + DP,

for LABSET is

12P + 18P

2 + DP + T,

-29-
and for TIMEXD is

14DP + T.

For several of the test cases P was about 15, D was about 300 and T was

1440, making the storage requirements 8200 for LABCOR, 10170 for LABSET,

and 64440 for TIMEXD. We note again that the formula for TIMEXD over- estimates the storage required, in this case since the actual number of

transfers per interior node is 3, rather than 4, and the number possible

at peripheral nodes is 2 or 1.

The difference in storage requirements is greatest for the sort of

situation described above when L = l and K = k. For a radial network it

is likely that K >> k, since all routes in or out along radials stop at

the center node. Thus in a radial network with 6 spokes, at least 12

routes (and more if there are spike routes *) stop at the center node,

whereas most other nodes have at most 4. A full beltway would have at

most 7 stops (one stop repeated) but a radial route could have as many

as desired. A partial beltway might have only 2 stops. Therefore there

is a great variability in the number of stops per route and routes per

stop, leading to a difference between K and k and between L and l.

Similarly in a rectangular network which is long and thin, storage must

be provided as if all routes had as many stops as the longer routes.

Thus whenever K > k and/or L > £ , LABCOR and LABSET, because of inefficient storage design, require more storage than they actually use,

whereas TIMEXD can be sized more tightly. In spite of not using storage

most efficiently, for most of the test cases LABCOR and LABSET required

significantly less storage than TIMEXD.

4 . 3 Comparison of Computation Times

Timings for the 26 test runs and the 25 cases for each run are listed in Table 3- The timings include only processing time, no input

or output operations, since test cases were chosen to be small enough

not to require reference to external storage. For each run, timings were made on all three algorithms at the same time of day (actually

within the same computer run), to ensure that the computer environments

were as comparable as possible.

There are many problems with timing an algorithm in a multiprocessing environment, such as the UNIVAC 1108 under the EXEC 8 operating

system, in which several programs are active in various stages of processing at one instant in time. In calculating the run time for each

algorithm on each case, we used a computer subroutine, CPUSUP, available

at NBS for summing the CPU time of a designated section of one program

only. However, our experience has been that timings of the same problem

*Spike routes are ones which begin or end at the center node, include

stops along one spoke and then deviate from that spoke to one final stop

not on any spoke.

- 30-
TABLE

3

ALGORITHM

TIMINGS

FOR

EACH

PATH

Timings

for

LABCOR

(Milliseconds

per

Path)

rH

OJ

r—

I

HrH

o

rH

On

go CM CO OOO CO VO .4 VO -4 CO UNVO oo NO CO CO CO COOO coco cm vo

UA CM UA CO UA CO t— [— CO f— CO UA t—

rH i I i—I rH i—( i—I i—I i—I i—I i—I H I—li—

I

On ON On t— H ONOVOU) J- rH -4 CO

UA CM IA CO t- -4VO-4VO-4VO-4VO HHHHrlHrlHHHrHHH

OOCMCMOOCMOOt~--4COOOONOOCO -^OJOH-OCOW(OC\J(OC\J(0 HHHHHHrlHHHrlHrl

On OO O Onoo On On On OO co t-oo co C\IOJ(OCVIOJC\IC\JCVICVIC\jC\JC\JCVI

LTN UA t— UA VO UA VO (AND LTN CO

rH i—I i—I rl H i—1 i—I i—I i—I —I i—I i—

I

On C— On ltn co -4" O ia On ia O t—

CO LTN CNJ UA CM VO -4 VO CO VO -4 VO HrHHHiHHHrlHrlrlH

t— OO CO CO t-—ONUAO\UAONVO-4 OCOOCOOCOONCOONCOONCO H rl rl rH H rH rH rH r—

I

rH CO t— O CO t— On CO CO ONONCO

COCMCMCOCMCMCMCMCMCMCMCM

CO CM On t— CM O CO -4 t-CO VO CO J- CO VO t— CO OO OO CO c— vo t— CO VO COCOCMCMCOCOOOCOCMCMCMCMCMCMCMCMCMCMCMCMCMCMCMCMCM

C\J VO

1—

1

CO

• • CM vo VO •—

i

rH

CM

i—

1

o • • rHUA rH H

co CO VO CO

• • CO t"— CM

i—

1

rH

co VO

ON

• • CO

CM

VO CO 4 -4 OO CM

CM

co

-4 OJ CO ON cyc-covoiAj'(\jHO\cjcococ\j^-oj-ojON(M-cfc-cncoiAj' ojojojojojojcocoojcoojojcocoooojojojcoojojojcoojco t— co

OJ

rHCM 4- H lA^tJ- rl O 0\V0 OOCOHOJIAIAHCOCOH

CMCMCMCMCMCOCOCMCMCMCMOOCOCMCMCMCMCMCM

-J- OJ CM J- IH

CNJ OJ CO CNJ OJ

-4

CO

LTN

C\J

CO

LTN co

VO Omr|COromONOONlACMlAHONA(n(\lt-t-CM(MHOHCCMCMCMOJOJCMOJOOCM<MCMOJCOCMCMCMCMOJCMCM<M<MCOOJCM

UA -4 VO ON -4 VO C— ON 00 CM CM UA CO UA VO On

4 -4 CM ON 00 C— -4 CM IA rH CMCM<MCO<MCMCMOOOOCO<MCMOOCOCMOJCMOOCMCMCM<MOOCMOO

-4 VOCOOt—OVOOCMOHOCVIOVOOLTNOVOONVO OOOOOOOHOHOHOOOOOOOnO H H i—l I—I

(—I fH I—I rH i—I i—I r I r H I—I i—I r—I(—| I—I I—I 1—

I

r| IA O UA-4

o o o o o

rH rH rH rH rH

00 IACO J On CM oo UA VO -4 VO .4

co On co Onco ON vo OnVD On VO LAWH^tHOOlAf-POCOCMCOCMCM

On CM On CM ON CM On On On On On

CM rHOCMHOCMt— OnVO HCO

UA t*— LTN f-— L/A C~— 4" t— 4 CO 4 l—I i—I i—I l—I

<—I <—I i—I H rl H H

ONl/AOOOOUArHCOCMOONCOONt— C—4 C-4 t— 4 t— 4 t*— UA VO 4- VO VO —I i—I i—I i—I f—I i—I

*—I rH i—I i—I i—I i I i—I i I

O IA r!4 H UA VO CO-4- UA UA VO CO VO OO LTN CO UA t— CO VO CO t— On

CM VO CM VO CM UA CO UA CO UA 00 t— rH t— rH t— rH C— ON t— ON t— ON UA

rl i—I rl rl H H i—I H rl rl rl rl l—I r| H l—I rl i—I rH rH i—

I

CM CO -4 UA VO t~— CO ON O rl CM CO -4 UAVOD— COO\OrHCMC0 4UA HHrlHHrlHHHHCMCMOJCMCMW

O CO

CO CO

• •

CM CO 4 VO

VO CO

co CO

CM

vo o

On rH COo

1—1 o On CO LTN

• • o CO t— CO

CM 4 UA O • • o CO vo rH

i—

i

vo

On

CM -4

r—

1

CM -4

t—

CM

w >

W

pi

a

w Q

> EH < m

- 31-
Timings

for

LABCOR

(Milliseconds

per

Path)

vo

C\J CM AO rH AO UN (O t— t— 4-OOHOOC~C\jnOt~H4-VO-} o o\ uv ro unununununununununununvo lanvo vo vo unvo un un un vo un un lan

un

CM iaonooj- o\otA(\)voomoo\0\o^-j^flOoioco

VO vo VO t— t— lf\ VD LTV VD VD IAVOVOVD LAN IA IAVD LAN IAN UN VO VO VO VO

-4

CM CMCMAOCMONUNVOtH-CMcOCMCMrHAOVO C— HVD OO C\l O 1A ON OUA

IfN UN IAN LT\ LAN LTV UA UN VO 1A IAVD lanunununlanunlanunununununun

ao

CVJ AO 0\ CO CO O AO -4 -4 IAJ-J ON i—

1

ON QO 1A PO (M vo vo vo vo t— t— co co vo vo vo lan t— vo t— t— t— t-—On O

c— vo IAP- 4-NO Ont- vo OO VO VO

CVJ CM H H HVO lAlANOVDIACVJIArOOONVD f-t— tr— AOCVJ CM -4 t— -4 ON VOVOVOVOVOVOVOVOVOVO IAN VO VO VO VO VO VO VO VO VO VO VO VO vo vo

rH

CVJ CM -4 O IAN AO vo 0 -4-4 O P-IAOCOCD ON A- -4 C— O VO CO H CM OO UNUNUNUNUNUNUNLANVOVO LAN UN LAN LAN LAN UN UN LAN LAN VO LAN LAN LAN VO LAN

O t-WOOOCOOCOJCOrlOOOOONCOHHHH H IAIAVO 1A 1A

CM co oO oo CO OnO OnOnOnO O OCOOOCOOOCOOOCOOOOOCOOOCOCO

i—I H H H

ON

i—

I

-4 t—O On VO CNONJCO J CVJ LANAOVO O O CO rH AOAOO A— CO OOOVO t— t— t—- tr— VO -4 VO CO t— VO CO co CO A- vo vo A- vo

OO LA t— On AO O VO CM CM A— CM LAN CO C— t— CO t— On O rH -3" VO ON A— LAN On VO CO LAN LAN LAN VO OO LAN t— OO VO CO -4 LAN -4 A— VO LAN UN C'O LAN -4 -4 004

ArH A— rH CO t— H -4 -4 LAN VO -4 AO -4 CM A— AO rl 4 4 O AO -4 ON CM AO rH -4 -4 -4 -4 -4 -4 CM -4 AO LAN -4 -4 LAN -4 AO LAN -4 -4 -4 AO -4 AO-4-4 LAN

VO

rH VO

AO.

LAN rH VO

AO -4 AO. A— rH t— CM CO CM LAN VO VO LAN VO VO ao H t— CM ON rH rH AO -4 AO -4 AO -4 AO -4 AO -4 AO -4 AO -4 AO -4 AO -4-4

UN LTn I—| -4 I—I LAN CM O CM rH AO H i—I O CM O rH On rl A— On O O LAN A— VO

VO CM VO CM VO CM VO AO VO AO VO AO A— rH A— H VO CM A— ON A— O A— ON VO

i—I r—I r—Ii—I r—I t—t i—1 i—I i J i—I i—I t—I rl i—I r—I i—I H i—I i—I rl H rl rH

-4 i—I LAN -4 ON AO CO O OO CM rH O i—I VO OO LAN ON LAN CO -4 —I CM -4 VO -4 O

rH LAN O LAN O LAN O LAN O LAN O LAN O LAN CO LAN CO LAN OO LAN OO VO ON A— ON CO

(—I i—I t—I r—I t—I r—I r—I i—I r—I r—I —I i—( r—I rH I—I rH rH I—I I I

rH CM AO -4 LAN VO A— CO ON O rH CM AO -4 LAN VO

r I rH r I rH i—I r—I i—

I

A— cO On O rH CM AO -4 UN HHrHCMCMCMCMCMCM

CM

rH t— VD

LTN AO

CO rH oo t—

• •

I—1 vo VD

CM AO

AO AO

• • l/\ AO

IT\

VC rH

LAN CM

• • o t—

A—

CM oo

rH rH

• • -4

VO

AO

CM CM On c—

— • UN CO UN

-4

CM rH

• • On a— CO

a—

CM CM

• • o

a—

ON

AO CO ON

• • t—

LTV rH

co AO o VO

AO VO

-4O O

vo AO On AO

AO

CM AO ON -4

• • CM A—

-4

rH

CM

VO t—

UN

• • co CM CM AO

rH

w

CD2

O

co - 32-
TABLE

3

(Continued)

Timings

for

LABSET

(Milliseconds

per

Path)

CO

OJ

r—

I

rH

Ono

COo

tr- o

voO

ir\ O

4-O

coo

OJo

I

I o

on 4- 4- oj owo Onco ckhoo co rH o 4 vo 4 ltn 4 h ltn co cm 4 ltn OnCO CM VO 4 rH IA IA On O VO CO ON C— H rH LfN CO VO CO 0O CO CO rHOJ

1 I*—I* l<—I i

If—I i—I rH i—If—I t—It—

I

VO 0\ ON (\J ON-} C— UNH t-O O W 1ACO J o H (VI4 tfN O IfN VO LTN VO CO ON J UN OJ VO 00 03 J OflOVO UN ITN ON t— 4 OO COCO LfN VO >HH H H i li If It I rH H rl H Hr-1 HHHH

hOO\WHVOlAt-COOHHC0 04CO 4VDCOc04HC004(0(MHm-OU- H f—I i—I i—i i—I i—| t—I r I O t^-4 LfN C~— CO t— 4 O CO CO H LTN O ONCO Hi—I H H H

ONH h- 4 VO CO co On H OJ C— On H O co co OJ UN HCO On On On C*

OJ OJ i I OJ t If I OJ HH HOJOJHOJHHHH HHOJ

C\IOCO(Mt-ONCOO\HC04VOC\JH(MOOCOVOlAVOcOOH(Yl CO OJ H OJ H H OJHHH CMCMCMCMCOHHHH OJOJOJ

t— t— OJ C— OJ H H CM H t/N H H t— VO CO H O CO t— LfN On -4 H CM CO OJHHH CO CM CM H H H CM CM

i—I LfN H H CM H

CO CO -4 ON On O CM LfN CM t— On VO 00 LfN LfN t— O CO CO O CO O O VO O CM H H OJ CO OJHHH CO H CM CM H H H CM H CM H

4 O CO

OJ CM CM — O LTN VO t— On C~— CO O VO OJ H ON LTN On VO O CM CO t

H CO CM HH CO H CM CM H H HCMHHH

ON oo CO CO -4 HCOVQ O VO UN UN CO H oo 0J O O O 0\C044 H 4 HH H CM CM OJ HH 00 H CM CM (\l H CM CM H rl H

HC04 V04 LTNVOVO CM UN O CO VO H4 CO ONCOOOLfNLfNt—OCO ON UOVO t— CO C— O VO 4 c- ON 14- O H VO LfN CO t— t— t— O CO t— CO c— o

H H i—\ i—

i

ONUNOCVJt— (M(MHUNUNOOnCOH 4044COVOCO(OOVOCO

CM LfN f— CO VO ON C~— ON IfN VO CO IfN CO 4 coco CM 1AH C- H4 CM CO CO

UN H CO H VO VO CM On co t— CM H4VO ON 4 tN- H 00 CO t— LfN CO OcO HCMOH4lACOUNOH(MCOCOiAOHHC04lAH(MOHVO

rH l—I i—I l—I i—I i—1 i—j i—| i—I i—I f—I l—I i—I i—I r—| i—I r I rH I—I —1 —1 —1 —' —1

i—I i—I i—I i—I i—

I

O co H UNCO CO CO CO H CM ON UN On CM H CO UN O C— cO VO t- On UN H LfN C— co LfN iHHH —| H On H -4 4 CO On t— O CM ltn Lf\ On -4 O O VO LfN CO LfN HH i—I i—I i—I i—

I

-4 VO

VO CO

CM CO O CO H

-4 -4

CM On O 1—

1

CO 4 i—

1

o 4 -4 4

ON CO ON CO O VO

-4 4

t— vo H

4 OO

CM LfN oo VO H

O ON

CM VO

• • VO c— H

OO LfN ON CM

• • VO OO

1—1

-4 ON

-4 LfN VO L— H

CO LfN VO 4

LfN t— H

CM CO

t— 4

H CO t— CM

co CO

CM LfN CO 4 LfN CM 4 t— VO On

• • co CO

CM rH

i—

1

4

O O

CO i—1 CO cn

CM CO -4 IfN VO t— CO On O H CM CO -4 lfN VO t— CO ON O H CM CO -4 UN HHHHHHHHHHCMCMCMCMCMCM

>M

Q

QEhCO - 33-
TABLE

3

(Continued)

Xi

-p

cd PhU

<DPU)C

o

o

(L) cn •H

VO

OJ

UA

OJ

dt

CM

oo

CM

CM

CM

r—

i

CM

O

CM

CK

OO

t—H

VO

dt

i—

I

CO H H H t— dt On

-d CM dt UA 00 OO-d

C— OO O CM CO rH C— VO OO

CM dt 00 CM OO LTN CM CM CM . tr— C— CM On I/O C— 0—

CM CM UN dt -d OO OO

CTN CO H t^VD lAd O UA UAVQ IA CM VO 00 O UA .d OO CO CO tr— CM rH O

lACMlAVOd-OdVOHd-lAOOCM-dd-OOOOCMd-OJOJd- UA UAdt dt

O H COCO® ONONt— OONf-CMVO On tr— l— dt 00 00 C— OnVO H -d- CM IA CMdd CO COd (OOOCMCMddCMCMCMdTOCMd-dlAOOd

i—

!

OO . O O oo oo VO t— O -d H VO CO C— VO ua CM H CM On On C— On On lAlAOJOOHddOOCMOOd-CMCMOOOOdOJOOOOd-OOd

CO O t— CM VO O CO

OO CM -d ua OO-d dt

UA CM O r—I On ua VO 0— 00 CM t— ON On VO O O VO

00 -d OO CM 00 00 CM CM CM -d CM CM dt 00 UA dt 00

OOOd 00 CO -d VO dt OO UA CM IAOVO CM ON O CM H OJ VO d d ONdt UNOOdVOd OOd lAd d H OOVOd OOd CO ia CM UA UNd O0 CM

H UNt-co t-H<Dd OUACOCVIVOCMIAUNOnCM (Ad rH CM H

-d OO OO CM UA CM CM H 00 OO H UA H H CM rH OO rH rH VO t— OO r—

i

o- rH OO dt

O CM OOd CM On ua t— (A -d On H OO VO O O rH ON OO VO O VO H -d O d OO CM >H OO d UA UA CM d CM CM rH UN OO I—I UN OO CM OO UA VO CM CO

O rH On on t^oo VO CO d OO CO O UN ONCO O-d ON O OO dt 0- O O O

VO 00 d d d OO i—I VO UA OO CM OO CM CO UA CM d UN CM UN UNd CM UN

rH tr— CO t— UA OO t— VO H O dt ON OO VO OOd}- CM CM UN On VO rH OO CO ON OOCMOOCMOOOOHOOOOrH OOCMCMCMOOCMOOH H CM CO OO

rH O CO O UA O VO CM On VO O Hd l— VO VO d tr— On H OO t— OO O rH OO CM CM d OO d 00 d CMOOrHCMOOrHOOOOCMOOOO d H CO CM CM d

On O HO rH CO On rH On On CO OnOnH O rHCM OnOnH t-O OWOVO

ON t— 0— UN CM rH ON CM OO OO CO CO VO O CM UA UA CO UAH O C— UA CO t—

r—i i—J i—I i—i i—t i—i H H H H

IAVO UNOnC-IAOnONCO UAVOdUNCOOOONOOHVOrlOIOVO

CO UAUAC— d On VO O HCO OO LTN OO C— On O On VO -d On t— On H t— UA H HHHH H <—I i I H

O

VO

UA

OO

-d

CM

VO

OO

VO

00

UA

OO

dtVOo

dt

dt

o

CM00

VOH

-d

00

CO

CO

ON

OO

VO

UA

UA

CM

dtVOO

OO

VO

dt

On

CO

CMUA

ON

t— VO

OO

LTN OO

UA

ITN H

t—

{

CO

ON

-d

coo

H

dt

UA

OO

UA VO

UA

(—

i

dtH

LTA ON

ON

l—

OO

ON

CM

CMOOdUAVOtr— OOONOHCMOOdUAVOId-COONOHCMOOdUA

i—I i—I i—I i—I r H i—I i—| i—I H i—I CM CM CM CM CM CM -3be

CO
TABLE

3

(Continued)

Timings

for

TIMEXD

(Milliseconds

per

Path)

po

c\j

Ono

coo

voo

ir\ o

-4O

POo

CVJ O

ONOOCO IAIAVD t-NOf-HHt-t-0\O t-J H W 0\C0 O-tCO -3- cr\ vo _=r co t—coco lo

4 -4 -4 -4 -4 -4 c— po lo h t- cm -4 .4 vo vo

i—

I

COJ-t-ON03C\|lAIAOCOOO CM C— rl IA4 rl CM N-4 UV LPv ON LPv PO CM p- LOCO IA OMA lA-a- PO PO ON LPv OO -4 OO IAPOJ ON LTV ON

C^- -3" C— CM -4 -4 C— PO PO CM CO -4 CM CM -3" t— O CM tv- CM -4 LPv PO 4 t~- CM CA CM J CO LPv LPv-4 t— VD^t4 PO PO l/\ 4 CO LTN f- 4 VO CO U"N 4 CO

On CO i—1 -3" O PI H C\ J UN VO rH PO O PO O On LPv VO P- rH CM 4 CM 4 ^CMCM0nCMCMHJ-HHHHCMPOWCM4HrlHWHCJCM4

PO CM H J H lA C\1 C\J- lAVOCMJ-J-t^OVOlACOOCMJ-VOcOt- 4 CM CM CM CM CM rH 4 rHiHHHCMCMCMCMlAHHCMCMi—ICMCMCM

CDOCMAHrOVOlACM^VO-4-cOoOCMOONCOVDPacOPOJ' ltn PO rn J- HvopOPOrH-3-CMcoPO vo44P0P0HPO4LrNCM4CM

HcOCMOCMPOOO\aDOCMHCM4lAhOOH(nCMlAHr|CO IPN 4 iH CM IPv 4 IPN rH 4 CO 4 4 H CO PO 4 LPv 4 CM CM 4 VO PO LPv CM

ICNCM ON iH CM O LPv VO PO CO CO CO ON CO PO CM H PO H CM CO 4 Lf\ LTN ttCN -4 CMLPv4POrH4rHCOCM VO PO LTN LCN -4 CM CM PO -4 CM PO CM

UNO ONUNHCOV04 H PO O PO ON On -4 CO t— C— CO t— CM VO -4 -4 PO

PO -4 iHPOPOCMHPOHPOCM VOPOIAPOPOHiHCCNIACMCMCM

OO PO ONtA OCO IAONVO H HND4 POOOCMVOHlACMCOCMCPPO

PO PO -4 CM LTN -4’ -4 CM 4 4 4 4 CM 00-4-4 LPvPOLPvlPvPOPOLPv4 LTN

-4 i—I -4 P— LTN i—I ON t— PO OO t— C— On ltn CO On CO lA O t— rH H t- CM aO

CM PO VO CM VO P— O rHLPvPOPOPOP-POcO -4 PO PO VO p— VO VO VO CO P—

rH rH

CO LTN 4 Hco rHOO rHCO 1A ON CM CO POCM POO P— p- CO ONt— -4 CM PO

LTN LTN LTN LTN f— CO p- CO VO VO VO t— t— CO VO VO P— t— CO CO LPv LTN LPv LPv VO

VO-4 LCN4 4 4 rHVOVOOO P-4 rH p- CM 4 rH PO VO H VO CO 4 4 ON PO-4-4 PO VO VO -4 VO CM CM PO-4-4-4VO OO PO -4 CO VO LTN -4 PO LP\ VO

o P- vo LT\

• • OO ON

LPN

O PO

CM vo

1 1 CM VO CM

VO VO

p- VO

• •

1—

1

c—

LTN rH

CO rH CM ON

1

( CM rH O rH CM CM

• • rH CM rH O PO

^=t l—

1

LPv PO rH o vo

-=t t—

ON vo

CO 1—

1

o o

vo o

-3- LPv PO rH

CM o

LTN p- O lr\ PO rH

rH CO ON

rH CO

CM o

PO OO ON

LTN CM

CM O

rH vo

CO 1 1 vo rH o pOO ON p- -=T -4 rH

PdO

i—1 CM PO —4 LTN VO P— OO ON O rH CM PO -4 tA VO t— CO On O rH CM PO -4 tA H i—IrHrHi—I rl H H i—ICMCMCMCMCMCM

W

Q

d&H

CO -35-
Timings

for

TIMEXD

(Milliseconds

per

Path)

VO

OJ OCOVOVO-4COONrHCOCM.irNf-OOOCOCMCOVOONCOCMVOVOt—

vo cm -4 co oo on j- h cj lcn 00 cm -4 c— oo cm cm oo cm cm c— vo lo _4 -4

OV0O^WO4CMO4hO4O\H0nhHH0nO4H(nt“ VO CM VO 0-4- CO 1AH4VD4- CC4 4 OOCM CM -4 COCOVO t'-VO 10-4

cm o\co vo iA4 odmcMvococooNHt-t- co on h on o\vo cm ia

t— CM LTV CO -4 -4 VO r—1 CO LfO CO CM -4" VO CO CM CM -4" CO 00 t— LTN t— -4" LCN

Ov f—I VO CO i—t H COVO Ov CO CO LTV CO VO On CO CM VO t— CO LTV On CM t— H

t"— -4" t— t— C- 00-4 rH UV LCN-4 CO -4- VO CO CM -4“ CO LfN CO -4" l/VVO LOCO

-4 -4 CO CM -4 CO t— CM rH t--0 On CO CM COLfNCO C— CM -4 f- 00 O -4 VO

-4“ CM LTN CO -4 -4 lAr|4 LTN44 CM -4 -4 OOCM CM -4 CO CO CO -4" f- 10-4

O co CO C— O ONVOOOCO ITN t/NVO COVO ON O CM On Lf\ O CM oo t— t— CO

-4" CM CO t— -4 CM CO CO CO CO H CM VO CO CO CO CM -4 CM LCN -4 CO CO CM

HcoiApot-OHmj coiAcnj hvocmcohcohvoooc— t— on COCMCMCMcnCMCMHCMCMHOOHHHHWHH LO VO CM H CM CM

-4 VO CO O VO COCOONO ONrHC— C— CM ITNt— CO r—I CM CM CO rH O VO ON

-4 00 CM CM CO -4 Lf\ _4 CO CO CO CM i—I VO CO rH CO CO CM CO -4 rH LTv CM CM

rH CM CM O OO CO C— CMt— ONOtfV-4COCMrHt~- OO C— 4 ON CM UN04 VOOOUNlAJ-OOtHCMACOCMCMCJ C04 H44CMVOIA(OCMIA

O CM 00 CO LTN CM CO r—I LTV LfN CM CO U"N -4 CO C"— t— O VO rH ON -4 ON Lf\ CM ICN-4 LP\ CO LTn VO CM VO -4 H HVO CO -4 CO-4 CM LTN CM CM CM OO LTN VO H

f- HOt— C— t— VO ON t— VOOnCMOnOOONOOI'- H rH ON ON OO rH -4 CMWOOCMCOCMh-CMCMCMHCMCMCM -4 CM CM CM U"N OO rH CM -4 CM -4

O CO On CO On CM VO O VO VO VO CM H VO CO CM LTN rH CM O CO -4 O rH IA

t— LTN _4 -4 t— t— l/\ CO COCO-4 LTN O LTV VO -4 CO LTN On C— VO LTN-4VO LTV rH rH

V0t-lAC0CMt-HH0\CM0NC04t“t^C0Oy4 0N4 44OV0lA

10-4-4 IA O LC\ -4 VO ION l/\ VO -4 OO -4 l/N VO ICN-4 t— VO ITnVO C— LT\ CM

-4 On o CM CM OO

-4 <

1

CM CO CO

• • LfN ON

rH

CMON CO VO CO -4 rH

CM CM t— VO

• • oLTv rH o CM o• • LTN t- -4 r—

1

-4 CO

CM -4

• • vo

CO 1

1

-4 •H O t-

• • -4 CM

CM rH

VO

rH

• • CM CO rH

CO -4 VO o

ON ON

CO rH

-4 VO

CM CO

• • O vo

-4 rH

vo t—

ON -4

o CM co rH

-4 CO O On

CM LfN VO CM

-4 VO o o

CM ON VO rH

rHCMOO-4lT\VOtr-OOONOrlCMCO-4irNVOt— COONOHCMCO-41A

i—

I

i—| i—I i—I i—I i—I i—I i—I i—i i—| CM CM CM CM CM CM

w

o £

Q

- 36-
may differ by as much as 20 percent depending on the time of day and

machine load at the time. By timing all three algorithms on the same network in immediate sequence, we sought to make cross-comparisons on the same problem appropriate and valid. Most runs were made in low

activity periods to minimize the influence of other programs being run

on the computer at the same time. (it is generally true that the timing

of the same program will be greater during periods in which the computer

has a heavy load. ) Thus care should be exercised in imputing precision

to the timings reported here and in extrapolating from them. However,

the testing procedure was designed to facilitate comparisons of performance among algorithms.

Table U contains a summary of the average and standard deviation of

the 25 timings for each of the 26 test runs along with the size parameters describing each test network. TIMEXD is the fastest on the average,

but in more than half of the runs LABSET was as fast or faster. In

general LABSET is faster than TIMEXD on networks with fewer nodes.

Since the networks used in these tests are all fairly small, compared to

most real transit systems, one would generally expect TIMEXD to calculate itineraries more quickly for real transit systems. In all but

four small networks, LABCOR took more time than did either of the

other two algorithms. It is always slower than LABSET, but beats TIMEXD

on very small networks. However, we note again that LABCOR always produces paths which are at least as desirable and often more desirable,

because they have fewer transfers, than those produced by the other

algorithms. On the average for these test runs, these better paths

required 77 percent more time to calculate, and the time difference was greater for larger networks. For example, for the five 15 by 15 grid

networks, TIMEXD was on the average 2.5 times faster than LABCOR.

The average standard deviations for the LABCOR calculations were smaller than those of either of the other two algorithms, indicating

that for a particular network the timings of different cases using

LABCOR were closer together than those of LABSET or TIMEXD. However,

the standard deviation of the average times for the 26 networks was greatest for LABCOR, which is indicative of greater variation of the

timing from network to network. TIMEXD varies least with network. Thus

LABCOR has most consistent timing for one network but varies most among

different networks, whereas LABSET and TIMEXD show greater variability

in timing the different cases for the same network, and TIMEXD varies

least from network to network with LABSET varying more but less than

LABCOR.

Table h lists for each of the 26 test networks the number of nodes

and the number of vehicle departures (or runs) for that particular

network. These two parameters, along with the product of the two, were thought to most directly characterize the network size. Correlation

coefficients and Spearman rank correlation coefficients were calculated

to assess the degree of relationship between the timings and each of

these parameters. The correlation coefficients are displayed in Table

5. Correlation coefficients are statistics with values between —1 and

+1. A coefficient of 0 indicates no association; coefficients close to

+1 indicate a high association in which as one variate grows the second

grows also; a coefficient of nearly -1 also indicates a high degree of

association but one in which as one variate grows larger the other

becomes smaller.
TABLE H

COMPARISON OF TIMINGS OF THE THREE ALGORITHMS

NETWORK DESCRIPTION

TIMINGS (MILLISECONDS)**

LABCOR LABSET TIMEXD

NO. TYPE SIZE * NODES RUNS y a y a y 0

1 G 15 15 225 285 1H3 27 88 31 H8 15

2 G 15 15 225 288 l6l 13 129 19 68 12

3 G 12 lh 168 23H 71 3H 53 25 59 25

H G 12 Ik 168 328 10H H 72 23 H2 9

5 R 6 11 Ho 800 29 H 16 7 31 16

6 R 6 11 Ho 800 25 3 16 8 35 15

7 R 6 11 Ho 960 26 H 17 8 39 17

8 R 6 11 Ho 960 28 H 16 8 3H 15

9 R k 16 50 H80 28 2 18 7 2H 11

10 R k 16 50 H80 28 1 17 6 2H 12

11 G 10 20 200 280 12H 18 99 33 52 18

12 G 5 Ho 200 HlO 151 lH 130 H2 6l 23

13 G 15 15 225 285 162 17 103 33 59 20

lH G 15 15 225 285 128 32 95 30 62 19

15 G 15 15 225 285 1H3 27 9H 38 62 26

16 G 8 8 6H HH8 HO 3 31 10 31 13

17 G 10 8 80 252 H3 7 26 11 HO 16

18 R 8 7 80 33H 58 15 Ho 15 Ho 19

19 G 10 12 120 220 70 9 3H 16 3H 12

20 R 9 6 120 192 89 7 32 17 2k 13

21 G 9 9 81 270 56 H Hi 15 36 lH

22 G 9 9 81 270 6H 3 35 11 H5 17

23 G 9 9 81 270 71 7 37 10 51 18

2k G 9 9 81 270 55 3 36 12 H7 19

25 G 9 9 8l 270 62 7 Hi lH H6 20

26 G 9 9 81 270 56 H 36 12 H2 18

AVERAGE 77-5 10.5 52.0 17.7 H3.7 16.6

STD. DEV. OF AVG. H6.H 9.8 36.3 10.6 12.7 n.2

*For a grid network (G), 'size' i s given by the numbers of horizontal and

vertical grid elements; for a radial (R), by the numbers of radials and

beltways

.

**Statistics for 25 origin-destination pairs in each network.

- 38-
TABLE 5

CORRELATION OF TIMINGS AND NETWORK

SIZE PARAMETERS

Correlation Coefficients

LABCOR LABSET TIMEXD

NODES .9653 • 931+3 .7867

RUNS -.5122 -.1+226 -.3711

NODES x RUNS .8397 .8907 .7076

Spearman Rank Correlation Coefficients

LABCOR LABSET TIMEXD

NODES .9641 .9122 .7596

RUNS -.3982 3082 -.2300

NODES x RUNS .5^98 .5329 .1+981

- 39-
The negative correlation between timings and the number of runs

seems at first surprising, since one would expect that as the number of runs increases the number of possibilities to be checked at least re- mains the same and might (particularly for TIMEXD) grow larger. The

negative correlation arises in this data set because we were attempting

to test fairly large networks, where 'large* is measured relative to the

amount of computer storage available to us, 65,000 words. Therefore the

product of numbers of nodes and runs (vehicle departures) was relatively

fixed. Networks with many nodes had fewer runs, and networks with few

nodes had many runs. Timing is definitely positively correlated with

the number of nodes, but because of our choice of test examples, the

number of nodes was negatively correlated with the number of runs. Thus

the timings are negatively correlated with the number of runs. That

negative correlation also contributes to the lower correlation of timings

with the product of nodes and runs than with the number of nodes alone.

The correlation of timing with the number of nodes is quite high,

especially for LABCOR and LABSET as one would expect from the structure

of the algorithms in which each step involves examining a new node. The

correlation is less pronounced for TIMEXD which must examine timeexpanded nodes whose number depends on both the number of network stops

and vehicle departures. The unfortunate (for this purpose) design of

the set of computer runs to be performed obscures this relationship

because of the negative correlation between nodes and runs.

As an aid in interpolating and in further understanding the re- lationship between the number of nodes and the timings, linear regressions, with the timing as dependent variable and the number of nodes as independent variable, were performed. That is, we obtained values for

the coefficients a^ and a^ in the following equation:

where t is the timing in milliseconds and N is the number of nodes. The

coefficients, their standard deviations and the residual standard deviation of the fit are given in Table 6. This means, for example, that

one may use the equation

t LABC0R

= 2.22 + .637N

to estimate the time required to calculate an average itinerary using

the program LABCOR on the UNIVAC 1108. Two caveats must be mentioned.

Since the networks used to fit these equations varied in size only from

U0 nodes to 225 nodes, it is really not appropriate to use the equations

for much larger networks. In addition, the timings reported here were obtained on a particular computer and while we have no reason to suppose

relative performance would differ on another machine, actual time is

likely to be quite different.

- 40-
TABLE 6

LINEAR REGRESSION COEFFICIENTS FOR

THE FIT OF TIMING AS A FUNCTION

OF THE NUMBER OF NODES

a

o a

l

Std. dev.

a

0

Std. dev.

a

i

Lack of

fit F ratio %

point*

LABCOR 2.22 • 637 4.81 .036 (?. 3 LABSET -k.9h .482 6.14 .038 87.7

TIMEXD 26.82 .14 3 3.14 .023 88.6

*This statistic compares the standard deviations of repeated observation?

with the standard deviation of the fit. A value between 3t and 97% indicates an acceptable linear fit.
As an experiment to check algorithm performance on a larger network, LABCOR and LABSET were run on a 40 by 40 grid network, having

therefore 1600 nodes. Actual running times for this network are given

in Table J. We also compared the timings actually obtained with those

predicted by the linear regression equations. The estimates are 1021

milliseconds for LABCOR and 766 milliseconds for LABSET. The estimate

for LABCOR is in error by more than a factor of 2, reinforcing the

earlier warning about applying the regression equations outside the

range of the original fit. However, the estimate for LABSET is only lb

percent in error, which leads greater credence to this equation in

estimating timings for at least medium sized networks. The ratio of the

time required by LABCOR to that required by LABSET is greater for this

larger network than for all but one of the 26 test runs , indicating that

the slope of the line for LABCOR should be greater than for LABSET, as is

indeed the case in the regression equations. This means that the time for

LABCOR increases at a greater rate with the number of nodes than does

that for LABSET.

In [l]> computation time for a large network (containing perhaps

3000 nodes) was estimated at approximately one second per itinerary,

with the critical time factor being access and transfer of pages of the

network and schedule data from peripheral storage to the main memory.

Using the regression results in Table 6 we obtain estimates of 1.9

seconds for LABCOR, 1.4 seconds for LABSET, and 0.5 seconds for TIMEXD

for the computation time per trip for a large transit system. These

estimates do not contain any allowance for input/output, which was estimated in [l] to require an additional one half to one second. If some computations can be done in parallel with the input/output transfers,

then the total time could be less than the sum of the two figures, but

with the sum as an upper bound, the total time estimates for LABSET and

TIMEXD then become 2.4 and 1.5 seconds respectively. Since we know from

the timing on a medium-sized network that the regression equation

seriously underestimates the time required by LABCOR, in a network of

3000 nodes, it might be expected to be perhaps more than 5 seconds per

trip itinerary, a time which piay be unacceptably long. The times for

LABSET and TIMEXD, although slightly longer than the original estimates

in [l], are well within those required to permit demand in a large city

to be handled by the information center without irritating delays.

These timings were made on the UNIVAC 1108 computer here at NBS,

and the magnitude of computation time on other computers is likelv to be

different. However, since the UNIVAC 1108 is a relatively old computer,

one would expect that computation times on most other machines would be

less than those recorded here or at worst would be of the same order of

magnitude.

- 42-
TABLE T

ALGORITHM TIMINGS (MILLISECONDS) FOR LABCOR AND LABSET

ON 40 x 40 GRID NETWORK

PAIR ORG DST LABCOR LABSET

1 432 539 2915 338

2 432 837 2900 1692

3 432 120 2899 1785

4 432 9b6 2927 717

5 432 336 2898 1007

6 1247 1454 2537 1326

7 1247 793 2537 1063

8 1247 76l 2542 663

9 1247 1142 2570 365

10 1247 1278 2538 1446

11 1026 434 1765 1284

12 1026 698 1762 526

13 1026 1074 1767 803

l4 1026 1300 1769 586

15 1026 855 1863 674

16 255 848 1856 810

17 255 666 1857 574

18 255 272 1852 748

19 255 43 1853 1639

20 255 1011 1851 591

21 1273 960 1905 545

22 1273 1179 1890 349

23 1273 l44o 1882 878

24 1273 1026 1880 269

25 1273 1543 1885 1148

Average 2192 873

St d. dev. 462.3 443.3

- 43-
4 • 4 Additional Analyses

Characteristics of the 26 test runs used in the analyses above are described more fully in Table 8. These parameters were chosen in such a way as to allow the analysis of the dependence of timing and path

calculations on several factors, such as variability of the minimum

transfer time requirement, the network shape, various frequency patterns,

and the relative speed and frequency of express and local runs.

In assessing the effect of minimum transfer time on the computation

of itineraries we will refer to Table 9- No clear pattern of variation

of computation time with increase in transfer time holds for all the

algorithms. The behavior of LABCOR timings seems to be exactly opposite

to that of the other two. LABCOR computation time increases with an increase in the transfer time at the center node of a radial network and

decreases as the transfer time increases in a grid. This pattern of

increase and decrease is the same as the pattern of increasing and decreasing numbers of transfers, reflecting LABCOR computation time's dependence on the number of transfers. LABSET and TIMEXD times decrease

with the long transfer at the center node of the radial network and in- crease as the grid transfer times increase. The increase in time for

calculating paths in a grid network with longer transfer times may

result from the generally longer trip lengths, which require examining

more possible trips before finding a shortest one. The decrease in

computer time for producing itineraries in a radial network with more

time required to transfer at one (central) node may reflect the fact

that although trips may be somewhat longer, the total number of com- pering itineraries is still reduced because many of those utilizing the

central node are now effectively blocked.

The average number of transfers required increases when the minimum

transfer time at the central node is increased, because some one-transfer

trips traveling in one radial and out another become two-transfer trips

utilizing a beltway. When the minimum transfer time is increased at all

nodes in the grid network, it becomes less desirable to transfer since

that requires significantly greater unit time, so the average number of

transfers decreases.

A second analysis concerns the effect of grid shape on computation.

In a previous study [2] of the performance of shortest-path algorithms,

it was noted that some label-correcting algorithms performed very badly

on elongated grid networks, because they depended critically on the

length of the longest shortest path. In our grid transit network, there

was some increase in the computation time as the grid became elongated

but it is not as pronounced as with the standard shortest path com- putation, partly because the average number of transfers does not increase

as much as the length of the longest shortest path. A comparison of

computation times for networks 11 and 12, respectively a 10 x 20 grid

and a 5 x 40 grid (both with 200 nodes), shows increases of 22, 31 and

17 percent respectively for LABCOR, LABSET and TIMEXD with the more

-hh-
DESCRIPTIONS

OF

THE

NETWORKS

FOR

THE

TESTS

- 45-
£1

- 1* 6-
TABLE 9

INFLUENCE OF TRANSFER TIME

CASE TRANSFER COMPUTATION TIME* AVG. NO. OF TRANSFERS

NO. TIME LABCOR LABSET TIMEXD LABCOR LABSET TIMEXD

6 2 25 l6 35 .68 .68 .72

5 10

(at center node)

29 16 31 .88 .92 .92

7 2 26 IT 39 .68 .68 .68

8 10 X (at center node)

28 16 3b .76 .76 .88

1 2 1U3 88 bQ 1.12 1.28 1.32

15 3 1U3 95 62 1.08 1.16 l.l6

lb 5 128 9b 62 .84 1.00 .96

^Computation time is in milliseconds
elongated network. The average number of transfers is greater by 4 , 31,

and 4 percent respectively for LABCOR , LABSET and TIMEXD on the elongated

network, although the number of stops in any diagonal trip (across the

whole network) increases by 50 percent. Therefore, despite some increase

in both computation time and the average number of transfers with an elongated network, the computations in a transit network are not as sensitive to the network shape as is a standard shortest-path calculation.

The sensitivity of computation time and number of transfers to the

relative speeds of express and local service was examined, and the

results are displayed in Table 10. As express service becomes more attractive (i.e., faster relative to the local service), the number of

transfers increases since most trips try to take advantage of the ex- press service, often transferring from local to express and then back to

local. The local service effectively operates as a feeder service for

the express service when the speed differential is fairly large. Computation time also increases commensurately with the number of transfers.

When express service is provided by a fixed rail system, ratios of 3 to

1 in speed may easily hold. The system changeover from express bus to

express rail, as for example in Washington, may bring an increase in the

average number of transfers per trip and an increase in the computation

time per trip itinerary, even with no increase in the number of stops.

Several other characteristics were examined for effects on either

computation time or path output and were found to elicit no discernable

pattern of response. Among these are the difference between grid-type

and radial- type network structure, variations in the initial departure

tim s (with constant frequency), variation of the time between express

runs (again with frequency held constant), and various geographical

frequency patterns, such as north-south routes frequent while east-west

routes are less so, certain streets having frequent service while others

have less, or radial runs frequent toward the center but not as frequent outwards. Although it might be expected that any of these parameters might affect algorithm performance, none had a great effect and no discernable pattern emerged.

- 48-
TABLE 10

INFLUENCE OF RATIO OF EXPRESS

TO LOCAL SPEED

RUN SPEED RATIO

-COMPUTATION TIME* AVG. NO. OF TRANSFERS

LABCOR LABSET TIMEXD LABCOR LABSET TIMEXD

21 1.1 56 4l 36 1.0 1.28 1.28

22 2.0 61* 35 1+5 1.2 1.32 J .40

23 3.0 71 37 51 1.1* 1-52 1.84

Computation time is in milliseconds.
5. CONCLUSION AND RECOMMENDATIONS

This report has discussed, the comparative performance of three

algorithms for producing itineraries by computer for use in an automated

transit information system. The test networks used in the analysis were designed specifically to highlight performance variation as a function

of network size and type and ranges of parameter values. The results of

the analysis are summarized below in three categories: path output,

program size, and timing.

LABCOR is guaranteed to produce, among all trips arriving at the

destination at the same time, that trip having fewest number of transfers. In 9 percent of the test cases LABSET produced a trip with more transfers than did LABCOR. TIMEXD had more transfers in l4 percent of

the cases. TIMEXD also produced itineraries in which an extra transfer

occurred because of an express overtaking a local vehicle. This situation does not occur with LABCOR. Thus in all cases LABCOR produced

significantly more desirable itineraries about 10 percent of the time.

Computer storage requirements for LABCOR and LABSET are similar and

depend mainly on storing the route and schedule information, which

requires the list of stops on each route and the arrival time at each

stop for each departure. Other arrays whose sizes depend primarily on the number of stops are required. The storage required by TIMEXD depends

mainly on the number of arcs in the time-expanded network, which is

determined by the number of vehicle route segments and the number of

possible transfers. The storage for a square 15 by 15 grid with about

300 departures was estimated as 8200 locations for LABCOR, 10,170 for

LABSET and 6U,UU0 for TIMEXD. The square grid, which admittedly is a situation least favorable to TIMEXD, nonetheless illustrates the difference between the requirements of the two types of algorithm. Even

in a more favorable situation, TIMEXD is likely to require substantially more computer storage than either of the other two algorithms. In

addition, our programming of LABCOR and LABSET has not taken full advantage of

most efficient storage practices, whereas TIMEXD has much less leeway.

TIMEXD is clearly fastest for larger networks, and as shown by the

regression equation, its calculation time grows more slowly with an in- crease in network size. LABCOR, which produces better paths, averaged 77

percent longer computation times and for the larger networks included in

the analysis, the 15 by 15 grids, was 2.5 times as slow as TIMEXD. The

timing of each of the three algorithms was highly correlated with the

number of nodes, with the rate of growth being greatest for LABCOR, moderate

for LABSET and lowest for TIMEXD. Timing also depends on network characteristics, such as the number of transfers, the minimum transfer time

requirements, the relative speeds of express and local service, and network

shape.

A recommendation on the choice among the three algorithms depends

in part on the appropriate tradeoff between speed and quality of the

output itinerary. If the speed of the LABCOR algorithm is sufficient

for the particular application, its clearly-more-desirable itinerary

output makes it the algorithm of choice, but if speed is more important

- 50-
then TIMEXD becomes attractive. Our analysis did not attempt to fine-tune

the networks, for instance, to examine individually the transfer arcs included in TIMEXD networks to see if undesirable transfers could be

curtailed by removing some of these arcs as spurious candidates. Other

heuristics or data manipulations are also possible and might improve the

path output from TIMEXD without degrading its performance significantly.

TIMEXD also has the disadvantage of requiring a large amount of core

storage; both of the other algorithms require much less. LABSET produces paths which may be longer than those output by LABCOR, although

this does not happen as frequently as with TIMEXD. LABSET is faster

than LABCOR but not as fast as TIMEXD, and requires only slightly more

storage than LABCOR. Thus in situations where speed is important but

better quality path output than available from TIMEXD is desired, LABSET

may be an acceptable compromise.

- 51-
6. REFERENCES

1. Judith F. Gilsinn, Patsy B. Saunders, and Martin H. Pearl, Path

Finding Algorithms and Data Structures for Point-to-Point Trip

Management, National Bureau of Standards Report Number NBSTR 75-676,

January 1975-

2. Judith Gilsinn and Christoph Witzgall, A Performance Comparison of

Labeling Algorithms for Calculating Shortest Path Trees, National

Bureau of Standards Technical Note 772, May 1973.

3. Douglas R. Shier and Judith F. Gilsinn, Cost/Benefit Analysis of

Automated Transit Information Systems, National Bureau of Standards

Report Number NBSIR 77-1253, June 1977-

- 52-
APPENDIX A

DOCUMENTATION OF PROGRAMS FOR TEST-PROBLEM

GENERATION AND ITINERARY-FINDING

The computer programs used in performing the analyses described

in Section L are documented in this appendix. A flowchart of these

programs appears in Figure A.l, with the programs shown in rectanguiar

boxes, input files in rectangular boxes with a cut-off corner, intermediate data files in boxes with rounded sides, and output in the box

labeled "TRIP ITINERARIES" . The numbers in the upper right corners of

program boxes are keyed to the section in which the program is documented.

For instance, documentation of program RAD is in section A.l. The number

in parentheses in either an input or an intermediate file box refers to

the logical unit number used in referencing the file. Descriptions of

the contents and formats of the files appear in Section A. 10. Two programs not appearing in this chart have been included in the documentation, because they would be important parts of an actual information

system's computer-program package and because they have been discussed

both in [l] and in the text of this report. They are an arrivaloriented version of the time-expanded network algorithm, described in

Section 2.2.2, and a program to remove extraneous, non-decision nodes

from a transit network. Computer listings of all programs appear in

Appendix B.

All programs are written in FORTRAN V, UNIVAC's enhanced version of

FORTRAN IV, and were run on the UNIVAC 1108 at NBS under the EXEC 8 operating system. Generally, all programs for a single test case were exe- cuted in sequence in the same computer run with network generation followed by necessary preliminary processing, followed immediately by itinerary computation by each of the three algorithms in sequence. Thus for

radial networks, the program execution sequence is RAD, TRA, ACYCLE,

LABCOR, LABSET and TIMEXD; for grid networks the sequence is similar but

omits TRA, thus becoming XGRID, ACYCLE, LABCOR, LABSET, and TIMEXD . Input files TMIN and TRIPS, together with the input required for either the

grid or radial network generators, must be prepared in advance. All

other files are generated by the programs as they are executed.

Since these programs were coded primarily for use in the analyses

described in this report, no special effort was made to limit code to a portable subset of FORTRAN. Program characteristics which affect portability are listed below:

1. Card input is from logical unit 5, printer output is on logical

unit 6 , and units 7 through 12 are used for various data files.

2. In the path computation programs, a variable INF, representing

a very large integer, is set equal to 999999999

5

which may be

too large for machines with smaller word sizes.

- 53-
FLOWCHART

OF

THE

TRANSIT

PROGRAM

SYSTEM
3. We have used the "PARAMETER =" statement to set program dimensions. This may be replaced by explicit numerical values

wherever the PARAMETER variable occurs.

4. The UNIVAC FORTRAN V compiler ignores all remaining characters

following the character § on any line. This has been used to

add short comments to lines of code, and all characters after

and including the § on any line.

5. The IMPLICIT INTEGER (A-Z) statement makes all variables of

integer type, and may be replaced by a list of all variables

appearing in the code.

6. The "END=" clause in a REAL statement transfers control to the

statement number given when an end-of-file condition is sensed

in input.

7. The path-finding algor ithm codes all call the special system

subroutine CPUSUP which computes the CPU time in milliseconds

since the start of the run. Any equivalent clock routine can

be used.

Detailed documentation and user instructions for the programs shown

in Figure A.l, together with the two additional codes discussed above,

are included in the sections below. In each case there is a narrative

describing the program's function, a list of the variables and arrays

appearing in the code, a list of the input required and outputs produced

together with their formats, and descriptions of subroutines. Listings

of the codes appear in Appendix B.

- 55 -
A.l. PROGRAM RAD

This program generates a user-specified radial, or "spider veh"

,

network in which routes go outward from a central node along radial

segments or go between radials in circular arcs or portions of such

arcs. The user specifies the number of radials, the number of stops and

distances between stops along each radial, the stops on radials con- nected by circular segments (or "beltways"), and the stops at which

"spike" routes connect to radials. These latter are routes which proceed from the central node out along a radial but diverge from the

radial at some node along it.

By user specification, any radial, beltway or spike can also have

an express route. Each route, local or express, has a complementary

route which traverses the same set of stops in reverse order. Express

routes stop only at intersections with other express routes.

Schedules for each route are computed from input data which include

the number of runs, the headway between runs, and the departure time of

the first run for each route for each time period. Time between stops

is computed from interstop distance by using a user-supplied conversion

factor. Both local and express conversion factors are input for each

time period.

The main program RAD serves both as a network-description input

routine and as a calling routine to generate the radial transit route

system. Subroutine LOCAL is called to create the local network and

subroutine EXPRES is called to create the express routes. Subroutine

RSCHED is called from LOCAL and EXPRES to compute schedules for each

route

.

A. 1.1 Variables and Arrays Used in RAD

Time period input

I PD number of time periods used in computing

schedules. (Headways are constant during

a time period.

)

ZK(I),

1=1, IPD

factor used in converting distance to

time for local routes for each time period

XZK(I),

1=1, IPD

factor used in converting distance to time

for express routes for each time period

- 56-
Radial input

IRAD number of radials

ANGLE ( r

)

angle of radial r, measured counterclockwise from east

ISTP(r) number of stops on radial r not counting

the center node

DSTRAD ( r , j ) - distance between stops j and j + 1 on radial r

REXP(r) a flag set to 1 if radial r is an express

route

Beltway input

I BELT number of beltways

IBIN(b) initial (east-most) radial connected by

beltway b

IBFIN(b) final radial connected by beltway b

NB(b) number of radials intersected by beltway b. (Note that beltway b will intersect all radials between IBIN(b) and

IBFIN(b). If IBFIN(b) <_ IBIN(b) it will

intersect radials IBIN(b) to IRAD and 1 to IBFIN(b). When IBIN(b) = IBFIN(b) the

beltway is a full beltway encircling the

center node; otherwise it is only a "partial circle" . )

IBSTP(b,i) -

i = 1, NB(b)

stop on radial IBIN(b) + i - 1 at beltway b,

where the center is counted as stop 1 on each radial. (Note that the length of the

beltway segment, between the ith and (i + 1 )st

radials it intersects, is calculated as the

average of the circular arc length at the radius

determined by stop IBSTP(b,i) on the ith radial

and the circular arc length at the radius determined by stop IBSTP(b,i+l) on the ( i+1 ) radial.)

BEXP(b) a flag set to 1 if beltway b is an express

route

Spike input

ISPIKE number of spikes

- 57-
ISRAD(s) radial to which spike is connected

ISSTP(s) stop on radial ISRAD to which spike is

connected

DSPIKE(s) length of spike

SEXP(s) a flag set to 1 if spike s is an express

spike

Node description

KRAD(k) radial on which node k is located

KSTP(k) stop on radial KRAD(k) which is node k

NODE(r,j) node for stop j on radial r

Route description

MRTE(m,n) nth stop on route m. (Note that MRTE(l,j)

= MRTE(2,n - j + l) since routes go in

both directions and appear in pairs.)

DTEMP ( m , n ) - distance between stops n and n + 1 along

route m. (As noted for MRTE, the distances in

DTEMP(l,k) appear in the reverse order to

DTEMP ( 2 , k )

. )

Input schedule description

JRUNS number of runs of this route this time

period

JHEAD headway between runs of this route this

time period

PDTM time of first run of this route this time

period

Counters

K the number of nodes

Ml current route in one direction

M2 route in the opposite direction to Ml

traversing the same stops in reverse order

-38-
A. 1.2 Program Input

Input to program RAD includes a description of the radial network

to be generated and schedule data for each route. The input, read from

cards on logical unit 5, consists of three main sections: (1) the topological and route structure of the radials, beltways and spikes, (2) tne

schedule information for local routes and (3) the schedule information

for express routes. The actual card formats are given below in the order

in which they are to appear.

Time period input

Contents Format

1PD 15

ZK( I ) , 1 = 1, I PD 8F10.1

XZK(l),I =1, IPD 8F10.1

Radial input

IRAD 15

For each radial:

REXP 15

ANGLE, ISTP F10.1, 15

( DSTRAD( radial , J), J=l, ISTP) 8F10.1

Beltway input

I BELT 15

For each beltway:

BEXP 15

IBIN , IBFIN 215

(IBSTP (beltway, J), J=l, NB) 1615

Spike input

ISPIKE 15

For each spike:

SEXP 15

ISRAD, ISSTP, DSPIKE 215, F10.1

A description of the schedule input data follows. Within each group

of schedule data, the order must be the same as the order of the topology

input above.

- 59-
Local radial schedule input

For each radial

:

Route going outward from center, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going inward toward center, one card for each time period

JRUNS , JHEAD, JDTM 315

Local beltway schedule input

For each beltway:

Route going counterclockwise, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going clockwise, one card for each time period

JRUNS, JHEAD, JDTM 315

Local spike schedule input

For each spike:

Route going outward from center, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going inward toward center, one card for each time period

JRUNS, JHEAD, JDTM 315

Express beltway schedule input

For each express beltway:

Route going counterclockwise, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going clockwise, one card for each time period

JRUNS, JHEAD, JDTM 315

Express spike schedule input

For each express spike:

Route going outward from center, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going inward toward center, one card for each time period

JRUNS, JHEAD, JDTM 315

-60-
Express radial schedule input

For each express radial:

Route going outward from center, one card for each time period

JRUNS, JHEAD, JDTM 315

Route going inward toward center

JRUNS, JHEAD, JDTM

one card for each time period

315

A. 1.3 Program Output

Output consists of the file SDATA (on unit 7) which gives for each

route the number of stops,- the number of runs, the list of stops and the

times at each stop for each run. This information is also printed.

A.l.U Subroutine LOCAL

Subroutine LOCAL generates the nodes and local routes of a radiaJ

transit route system. The network topology description is available

through three common blocks - RADIAL, BELTWY and SPIKE. The subroutine

constructs the node description arrays KRAD, KSTP and NODE as it com- putes the local radial routes. Local beltway and spike routes are then

computed. After each route and its complement are computed, subroutine

RSCHED is called to compute the schedules.

A. 1.5 Subroutine EXPRES

This subroutine generates the express routes of a radial transit

route system. Two-way express routes are computed for radials, beltways

and spikes designated by the user to be major routes. Subroutine RSCHED

is called to compute the schedule of each route and its complement.

A. 1.6 Variables and Arrays Used in LOCAL and EXPRES

Radial description

IRAD number of radials

ANGLE(r) angle of radial r, measured counterclockwise from east

ISTP(r) number of stops on radial r not counting

the center node

DSTRAD(r,j) - distance between stops j and j + 1 on radial r

REXP(r) a flag set to 1 if radial r is an express

route

-6l-
Beltway description

I BELT number of beltways

IBIN(b) initial radial connected by beltway b

IBFIN(b) final radial connected by beltway b

DSTBLT(b,j) - distance between stops j and j + 1 on belt'

way b

NB(b) number of radials intersected by beltway b

IBSTP(b.i) - stop on radial IBIN(b) + i - 1 on beltway

b, where the center is counted as stop 1

BEXP ( b

)

Spike description

a flag set to 1 if beltway b is an express

route

ISPIKE number of spikes

ISRAD(s) radial to which spike is connected

ISSTP(s) stop on radial ISRAD to which spike is

connected

DSPIKE(s) length of spike

NDSPK(s) node number of stop at end of spike

SEXP(s) a flag set to 1 if spike s is an express

route

Node description

KRAD(k) radial on which node k is located

KSTP(k) stop on radial KRAD(k) which is node k

NODE(r,j) node for stop j on radial r

KEXP(k)

Route description

true/false express node indicator

MRTE(m,n) nth stop on route. (Note that MRTE (l,j)

= MRTE (2, n-j+l) since routes go in both

directions and appear in pairs .

)

- 62-
DTEMP (m,n) distance between stops n and n+1 along

route. (As noted for MRTE, the distances

in DTEMP (l,k) appear in the reverse order

to DTEMP (2,k).

)

Counters

K the number of nodes

Ml current route in one direction

M2 route in the opposite direction to Ml

traversing the same stops in reverse

order

Subroutine RSCHED

This subroutine computes and outputs schedule information for

routes Ml and M2. Input, which is transmitted through calling arguments and the common block GENRAL, includes the stops along routes Ml

and M2 stored in MRTE, the distance between stops in DTEMP, the number

of stops along these routes in N, and time period information stored

in IPD, ZK and XZK. After schedules for both routes are computed,

RSCHED outputs the route number, the number of stops, the number of runs,

the list of stops and the times at each stop for each run both to file

SDATA and to the printer.

A. 1.8 Variables and Arrays Used in RSCHED

N

MRTE(m, j

)

DTEMP (m, j

)

Ml

IPD

ZK(i)

XZK(i)

number of stops along either of the cur- rent pair of routes

jth stop along the route (Stops in MRTE(l,-)

appear in the reverse order to those in

MRTE ( 2

, - ) .

)

distance between stops MRTE(m,j) and

MRTE(m,j + l)

number of the first of the pair of routes

being considered

number of time periods for which schedules

are to be constructed

factor for converting distance to time for

local routes in period i

factor for converting distance to time for

express routes in period i

- 63-
JRUNS ( i

)

number of runs of the current route in

period i

JHEAD(i) headway between runs of the current route

in period i

JDTM(i) time of first run of the current route

in period i

NRUNS number of runs of the current route over

all periods

MM keeps track of which of the pair of routes

is the current route

JTIME(H) the time that the current vehicle stops

at stop MRTE(MM,0

LOE Equal to 1 if RSCHED is being called from

LOCAL. Equal to 2 if RSCHED is being called

from EXPRES

A. 2. PROGRAM XGRID

This program generates a P x Q grid transit network with routes

running in the horizontal (west-east, east-west) and the vertical (northsouth, south-north) directions. Stops are numbered consecutively from

left to right and from top to bottom. Routes are numbered consecutively

in the order: W-E, E-W, N-S and S-N. Express horizontal and vertical

routes are numbered in a similar order beginning with route number 2P + 2Q + 1. Any stop is allowed to be a transfer point between routes which

stop at that point. The minimum transfer time between any two routes is

considered to depend only on the stop at which the transfer occurs. Routes are assumed to follow regular schedules (constant headways)

during each of a number of time periods. A different conversion factor

may apply for converting distance into travel time during different periods,

and different factors apply to local and to express routes.

The program XGRID makes calls to four subroutines: GRID (which

creates the local grid network), XPRESS (which creates express routes),

XSCHED (which produces the complete schedule information) and TRANS

(which outputs the appropriate transfer information). These subroutines

are described in fuller detail below. Input to XGRID includes the

number of stops P and the number of stops Q which define, respectively,

the vertical and horizontal dimensions of the P x Q grid. In addition,

the user must specify the interstop distances between successive "rows"

and "columns" of the grid, as well as the number of time periods and

conversion factors for each period for local and for express routes.

Subroutine XPRESS requires designation of the horizontal and vertical

-6U-
elements to be used for express routes, subroutine XSCHED requires the

input of abbreviated schedule information and subroutine TRANS requires

the input of (minimum) transfer times at each stop. Output of the grid

generator consists of detailed schedule information and transfer information

A. 2.1 Variables and Arrays Used in XGRID, GRID, and XPRESS

Input parameters

P vertical dimension of grid

Q horizontal dimension of grid

L(i) distance between rows i and i - 1

w(i) distance between columns i and

i - 1

PDS number of periods

ZK(j) converts distance into time for local

routes for period j

XZK(j) converts distance into time for express

routes for period j

Route description

NN(r) number of nodes (stops) on route r

NODE(r,i) the ith node on route r

D(r,i) the ith inter stop distance along route r

RBASE convenient reference base for absolute

route numbers

Transfer node description

TNODE ( j

)

the jth transfer node

RTl(j) route from which a transfer is made at

TNODE (j

)

RT2(j) route to which a transfer is made at TNODE(j)

NTRANS number of transfers

- 65-
A. 2.2 Program Input

Input to the grid generator consists of five types:

1. Structural parameters of the local grid, read in

from cards (unit 5) hy XGRIB.

2. Structural parameters of the express routes, read in

from cards (unit 5) hy XPRESS.

3. Conversion factors for each period, read in from

cards (unit 5) hy PGRID.

4. Abbreviated schedule information, read in from cards

(unit 5) by TSCHED.

5. Minimum transfer times at each node, found on file

TMIN (unit 12) and read by TRANS.

Specific formats for data types 1, 2, 3 and 4 are given below.

Local Structural Parameters

Contents

P,Q,(L(I),I = 2,P),

(W(I),I = 2,Q)

Express Structural Parameters

NMP,NMQ

(MAINP(I), 1=1, NMP)

(MAINQ(J), J=1 ,NMQ)

Conversion Factors

PDS ,( ZK( I ) , 1=1, PDS)

( XZK ( I ), 1=1 , PDS

)

Abbreviated Schedule Information

NR ,( ROUTE (J ) , J=1,NR

)

— one card for each

group of routes, followed by —

RUNS(I), HEAD ( I ) , (DTlME(l,J)

J=l, NR) (1615

)

— one card per group

for each time period —

(applies to all routes

in the group)

@EOF

Format

(1615)

215

(1615)

(1615)

15, (15F5.2)

(5X,15F5.2)

(1615)

- 66-
A. 2.

3

Program Output

Output from the grid generator consists of two files:

1. Detailed schedule information is produced by XSCHED

and is written onto file SDATA (unit J).

2. Transfer information is produced by TRANS and is

written onto file TDATA (unit 8).

A. 2.

4

Subroutine GRID

This subroutine generates the nodes, local routes and transfer data

for a P x Q grid network, where P,Q > 1. The variables P, Q, RBASE and

the arrays LL, W are transmitted from PGRID. The subroutine defines the

variable NTRANS and constructs the arrays NN, NODE, D, TNODE, RT1 and

RT2; these quantities are then made available to other (sub) programs

through COMMON.

A. 2.

5

Variables and Arrays used in GRID

Input parameters

p vertical dimension of grid

Q horizontal dimension of grid

LL(i) distance between rows i and i - 1

W(i) distance between columns i and

i - 1

RBASE convenient reference base for absolute

route numbers

Route description

NN(r) number of nodes on route r

NODE(r,i) the ith node on route r

D(r,i) the ith interstop distance along route r

Transfer node description

TNODE (j

)

the jth transfer node

RTl(j) route from which a transfer is made at

TNODE (j

)

RT2(j) route to which a transfer is made at

TNODE (j

)

- 67-
NTRANS number of transfers

A. 2.6 Subroutine XPRESS

This subroutine generates the express routes for a PxQ grid. The

variables P, Q, RBASE and the arrays LL and W are transmitted from

XGRID. The subroutine increments the variable NTRANS and constructs the

arrays NN, NODE, D, TNODE, RT1 and RT2 for the express routes; these

quantities are then made available to other (sub) programs through

COMMON. XPRESS reads from cards (unit 5) NMP and NMQ and the arrays MAINP

and MAINQ identifying those vertical and horizontal elements used by ex- press routes. XPRESS calls subroutine XTRANS to construct transfers.

A. 2.7 Variables and Arrays used in XPRESS

Input parameters

p vertical dimension of grid

Q horizontal dimension of grid

•H i distance between rows i and

i - 1

w(i) distance between columns i

and i - 1

RBASE convenient reference base for absolute

route numbers

Route description

NN(r) number of nodes on route r

NODE(r,i) the ith node on route r

D(r,i) the ith interstop distance along route

Transfer node description

TNODE (j

)

the jth transfer node

RTl(j) route from which a transfer is made at

TNODE (j

)

RT(j) route to which a transfer is made at

TNODE (j

)

NTRANS number of transfers

- 68-
Express route input

NMP number of horizontal express routes

NMQ number of vertical express routes

MAINP(i) ith main horizontal element (express routes

travel along the main elements)

MAINQ(i) ith main vertical element

Express route descriptors

SP(i) ith main horizontal element, including

endpoints if they are not in MAINP

SQ(i) ith main vertical element, including endpoints if they are not in MAINQ

NSP number of entries in SP

NSQ number of entries in SQ

DP(i) distance between ith and i + 1st elements

in SP

DQ(i) distance between ith and i + 1st elements

in SQ

FLAG(i) an array designating which transfers are allowed between the current route r and

other routes stopping at the same node.

FLAG = 0 indicated no transfer; FLAG = 1

indicates transfer is allowed. The transfers controlled by FLAG are as follows for

each value of i

i=l: r to local West East route

i=2: local West East route to r i=3: r to local East West route

i=k: local East West route to r i=5: r to local North South route

i=6: local North South route to r i=7: r to local South North route

i=8: local South North route to r i=9: r to express East West route

i=10: r to express West East route

i=ll: r to express North South route

i=12: r to express South North route

69-
A. 2.

8

Subroutine XTRANS

This subroutine creates the express route transfers indicated in

the array FLAG. The subroutine increments the variable NTRANS and con- structs the COMMON arrays TNODE, RT1 and RT2 for express routes at nodes

at which vertical and horizontal express routes intersect. (Analogous

arrays for nodes at the ends of express routes, along the periphery of

the grid, are constructed in XPRESS. )

A. 2.

9

Variables and Arrays Used in XTRANS

Input parameters

P vertical dimension of grid

Q

FLAG ( i

)

R

horizontal dimension of grid

array designating which transfers are allowed between the current route r and other

routes stopping at the same node. FLAG = 0

indicates no transfer; FLAG = 1 indicates

transfer is allowed. The transfers con- trolled by FLAG are as follows for each

value of i

:

i=l: r to local East West route

i=2: local East West route to r i=3: r to local West East route

i=4: local West East route to r

i=5: r to local North South route

i=6: local North South route to r i=7: r to local South North route

i=8: local South North route to r i=9: r to express West East route

i=10: r to express East West route

i=ll: r to express North South route

i=12: r to express South North route

current express route for which transfers

are being calculated

I local grid horizontal element of current

node

J

LI

L2

NMP

NMQ

local grid vertical element of current node

express horizontal element of current node

express vertical element of current node

number of horizontal express routes

number of vertical express routes

- 70-
A. 2 -10 Subroutine XSCHED

This subroutine reads in (from unit 5) a group of routes together

with abbreviated schedule information and then produces detailed schedule

information for each route and period. The detailed schedule information

is written out onto file SDATA (unit 7)* The variables PDS, RBASE,

PQ and the arrays NN, NODE, D, ZK, XZK are transmitted from XGRID.

A . 2 . 11 Variables and Arrays Used in XSCHED

Input variables and arrays

PDS number of periods

RBASE convenient reference base for absolute

route numbers

PQ - the number of local routes (2*P+2*Q)

ZK(j) converts distance into time for period j

for local routes

XZK(j) converts distance into time for period j

for express routes

NN(r) number of nodes on route r

N0DE(r,i) the ith node on route r

D(r,i) the ith interstop distance along route r

Additional variables and arrays (read from unit 5

NR number of routes in a group

ROUTE (j)

RUNS(i)

the jth route of the group

number of runs for period i

HEAD(i) headway for routes in period i

DTIME(i,j) -

Working arrays

initial departure time for route j in

period i

SCHED(k) schedule time for kth node along route

-71-
A. 2. 12 Subroutine TRANS

This subroutine writes out onto file TDATA (unit 8) the transfer

information previously generated. The transfer time array TMIN is read

from unit IN = 12. The variables PQ, RBASE, NTRANS and the arrays

TNODE, RT1, RT2 are transmitted from XGRID.

A. 2. 13 Variables and Arrays Used in TRANS

Input variables and arrays

PQ - number of nodes in grid network

RBASE - convenient reference base for absolute

route numbers

NTRANS - number of transfers

TNODE(j) - the jth transfer node

RTl(j) - route from which a transfer is made at

TNODE (j

)

RT2(j) - route to which a transfer is made at

TNODE (j

)

TMIN(i) - minimum transfer time between any two

routes at node i

A. 3. PROGRAM TRA

This program produces a list of allowable transfers between routes

from the route descriptions and minimum transfer times for each node.

It is assumed that routes occur in pairs, with routes i and i + 1 having

the same stops in reverse order. Transfers are allowed between all

routes stopping at a node except that:

1. One cannot transfer from the first stop on a route,

2. One cannot transfer to_ the last stop on a route, and

3. One cannot transfer from a route to its reverse counterpart .

A. 3.1 Variables and Arrays Used in TRA

MINTRA(i) - minimum time required to transfer between

routes at node i

- 72-
STP(k)

NSTP(i)

RTE( i , j )

BE ( i , j

)

NODE

the kth stop along the current route (used

in reading the route information)

the number of routes stopping at node i

the jth route stopping at node i

1 if node i is the first node on route

RTE(i,j). 2 if node i is the last node

on route RTE ( i , j ) . 0 otherwise.

the number of nodes

M the number of stops on the current route

N the number of routes stopping at the

current node

A. 3.2 Program Input

Input to TRA consists of one card and two files:

1. Card with number of nodes (15 format).

2. Schedules from file SDATA on unit 7.

3. Minimum transfer times in file TMIN on unit 12.

A. 3.

3

Program Output

Program output is the file TDATA which gives, for each node, the

route pairs between which transfers are allowed and the minimum time required

to transfer between those routes at that node.

A. 4. PROGRAM ACYCLE

This program produces an appropriate time-expanded network from

given schedule information and transfer data. Each node of the timeexpanded network that is constructed represents a particular (stop,

time) pair. Transfers are accommodated by using transfer arcs between

nodes; such transfer arcs are labelled with the fictitious route number

9999 . Output consists of the time-expanded node and arc data. Nodes

are sorted by their time component, while arcs are sorted by their

origin node. This program makes use of the subroutine SORTP having

arguments X, N, Y, XPOS. That routine sorts the N elements of the array

X into nondecreasing order, thus forming array Y. The ith element

of array XPOS indicates what position of the original array X corresponds

to the ith ordered observation Y(i).

- 73-
A. 4.1 Variables and Arrays Used, in ACYCLE

Input variables and arrays

RT - route number

NN - number of stops on route

RUNS - number of runs

NODE(i) - the ith stop along the route

SCHED(i) - the ith schedule time along the route

TNODE - stop at which transfer occurs

RT1 - ro.ute from which transfer at TNODE

RT2 - route to which transfer at TNODE

TMIN - minimum transfer time at TNODE

Constructed arrays

N(i) - stop associated with network node i

T(i) - time associated with network node i

START(r) - first position where information may be

found for route r on node list

END ( r

)

- last position where information may be

found for route r on node list

LLEN - length of network node list

FROM( j

)

- starting node of arc in position j of

arc list

TO(J) - ending node of arc in position j of arc list

RTE(j) - route number corresponding to arc in

position j of arc list

MLEN - length of network arc list

Working arrays

TT(i) _ the ith ordered element of T

- 74-
TIND(i) the position in T of the ith element of TT

NEW(i) - the position in TT of the ith element of T

FF(i) - the ith ordered, element of FROM

FIND(i) - the position in FROM of the ith element

of FF

A. 4.2 Program Input

Input to ACYCLE consists of the following two files:

1. SDATA (unit 7) contains detailed schedule information

for each route.

2. TDATA (unit 8) contains transfer information for

each transfer point and routes connecting there.

A. 4.

3

Program Output

Output from ACYCLE consists of the following two files:

1. NDATA (unit 9) contains the node data for the

time-expanded network, sorted by time.

2. ADATA (unit 10) contains the arc data for the

time-expanded network, sorted by origin node.

A. 5- PROGRAM LABCOR

This program calculates trip itineraries using the labe] -correcting

bipartite route/stop scheme described in Section 1.1. Program input

consists of the route and schedule data, minimum transfer times, and a list of

trips to be calculated. Output is the itinerary for each trip, the calculation time in milliseconds for each trip, and the average and standard

deviation of the calculation times for all trips.

A. 5.1 Variables and Arrays used in LABCOR

Stop information

NR(s)

ROUTE ( s , j ) -

MINTRA(s)

number of routes stopping at s

jth route stopping at s

minimum time required to transfer between

routes at s

-75-
Route information

NS(r) - number of stops on route r

STOP(r,i) - ith stop on route r

SCHED(k,

i

)

1 - arrival time at the ith stop of the kth

departure

SBEG(r) - location in SCHED of the first scheduled

departure for route r

SEND(r) - location in SCHED of the last scheduled

departure for route r

Arrays used in the algorithm

L(s

)

- sequence list of stops to fan out from

F(s) - position of stop s in list L

T(s) - arrival time at stop s

TB(s) - boarding time for vehicle arriving at s at T(s)

PS(s) - stop preceding s in the path to s

PR(s) - route from PS(s) to s

Arrays used in printing the path

SPRT(j) - stop

RPRT(j) - route

TPRT ( j

)

- arrival time

TBPRT(j) - boarding time

Variables used in timing calculations

RUNTIM - CPU time (in milliseconds) used in calculating one trip

RTIME - sum of RUNTIM'

s

RTSQ — sum of squares of RUNTIM'

s
NRIJJM - number of trips calculated

ROUT - used in printing average and standard

deviations

Variables describing the trip to be calculated

ORG - trip origin stop

DST trip destination stop

TIME desired departure time

A. 5.

2

Program Input

Input to LABCOR consists of three files:

1. Schedules from file SDATA on unit 7-

2. Minimum transfer times in file TMIN on unit 12.

3. Trips to be found in file TRIPS on unit 11.

A. 5>3 Program Output

All program output is on the printer and consists, for each desired

trip, of the origin, destination and departure time, the trip itself

with route, boarding and alighting stops, and times for each segment of

the trip and computation time. At the end of the run the average computation time for all trips and its standard deviation are also printed.

A. 6. PROGRAM LABSET

This program calculates trip itineraries using the label-setting

bipartite route/stop scheme described in Section 2.2. Program input consists

of the route and schedule data, minimum transfer times, and a list of

trips to be calculated. Output is the itinerary for each trip, the calculation time in milliseconds for each trip, and the average and standard

deviation of the calculation times for all trips.

A. 6.1 Variables and Arrays used in LABSET

Stop information

NR(s) number of routes stopping at s

ROUTE ( s , j

)

jth route stopping at s

MINTRA(s) minimum time required to transfer between

routes at s

-77-
Route information

NS(r) number of stops on route r

STOP(r ,i) ith stop on route r

SCHED(k,i) arrival time at the ith

departure

stop of the kth

SBEG(r) location in SCHED of the

departure for route r first scheduled

SEND ( r

)

location in SCHED of the

departure for route r last scheduled

Arrays used in the algorithm

L(s) - sequence list of stops to fan out from

LPRED(s) predecessor node to node s in chain of

nodes representing a level in sequence list

L. If s heads the chain (i.e. HEAD(s)

is true), this pointer gives the position

of s in the chain of nodes.

LSUCC(s) - successor node to node s in chain of nodes

representing a level in list L

HEAD(s) - logical variable used to indicate whether s heads a chain in L

T(s) - arrival time at stop s

TB(s) - boarding time for vehicle arriving at s at T ( s )

PS(s) - stop preceding s in the path to s

PR(s) — route from PS(s) to s

Arrays used in printing the path

SPRT(j) - stop

HPRT(j)

TPRT ( j

)

TBPRT( j

)

route

arrival time

boarding time

- 78-
Variables used in timing calculations

RUNTIM CPU time (in milliseconds) used in cal

culating one trip

RTIME - sum of RUNTIM* s

RTSQ - sum of squares of RUNTIM*

s

NRUN - number of trips calculated

ROUT - used in printing average and standard

deviations

Variables describing the trip to be calculated

ORG - trip origin stop

DST - trip destination stop

TIME - desired departure time

A. 6. 2 Program Input

Input to LABCOR consists of three files:

1. Schedules from file SDATA on unit 7-

2. Minimum transfer times in file TMIN on unit 12.

3. Trips to be found in file TRIPS on unit 11.

A. 6. 3 Program Output

All program output is on the printer and consists, for each

desired trip, of the origin, destination and departure time, the trip

itself with route, boarding and alighting stops, and times for each

segment of the trip and computation time. At the end of the run the

average computation time for all trips and its standard deviation are also printed.

A. 7. PROGRAM TIMEXD

This program uses a time-expanded representation ( see Section

2.2) in order to calculate a "best" itinerary from a given origin to a given destination. The trip produced must not depart the origin before

some specified time and must arrive at the destination as early as possible. Program input consists of the node and arc data for the

- 79-
time-expanded network together with a list of trips for which itineraries are required. Schedule times are assumed to be given for 1

through 1600 minutes. Program output consists of an itinerary for each

trip, the calculation time (in milliseconds) for each trip as well as the average and standard deviation of calculation times for all trips

in the list.

A. 7.1 Variables and Arrays used in TIMEXD

Node and arc data

N(i) stop associated with network node i

T(i) time associated with network node i

ARC(i) last position where information may be

found for node i in arc list

TO(j) ending node of arc in position j of arc list

RTE(j) route number corresponding to arc in

position j of arc list

NN(t) node corresponding to the first occurrence

of time t or later

NODE number of network nodes

Input variables for trip

ORG desired origin stop of trip

DST desired destination stop of trip

TIME time at or after which trip is to begin

Variables and arrays used in the algorithm

DONE first node for which the destination stop

has been encountered

P(i

)

predecessor node to node i along the cur- rent path

PRTE(i) route into node i along the current path

Arrays used in printing the path

PATHN(k) stop in position k along path

PATHT(k) time in position k along path

-80-
PATHR(k) route in position k along path

Variables used in timing calculations

DIFF

RTIME

RTSQ

NRUN

ROUT

CPU time (in milliseconds) used in calculating one trip

cumulative Siam of DIFF's

cumulative sum of squares of DIFF's

- number of trips calculated

used in printing average and standard

deviation of trip calculation times

A. 7-2 Program Input

Input to TIMEXD consists of three files:

1. Node data in time-expanded form, sorted in increasing

order by time and found on file NDATA (unit 9)*

2. Arc data in time-expanded form, sorted by origin

node and found on file ADATA (unit 10).

3. Trips to be found, on file TRIPS (unit 11 ).

A. 7-3 Program Output

All program output is produced on the line printer and con- sists of the following information:

1. The origin, destination and departure time for each

trip.

2. The trip itinerary with route, boarding stop, boarding

time, alighting stop and alighting time for each

segment of the trip.

3. Computation time for the trip calculation.

1*. Mean and standard deviation of computation times for

all trips.

A. 8. PROGRAM TIMEXA

This program uses a time-expanded representation (see Section 2.2)

in order to calculate a "best" itinerary from a given origin to a given

destination. The trip produced must arrive at the destination by a

-81-
specified time and must depart from the origin as late as possible.

Program input consists of the node and arc data for the time-expanded

network together with a list of trips for which itineraries are required. Schedule times are assumed to be given for 1 through 1600

minutes. Program output consists of an itinerary for each trip, the

calculation time (in milliseconds) for each trip as well as the average

and standard deviation of calculation times for all trips in the list.

A. 8.1 Variables and Arrays used in TIMEXA

Node and arc data

N(i) stop associated with network node i

T(i) time associated with network node i

ARC(i) last position where information may be

found for node i in arc list

TO (j ) ending node of arc in position j or arc list

RTE(j) route number corresponding to arc in

position j of arc list

NN(t) node corresponding to last occurrence of

time t or earlier

NODE number of network nodes

Input variables for trip

ORG desired origin stop of trip

DST desired destination stop of trip

TIME time by which trip is to be completed

Variables and arrays used in the algorithm

S(i) successor node to node i along the current

path

SRTE(i) route out of node i along the current path

Arrays used in printing the path

PATHN(k) stop in position k along path

PATHT(k) time in position k along path

- 82-
PATHR(k) route in position k along path

Variables used in timing calculations

DIFF - CPU time (in milliseconds) used in calculating one trip

RTIME - cumulative sum of DIFF's

RTSQ - cumulative sum of squares of DIFF's

NRUN - number of trips calculated

ROUT - used in printing average and standard deviation of trip calculation times

A. 8.

2

Program Input

Input to TIMEXA consists of three files:

1. Node data in time-expanded form, sorted in increasing

order by time and found on file NDATA (unit 9)*

2. Arc data in time-expanded form, sorted by origin

node and found on file ADATA (unit 10).

3. Trips to be found, on file TRIPS (unit 11).

A. 8.

3

Program Output

All program output is produced on the line printer and consists

of the following information:

1. The origin, destination and departure time for

each trip.

2. The trip itinerary with route, boarding stop, boarding

time, alighting stop and alighting time for each segment of the trip.

3. Computation time for the trip calculation.

4. Mean and standard deviation of computation times

for all trips.

- 83-
A. 9. PROGRAM REMOVE

This program removes unnecessary nodes from a transit network,

leaving only those nodes at which transferring is possible and likely.

All nodes which are on only one route and which are not the first or last node on that route are deleted since no transferring is possible

at any of these nodes. When several routes have a segment in common,

intermediate nodes on that segment can be deleted, since any transfers

can take place at the initial or final node of the segment. Thus a node is removed whenever it lies between the same two stops on all

routes which stop at that node.

Program input consists of the stops on each route from file SDATA.

The program then sorts the nodes on the number of routes stopping at the

node and deletes all nodes serviced by only one route, as long as the

node is not the first or last stop on the route. Finally other nodes

are examined to see if they lie on the same segment on all routes. The

program prints a list of deleted nodes and the revised network.

A. 9-1 Variables and Arrays used in REMOVE

Route Input

SRTE(i) stops on each route. REND is used to

indicate which section of SRTE refers to

a particular route

REND ( i

)

position in SRTE of the last stop of route i

Stop Description

RSTOP(j,j) - jth route stopping at node i

NRTE(i

)

number of routes stopping at node i

NIN(i) is true if node i has not been removed

(i.e., node i is Da the network) and is

false if node i has been removed.

Temporary storage

TEMP( j

)

used for input and output of the nodes on a route. Also used as an intermediate array

storing the position in each route stopping

at a node of that node.

ORDER ( i

)

used in sorting; the original position

of the ith entry in sorted order

- 84-
SORTN ( i

)

TIME(j

)

INDEX (J

Counters

NRTE

NR

NEND

NDEL

used in sorting; contains the sorted array

in sorted order

used for storing schedule data

used while printing the revised network

data. INDEX(j) is the position in the old

route stop list of the jth stop in the

revised network.

number of routes

total number of stops on routes

number of nodes which begin or end a route

number of nodes deleted

NS number of stops on the current route

NT number of runs in the schedule for the

current route

A. 9.

2

Program Input

Input to program REMOVE consists of the file SDATA (on unit 7)

containing route descriptions and schedules for the network.

A. 9.

3

Program Output

Program output is a set of revised routes and schedules written

on logical unit 13 in the format for file SDATA. This file can be used

instead of SDATA in all subsequent runs (and thus be assigned to unit

7 for other runs).

In addition to creating a revised SDATA file, program REMOVE

prints out a list of the deleted nodes and also the revised routes. Two error prints may occur, most commonly because of improper dimensions.

A. 10 FILE FORMATS

A. 10.1 Format for File SDATA (unit 7)

Contents Format

route number,

number of stops,

number of runs

,

stops on route 2015

-85-
For each run on the route

:

time at each stop 2015

A. 10. 2 Format for File TDATA (unit 8)

For each node and possible transfer:

node,

from route,

to route,

minimum transfer time 415

A. 10. 3 Format for File NDATA (unit 9)

stop, 215

time

A.10.U Format for File ADATA (unit 10

)

arc origin node, arc destination node,

route number 315

A. 10. 5 Format for File TRIPS (unit 11)

For each desired trip itinerary:

trip origin,

trip destination,

desired departure time 315

@E0F

A. 10. 6 Format for File TMIN (unit 12)

minimum transfer time

at each node 1615

§I0F

- 86-
APPENDIX B

LISTINGS OF PROGRAMS FOR TEST-PROBLEM GENERATION

AND ITINERARY-FINDING

- 87-
ooioooo

B.l PROGRAM RAD

C THIS PROGRAM SERVES BOTH AS A'i INPUT »OUTtm_E Amq_AS \ DRIVER

C ROUTINE TO 'GEUER'TE A RADIAL T R A NS T T~ P 0 U T F SYSTEM.

C THE USER SPECIFIES THE rMIMRER OF PHIALS* THE DIRECTION OF E A CH

C RADIAL. THE NUMBER OF STOPS AND DISTANCES BETWEEN STOPS ALONG FACH

C RAUIAL. THE USE° ALSO MUST SPFCIFY BELTWAYS WHICH CONNECT STOPS ON

C DIFFERENT RAO I ALS AND S

n lKfS WHICH COMMFCT A STOP om a RADIAL WITH a C POINT NOT ON AMY RADIAL.

CC

NATIONAL BUREAU OF STANDARDS APRIL* 1976

REVISED DECEMBER 1976 BY E. LFYFMPECKER

CC

CC

C

CC

CC

C

cC

c

c

c

cc

1

1

1

1

parameter

PAR A\ ETER

parameter

parameter

parameter

PARAMETER

LOGICAL

INTEGER

MR a D T I - 70

MSTPS =50

MAX Nl'MBFR of raotals

illvlREP

mnodes=mstps*mradii

OF

Q

STOPS PER

NUMRER OF

MSTOPS=50

MRELT =10 Q

MSPlK E=20 « KFXP

REXP»nrxPrSEXP

NUM BER OF STOPS PPR

max number of "beltways

MAX fjUMRFR OF SPIKES

P A_D I A L

NODES ON RAniALS

ROUTE

COMMOM/NODES/'<PAD(MNODES) »KSTP(MNODES) »KEVP(MNOnES> » NODE (MR ADI I * MSTPS)

C0MM0N/GENRAL/MRTE(2*MST0PS) *pTEMP(?*MSTOPS) t ZK (?0) *XZK(?0) * I PD

COMMON/RADIAL /ANGLE (MR AD 1 1 ) * TSTp(MRADII) * PSTRAP ( MP ADI I » MSTPS )

REXP ( MR AD I I ) » IPAD

COMMOM/BEL Tw Y / I B IN ( MBELT ) , T RF I N (J-1PEL T ) * IBSTP ( MBEL T » MP A PI I ) * MB ( MRELT ) * REXP ( moelt ) * DSTBLT ( MRELT t MR ADI I ) * I BELT

COMBO! I/SP IKE/TSR AD ( MSP I KE ) * I SSTp (

M

SPIKF)

>

n SPIK r

(

MSP IKE)

SEXP (MSPIKF ) * NDSPKTmsP IK E ) * I SP I KE

VARIABLES AND ARRAYS USED IN THIS PROGRAM

RADIAL INPUT

IRAQ - NIIMRFR OF RADIALS

ANGLE ( I ) - ANGLE OF RADIAL I* MEASURED COUNTERCLOCKWISE FROM FaST

ISTP(I) - NUMBER OF STOPS ON RAQTAL I* NOT COUNTING THE CENTER

DSTR AD ( I * U ) - DISTANCE BETWEEN STOPS J AMD J+1 ON RADIAL I REXP ( I ) - A FLAG SET TO 1 IF PADIAL T IS AN EYPR FS S ROUT E

bELTWAY INPUT

- " IBFLT - NUMBER OF BELTWAYS

IBIN(I) - INITIAL RADIAL CONNECTED BY BELTWAY I

I P F I n ( I ) - FINAL R AD T AL CONNECTED BY BELTWAY T IBSTP ( I » J) - STOP ON OADTAL J ON BELTWAY I REXP(I) - A =1 AG SET TO 1 IF BELTWAY T IS AN ryPRFSS ROUTE

-88-
ooo

ono

o

n

o

oooooonoooooooooooo

SPIKE INPUT

" “ - ~ - ISPIKE - NUMBER OF SPIKES

ISRAD ( I ) - RADIAL TO WHICH SPIKE I IS CONNECTED

ISSTP(I) - STOP ON RADIAL TO WHICH SPTKE I IS CONNECTED

DSPIKE ( I ) - LENGTH OF SPIKE I SEXP(I) “_A_FLAG SET TO 1 IF SPIKE IS AN EXPRrSS ROUTE

NODE' DESCRIPTION'''

KRAD(K) - RADIAL NODE K IS ON

KSTP(K) - STOP ON RADIAL KRAOU) WHICH IS NOD^ K

NODE ( I » J ) - THE NODE FOR STOP J ON PADIAl I ROUTE DESCRIPTION “ ’ ‘ MRTE ( M » N ) - NTH STOP ON pOUTe M. MRTE (

1

1 J ) =MBTE ( 2 » N-J+ 1 ) SINCE

ROUTES GO IN BOTh DIRECTIONS"

DTEMP.(NrM) - DISTANCE BETWEEN STOPS N AND N+l ALONG ROUTE

INITIALIZE

K = 1 13 NODE COUNTER

Ml=-1 Q ROUTE COUNTER' IN ONE DIRECTION

M2=0 0 ROUTE COUNTER IN OTHER DIRFCTION

P-3. 1415926 5/ l BO • I3DEGR£e5 TO RAT5TANS

DO 5 I = 1 » MNOOES

KEXP( I )=. FALSE'.

5 CONTINUE

READ IN NUMBER OF TIME PERIODS AND CONVERSTION FACTORS

REAL) ( 5 r 900 ) IPO

READ (5> 902) ( ZK (IT » I=l» IPD

)

READ ( 5 » 902 ) ( XZK ( I ) » 1=1 » IPD)

READ IN RADIAL DESCRIPTION

READ (5*900) IRAD

DO 10 1=1 » IRAD

READ ( S » 900 ) RFXP(I)

READ (5*901) ANGLE ( I ) » ISTP ( I

)

ANGLE ( I ) =ANGLE ( I ) *P

JSTP=ISTP( I

)

READ (5r 902) (DSTPAD( I# J) » J=lr JSTP)

10 CONTINUE

READ BELTWAY DESCRIPTION

READ ( 5 f 90 0" T~ IR ELT

DO 20 I=1»IBELT

READ ( S » 900 r~PEXP ( I

)

READ ( 5 » 900 ) IRIN( I ) » IRFIN( I

)

-89-
OOO

OOOjOOO

ooo

NI3( I ) = IBFIN( I )-IRIN( I )+]

IF ( IBIM ( I ) • GE. IRFIN ( I ) ) NP ( I )=lBFIN( I )+IRAD-lBTN( T )+l

N=NB(T)

READ ( S » 900 ) ( IB5TP ( I » J) » J=l # M)

20 CONTINUE

READ SPIKE DESCRIPTION

READ ( Sr 900 ) TsRTKE

IF ( ISPIKE.EQ.0JG0 TO 40

DO 30 1 = 1 » ISPlKE

" READ ( S » 900 ) SEXP(I)

READ (5f 903) T SR AD (I) r ISSTP (

I

T » DSPTKE ( T

)

30 CONTINUE

CA LL SUBROUTINE LOCAL TO GENERATE LOCAL ROUTES

40 C ALL LOC AL ( K ,M 1 t M2 )_

CALL SUBROUTINE EXPRES TO GENERATE EXPRESS ROUTES

CALL EXPRES (K, Ml* M2 )_ ENDFILE UN I T_ 7 - SCHEDULE INFORMATION FILE

ENDFILE 7 __ STOP

900 FORMAT ( If 15

)

901 FORMAT (F10 • 1 » 15)

902 FORMAT (8F10. 1

) _ _ __ 903 'FORMATV2r5vno.IT"

END
ooooor>oo,

ooooor>oor>oo

ooooooooioooooo

B.1.1 Subroutine LOCAL

SUBROUTINE LOC Al.(K *M1 ,M?)

THIS SUBROUTINE GENERATES the local routes OF 'a RAOTAI transit route

system, two-way routes are constructfd connecting thf center with the

END OF each RADIa L

THE CENTER WlTM jHE ENnPOTuT OR EaCh SPIKF, Arm

THE endpoints OF EACH RELTWAY. program OUTPUT INCLUDES the schedule

FOR EACH ROUTE* THE STOPS ON FACH ROUTE AMD THF ROUTES STOPPING AT

EACH STOP.

NATIONAL BUREAU OE STANDARDS APRIL* 1976

REVISED DECEMBER 197ft BY F. L.EYFNOECKER

PARAMETER MRlDTI=20 « MAX MUMBFR OF RADI ALS

PARAMETER MSTPS =50 Q NUMBER OF STOPS _PFR R AD I Al PARAMETER MNODES=m STPS*MRADI I 0 NUMBER OF NODES ON RADI ALS

PARAMETER MSTOPS=50 i? NUMBER OP STOPS PER ROUTE

PARAMETER MBELT =10 ’ U MAX NUMRFR OF BELTWAYS

PARAMETER MSPIKE=20 a max number of spikes

LOGICAL KFXP

INTFGFR RFXP*DFXP*SFXP

COMMON/NOPES/KRADIMnODES) *KSTp(MNODFS) * KEYP ( MNOnES i * 1 NODE ( MRADI I * MSTPS

1

COMMON/GENRAL/MRTE ( ?'» MSTOPS ) *bTEMP ( ? , MSTOPS ) » ZK ( 20 ) * XZK ( ’0 ) TDPi

COMMON/RADIAL/ ANGLE ( MR ADI I ) * ISTp(MRADTI ) * DSTP AP ( MR AD 1 1 > MSTPS )

1 REXP(MRADII) » I R AD

C0MM0N/BELTWY/IBIN(MBELT) » IBFIN(MBELT) , I0STP(MreLT,MRADIT )

1 mr(MBELT) *BEXP(MBELT) »DSTBL t(MBEt T*MRADII ) » I BELT

COMMON/SPIKE/ TSPAD(MSPJKE) » iSSTp ( MS^IKF ) * PSP

I

KE (

M

SPIK E )

1

' SFXP (MSPIKE ) »NDSPK (MSPIKF) * ISPIKE

VARIABLES AND ARRAYS USED IN THIS PROGRAM

RADIAL

' ‘ ~

IPAD - NUMBFR OF RADIALS

ANGLE ( I ) - ANGLE OF PAQlAL I* ME/'SURFD COUNTERCLOCKWISE FROM FA^T

ISTP(I) - NUMBER OF STOPS ON RADIAL T* NOT COUNTING THE CENTER

DSTRAD(I*J) - DISTANCE BETWEEM STOPS J AND J+1 ON RADIAL I REXP(I) - A FLAGSET TO 1 IF RADIAL I IS AN EYPRFSS ROUTf __ BELTWAY

IBELT - NUMBER OF BELTWAYS

IBIN(I) “ INITIAL RADIAL CONNECTED BY BELTWAY I IBFIM(I) - F J MAL RADIAL CONNECTED BY BELTWAY I IRSTP ( I » J) - STOP ON RADIAL J ON RFLTWAY T DSTRLT ( T » J) - DISTANCE BETWEEN STOPS J AND J+1 ON RFLTWAY T NR(J) - MUMRcp OF PADTfiLST IHTF^SECTFT) BT RElT''^Y“ T‘ BEXP(I) - A r LAG SET TO 1 IF RELTWAY I IS AN FXPRFSS ROUTf

-91-
n

o

otoo

C

- SPIKE

C ISPIKE “ MU-’iFR OF SPTKFS

C ISRAD(I) “ 3 AO I AL TO WHICH SPTKF I IS CONMECTFP

C ISSTP(I) - STOP OH RAOIAL TO W H TCH SPTKF I IS CONNECTED

C DSP IKE ( I ) - LENGTH OF SPTKF I C NDSPK(I) - ''ONE NUMBER FOR STOP AT ENP OP SPIKF

C SEXP(I) - A FLAG SFT TO 1 IF SPI^E TS AN PXPRPSS ROUTP

C NODE DESCRIPTION

C KRADOTf - R/'OTAL NODE K TS ON

C KSTP(K) - STOP ON RADIAL K R A p ( K

)

WHICH IS NOOr K C KEXP(K) - NOnF IS/IS NOT AN EXPRESS hodE

C NODE ( T r J ) - THE MODE FOP STOP J ON RADIAL T C ROUTE DESCRIPTION

C MRTE ( M » N ) - NTH STOP ON ROUTE M. mRTP

(

1 » J) =MPTE

(

2 t M-J+l ) SlMr E

C ROUTES GO IN BOTH DIRECTIONS

C DTEMP(NrM) - DISTAtjCE BETWEEN STOPS M AND N+l ALONG ROUTE

C

C

C INITIALIZE

C

C

PI=3. 1415926S

COMPUTE RADI ALS

DO 2 1 = 1 » TRAD

node(t»i)=i

Ml=Ml+2

M2=M2 +2

ISTP1=ISTP ( I ) +1 _ _ MPTF ( 1 » 1)=1

MRTE ( 2 » ISTPl ) r

1

DO 1 J=2» ISTPi

C COMPUTE ROUTFS

K=K + 1 MRTE(_1 r_J)_=K

MRTF(2» ISTP1+1 -J)=K

D=DST D AD ( I * JJ)

DTEMPt 1» JJ)=D

DTEMP ( 2» ISTPl-JJ) =0

C COMPUTE NODE DATA

KRAD(K)=r

KSTP ( K ) -

J

NODE ( I f J) =K

1 CONTINUE

CALL KSCHFP( ISTPl , i

)

2 CONTINUE _

KMAX=K -number OF NODES ON RADIAL S

-92-
o

o

o

r COMPUTE RFLTW.AYS

DO 3 I J=T »"I BELT

Ml=Ml+2

M2=M2+2

I=IBIN( IJ)

N = NB ( IJ)

DO 4 TI=lrN

C COMPUTE ROUTES

J= I RSTP ( I J * 1 1

)

Nl=NOQE( I » J

)

MRTE ( 1» II)=M1

MRTE ( 2 r N + l — I T ) — f

.i 1 IF (II.EQ.N) 00 TO 4

IT=II+1

J1=IRSTP( IJ» TT)

11=1+1

IF (Il.6T.IR4D) 11=11-1 RAD

N2=N0DE( II t Jl

)

C COMPUTE the arc length as the average of the APC LENGTHS BETWEEN the

C TWO RADI ALS AT' RADII OF STOP J ON RADIAL T AND STOP J1 ON RADIAL It

A=ANGLE (II) -ANGLE ( I

)

IF (A.LT.O.T a=A+?.*PI

R 1 = 0 . _ _ JEND= J-l

DO 31 JJ=1 * JEND __ R1=R 1 +DSTRAD ( I » JJ)

31 CONTINUE

R2=0 . JEND=J1-1

DO 3? JJ=l»JEun

R2 = R? + DSTRAD ( T 1 * JJ)

32 CONTINUE

R= ( R2+R 1 ) /2.

R=ABS(R)

D=R*A _ _ OTEMP ( 1 » 1 1 ) =' UTEMP(2»N-II )=U

DSTBLT ( I J» T I ) =D

1 = 1 + 1 IF (I.GT.IPAD) 1=1

4 CONTINUE _

CALL RSCHED ( mh ( I J ) , mi 1

)

3 CONTINUE

-93-
c

r

C COMPUTE S n I KF n C nrr S

Cc

I F ( ISPIKE.f'O. 0 ) PFTUrU

DP S 1 = 1 » ISPTKF

K=K +

1

NDSPK ( I )=k

v 1 r M 1 + 2

M2=M£+2

C COMPUTE SPIKE ARCS

C COMPUTF ROUTED

MM=ISSTP ( I ) +1

MRTE (lr 1)=1

MRTF ( 2 » MM ) -

1

MRTE ( i»mm)=k

MRTE ( 2 » 1

)

LSTP=ISSTP( I

)

DTEMp ( 1 rLSTP) rOSPIKE ( I

)

DTE M P ( 2 » 1)=DSPIKE( I)

LRAD=ISRA n < I

)

Jl = NOOr ( LPAP » 2

)

Nl=MOPE(LRAD»l_STP)

MT = mm

11 = 1 DO 6 J=J1> 1 DTEMP ( 1 r 1 1 ) =I 'STRAD(LRAD» I I ) DTFMP ( 2 » MM— I I)=DSTRAD(LR'\ n » I I ) 11=11+1

mt=mt-i

MRTF ( 1 r I I )=J

MRTF (2rMT)=J

6 CONTINUE

CALL RSCHFP ( ‘"Mr Ml » 1 ) 5 CONTINUE

RETURN

END

-9b-
o

o

o

o

r>

B.1.2 Subroutine EXPRES

SUBROUTINE FXORFStK » Mir M2)

c this subroutine generates the express routes gf a r a p t a l transit roljTf

C SYSTEM. Two-way routes are CONSTRUCTED EOR R API AL r BELTWAY amp sptke

C EXPRESS ROUTES. PROGRAM OUTPUT INCLUDES THE SEMED'H c Ef)R EAPH EXPRESS

C ROUTE* THE STOPS Oh' EAr H EXPRESS ROUTf amp THE ROUTFS STOPPING AT EACH

C STOP. EXPRESS ROUTES STOP ONLY AT THE OTHF° MAJOR ROUTES.

C

CNATIONAL BUREAU OP STANDARDS JANUARY 1977 E . LEYENDECKER

parameter mradtj=2o q max number of rapials

parameter mstps =5o n numpep OE STOPS PER RAPIAL

PARAMETER MNOOES=MSTPS*MRADII 9 NUMBER OF NOPFS ON RADIALS

PARAMETER MST0PS = 50 iu NUMBER OF STOPS PFR ROUTE

PARAMETER MRELT =10 Q MAX ‘NUMBER of beltways

PARAMETER MSPlK E = 20 q max number of spikes

LOGICAL KEXP

INTEGER REXPrBEXPrSEXP

COMMON/NODES/KRAD(MNODES) r k STP ( MMO npS ) » KEXP ( MNOPES )

r

1 NODE ( MR API I r MSTPS

)

C0MM0N/GENRAL/MRTE(2»MST0PS) »DTEMP(?» METOp S) * ZK (20) t XZK ( 20 ) rlPP

COMMON/RADI AL/ ANGLE ( MR API!) > ISTp ( MR APT I ) *

D

STR AD ( MR ADI I r

M

STPS )

r

1 REXP ( MRADI I ) » TRAP

COMMON/BELTWY/IBIN (MRELT) , 1 8F IN ( MRELT )_r_IBSTP ( MRELTjMRaDI I )

,

1 NS ( MOELT ) » BEXP ( MRELT ) r DSTBLT ( MBELT r MRADI I ) r I PELT

COMMON/SPIKE/TSPAD(MSPIKE) » iSSTp(MSPIKF) »DSPIKE(MSPIKE)

1 SEXP ( MSPIKE ) »NDSPK (MSPIKF) » ISPIKE

C _ _ CCC VARIABLES AND ARRAYS "SEP IN THIS PROGRAM

C

C RADIAL

C IPAD - NUMBER OF RADIALS _

C ANGLE ( I ) “ ANGLE OE RAM«L It MEASURED COUNTERCLOCKWISE ‘FROM EaST

C ISTP ( I ) - NUMBER OF STOPS ON RADTAL Tr N*T COUNTING THE CENTER

C DSTRAD C I r J) - DISTANCE BETWEEN STOPS J AND J+1 ON ‘RADIAL I C REXP(I) - A FLAG SET TO 1 IE RADTAL T IS AN EYPRFSS ROUTE

C BELTwAY

C I BELT “ number OF BELTWAYS _

c ibin(i) - Initial radial conmFc'tfd by beltway i C IBFIU(I) - PINAL RADIAL CONNECTED BY RELTWAY T C IBSTP(IrJ) - STOP ON RADIAL J ON RELTWAY T C DSTpLT ( I * J) - DIS T ANCE BETWEEN STOPS J AND J+1 ON BELTWAY I C NB ( I ) - NUMBER OE RADIALS INTERSECTED BY BELTwaY I C BEXP ( I ) - A FLAG SET TO 1 IE RELTWAY T IS AM ryPPESS ROUTE

-95-
ooooo

nooooooooooioo

nonoooon

SPIKE

ISPIKE - MU'^FR OF SPIKES

ISRAD(I) - RADIAL TO WHICH SPIKE I I r COmnECTfd

ISSTP(I) - STOP ON RADIAl. TO WHICH S°TKE I IS COMNECTFD

OSPIKF(I) - LFNGTH OF SPTKE I NDSPK(I) - HOOF NUMBER FOR STOP at Fun OF sPI*E

”SEXP(I) - /A FLAG SET TO 1 IF SPIFF IS aTJ FX'PRfs'S RoUTF

NODE DESCRIPTION

K R A OTK ) -RADIAL NODF K IS ON

KSTP(K) - STOP OM RADIAL K R A n ( K ) WHICH IS MODF K KEXP(K) ~ KtOoE” TS/TS "NOT AN EXPRESS MODE

NODE ( I * J ) - THF NODE FOR STOP J ON RADI A! I ROUTE DESCRIPTION

MRTE(M»N> “ NTH STOP ON ROllTF M. MRTr ( 1 , J ) =MRTE ( ? r N-J+ I ) SINCE

ROUTES GO IN ROTH DIRECTIONS

DTEMP ( N» M) - O I STANCE BETWEEN STOPS M ANO n+1 ALONG ROUTE

INITIALIZE

KSTOP=C Q KSTOP COUNTS STOPS ON AN FXPRESS ROUTE

DIST=0. 0 P DISTANCE ACCUMULATOR FOR EXPRESS ROUTES

COMPUTE EXPRESS BELTWAYS

DO 200 1 = 1 * I

J[r LT

IF ( REXP ( I ) • NE. 1 ) GO TO 200 _ Ml=Ml+2

N2=M2+2

IR=IBIN( I

>

NUMB=NB ( I_) Ct****C aLCULATE EXPRESS stop's AND TNTER-STOP DISTANCES TM One OIRECTI0N

DO 150 11 = 1* NHMEl

J= I RSTP ( I * 1 1 ) ND=NODE ( IR* J)

IF( IR.EO.

I

Q IN( I ) .OR. TR.EQ. IRFIM( I ) ) GO T 0 110

IF(REXP( IR) .FO. 1 )GO TO_Un

DO 100 I S= 1 * TSPIKF

IF ( ISRAD ( IS ) . NE , IR ) GO TO 100

IF (SEXP( IS) .CO. 1 • AND* ISSTPt IS) *GF. J) GO TO 310

100 CONTINUE

GO TO 120

110 KSTOP=KSTOP+l _ _ MRTE ( 1 *KSTOP)=NO

KEXP(ND)=.TRMF.

- 96-
120 iFtll.E’Q.l, 0

° » • NOT , KFXP ( NP ) ) GO TO 130

DTEWP( 1 »KSTOp -l )=PIST

OIST-O.O

130 IF ( 1 1 .FQ.MUM O 00 TO 140

"oystsd i sr+dstplt n » rn

~ 140 IR=IR+1

IF( IR.OT. IFAO) I P=

1

150 CONTINUE

C*****FlLL MRTE ( 2 r ) ANP PTEMP(2* ) DO 160 II=l#KSTOP

MR T E ( 2 f K ST0 P

+~ 1 -I IT = MRTE ( 1 #"T I )

' — ~ ~ ~

IF(II.NE.KSTOP) DTEMP(2»KST0P-TI )rOTEMP(l r IT

)

160 CONTINUE

C*****CALL RSCHED

CALL RSCHED(KST0P»M1 ,2)

KSTOP=0

200 CONTINUE

~ ' " " ‘ " £

L —

C COMPUTE EXPRESS SPIKES

C

IF ( ISPIKE. FQ.OlGO TO 500

DO 400 1 = 1 * ISPIKE

IF(SEXP(I> .NE.l >GO TO 400

LRAD=ISRAD( I

)

Ml=Ml+2

M2=M2+2

MM=ISSTP( I)

C*****CALCULATE EXPRESS STOPS AND INTER-STOP DISTANCFS TN ONE DIRECTION

DO 350 1 1 = 1 r MM

ND=NODE ( LR AD * 1 1

)

irTlI.EQ.DGO TO 310

IF (KEXP (ND) ) GO TO 310

IF ( 1 1 • NE • MM ) GO TO 320

IF (REXP(LRAD) . EQ. 1 ) GO TO 310

DO 300 IS=1 r ISPIKE

IF(I.FQ.IS.OR.ISRADdS) .NE.LRADJGO TO 300

IF ( SEXP ( IS7"#EO* 1 • AND • ISSTP (IS) » GE .MM ) GO TO 310

300 CONTINUE

GO TO 320

310 KSTOP=KSTOP+l ___ _

MRTF(l»KSTOP)=NP

KEXP(ND) = dRUE. _ __ 320 I F ( II • EQ • 1 • OR • • NOf • K EXP ( NO ) ) GO TO 330

OTEMP(l,KSTOP-l)=DTST

DISTzO.O

330 IF(II.LT.MM) r'IST=DlST +DSTRAD ( LR AP » 1 1

)

IF ( II .EQ.MM) DlST=niST+DSPlKE(T)

350 CONTINUE

-97-
o

o

r>oo

C*****CONSIDER STOP AT EN° OF S°TkF

KSTOP=KSTOP+t

MRTF ( 1 # KSTOP ) zMDSPK ( I

)

TEMP ( 1 » KSTOP- 1 ) =HIST

DISTrn.o

C*****FILL MRTE(Pr ) AND oTE*1p <?» ) DO 360 11 = 1 r K ST OP

MRTE (2 >KSTOP+1 -1 1 ) =MRTE( 1,11)

IF (I I. NE. KSTOP) DTEMP(2»K5T0P-TI )=DTFMP(1» II)

360 CONTINUE

C*****CALL RSCHED

CALL RSCHED(KST0P»M1 r2)

KST0P=C

400 CONTINUE

COMPUTE EXPRESS PADIALS

500 DO 600 I = 1 » I R A

IF(REXP(I) .NF.l) GO TO 600

Ml=Ml+2

M2=M2+2

MM=ISTP(I)+1 _ _ C*****CALCULATF FXP°FsS STOPS A\|D InTER-STOP DlS'TANCFS IN ONE DIRECTION

DO 650 I_I = 1 »_MM

NOrNOnE ( I Vi I

)

IFdl.PQ.) .OP.II.EO.^MJjSO TO 610 _

IF (KEXP(NO) ).0 TO 610

GO TO 620

610 KSTOP=KSTOP+l

MRTE (• KSTOP )rND

620 IF ( 1 1 .EQ« 1 ) GO TO 630

IF (II. JE.MN.AND. .NOT.KFXP(MD) ) GO TO 63jl

DTEMP( 1 »KSTOP-l ) =UIST

DIST=0.0

630 IF(II.LT.WM) ^IST=DIST + DSTPAD( I » II

)

650 CONTINUE

C*****FILL MRTE (

1 ) AND PTEMP(2» ) DO 660 1 1 = 1 » KSTOP

MRTE ( 2 * KSTOP + 1-1 1 )=MRTE( 1 » 1 1)

IF ( I I. ME. KSTOP) DTEMP(2»KST0P-TI )=DTFMP(1» TI)

660 CONTINUE

C*****CALL RSCHFD

CALL RSCHFO(KSTOP»M1 »2)

_ _ HSJ OP=0 . __ ... - 600 CONTINUE

RETURN . _

END

-98-
B.1.3 Subroutine RSCHED

SUBROUTINE RSCHF.n ( N , Mi » LO r ) C THIS SUBROUTINE COMPUTES AND PRINTS OUT SCHEDULE INFORMATION FOP

C Ml AND Ml+1. INPUT INCLUDES THE STqPS ALONG ROUTES mi AND Ml +5,

C STORED IN MRTF(1,I) AND MRTE (2*1) RESPECT T \/EL Y » THf Nt l M BFR QP

C STOPS ALONG THESE ROUTFS IN N* AND THE D I

S

T ANOF PE t wEFM STOPS im n.

C INPUT ALSO INCLUDES THE NUMBER OF TImF PERIODS IPD AND THE FACTOP

C USED TO TRANSLATF DISTANCE TO TIME IN EACH PERIOD STOP^O IN AN n YZ*

PARAMETER MSTOPS=SO

parameter mpos=io

COMMON/GEMRAL/MRTE (

2

* MSTOPS ) »pTEMP(2»MST0PS) *ZM?n) »V7K(RO) , IPO

DIMENSION JRIJNS(MPDS) * JHFAD(mPDS) »JDTM(MPDS) * . JTIMF ( MSTOPS

)

MM=M1

DO 3 IR0UTE=1*2

NRUNS=0

DO 1C IPERD=1 , TPD

C READ THE NUMBER OF RIJNS OF THIS ROUTE THIS PERIOD (JRUNS>* THE

C HEADWAY BETWEEN RIJNS (JHEAD)* AND THE TIMF OF THF p I RST RUN (JPTM).

READ (5*901) JRUNS( IPFRF’I) » JHEAD( IPFRD) . JDTM( IP r Rn)

90 1 FORMAT ( 2 n T 5

)

NRUNS=NRUNS+JRUNS( IPERD)

10 CONTINUE

WRITE (6*900) Mv r N»NRUMS» (MRTE* IROUTE* J) » J=1»M)

900 format ( * opoute ’ * 14 *

* has»*J3*» stops***I4»* rums*/^x» »stops» *? ni5>

WRITE (7*901) MM * N * NRUMS * ( MRTF ( I ROUTE * • I ) » J”1 * N)

DO 21 I PERDzi t I PD _ _ JJ=JRMNS( IPER^)

IF (JJ.EQ.O) GO TO 21

DO 2 TRUN=l*JJ

JTIME( 1 )=JDTM( IPERD )+ ( IRUN-1 ) *JHFAD( IPRRD)

DO 1 L=2*N

IF(LOE.EQ.l) JTTME(L)=JTIMF(L-1 ) +DTEMP ( TROUTE * L-1 ) *?K ( IPEP p ) IF(L0E.E0.2) JTIME(L)=JTIME(L-1)+DTEMP( TROUTEr L-l )*XZK ( IPPPp)

1 CONTINUE

WRITE (6*902) ( JT IME ( L ) * L= 1

* N

)

902 FORMAT (10X*2n!5)

WRITE (7*901) ( JTIMF(L) *L=1 *N)

2 CONTINUE

21 CONTINUE

J|M=MM+1

3 CONTINUE

RETURN

END

- 99-
r>

n

o

B. 2 PROGRAM XGRID

c ***************** XGRlL : PURE GRID GEMFRATOo *****************

c “This pro-am Generates a ~ du^fgrih TpiF7s‘iT

_svsirM wTtu north-t^outh,

C EAST-WEST ROUTES. THE USFR SPECIFIES THF NUMREP of STOPS p AMO THE

C NUMBER OF STOPS 0 WHICH DEFINE » RESPECTIVELY » THE VFRTI CAL AND

C HORIZONTAL DIMENSIONS OF THE P-PY-Q G D ID. IN ADDITION THF USFP

C MUST SPECIFY THE IMTERSTOP DISTANCES L ( I ) AND w(I) RPTwEEM SUCCESSIV

C ROWS’ AND * COLUMNS OF THE OR ID. STOPS WILL RE _Ml i MRFRED FROM LFp T

C TO' RIGHT# TOP T p BOTTOM IN SEQUENCE , ANY"stop" IS ALLOWED' TO" BE A C TRANSFER NODE BETWEEN ROUTES » WHICH ARF assumed TO RUN WEST-EAST,

C EAST-WEST r NORTH-SOUTH AMD SOUTH-NORTH ONLY. THE TRANSFER T I MF

C BETWEEN ROUTES IS ASSUMED TO RE CONSTANT AT FACH tpamSFFR STOP.

C ROUTES FOLLOW REGULAR SCHEDULES THROUGHOUT EACH PFRion, AND THFRP

C MAY BE A DIFFERENT CONVERSION FACTOR FOR CONVERTING PTSTaNCF INTO

c Time for each pfriod, this version allows express routes

C BY THE SPECIFICATION OF MAJOR X and y routes, these routes

C STOP ONLY at THE OTHER MAJOR ROUTES.

c _

C

c _ C NATIONAL BUREAU OF STANDARDS MAY, 1 97B

C

c

c

c

c

cc

cc

c

c

c

c

c

cc

c

c

PARAMETER

PARAMETE_R

PARAMETER

parameter

PARAMETER

PARAMETER

DIMENSION

COMMON

MAXP=50

MAXQ-SO

_

MAXPDrjn

MRTES=200

MAXM=50

TRANSF=5000

DIMENSION

DIMENSION

NUMBER OP

NUMBER OF

mumbpr OF

MUMPER of

OF GRID

OF GRID

P

Q_

PFRTODS

ROUTES

NODFS/ROUTE

TRANSF r RS

L(MAXP) rW(MAXQ) »ZK (M aXPD) »X7K (maXPD)

NN(NRTFS) ,NODE(NRTES»mAXM) » D ( NRTES , MAXN) r TNODE(TRANSF) , RT t (TRArjSF) ,PT?(TRAMSF) ,f -TRANS

VARIABLES AND ARRAYS USED IN THIS PROGRAM

INPUT PARAMETERS'”'

P - VERTICAL DIMENSION OF G R T

P

Q - HORIZONTAL dimension OF grid

L ( I

)

- DISTANCE BETWEEN VERTICAL ROWS I» T -1

W(I) - DISTANCE BETWEEN HORIZONTAL COLUMNS I , T -

1

PDS - NUMBER OF PERIODS

ZK ( J

)

- COMVFRTSr DISTANCE INTO TTMF FOR PFRIOP j'

ROUTE DESCRIPTION

NN ( R ) - NUMBER OP MODES Or) ROUTE R

NODE ( P » I ) - THE I -TH NODE ON ROUTE R

D ( R » I ) - THE I-TH TMTERSTOP DI STANC E ALONG ROUTE P

-100-
C TRANSFER NODE RESCRIPT IOM

C TMOOFd.) - TMF L-TH TRANTER ^00'"

C RT1 (! ) - ROUTE FROM WHICH TRANSFER yc M A^F AT tmoDE ( l_

)

C PT2(l) - POUTF TO WHICH TRANSFER IS v ADF AT TnnTrft ) C NTPAMS - MUMPER OF TRANSFERS

C

C

c IMPLICIT INTEGER (A-Y)

RFAL XZK

C

C READ STRUCTURAL PARAMETERS OF GRl n . C

RFAT (

5

» 900 ) P»0»(L(I)»I=2rP)»(W(I)»I = ?»Q)

900 FORMAT (1615)

RHASF=0 0 CONVENIENT REFERENCE RASE FOP ABSOLUTE ROUTF MUMPER?

C

C CPLATF NODES » ROUTES » TRANSFER DATA.

C

CALL GRID ( P » 0 » I. » W» PHASE ) CALL XPRESS ( P r 0 » L. » W » RRASE ) C

C READ CONVERSION FACTORS FOP EACH PERIOD.

C READ ( 6 » 90 1 ) p 'S» (ZK ( I ) »

I

= l»Pns)

901 FORMAT( I5r ( 1BF5.Z)

)

READ (5»90P) (X7K(I) »I=1»PDS)

902

FORMAT (5X* l^r-5.2)

C

C COMPUTE COMPLETE SCHEDULE INFORMATION FOP EACH RO' 'TF AND PEPIOD.

C Pq=2*P+2*0

CALL XSCHEO ( MM » NODE » D » ZK t Y7.K t PDS , PR A SF » PQ ) C

C THE TRANSFER DATA GENERATED IN GRID IS PRTNTm.

C PO=P*0

C ALL TP AMS ( NTP AMS » Tr jODE » RT 1 * RT? » PO » RP A SE

)

STOP

E"D
B . 2 . 1 Subroutine GRID

C

C

c

cc

c

c

c

cc

cc

cc

cc

ccc

c

c

c

c

c

c

c

c

cc

c

cc

c

cc

c

c

SUPROUT I NE G° TO ( P » 0 » LL r W » PR ftSf > This subroutine •s'enerates the nodes', pouter ahK tr*msffr

' DATA FOR A P-RY-0 GRID NETWORK. THE VAPTarLFS P.'-'.RPASE ANR

THE ARRAYS LL..W APE TP ANSM ITTFQ FROM THE MAIM PROGRAM. IT TS

ASSUMED THAT P»0 > 1. NODES ARF MUM^ERE" FROM LEFT TO R T GMT

TOP TO BOTTOM I s SFOUENGE. ROUTES ARF ASSUMED TO RUM WFSTEAST .EAST-WEST .NORTH-SOUTH. SOUTH-NORTH OMIY. TRA_mSFfPS ARF

ALLOWED TO OCCUR BETWEEN ROUTFS AT AMY MODE,

NATIONAL BUREAU OF STANDARDS M A Y » 1 R7G

PARAMETER mayp=50 3 DIMENSION P OR GRID

PARAMETER MA <0=50 Q OTMFNSIOA' G OF GRXD _

PARAMETER NRTfS=200 0 NUMBER OF ROUTES

PARAMETER MAXM=50___ JA NUMBfR OF NQRFS/BPUTF

PARAMETER TRV|SF=50b0 Q NUmRER TRAmSFFRS

DIMENSION LL(MAXP) »W(MAXQ)

COMMON NN(NRTES) » NODE ( NRTFS » MftVN) r D ( NRTES » MAXN)

1 TMODE(TRANSF) »RT1 (TRANSF) .RT2(TRAmSF) »mTRAMS

VARIABLES AND ARRAYS USED IN THIS SUBROUTINE

INPUT PARAMETERS

P - VERTICAL DIMENSION OF GRID

0 - HORIZONTAL DIMENSION OF GRID

LL(I) - niSTANCE BETWEEN VERTICAL ROWS' I » 1-1

W(I) - DISTANCE BETWEEN HORIZONTAL COLUMNS I^T-L_

RBASF - CONVENIENT REFERENCE RAS r FOR APSOLUTr ROUTE NIIMpppS

ROUTE DESCRIPTION

MN(R) - NUMBER OF NODES ON ROUTE R

NODE ( R » I ) - THE I-TH MODE ON ROUTE R

0 ( R » I

)

- THF T-TH INTERSTOP DISTANCE ALONG ROUTE R

TRANSFFR NODE DESCRIPTION

TNODF(L) - THE L-TH TRANSFER NODR

RT1(L) “ RO'ITE FROM WHICH TRANSFER IS MADE AT TNODE ( L

)

RT2(L) -""ROLTtE” TO WHICH TRANSFER IS MADE AT TNODF(L)

fJTRANS - MUMPER OF TRANSFERS
IMPLICIT IMTFGER C 'X — Y ) GENERATE FOR EACH POUTF THE MOOES ON IT. ALSO CRFATF INTERSTOP 1ST AMCES

PP=2*P

PPQ=PP+Q

DO 110 R=1 »P

NN ( P ) =0

' " IS = G* (R-l

)

NODE ( R » 1 ) - IS+

1

DO 100 I=2»Q

NODE(R» I)=IS+I

D(R» I-1)=W( I ) 100 CONTINUE

110 CONTINUE

DO 130 RR=1»P

R=RR+P

NN(R)=0

IF=Q*RR+1

NODE ( R r 1 ) =IF-1

DO 120 I=2»Q

NODE ( R f I ) =IF-I

0(R» 1-1 )=W(Q-I+2)

120 CONTINUE

130 CONTINUE

DO 150 RR=1 t

9

R=PR+PP

MN(R)=P

NODE ( R » 1 ) =RR

DO 140 1=2 »P

NODE ( R r I ) =RR+ ( 1-1 ) *0

D(R» 1-1 )=LL( T)

140 CONTINUE

150 CONTINUE

DO 170_ RR=1 »0

R— RR+PPQ

NN(R)=P

IFz ( P-1 ) *0+RR

NODE(R» 1 )=IF

DO 160 I=?»P

NOPF (Pr I ) =IF— ( I— 1 ) *0

0(R»I-l)=Lt.(!:, -T+?)

160 CONTINUE

170 CONTINUE

-103-
oo

o

CRtL/'TE TRAUSFro ^ a T

A

M=0

L = 0

00 240 1=1 »P

DO 230 J=1»Q

N=M+

1

IFCI. ro. 1) GO TO 210

IFCJ. ro. 1) 60 TO 200

L=L+ 1 TNODE ( L ) =N

RT1 (L)=PP+J

RT2(L)=P+T

L=L + 1 TNODE ( L ) =N

R T 1 ( L ) = I RT2(L)=PP0+J

200 IFCJ.ro. Q) ro TO 21u

L=L +

1

TNOPE ( L ) =' I RT1(L)=PP+J

RT2(L)=I

L=L+

1

TNODF(L)=N

RT1 (L)=P+"I

RT2 ( L ) =PPO+

J

210 IF ( J.FQ. 1 ) GO TO 220

IF(I.fO.P) GO TO 220

L = l. + 1 TNOPE ( L ) —

N

RT1 ( L ) =1

PT2 (L)=PP+J

L=L +

1

TNODE ( L ) =N

RT1 ( L ) =PPQ+

J

RT2 (L) =P+I

220 IFCJ.FO.O) GO TO 230

IFCI.FO.P) GO TO 230

L = L +

1

TMOOE(L)=N

RT1 ( L ) =P+

I

RT2 (L ) =PP+J

L=L +

1

TNODE (L)=M

R T 1 (L ) =PPO + J

RT2 ( L ) =

I

23D CONTINUE

240 CONTINUE

NTR ' NS=l

RFTUR 1

' END

-10U-
B.2.2 Subroutine XPRESS

900

1

2

3

131_

SUBROUTINE XPRr SS ( P » 0 » LL » W » RRASE

)

PARAMETER w p=2 5

PARAMETER mq=?5

PARAMETER NRTES=200

PARAMETER MJ*XN=50

PARAMETER TRANSF=5000

DIMENSION LL(1)»W(1)

DIMENSION MAINP(MP) r M A I NO ( MO ) f DP ( MP ) »OQ(mo) , SP(MPl * SQ ( MO ) , 1 FLAG (12)

COMMON NN(NRTFS) » NODE ( NRTES » M AXN

)

* D ( NRTES » MAXm

)

t TNODE ( TR Ar'SF )

1 RT1 (TRANSF) » RT2 ( TRANSF ) rNTRAMS

IMPLICIT INTEGER ( A-Y

)

READ ( 5 » 900 ) NMPrNMQ

FORMAT (16T5)

IF (NMP.LE.O.OR.NMQ.LE.O) RETURN

READ ( 5 r 900 ) (MAINP( I ) » 1 = 1 »NMP)

READ ( 5 » 900 ) (MAINQ( I ) »

1

= 1 rNMQ)

L1

J=1 _

IF (MAINP(f) •EQ.l) GO TO 1 SP(1 )=1

L-2

SP(L)=MAINP( J)

L=L + 1 J=J+1

IF ( J.LE.NMP) GO TO 1 IF (MAINP(NMP) .FQ.P) GO TO 2

SP(L)=P

L=L + 1 NSP=L-1

L-l

J=1

IF (MAINQ(l)

p 0 • 1 ) GO TO 3

SQ(1)=1

L=2

SQ(L)=MAINQ( J)

L=L+1

J=J+1

IF (J.LE.NMQ) GO TO 3

IF (MAINO(NMO) .EQ.Q) GO To 131

SQ(L)=Q

L=L+

1

NSQ=L-1

IEND=1

DO 5 I=2fNSP

11=1-1

DP ( I I ) =0

IBEG=IEND+1

iFur=sP( i

)

-105-
^

i

-p

DO 4 J=I8FG»TFND

DP(II)=DP( II)+LL( J)

CONTINUE

CONTINUE

IEMD=1

DO 7 I=2»NSQ

11 = 1-1

DQ(II)=0

IBEG=IEND+1

IEMD=SO(I

)

DO 8 ~J= IE3FG r I END

DQ(II>=DO(II)+W(J)

CONTINUE

CONTINUE

Rl=2* (P+0)

Q1=NSQ+1 _

DO Q I=1#NNP

R1=R1+1

R2=R1+NMP

BASE=(MAINP( T )-] )*Q

DO 8 J=1*NSQ

N OD- BASE+SQ ( J

)

NODE ( R1 > J) =NOD

NODE ( R2 » Ql-J) =MOD

IF (J.EQ.MSQ) GO TO 8

D ( R1 » J ) =00 ( J

)

n(R?rN5Q-J)=no( J)

9 CONTINUE _ _ NN(R1)=NS0

NN(R2)=NSQ_ _

p continue

Rl=2* (P+Q+NNP)

PI =', '5P+

1

DO. XI 1 = 1* NMO _

Rl=RJ +1

R2=R1+NM0

BASE=NAING( I

)

DO 10 J=1»NSP

N0D=BASE+(SP(.J)-1 )*0

NODE ( R 1 » J) = NOD

NODE ( R2 t Pl-J) =NOD

IF (J.EQ.NSP) GO TO 10

D ( P 1 # J)=DP( J)

D(R2»NSP-J>=nn( J)

10 CONTINUE

NN_( R 1 ) =NSP

NN('R2) =N5P

11 CONTINUE

-106-
PQ=2*P+2*Q

DO 3ft L. 1 = 1 » N^°

I=MAINP(L1

)

DO 38 L2=lNMQ

J=MA f NO ( L2

)

R-PQ+L1

DO 12 L=1 » 12

FLAG(L)=1

12 CONTINUE

FLAGJ 9 ) =0

FLAG ( 10 ) -0

IF (J.NE.l) GO TO 13

FLAG ( 1 ) =0

FLAG ( 2

)

= 0

FLAG ( 3 ) =0

FLAG ( 5

)

= 0 _ FLAG (7) =0

FLAG ( 1 1

)

= 0

FLAG ( 1 2 ) =0

13 IF (J.NE.O) gO TO 14

FLAG ( 1 ) =0

FLAG ( 2 ) =0

FLAG ( 4 ) =0

FLAG ( 6 ) =0

FLAG ( ft ) =0

14 IF (I.NE.l) GO TO 15

FLAG ( 7 ) =0

FLAG ( 6

)

= 0

FLAG ( 12) =0

15 IF (I.NE.P) GO TO 16

FLAG(5)=0

FLAG ( ft) =0

FLAG ( 1 1 ) =0

16 CALL XTRANS(P»0»FLAG»R» T» JrLl »L 2 »NMP#MWQ)

IF (L2.GT.1) GO TO 18

IF (SO(l) .EQ.MAINQ(l) ) GO TO 17

NOD=( 1-1 ) *0+1

IF (I.EQ.l) G^ TO 161

NTRANS=NTPANS+1

RT 1 ( NTRAMS ) =2*P+1

RT2(NTRANS)=R

TNODE (NTRANS)rMOD

161 IF (I.FO.P) GO TO 17

NTRANS=NTRANS_+1 _

RT1 (NTRANS)=2*P+Q+1

RT2 (NTRANS)=R

TNODE (UTRANS)=NOP

17 IF (SO(NSQ) .EO.MAINO(NWIQ) ) GO TO 1ft NOD=I*G

IF (I.EQ.l ) GO TO 171

-107-
NTRANS=NTP ANS + l RT1 ( NTRANS ) =P

RT2< NTRANS )=PQ

TNODE( NTRANS )=NOD

171 IF (I.EQ.P) GO TO IB

NTRANS=NTRANS+1

RT1 (NTRANS) = ° RT2(NTRANS)=2*P+0

TNODEt NTRANS )=NOD

18 RsPQ+NMP+l.l

DO 19 L=lr 12

FLAG(L)=1 _ _

19 ' CONTINUE

FLAG ( 9 ) =C

FLAG ( 10 ) =0

IF (J.NE.l) GO TO 20

FLAG ( 2 ) =0

FLAG ( 3 ) = 0

FLAG (4) =6

FLAG ( 6

)

= 0

FLAG ( 8) =0

20 IF (J.NE.Q) go jo 21

FLAG ( 1 )=0

FLAG ( "5 ) =0

FLAG <4 ) =0"

FLAG(S) =0

FLAG ( 7 ) =0

FLAG( 11) =0 _ “FLAG (' 12 ) =0

21 IF (I.NE.l) GO TO 22

flag ( 7 ) =0

FLAG ( 6

)

= 0

FLAG ( 12

)

= 0

22 IF (I.fJE.P) GO TO 23

FLAG ( 5 ) =6

FLAG ( 8 ) =0

FLAG ( 1 1 ) =0

23 CALL XTR AMS ( P » Q » FLAG » R » I » J » Ll r 1.2 » NMP » NMQ

)

IF (L2.GT. 1 ) GO TO 25

IF (SQ(NSQ) .EO.MAINQ( NMQ ) ) GO Tq_?4_ _

NOD=I*Q

IF (I.EQ.l) GO TO 231

NTRANS=NTRANS+1

RT1 (NTRANS) =?*P+0 _

RT2 ( NTRANS ) =R

TNODE (NTRAfJS) =MOO_

231 IF (I.EQ.P) Go TO 24

NTRANS=nTRANS+ 1 RTl ( NTRANS ) =2 *P+2*0

RT2 ( NTRANS )

P

TNODE( NTRANS )=NOD

-108-
24 IF (S011) ._EG.'iAIMQ( 1 ) ) GO TQ ?5

NOD- ( T-l)*0+j

IF ( I .FQ. 1 ) Go TO 241

NTRANS=NTRANS+1

RT1 (NTRANS) =R

RT2 (NTRANS) =2*P+Q+1

TNODF (NTRANS) =NOD

'241 ' IF ( I . FQ.PT ' GO TO 25

NTRANS=NTRANS+1

RT1 ( NTRANS ) =R

RT2 (NTRANS) =2*P+1

TNODF. ( NTRANS) =NOD

25 _ R=PQ+2*NMP+L2

DO 26 L=l* 12

FLAG(L)=1

26 CONTINUE

FLAG ( 11) =0

FLAG ( 12) =0

• IF JJ.NE._l) GO_TO_ 27_

FLAG ( 2

)

= 0

FLAG(3)=0

FLAG ( 1 C ) =0

27 IF (J.NE.O) GO TO 28

FLAG ( 1 ) =0

FLAG ( 4 ) =0

FLAG (9) =0

28 IF (I.NE.l) GO TO 29

FLAG ( 1 ) =0

FLAG(3)=0

FLAG(5)=0

FJ_AG ( 6J =0_

FLAG ( 7 ) =0

FLAG ( 9 ) =0

FLAG (TO) =0

29 IF (I.NE.P) GO TO 30

FLAG ( 2 ) =0

FLAG ( 4 ) -0

FLAG ( 5 ) =0

FLAG(6)=0

FLAG ( 8 ) =0

30 CALL XTRANS(P»Q»FLAG»R» I» J»L1»L2#NMP»Mmq)

IF (Ll.GT.l) GO TO 32

IF (SP(1) .EQ.MAINP(l) ) GO TO 31

NOD=J

IF ( J.EQ.J ) GO TO 301

NTRANS=NTRANS+1

RT 1 ( NTRANS) =1

RT2 ( NTRANS

)

TNODE (NTRANS) =NOD

-109-
301 IF (J.FQ.O) on TO 31

NTRANS=NTRAM?+1

RT1 (NTRANS)=P+1

RT2 ( NTftANS ) =?

TNODE ( JTRA’IS) rr.'OO 31 IF (SP(NSP) .FQ.mATNP(NMP) ) 00 To 3?. N0D=(P-1) *Q+J

IF ( J.EQ.l ) oo TO 311

N trans=ntpanis*i

RT1 (NTRAM5)=R

RT2 (NTRANS)=2*P

TNOOE ( MTR ANS ) zNOD

311 IF ( J.tq.Q) on To 32

NTRANS=NTPAN|F + i

RT1 (MTRANS)=p

RT 2 ( NTRANS ) =P

TNOPE ( NTRANS) =NOD

32 R = PQ + 2*NMP + N

r ’Q + L2

00 321 L- 1 >12

FLAG (L) =1

321 CONTINUE

FLAG ( 11 ) =C

FLAG ( 12) =0

IF ( J.NE. t ) GO TO 33

FLAG ( 2 ) =0

FLAG(3)=0

FLAG ( 10=0

33 IF (J.NE.Q) GO TO 34

FLAG ( 1 )=n

FLAG ( 4 ) =0

FLAG ( o ) =0

34 IF (I.NE.l) GO TO 35

FLAG(2)=0

FLAG (4) =0

FLAG(G)=0

FLAG ( 7 ) =0

FLAG(«)=0

33 IF (I.NE.P) GO TO 76

FLA G ( 1 )=C

FLAG ( 3 ) =0

FLAGGS) =0

FLAG ( 7 ) =0

FLAG ( '0=0

FLAG ( Q ) =0

F L A G ( 1 6 ) = 0

36 CALL XTRAMS(°»Q»FLAG»R»T» J»L1 »L2#mMP»NMQ)

IP (LI .GT. 1 ) GO TO 3S

IF (SP(NlSP) . EO « MA IMP ( NMP ) ) GO To 37

N00=(P-1 ) *Q + J

- 110-
IF (J.EQ.l) GO TO 361

NTRAMS=NTR/\NI5 + 1 RTJ (NTRANS)=P

KT2 (NTRANS)=R

TNOnE ( MTRANS) =MOD

361 IF (J.EO.Q) GO TO 37

NTRANS=NTRANS+1

RTl ( MTRANS )=?*p

RT2 ( MTRANS) =R

TNOC E (MTRANS) zNOD

37 IF (SP(1) .EQ.'iAIMP(l) ) GO TO JP

NOD=J

IF i J , EfijlI. L. G 0 10. .371

ntrans=ntrans+i

RTl (NTRANS)=R

RT2 (

f

1 'TRANS ) =P+1

TNODE ( fJTR AMS ) =NOD

371 IF (J.EQ.Q) GO TO 3P,

NTRANS=N1RANS+1 _ RTl"(MTRANS)=R

RT2 ( I 'T D ANS ) = 1 TNODE (MTRANS) =MOP

38 CONTINUE

RETURN

END

-111-
B.2.3 Subrout ine XTRANS

1

2

3

4

5

6

7

P

9

SUBROUTINE XTRANS ( P_, 0 » FL AG » R » I » J » l 1 » L7 * NMP » NMQ)

PARAMETER nrTEs=2oo

parameter MAXN=50

parameter transf=5o0o

COMMON NN(NRTES) »NODE (JMRTES • MAXN) »D(NRTES»_MAXm) fTNODE(TRANSF) . 1 RTl(TRANSF) » RT2 ( TRANSF

)

t N TRANS

IMPLICIT INTEGER (A-Y)

DIMENSION TLAGUT

' ' ' “ NOn=( 1-1 ) *Q+ J PQ=2*P+2*Q

LL=NTRANS

IF ( FLAG ( 1 ) . EO • 0 ) GO TO 1 LL=LL+1

RT1 (LL)=R

RT2(LL)=I

IF ( FLAG f 2 ) • F 0 • 0 ) GO TO 2

LL=LL+1

RT1 (LL)=J

RT2(LL)=R

IF ( FLAG ( 3 ) . EQ .’O ) GO TO 3

LL=LL+1

RT1 (LL)=R

RT2(LL)=P+I

IF ( FLAG ( 4 ) • EO « 0 ) GO TO 4

LL=LL+1

“pfi(LL )=P+I

PT2 (LL )=R

IF ( FL AG ( 5 ) • EG • 0 ) GO TO 5

LL=LL+1

RTl (LL)=R

RT2 ( LL )_=2* P + J _

IF ( FLAG ( 6 ) .EO • 0 ) GO TO F> LL=LL+1

RTl (LL)=2*P+J

RT2(LL)=R

IF ( FLAG ( 7 ) . E 0 0 ) GO TO 7

LL=LL+1

RTl (LL)=R

RT2(LL)=2*P+0+J

IF ( FLAG f 8 ) • Eq . 0 ) GO TO 8

LL=LL+1

RTl (LL) =2*P+0+J

RT2(LL)=R

IF ( FLAG fQ ) . EO . 0 ) GO TO 9

LL=LL+1

RTl (LL)=R

RT2(LL)=P0+L1

IF ( FLAG (

1

0 ) . FO . 0 ) GO TO 10

LL=LL+1

RTl (LL)=R

RT? ( LL) =P0+NMP+L1

-112-
10 IF (FLAG(ll).FO.O) GO TO 11

LL=LL+1

RT1 (LL)=R

RT2 ( LL) =PG+2*MMP+L?

11 IF (FLAG (12) .^0.0) 00 TO 1?

LL=LL+1

RT1 (LL)=R

RT2 (LL) =po+2*nnp+mmq+l?

12 LBFG=NTRANS+1

DO 13 L=LREG» LL

TMODE ( L ) -MOD

13 CONTINUE

NTRAN5=LL

RETURN

END

-113-
OiOOOOOOIOOOOOO

B.2.U Subroutine XSCHED

SUBROUTINE XSCHED ( Ml) » NOOE» P» ZK » XZ^ »POS» RB ASF »P0)

This Subroutine reads IN A GROUP RF POUTbS t^geThbr WTTH

ABBREVIATED SCHEDULE INFORMATION «ND PRODUCES COMPLFTF SCHEDUl b

INFORMATION FOR ROUTES In EACH RFRlon. THE VARTARl EG RRS»RBASE

ANu THE ARRAYS NM t NODE » D » ZK ARE TRANSMITTED PROM THE M A I N PROGRAM.

THE PROGRAM WRITES OUT THE DETAILED SCHEDULE INFORMATION USING

UNIT OUT = 7.

NATIONAL BUREAU OF STANDARDS MAY * l°7f>

PARAMETER

parameter

PARAMETER

PARAMETER

DIMENSION

12

C

C

C

c variables and arrays used in this subroutine

c

c input parameters

C PDS - NUMBER OF PERIODS

C RBASE - CONVENIENT REFERENCE BASF FOR ABSOLUTE ROUTF NUMBERS

C ZK(J) - CONVERTS DISTANCE INTO T T MF FOR PERIOD J

C _ C ROUTF DESCRIPTION

C NN ( R ) - NUMBER OF NODES ON ROUTE R

C NODE ( R r I ) - THE I-TH NODR ON ROUTE R

C D ( R » I ) - THE I-TH TNTERST OP DISTANCE ALONG ROUTE R

C

C ADDITIONAL VARIABLES AND ARR AYS_ (FROM UNIT 5)

C NR - NUMBER OF ROUTES IN A GROUP

C ROUTE (J) - THE J-TH ROUTF OF THE GPOIIP

C RUNS ( I ) - NUMBER OF RUNS BOR PERIOD T C HE AD ( I ) - HEADWAY FOR ROUTES IN Dfrpjon I C DTI ME ( I » J ) - INITIAL DEPARTURE TIME BOR ROUTE J TM PERIOD I C _ _

C WORKING ARRAYS

C SCHED(K) - SCHEDULE TIME FOP K-TH NODE ALONG ROUTB

C

MAXPO=1 0 0 NUMBER of

NRTeS=2O0 Q NUMBER of

MAXN=50 0 NUMBER OF

NGPOUP=100 Q NUMBER OF

PERIODS

ROUTES

NDDES/ROUTF

ROUTES/GROUP

NN(NRTES) » NODE ( NRTES » MAXN)

n ( NRTES * MAXN ) »ZK(MAXPD)

ROUTE ( NGROtiP) »RUNS^MAXPD) »‘hba'dTmA*XPD)

DTIME( MAXPD r NGROUP ) ,SCHFD(MAYN) , XZK (ma.XPD)

-llU-
or»n

o

o

r>

ooo

ooooi

non

or>o

on IMPLICIT INTEGER (A-Y)

REAL XZK " ‘ “ "

DEFINE OUTPUT UNIT.

OUT = 7

"REACTTN A GROUP' OF P0UTE5"" (SmUT RTI^TH^W"A YSTT

10 READ (S^ 900, ENR=fl0> NR-, (ROUTE ( J) > J=1 * NP ) 900 FORMAT! 1615)

FOR EACH ROUTE IN THE GROUP, READ IN THE SCHFDULE PARAMETERS RY TIME

PERIOD.

NRUNS=0

DO 20 1=1, PDS

READ ( S , 900 ) RUNS ( I ) , HEAD ( I ) , (DTIME ( I , J) ,J=1 , NR ) NRUNS=URUNS + R! INS ( I ) 20 CONTINUE

REGIN CONSIDERATION OF EACH ROUTE IN THE GROUP.

DO' 70 J=l»riR

R=ROUTE( J)

NNR=NN(R)

RT=R+RRASE

... PRI NT R OU I£S AND N Q DES ON R OUTES.

WRITE ( OUT , 800 ) RT , NNR , NRUNS , LNOpE ( R » I ) , 1=1, NNP

)

800 FORMAT(20I5)

COMPUTE SCHEDULE INFORMATION.

DO 60 II=l,PoV

SCHED ( 1 ) =DTIME ( 1 1 > J

)

Z=ZK(II)

IE (P.GT.PO) 7=XZK ( T I

)

HD=HEAD( II)

RNS=RUNS ( 1 1 ) -1 _ _ ___

DO 30 I =2, NNR

SCHED ( I )=SCHFp ( I-1) + (Z*D(R, 1-1 ) ) 3n CONTINUE

- 115-
o

o

o!

o

r>o PRINT SCHEDULE INFORMATION FO° FIRST DEPARTUpf IN PFPTOP

WRITE (OUT » 800 ) ( SCHED ( I ) » T = 1»NNR)

IF(RNS.EQ.O) go to go

DO 50 K=1*RNS

DO 40 1=1 » MNP

SCHED ( I ) =SCHEP ( I ) +HD

40 CONTINUE __ PRINT SCHEDULE INFORMATION FOR REST OF PERIOD.

WRITE (OUT » 800) ( SCHED ( I ) » I=1»NNR)

50 CONTINUE

60 CONTINUE

70 CONTINUE

GO TO 10

80 ENDFILE OUT

RETURN

END

-
noo

0.0

0

ooooooooooooooooo

ooooooooooooo

B.2.5 Subroutine TRANS

SUBROUTINE TRANS(NTRANS»TNO0F»RTl#RT?»PQ» r’RASn

this subroutine writes out using unit out = «» the transfer

INFORMATION PREVIOUSLY GENERATED By GRID. THE ROUTr NUMBERS

PRINTED ARE ABSOLUTE (I.E. NUMBERS RUN CONSECUTl VR. Y fROM RRASE).

The VARIABLES P0»RBASE»NTRANS AMD THE ARRAYS TNODF » RTI r RT2

ARE TRANSMITTED FROM THE MAIN PROGRAM. THF ARRAY tmTM IS READ FROM

UNIT IN = 12.

NATIONAL BURFAU OF STANDARDS MAY»197G

PARAMETER TRANSF=50G0 5> NUMBER OF TRANSFERS

PARAMETER MNODE=1000 0 NUMBER OF MODES

DIMENSION TNODE(TRANSF) > RTI (TRAnSF) »RT2(TPANSF1 »TmIn(MNODE)

variables and arrays used in this subroutine

input parameters

RRASE - CONVENIENT REFERENCE BASF F0R ABSOLUTf ROUTE MUMPERS

TMINJI) - MINIMUM TRANSFER TIME BETWEEN ANY TW O P 0UTES AT NO OF I TRANSFER NODE DESCRIPTION

TNODE(L) - THE L-TH TRANSFER MODE

RTI ( L ) - ROUTE FROM WHTCH TRANSFER IS MADE AT TNODE ( L

)

RT2(L) - ROUTE TO WHICH TRANSFER IS MADE AT TUODF f L ) NTRANS “ NUMBER OF TRANSFERS

IMPLICIT INTEGER (A-Y)

DEFINE INPUT AMD OUTPUT UNITS.

IN=12

0UT = 8

READ IN MINIMUM TRANSFER TIMES AT EA r H NOnE.

READ ( IN » 900 ) ( T M I N ( I ) t 1 = 1 1 PqI

900 FORMAT (1615)

-117-
oo

r> PRINT TRANSFER NODE INFORMATION.

DO 10 l=i»ntrans

R 1 =RTl(L ) A sT

R2=RT2 (L) +RB'SE

TNrTNODETO

WRITE (OUT* 800 ) TN * R 1 r R2 » Twin ( TN

)

800 FORMAT ( 4 1 5

)

10 CONTINUE

ENDFILE OUT

RETURN

END

-118-
B.3 PROGRAM TRA

PARAMETER

parameter

PARAMETER

DIMENSION

1

MNOPE=20Q

M?1 r 2 0

MN=50

RTE(MNODE»MN) * STP ( MM )

,

MINTRA CMMOOF ) ,NSTP(MN0nE)

BEriNOHE * MN)

IMPLICIT INTEGER (A-?)

DO 1 I=l»MNODE

NSTP( I ) =0

DO 1 J=1»MN

BE ( I * J) =0

1 CONTINUE

READ (5*900) NODE

900 FORMAT (2015)

READ ( 12 * 90*5) (MlMTRA ( D * T = 1 rNODE)

903 FORMAT (1615)

2 READ (7*900 »END=6) R * M » NRUNS * ( STP ( f ) » T = 1 * m

)

DO 4 1 = 1 * M

J=STP( I

)

N=MSTP ( J ) +

1

RTF ( J * N ) =R

NSTP ( J ) =N

IF (I.GT.l) GO TO 3

BE ( J * N ) =1

GO TO 4

3 IF (I.LT.M) GO TO 4

BE ( J* N) =2

4 CONTINUE

DO 5 L=l* NRUNS

READ (7*901) DUMMY

901 FORMAT (A6l

5 CONTINUE

_

GO TO 2

"

6

CONTINUE

DO 10 L=1 * NOnr N=NSTP ( L

)

DO II? 1 1 = 1 * N

IF (PE(L»JI) .EO.l) GO TO in

I=RTE (L * II)

J1=I 1-1

IF (MOD( II *2) .EQ.O) Jl = II-2

IF (Jl.LT.l) GO TO 3

DO 7 JJ=1*J1

IF ( BE ( L * JJ )

r Q • 2 ) GO TO 7

J=RTE ( L » JJ

)

WRITE (8*900) L*I*J»MINTRA(L)

7 CONTINUE

-119-
R J1=II+1

IF ( MOD ( I "I » 2 ) . EQ» 1 ) J1 = II+P

IFJJKGT.M) GO TO 1C

DO 9 JJ=J1*N

IF (PE(L» JJ) .FQ.2) GO t 0 q

J=RTE(L» JJ1

WRITE ( 8 » 900 ) L»I»J»MIMTRA(L)

9 CONTINUE

10 CONTINUE

~ERdFTlT~5

STOP

END

-120
B. 4 FR'JGRAM ACYCI..E

C

C

rC

C

C

CC

C

C

c

cc

c

cc

cc

ccc

c

c

c

cc

cc

cc

cc

c

cc

c

****************** ACYLE : ACYCLIC Tc ANSI. ATO° ******************

THIS PROCRAM PROHHCFS AN APPROPRIATE TT MF -EXPANDFr> NFTwOPK FPQM

GIVEN SCHEDULE INFORMATION AN" TcMNS r FP TATA. F

A

r H a'ODF OF TpF

TIME-EXPANDED NFTWORK REPRESENTS A PARTICULAR (STap,TTmF) PAIR.

TRANSFFRS ARE ACCOMMODATED USING TRANSFER AR^S WITH TME FICTITIOUS

ROUTE 9999 .

NATIONAL BUREAU OF STANDARDS JULYr 1076

COMPILER (XM= 1 ) PAPAMFTER may

s

=

1

O' PARAMETER

PARAMETER

PARAMETER

DIMENSION

COMMON

COMMON

/RLK 1 /

/RU<2/

Q NUMBER OF STORS/ROIITF

Q NIIMRFR OF RCIJTFS

O NUMBER of NODES

Q NIJMRFR OF APCS_

NODE ( MAXS ) t SCHED (MAYS) , FT ART ( NRTES ) r fnp'(MRTES)"

N(MAXN) »T(MAXN) »Tt(MAXN) » TIND ( MAYN )

NEW ( MA YN

)

FPOM(MAXA) f TO ( MAX A ) fRTE(MAXA) »FF( mAXA)

E I Nr

(

ma X A )

NRTFS=?00

MAXN=4S00

MAXA=13000

VARIABLES AND ARRAYS USFD IN TlTlS PR(V5 RA"w“

INPUT VARIABLES AND ARRAYS

RT - ROUTE NUMBER

NN - NUMBER OF STOPS ON ROUTE

RUNS - NUMBER OF RUNS

NODE ( I ) " THF I-TH STOP ALONG THF ROUTE

SCHED(I) - THF I-TH SCHEDULF T I MF ALONG THE ROllTF

TNCDF - ST

0

D AT WHICH TRANSFER OCCURS

RT 1 - ROUTE FROM WHICH TRANSFER AT TmODE

RT? - ROUTE TO WHICH TRANSFER AT TNOnF

TMIN - MINIM'JM TRANSFER TIME AT TMODF

CONSTRUCTED ARRAYS

r ; ( I ) - STOP ASSOCIATED with NETWORK MODE I T ( I

)

- TIME ASSOCIATED WITH NETWORK NODE T START ( R

)

- FIRST POSITION WHERE INFORMATION May RF FOUND

FOP ROUTF R ON N0OF LIS^

END(R) - LAST POSITION WHERE INFORMATION MAY RF FOUND

FOR ROUTE P ON NODE LIST

- 121-
r>o

o

C LLEN - LENGTH OF NETWORK NODS LIST

C EROM(J) - STARTING NOD^ OF ARC IM POSITION J or /\oq lIS t

c totj) - ending nodf of arc Tm position j pf arc' i 1st

*

C RTE(J) - ROUTE NUMPER CORRESPONDING TO A^r in POSITION J

C OF ARC LIST

C MLEN - LENGTH OF NETWORK ARC LIS T

C

C WORKING ARRAYS

C

" * ' ~ - ' ' *

C TT ( I

)

- THE I-TH ORDERED ELE^FNT OF T

C T I ND ( I ) “ THE POSITION IN T OF T HE T-TH FLEMFNT OF ff

C _ NEW a) - TUP POSITION IN 7T_0f THE I-TH fUfME^T Of _T_

C FF ( I ) - THE T-TH ORDERED ELEMENT’ OF FROM

C FIND ( I ) -TIE POSITION IN FROM OF THF I-TH FLFMFMT OF FF

C

C —

c IMPLICIT INTEGER (A-Z)

DEFINE INPUT UNITS.

IN1 = 7 Q INPUT FILF FOR SCHEDULE n AT A IN2=8 0 INPUT FILE FOR TRANSFER DATA

CC »EGIN PROCESSING SCHEDULE INFORMATION. CREATE NODES AND ARCS

C OF THE TIME-EXPANDED NETWORK.

C

L. — 0 __ M=0

c _ _ _

C READ IN ROUTE* AND SCHEDULE DESCRIPTION. CONSTRUCT NOKE ANO AR

C NOTE THAT ONE MUST HAVE NN > 1 AMD RUNS >0.

C

10 READ( INI » O00 » <r ND=40 ) RT » NN f RUNS , ( mODE ( T ) r T = 1 » MM

)

900 FORMAT (2015)

START (RT)=L+1_ _ DO 30 jj=i»RUNS

READ ( INI » 900 ) (SCHED( I ) » 1 = 1 »NN)

L=L+1

N ( L ) =MODE ( 1 ) T ( L ) -SCHED ( 1)

DO 20 J=2*NN _ . m=m+1~

FROM(m)=L

T0(M)=L+1

RTE ( i " ) =RT

L-L +

1

M(L)=NODE(J)

T(L)=SCHET)( J)

2 f) CONTINUE

30 CONTINUE

- 122-

!<J
EWRT ) -L

GO TO 10

40 LLEN=L

C

C READ IN TRANSFER DATA AND UPDATE ARC LTS t . c 50 REAP ( TN2» O00 r FND = A0 ) TNODf7 » RTl » RT2 r TMJN

LS1=START(RT1

)

LF1=END(RTI)

DO 7o L=LST»LFl

IF (N(U .NF.TMQDF) GO TO 70

TM=T(L) +TMIN

LS2=ST ART ( RTP ) LF2=EMD(RT2)

DO 60 LL=t S2>LF2

IF ( N (LL ) .NE.TMODE) GO TO 60

IF(T(I.L ) .l-T.TV) GO TO 60

IF (LL.FQ.LF2) GO TO 5~5 IF(N(LL) .FQ.N(LL + 1) )GO TO (AO

55 M=M+1

FROM ( M ) =L

TO(M)=LL

RTE(r)=9999

GO TO 70

60 CONTINUE

70 CONTINUE

MLEN=M

GO TO 50

C

C SORT NODE ARRAY BY TIME.

C

80 CALL SORTP(T»LLEN»TT»TIND)

DO 90 1 = 1 » LLEN

J=T I ND ( I

)

NEW ( J ) =

I

^0 CONTINUE

C

C RENUMBER NODFS IN ARC LIST.

C DO 100 1=1 >MLFN

K l=F'RO: i(I)

K2=I 0 ( I

)

FROM ( T ) =NEW ( K 1

)

T 0 ( T )=NEW(K2)

100 continue

c

C SORT ARC ARRAY n Y ORIGIN NODr • C CALL SOR TP ( FROM » MLEN » FF » FIND )

- 123-
o

o

o

r>

r> WRITE OUT NETWORK NOPE DATA, SOPTr

C "M T.

OUT 1 =9 n AFFINE OUTPUT UNIT FOR * OOP D*TA

.

DO 110 1 = 1 r LLEN

J=TIND( I

)

WRITE (OUT 1» 901) M (J)»T ( J)

901 FORMAT ( 3 I E

)

110 CONTINUE

ENDFILE 01 IT 1 WRITE OUT ARC DATA* SORTED RY ORIGIN N'PD r • 0UT2- 10 DEFINE OUTPUT UUTT F^P ARC DATA.

DO 120 1 = 1 f ML^N

J=F I NO ( I

)

WR I TE ( OUT 2 » 90 i ) FROM ( J) ,T'MJ),RTF'J)

120 CONTINUE

ENDFILE 0UT2

STOP

END

-124-
.1 Subroutine SORTP

SUBROUTINE SORTP(X,",Y, xPOS)

THIS ROUT I ME" SORTS THP rLFWrNTS OF THF INPUT Vt-rTnD X AMD PUTS THF SORTED

ELEMENTS INTO THE VF^TOR Y. IT Al SO CARRTFS Ai ONG THF INDEX NMwBFR

OF EACH ORnE Q F(l OBSERVATION—THftT IS, TT CARRIFS a| OMG THP POSITION OF

THE T-TH OROFrED OBSERVATION (FOP EACH I) AS TT WAS IN THE ORIGINAL

UNORDFRED DATA VECTOR X. ThESF POSITIONS ARE PL AOFO IN THE VF^TOR xPOS.

THIS ROUTINE IS USEFUL IN ATTEMPTING TO LOCATF THP MINIMUM, Th^ maximum,

OR SOME OTHER ORDERED OBSERVATION OF INTEREST TN THE ORIGINAL 1 'nORD'ered

INPUT VECTOR X.

THE INPUT To THIS ROUTINE TS TH£ SlNGLF PRFCISTON VECTOR X OF

(UUSORTED) OBSERVATIONS* THE TMTFGFR V/ALUF n (r SAMPLE SI 7 F)

AN EMPTY SINGLE PRECISION VFCTOR Y INTO WHTCH ThF SORTED OBSERVATION

WILL RE PLACED, AND AN EMPTY SINGLE PRFCISTON RECTOR XPOS INTO wHIO H THE

POSITIONS OF -

THE SORTED OBSERVATIONS WILL" BE Pt A~CFn.'

THE OUTPUT FROM THIS PONTIME I c Thp SINGLE PRECISION VFCTQR Y TmTo WHICH

THE SORTED OBSERVATIONS HA VF BEEN PLACED* AND ThF SINGLE PRFCISION VECTOR

XPOS INTO WHICH THF POSITIONS OF THF SORTFD OBSERVATIONS HA VF BEEN PLACED.

RESTRICTIONS ON THE maximum ALLOWABLE VALUE OF N —ThF DIMENSIONS

OF VECTORS IN A_ND I_L (DEFINED A ND US ED INTERNALLY WIT HIN THIS ROUTTn[Fj_

DETERMINE THE MAXIMUM ALLOWABLE VALUE OF N FOR THIS

ROUTINE. IF IN AND IL EACH HAVE DIMENSION jO THFN_ N MAY MOT EXCEED _

?**(K+1) ~ 1. FOR THIS ROUT lN r AF WRITTEN* THF DIMENSIONS OF TU Amq xi HA VF BEEN SET to 56* THUS THE m AX tmuM ALLOWABLE VALUE OF N IS

APPROXIMATELY 157 BILLION. SINCE THIS EXCEEDS THF MAXIMUM ALLOwARI.E

VA_LUE FOR an TNJEGER VARIARLE in man y COMPUTERS , AND SINCE A SORT OF 137

BILLION ELEMENTS IS PRESENTLY IMPRACTICAL AND "NLTKELY, THEREFORE No"

TEST FOR WHETHER THE INPUT SAMPLE SIZF N FXCEFos 1 57 BILLION HAS BEEN

INCORPORATED INTO THIS ROUTINE. TT IS THUS ASSUMFP THAT THERF IS No

(PRACTICAL) RESTRICTION ON Thc MAXIMUM VALUE Or N FqR THIS ROuTlNF.

PRINTING—NONF UNLESS AN FRROR CONDITION FXISTS

this rout tie i s sin gle precision i n internal oper ation.

SUPROUTIMFS NEEDED —NOME

SORTING method —binary sort

REFERENCE —CACM m A PCH 1Q69* PAGE 1 «6 (BINARY SORT ALGORITHM BY RlCH A Rn

C. SlNGLF TON. —CACM JANUARY 1970, P AG P 54. —CACM OCTOBER lP7u* P AGF 624. —

j

ac m January iqgi* pagf 4i.

WRITTEN BY JAMES J. FILL IREN* STATISTICAL

NATIONAL BUREAU OF STANDARDS* WASHINGTON,

FNGI m FFRTMG

D.C. 20254

LABORATORY (BOR. 03)

JIImF lQ7p

DIMENSION x ( i ) , Y

(

1 ) , XPOS ( 1

)

D I MENSI ON T

U

( 36) * I L ( 36

)

IMPLICIT INTEGER ( A - 7

)

CHECK THE INPUT APGUM ENTS FOR ERRORS

- 125-
I PR = 6

1F(M.LT. 1 )G0T05f

IF(N.EQ.1)GCT055 - - —

HOLD = X ( 1 ) D060 I -2. f M

I F ( y ( I ) . mf . HOlh ) GOT090

60 CONTINUE

WRITE (I PR, 9) MOLD

oo6fi=i »Ki — —

_ Y< I )=X( I >_

XP05 ( T )

I

t> 1 CONTINUE

RETURN

GO WRITE( IPR» 15)

WRITE ( I PR , 47 )

N

RETURN

55 WRITE ( IPR» 16)

Y ( 1 ) =X< 1

)

XPOS(1)=1.0

RETURN

90 CONTINUE

Q FORMAT ( 1H , ln^H***** NON-FATAL DIAGNOSTIC —THE FIRST INPUT ARGUMF

1UT (A VFCTOR) TO THP SORTp SUBROUTINE HAS ALL FLFMENTS = »E15.8»6

1H  )

15 FORMAT (1H , 91 H** *** FATAL ERROR —ThE SEC^!D~TmFUT ARSUMFNr TO TW

1 SOFTP SUBROUTINE IS MON-POSITIV^  )

18 FORMAT (1H , 100H** *** NON-FATAL DIAGNOSTIC —THF SECOND INPUT APGUMf

LIT TO THE SORTP SUBROUTINE HAS THE VALUE 1  )

47 FORMAT (1H , X5H** *** THE VALUE OF THE ARGUMENT IS >18 » 6H ****)

C

C COPY TUE VFCTnR X INTO THF VECTOR Y 001001=1 rN

Y ( I )=X( I

)

UiO CONTINUE

C

r DEFINE THE XPOS (POSITION) VECTOR. RfFORF SORTING » THJS WILL

C BF A VECTOR WHOSE I-TH ELEMENT IS r OUA| T9 I.

C 001501=1 »N

XPOS ( I

)

= I 15C CONTINUE

C _

c check' to see te the input vector ts already sopTEn

c N

4 1=N-1

0020 0 1 = 1 > N'M

IP1=I+1

I E ( Y ( T ) • LF # Y ( T P 1 ) )GOT0200

GOTO250

200 CONTINUE

R'TUR 1

-126-
250 M=l

1 = 1 J=N

305 IF ( I ,r-r . j) r.oT'V^'f

310 K -

I

mip=

(

i+j ) /?

AMEO=Y(Min)

BMED=XPOS(Min)

IF ( Y ( I )_.LF. AMFO) GOTO320

V (Min') =Y( T ) xpos(mid)=xpos( i

)

Y(I)=AMED

XPOS ( 1 ) =PMrn

AMED=Y (MIO)

nMEn=Ypo5 ( mi,))

320 L=J~

IF ( Y ( j ) . GF • AMEO ) GOT0340

Y(MID)=Y< J)

XPOS(MID)=XPOS( J)

Y( J)=AMEP

XPOS ( J ) =RMED

AMEn=v (Min)

BMED=XPOS(MIO)

I F ( Y ( I ) .LF.AMED)GOT0340

Y (MID)=Y( I

)

XPOS (MID ) =XPOS ( T

)

Y ( I ) =AMED

XPOS( I)=RMFD

ameo=y (M in)

BMEn=xPOS(Min)

GOT0340_

330 Y(L)=V(K)

XPOS ( L ) = XPOS ( /

)

Y (K) =TT

XPOS ( K ) — I TT

340 L=L-1

IF <Y (LUST. A Tr')GOT034_0

TT=Y(L)

ITT=XPOS(L)

350 K=K+1

IF(Y(k).LT.A TO ) GIT 0350

IF(K.LE.L) 00FOX30

lmi=l-i

JMK = J-I<

I F ( L M I LF • JMK ) OOTO360

I L ( M ) r I ILJ(M)=L

I=K

GOTt^'V

-127
360 IL(M_)=K

I U ( M ) 2J

J-L

M=M+1

G0T038 Q

_

370 M=M-1

IF (M.EQ.O) RETURN

I=IL(M)

J=IU(M)

38 f' JM I — J— I IF ( JMI .GF.ll ) 30T0310

TFTl .EQ. 1 )“^OT0305

1 = 1-1

39u 1=1+1

IF ( I . FQ . J ) GOT 0370

AMED=Y ( 1+1

)

BMFO=XPOS( 1+1 ) _

I F ( Y ( I ) .LF .A , ’Fpy'6OTO390

K = I 395 Y (K+l )=Y(K

)

XP0S(K+1 )=XP9S(K)

K = K-1

IF ( AMEO • LT . Y ( !< ) )G0T0395

Y (K+l )=AMFH

XPOS (K+l ) =RMrn

GOT0390

Etjd
r>

o

o

o

B.5 PROGRAM LABCOR

C

C

CC

c

c

cc

cc

cc

cc

c

c

c

c

cc

c

c

c

c

c

PARAMETER

PARAMETER

parameter

parameter

PARAMETER

parameter

PAP AMFTER

PARAMETER

MR- 100

MMR=MR+

1

MSrlPO

Ml, -MS

MSR=12

MRS=20

MQ=3000

MPr6

Q max MUMPER OF RQilTFS

Q max NH\1bfR OF STOPS

ft MAX POSITIONS IN L

IrJ '^x mu.mbfr OF STOPS Pfp route

ft M AX NUMPFR OF ROUTES PFR STOP

ft max N'lviBFP OF VEHICLF DEPARTURES

~Q max MUMPER of SFGMENTS ’ PFR PATH

PARAMETER MMn=MP+l

IMPLICIT INTEGF p (A-7)

REAL ROUT

DIMENSION T ( MS ) » TB ( MS ) » PS ( MS ) » PR ( MS ) » L ( ML ) »F(MS) »NR(MS)

12

3

NS (MR) f SR EG ( MMR ) r STOP ( MR t MSR ) »MINTRA (MS)

r

RO' ITE ( ms , MRS ) » SCHED ( MO » MSP ) * SPp T ( MMP ) , RPRT ( MP )'

t

T p PT ( MP ) r TBPPT(MP) , SEND

(

mmr)

ARPAYS USFD IN THIS PROGRAM

STOP INPUT

MR ( S)

ROUTE ( S » J

)

vjwTRA ( S

)

NUMBER OF ROUTES STOPPING at s JTM ROUTE STOPPING AT s MINIMUM TIme REOUIRFP TO TPANSFrp RPTWEEN ROUTES

AT NODE S

ROUTR INPUT

MS(R)

ST

0

P ( R » I

)

SBEG(R)

SEND ( R

)

SCHED ( K f I

)

ALGORITHM

L (S)

F (S)

T ( S

)

TB ( S

)

PS(S)

PR (S)

- NUMBFR_ Of _ST OPS Oil ROUJF_R_

- ITH STOP ON' ROUTE R - LOCATION IN THF SCHEDULE LTST O p THF FIRST

SCHEDULED DEPARTURE FOR ROUTE P - LOCATION IN THE SCHEDULE LTST OF TmF LAST

SCHEDULED OFPARTURF FOP ROUTE R

- ARRIVAL TIME AT THF ITH STOP OF THF «TH DFPARTDRF

C - SEQUENCE LIST OF STOPS TO FAN OUT p R 0 M

- POSITION OF STOP S IN LTST L - ARRIVAL TIMF AT STOP S

- BOARDING TIME FOR VEHICLE ARRIVING AJ S

- STOP PRECEDING S IN PATH TO S

- ROUTE FROM PS(S) TO S

PRINTING THE PATH

SPRT ( J

)

RPRT ( J)

TPRT ( J)

TBPPT ( J

)

STOP

ROUTF

ARRIVAL TIME

BOARDING time

INF= p 9999R990 ft INFINITY USED IN THF P ATH CALCULATION

RTSO=0

RTIMF.rO

NRUN=0

-129-
c DO 1 5=1 MS

NR (S) =0

1 CONTINUE

CC READ ROUTE INPUT

C __ “NSTOPV6 _ NR0UTE=0

K = 1 Q NUMRFR OF DEPARTURES IN TH^ SCHEDULE

2 RFAD ( 7 » 901 f EMD=6 ) P » M » KK t ( STOP ( R r J ) » J=1

)

901 FORMAT (2.0T5)

NS(R)=M

IF (P.GT.NROUTE) MROUTE=R

C

C READ SCHEDULES FOR ROUTE R

C

SBE'S ( R ) =K '

^ DO 3 KS=1»KK

READ ( 7 » 90 1 ) (SCHED(K»J) » jri*M)

K=K + 1 3 CONTINUE

SEND ( R ) =K-*1

C ADD ROUTE R TO LIST OF ROUTES STOPPING AT ^ACH STOP IN R*S STOP LTST

C

4 DO 5 1 = 1 fM

S=STCP(Rf I

)

IF (S.GT.NSTOP) NSTOP=S _

NR ( S) =NR ( ST+

1

J=NR(S)

ROUTE ( S » J ) =R

5 CONTINUE

GO TO 2

o READ (12*907) (MINJPA( I ) * 1 = 1 *NSTOD ) 007 FORMAT (1615)

C

C READ ORIGIN AMD DESTINATION

C7 READ ( 11* 9C3*END=24) ORGf HSTfTlMF

903 FORMAT ( 315) _ _ WRITE ( 6 r 904 ) ORGf DSTf TIME

904 FORMAT ( * 0 * /// * OTRIP FR0M*fl5f» TO’flSf* DEPARTING ON OR AFTER *

f

115/)

IF (TIME. GE. 1 .AMD. TIME. LE. 1440) GO TO A

WRITE (6f Q 9R)

992 FORMAT ( 5X » * MO TR I P . _ DEPARTURE TTME TS OUT OF RANGE . */)

GO TO 7

'

8 CALL CPUS* IP ( ST ART )

-130-
o

(in

kO

.

o

o

o INITIALI7F ARRAYS USFD I M THE ALGORITHM

DO 9 S=1»MS

T(S)=TNF

TR(S)=INF

PR(S)=0

P5(5)=0

F(S)=1

CONTINUE

T fORG ) = T I ME

' U=0

V = G I=ORG

TT=T( I

)

start algorithm

10 N=NR(I)

DO _1 8_J= 1 »_N REROUTE ( I » J )

" ~ M=fJS(R)

DO 11 JJ=lrM

IF ( STOP

(

p » JJ ) . FO . T ) GO TO 12

11 CONTINUE

C IF STOP(I) NOT FOUND IN ROUTE P» ERROR AND STOP

WRITE ( 6 f 990 ) 1 1 R

090 FORMAT CO*** FRROR *** ST0P»»T5C NOT FOUND ON ROUTE MS)

STOP

12 IF (JJ.EQ.M) GO TO 1ft C IF JJ IS LAST STOP ON ROUTE R CANNOT DFPART STOP I ON ROUTE R

IBEG=SBEG(R)

IEND=SEND(R)

DO 13 K=IREG* IEND

IF ( SCHEP ( K » J J ) . GE . TT ) GO TO 14

13 CONTINUE

C IF NO DEPARTURES ARE AFTER TT r TRY ANOTHER R0"T

GQ TO 18 . _ _

14 TIM=SCHED(K».IJ)

JJ=JJ+l

C TEST ARRIVAL TIMES AT STOPS AFTER STOP T dm ROUTE o DO 17 SS=JJ» M

S=STOP(R»SS)

IF (SCHED(K#SS_) .GE.T(S) ) ^

TO JJ _ _

PR(S)=R

PS(S)=I

IF (T(S) • GE . T NF ) GO TO 15

-131-
C IF S IS ALREADY ON THE LIST L» vOVF S DOWN TO f» NF'*' POSITION AMD ?FRO

C THE OLD POSITION

K_K=f_(S ) _ _ __ IF (KK.GT.O) L(KK)=0

15 T(S)=SCHED<K»SS)

Tri ( S ) — T I

M

C ADD S TO LIST L

16 V^V+1

IF (V.ST.ML) V=1 _

IF ( V . NE » U ) GO TO 161

C

C COMPACTIFY LIST L

C

25 W='J+l

i)0 26 IPOS=w»ML

IF (L( IPOST.SO'.O) GO TO 26

V = V + 1 ST=L( IPOS)

L(V)=ST

F VSTf-M

26 CONTINUE

W=U-1

IF (W.EQ.O) GO TO 16

DO 27 IPOS-1 t W

IF (L( IPOS) .EQ.O) GO TO 27

V=V+

1

IF (V.GT.ML) V=1

ST=L ( IPOS

)

L ( V ) = ST _

F(ST)=V

27 CONTINUE

GO TO 16

161 L(V)=S

F(S)=V

17 CONTINUE

18 CONTINUE

F(I)=0 _ _ _ _ IF (U.NE.O) L ( lTT=0

C STOP WHEN THE LAST STOP PROCESSED WAS THE LAST ON t hE L 1ST L

19 IF (U.E9.V) GO TO 20

U=U+1

IF (U.GT.ML) U=1

I=L(U)

IP (I. EQ.O) GO TO 19

TT=T( I ) +MINTRA ( I

)

GO TO 10

- 132-
c

C WRTTF OUT TRIP

C20 CALL CPUS' IP (FINISH)

RUNTT‘*=FINISH-ST ART

RTI^F=RTIMF + RUNTIV)

rtso=rtso+runttm*runtjm

nrun=nrun+i

WRITE (6*906) RUNT I

M

QOQ FORMAT ( 1 OX t ’RUN TIME FOR L APCOR , 1 1

0

t ’ MIL L I SECONDS ’ /

)

IF (PS(DST) .EO.O) GO TO 23

I-DST

SPRT(MMP)=r)ST

K = MP

21 II=PR(I)

RPRT ( K

)

= I

I

T3PPT ( K ) -TB ( I

)

TPRT ( F ) =T ( I

)

I=PS( I)

5PRT(K)=I

K=K-1

IF ( I IE.ORG)" GO TO 21

" K=K + 1 DO 22 J=K#MP

JJ=J+1

WRITE (6*905) PFRT( J) ,SPRT( J) »TRPRT( J) » SPRT( JJ) ,TPPT( J)

905 FORMAT (5X*’B0ARD ROUTE ’*15*’ AT STOP **T5*’ AT TTMF » » I6»

1* ARRIVE AT STOP ’ » I 5 >

* AT TTMF’ T5)

22 CONTINUE

GO TO 7

23 WRITE (6*906)

906 FORMAT (5X»’N0 TRIP FOUND*)

GO TO 7

24 R0UT=FLOAT( RTt

M

p ) /FLOAT ( NRUnF

WRITE (6*909) ROUT

909 FORMAT ( « 0’///*0AVERAGE RUrj Tl^E FOR LABCOR TS*»F1?.2*

1» MILLISECONDS’

)

ROUT=FLOAT ( NRI IN) * ROUT* POUT

NRUN=NRUN-1

ROUT= (FLOAT(RTSQ) -ROUTT /FLOAT ( NRUnO

ROUT=SQPT(ROUT)

WRITE ( 6 * Q 1 3 ) RO'JT

910 FORMAT (’OST 'HOARD DEVIATION OF RUN TIME FOR L AQCOp IS_’»F1?.2,

1* MILLISECONDS’

)

STOP

END

- 133-
oo

o

o

o

*r,

no

B. 6 PROGRAM LABSET

PA, PA ME TER

P AR A m'FTER

parameter

parameter

PARAMETER

PARAMETER

PARAMETER

PARAMETER

PARAMETER

IMPLICIT I REAL ROUT

LOGICAL HE

DIMENSION

2 SPEG(mmR)

3 SCHEQ ( MD * 4 LPRED(MS)

l ‘R -

1

00

MMP-MR+

1

MS-1P0

MSR=1?

MRSzpn

MD=‘*000

mp=g

MATrl44

1

MMD=MP+1

NTEOER (A-Z)

AD

" v-AV NUMBER or roiitfs

Q MAX NUMirFR OE STOPS

,u

' ftX Milfyqrp OE STOPS P~P ROUTE

O ' Ax NU.viRFR or R0"Trs RER STOP

ft max NUMBER OE VEHICLE DEP A p Tl IRES

ft max NUMRFR OE SEGMENTS PER D ATH

0 max arrival ttmf+i

T(MS) »TR(MS) »PS(MS) r RR ( mS ) »L(MAT) rNIR(MS) » NS ( MR ) r »SEnO(MMR) »STOP(Mq,MSR)

,

vtmtra(ms) » POUTF ( mS» MRS) » v MSR) »SPRT(MMP) t PPRT ( Mp ) , TpRT ( MP ) ,TRPpT(mP) »LSUCC(mS)

#h^aO(mS)

ARRAYS USED IN THIS PROGRAM

CC

Cr

C

cc

c

c

ccc

c

c

c

c

c

cc

c

STOP 1MPUT

NR ( S

)

ROUTE ( S» J) - MINTRA(S)

ROUTE INPUT

NS ( 9

)

STOP ( R » I

)

S9EG ( R

)

SENn(R)

SCHFO ( K » I ) - ALGORITHM

L (S)

LPRED(S)

L SUC C ( S

)

HEAD(S)

T(S)

TP ( S

)

ps rs )

' * - PR ( S

)

NUMPER OE ROUTES STOPPING AT s JTH ROUTE STOPPING AT S

MINIMUM TIME TO TRANSFER B

r TwFEM ROUTES AT NODE s NUMBER OF STOPS ^N. R_r-y Tr R ITU ’stop 6-1 ROUTE R LOCATION! IN THr SCHEDULE L T ST QE THE FIRST

SCHEDULED HEP APTi IRE FOR ROUTE R LOCATION IN THr SCHEDUl r LIST OR THE LAST

SCHEDULED PEPAPTuRr FOR RO"TE r. ARRIVAL TIME AT THE IJH STOP OE THE kTH DE_PAPTuRE

SEQUENCE LTST QE STOPS TO c an O' it from

PREDECESSOR MOPE Tp 'ODE S TN C^AIM OF NOOES

REPRESENTING a LCV r L TN SEOHENCF LT^T L. IF S

HEADS THE CHAIN (HEAP ( S) = . TRUE.') r THIS POINTER

G I

V

r S THE POST T I ON OE S IN THE SEQUENCE LTST.

SUCCESSOR NODE To MODE' S IN CHAT~m OE NODES

REPRESENT I NG A LEVEL In LIST L.

LOGICAL VARIABLE USED TO INDICATE WHETHER S

HEADS a CHATN TN L.

ARRIVAL TI"F at STOP s POARDlNG TIME EOr VFHICI E ARRIVING AT S

STOP" Preceding S' in path to s ROUTE FROM PS(S) TO S

-13U-
c

cc

cc

c

c

PRINTING Thp'P'Th

SPPT ( J)

RPRT ( J

)

TPRT(J)

TBPRT ( J)

STOP

ROUTT

ARRIVAL TlMF_

BOARDING TlMf

INF=Q99999999 S3 INFINITY USED IN THE ^ATh CALCULATION

rtime=o

NRUN=0

RTSQ=0

DO 10 S=1»MS

NR(S)=0

10 CONTINUE

CC READ ROUTE INPUT

C

NSTOP=0

NROUTE=0

K=1 frl NUMBER OF DEPARTURES IN THF SCHEDULE

20 READ (7»270» FjD=B0) R » M » KK » ( STOp

(

p

,

j) , j=T, M

I

NS ( R ) —

M

IF (R.GT.NROUTE) NROUTE=R

CC READ SCHEDULES FOR ROUTE R

C SBEG ( R ) =K

DO 30 KS=1»KK

READ ( 7 » 270 ) ( SCHED ( K » J ) » J=] » M

)

K=K + 1 30 CONTINUE

SEND ( R ) =K — 1 _ _____ _ C

C ADD ROUTE R TO LIST OF ROUTES STOPPING AT TACH STOP IN R*S STOP LIST

C DO 40 1 = 1 »M

S=STOP(R» I

)

IF (S.GT.NSJOP) NSTOP=S __ _ :mR(S)=nr (S) + i J=NR(S)

ROUTE ( S » J

)

= R

40 CONTINUE

GO TO 20

50 SBEG

READ

( NROUTF+

( 1 2 » 280

1

)

) =K

(MINTRA ( I ) » 1 = 1 » MS TOP) _____

CC READ ORIGIN AND DESTINATION

C

- 135-
60 REAP (11»?90»FND=260> ORGtOST,

T

j wf

WRITE (6*300 ORG»DST*TIMr W (TIME'.GE. 1. AND. TiMF.LE. 1440^ GO TO

WRITE (6*300) ORG*DST»TTMr

WRITE (6*310)

GO TO 60

70 CALL C^USUP (START)

CC INITIALIZE ARRAYS USED. IN" THE ALGORITHM

" “ " " ~ "

C

DO 80 S = 1

S

T(S)=inf

T8(S)=INF

PR(S)=0

PS(S)=C ------ • —

LSUCC (S)=0

LPRE0(S)=n

HEAD(S)=. FALSE.

80 CONTINUE

T(ORG)=TIME

T-ORG

TT -T ( I

)

U=TIME+1

DO PO S=U*MAT

90 L(S)=0

C

C START ALGORITHM

C

100 N=NR(I)

DO 200 J=ltN _

R=ROUTE< I * J)

M=NS(R)

DO 110 JJ=1»M

IF ( STOP ( R * JJ ) . EO . I ) GO TO 1?0

110 CONTINUE

C

CTF STOP(I) NOT FOUND IN ROUTE R» ERROR AND ST^P

C

WRITE (6*320) I»R

STOP

120 IF (JJ.EQ.M) SO TO 200

C _ C IP JJ IS LAST STOP ON ROUTE R CANmOT nEPART STOP I ON ROUTF R

C

I8EG=SNEG(R)

IEND=SEND(P)

DO 130 K = IPE6» TEND

IF (SCHEDCK* JJ) .GE.TT) GO To _^4£

130 CONTINUE

-136-
cC IF NO DEPARTURES ARE AFTER TT , TRY ANOTHER RO'iTF

C GO TO 200

1^0 TIM=5CHEp(K» J J) _ JJ-JJ+1

"

C

C TEST APRIVAL TIMES AT STOPS AFTER STOP I ON Route p

C DO 190 SS=JJ»M

S=STOP(R»SS)

I F ( SCHED ( K » SS ) . GE « f ( S ) ) GO TO 190

IF ( T ( S ) .GE. T *j p ) GO TO 170

CC IF S IS ALREADY ON TH^ LIST* REMOVE IT.

C

X-LSUCC (_S) Y = LPRED ( S T

IF (HEAD(S) ) GP TO ISO

LSUCC ( Y)=X

IF (X.NE.O) GO TO 160

GO TO 170

150 L(Y)=X

IT (X.FQ.O) Go' TO T70

HEAD ( X ) = . TRUE

.

160 LPRED ( X ) -

Y

C

C PUT S ON THE SEQUENCE LIST.

C_

170 "Y=SCHED ( K * SST+1

X=L(Y)

L(Y)=S

LSUCC (S)=X

HEAD ( S ) = • TPl F

.

LPRED(S)=Y

IF (X.EQ.O) G p TO 180

LPRED ( <)=S

HEAO(X)=. FALSE.

180 T(S)=SCHEP(K »SS)

TB(S)=TIM

PR(S)=R

PS(S)=I

190 CONTINUE

200 CONTINUE

C

C STOP WHEN POINTER RFACHES DST OP WHEN A COMPLETE PASS

C PRODUCES NO NEW ADDITIONS TO THE SHORTEST PATH TRE r • C

- 137-
210 I=L(i ) TF (I.M.O) on to 211

U=U + 1 IF (U.'fiT.M^T)'GO TO 220

GO TO 21?

211 IF (I.FQ.PST) on TO 220

TT = T( I ) +MirJTrM( T ) V= LSUCC ( I

)

L(U)=V _

IF (V.ro.0) GO TO ICO

" LPREp(v)=«'

HFAP( V)=.TRUF.

GO Tf ion

c

C WRITE OUT TRIP _

C

220 CALL CPUSUP (FINISH)

RUNTIM=FIMTSH-START

RTIME =RTI mf +ri INT I

M

rtsg=rtsq+runttm*runtim

NRUM-NPUN+

1

WRITE ~(6»340) RUNTTM

IF (PS(DST) .FG.O) GO TO 250

I -DST

SPRT (w».p)=DST

K = MP

2 30 II=PR(JJ

R PR T ( K ) — 1

1

TBPRT(K)=TB(T)

TPRT(K)=T(T)

I=PS< I

)

SPRT ( K ) -

I

K=K-1

IF (I. riE.ORG) GO TO 230

K=K + 1 00 240 J=KrMP

JJ=J+1

WRITE ( o » 350 ) RpRT ( J) » SPRT ( J) » TBPRT ( J) » SPRT ( JJ) » TpRT ( J)

240 CONTINUE _ _

GO TO 60

250 WRITE (6>36 CJ

GO TO 60

260 _ROUT=FLOAT (RTIMF) /FLOAT (NRIIM) _

WRITF (6*370) ROUT

ROUT = FLOAT(NP' IN) *ROUT*ROUT

NRUN-NRUN—

1

ROUT= ( FLOAT (RTSO) -ROUT) /FLOAT (NRUM)

ROUT=SORT (ROUT)

WRITF ( 6 » 3 0 0 ) ROUT

STOP

- 138-
270 FORMAT

2F0 FORMAT

2°0 FORMAT

300 FORMAT

2/)

310 FORMAT

320 FOP MAT

340 FORMAT

35 0_. FORMAT

2 ' ARR

360 FORMAT

370 FORMAT

1* MILL

3B0 FORMAT

( 2015 )

( 1 * 15 ) (315)

( *0'///*0TRlP FROM* r I * » * TO , »I e'»* nrPARTTNfi ON OR AFTER *

T 5

(5X» * fO TRIP.

( » 0*** FRPOR

DFPAPTURF TT vF TS OUT OF RflMfiE.*/) *** SToP'»T5r* MOT FOUN" Or« ROUTE* » IF)

( 1 OX r * RUN TIMF FOR L ABSFT » 7 T 1 0 » * MTLL ISFCOMDS » / >

( 5X fj RO/\RO__ROUTF_ * 1 15» * AT ST OP * r T5» * AT TTmF' rJF*

*- STOP • » I?r * AT TIME • TP

)

AT

( 5X » 'NO TRIP FOUND'

)

( »0'///»0AVEPAGF RUN

SECONDS*

)

costandard deviation

time FOR LABSrT IS»»F1?,2,

OF RUN TIME FOR iapSFT IS'»F1?.2

1* M

I

UL I SECONDS*)

C

c END

- 139-
O

O

O

O

olo

0^0

O

O

O

O

O

O

OlO

ojo

0.0

O

O

O

O

j

'O

O

O

ojo

O

O

o!o

OlO

Oio

o

o

o|o

B.7 PROGRAM TIMEXD ********** TIMEXD: DEPARTURE ORTENTRD CRITERION **********

This program us^s a time-fxp^jded representation 'in order to

CALCULATE THF BFST PATH FROM A GIVEN ORIGIN TO A GIVFN DESTINATION TO DEPART AFTER A SPECIFIED TIME (AND ARRIVE AS EARLY AS

POSSIBLE). INPUT CONSISTS OF THE NODE AND ARC DATA FOP THE

time-expanded network togfther with a LIST op trips For which

trip itineraries are required, output consists OF AM ITINERARY

For each trip > The calculation time in milliseconds eor each

TRIP AS WELL as the AVERAGE AMD STANDARD DEVIATION OF CALCULATION

Times for all trips in The l i St

.

NATIONAL BUREAU OF STANDARDS' JULY.' 1976

PARAMETER MT-1600 Q NUMBER OF MINUTES

PA RAMETER MAX-100 0 NUMBER OF RPUTES/PATH

PARAMETER NODES=4500 3 NUMBER OF NODES

PARAMETER ARCS=1300C 0 NUMBER OF ARCS

DIMENSION N( MODES) rT (NODES) »P( K 'ODES) .ARC (MODES) ,PRTE( NODES) »NN( mT)

1 . TO ( ARCS) .RTE( ARCS) . PATHM ( MAX ) .P ATHT(MAX ) .PATHR(MAX_)

REAL ROUT

variables and arrays used in this program

NODE AND ARC DATA

N ( I r

"stop associated wi th network node I T£I) - TIME ASSOCI ATED W ITH NETWORK MODE I ARC ( I

)

- LAST POSITION WHERE INFORMATION MAY BE

FOUND FOR NODE I IN ARC LIST

TO ( J) ~ ENDING NODE OF ARC IN POSITION J OF' ARC LIST

RTE(J) - ROUTE NUMBER CORRESPONDING TO A9C IN POSITION

J OF arc list

_NN(T) - NODE CORRESPONDING To TH^ FIRST OCCURRENCE 0F_

TIME T OR" LATER

NODE - NUMBER OF NETWORK NODES

INPUT VARIABLES FOR TRIP

ORG - OESIRF.n ORIGIN STOP OF Trip

DST - DESIRED DESTINATION STOP OF TRIP

TIME - TIME <\T OR AFTER WHICH TRIP IS TO BEGIN

-lLo-
ooo

,

oooooo

C VARIABLES AMD ARRAYS USED in ThF Al P0 R T THM

C

C DONE - FIRST NODE FOR WHICH THE nEr>T TMAT T ON STOP HAS

C DEEM ENCOUNTERED

C P(I) - PREDECESSOR NODE TO MO^E T ALOMG CURRENT PATH

C PRTE(I) - RO'JTE INTO MODF I ALOUD THF CURRENT PATH

C

Z~ ARRAYS USED I>' PRINTING THF PATH

C

C PATHN(K) - STOP IN POSITION K ALONG PATH

C PATHT(K) “ TIME IN POSITION K ALONG PATH

C PATHR(K) - ROUTE It) POSITION K ALONG PATh

C

C VARIABLES USED IN TIMING CALCULATIONS

C

C DIFF - CPU TIME (IN MSECS.) USED IN GALC"LATImc ONE TRIP

C RTIME - CUMULATIVE SUM OF DlFF»S

C RTSQ - CLTMULATIVF SUM OF SQUARES OF DIFF’S

C NRUM - NUMBER OF TRIPS CALCULATED

C ROUT - USED IN PRINTING AVERAGE AMD STANDARD DEVIATION

C OF TRIP CALCULATION TIMES

C IMPLICIT INTEGER (A-Z)

READ THE NETWORK NO n F DATA. SORTED ON T. ASSUME ALL T < I ) > 0.

THE SCHEDULE TIMES ARE GIVEN Up TO lfiOO MINUTES.

1 = 1 TT = 0

ini =9 q input unit for node data

100 READ ( INI » 900 . END=1 03 ) N(I)»T<T>

900 FORMAT (315)

IF ( T ( I ) .EQ.TT) GO TO 102 __

TN=TT+1

TM=T ( I ) DO 101 J=TN»TM

NM( J)=I

101 CONTINUE

TT=T ( T

)

102 1 = 1+1

GO TO 100

103 NODE =1-1

READ THE ARC DATA» SORTED RY ORlGI** NODr.

L = 1 K = 1 IN2 = 1 0 D T’lPi'T UNIT FOP APC DATA

-lLl-
o

oo

O'

n

o

0

0,00

104 READ( IN2»900»END=107) T » TO ( L ) » P TF ( L

)

IP(I.EO.K) GO TO 1C6

K M= I -

1

DO 105 J=K»K*

ARC ( J ) =L-1

105 CONTINUE

K = I 106 L=L + 1 _G0 TO 104

107 DO 1C6 J-I » NODE

ARC ( J)=L-1

10ft CONTINUE

WRITE (6>910)

910 FORMAT f 1 H 1

)

NRUN—

0

RTlf'fEO

RTSO=0

READ OR_I G IN » DESTINATION AND DES I REn_ST ACTING TIMF( ASSUMED TO RF

BETWEEN 1 AMD 1440» INCLUSIVE!.

IN3=11 Q INPUT UNIT FOR TRIP DATA

200 READ( IM3*900rEND=500) ORG t DST * T I’ir

WR ITE ( 6 * 911) ORG t DST » TIME

911 FORMAT ( //1H0 » •TRIP FR0M*»I5»* To*fT5»* DEPARTING ON OR AFTER *

115/)

IF(TIME.LT.1. OR. TIME. GT. 1440) GO to 405

IF (TINE.GT.TT) GO TO 406

CALL CPUSUP(STIME)

INITIALIZE PATH ARRAY.

00 201 1 = 1 » NO^E

P(I)=n

PRTF ( T ) =0

201 CONTINUE

BEGIN CALCULATION OF ROUTES FROM"' OPG~To"dS't“

DONE=NODE+

1

I=NN (TIME)

202 IF(N( I ) .EQ.ORG) GO TO 703

1 = 1 + 1 _

I F ( I . Gt . NODE ) GO to 4 06

GO TO 202

203 L=ARC(I-l)+l

IF(I.FQ.l) L=

1

END=ARC ( I

)

PRTI =PRTE ( I

)

-142-
r>oo

'

:

o

o

o

204 iF(ENn.LT.L) GO TO 206

IF(RTE(L) .EG.9Q 9°.AMD.PRTT .F0.999P) 60 TO 20^

J=T0(L)

P( J)=T

PRTF ( J)=RTF (L)

IF(N( J) .rjF.DST) GO TO 205

IF(D0NE.GT. J) OONE=J

205 L=L + 1 GO TO 204

206 1=1+1

IF(I .GT.NOOE) GO TO 4Q6

IF( I.fq.DOME) GO TO 300

I F ( P ( I ) .EQ.0. AND.Nt f) .NE.ORG) GO TO 206

GO TO 203

STORE INFORMATION ADOUT SELECTEO ROUTE FROM ORG TO OST.

300 M=DONE

K=MAX+1

301 K=K-1

R=PRTE ( M)

PATHN ( K

)

=N ( M

)

PATHT ( K

)

= T ( M

)

PATHR ( K ) =R_ _ __

302 M=P(M)

IF|N(M) .EO.OPGJ GO TO 303

IF(PRTE(M) .NF.R) GO TO 301

GO TO 302

303 K=K-1

PATHN ( K ) =ORG

PATHT (K)=T(M)

CALL CPUSUP ( FT I ME

)

PRINT ROUTE INFORMATION.

km=max-i

DO 3C 4 L=K»KM

LL=L+

1

IF(PATHN(L) .EO.PATHN(LL) ) GO TO 304

WRITE (6> 90 1 ) PATHR (LL) » PATHN <L> f PATHT (L) »PATHN(LL> » PATHT (LL)

901 F0PMAT(5X» ’BOARD ROUTE* »I5»» AT 5T0P»»T5f» AT TIME'S I5»

1’ ARRIVE AT STOP ’ » 1 5 » * AT TIME*, IS)

304 CONTINUE

305 DIFF=FTIMF-STIME

NRUN=NRUN+

1

rtimf=rtime+dtff __ RtSG=RTSO+niFF*PIFF

WRITE ( 6 » 902 ) PIFP

902 FORMAT ( 1H0 » * pi JU TIME FOR TIMEXO r ’ r I6r

MILLISECONDS*

)

GO TO 20 r

;
405 WRITF ( 6 t 905 ) TU,r 905 FORMAT ( IX »

* T T '^F ' » 1 5 » ?X » ' SHOULD BE BETWEEN 1 AND 1440 TRY AGAIN

1 ’ ) GO TO 200

406 CALL CPUSUP(ftIMF)

WRITF (6» 906)

906 FORMAT ( 1 < r

* NO TRIP EXISTS FROM ORIGIN TO DESTINATION LEAVING W

1 I THIN 160 MINUTES AFTER THE R^OUESTED TIME TR Y ANOTHER DEPARTU

2RE TIME*)

GO TO 305

500 R0UT=FL0AT(RTIME) /FLOAT ( NRIJN)

WRITE ( 6 » 907 ) POUT

907 FORMAT ( /// 1 HR » ’AVERAGE RUN TIME =»»F1?.2>» MI LI T SECONDS *

)

ROUT=FLOAT(NRUM)*ROUT*ROUT _

NRUN=MRUfl “l

ROUT= (FLO AT (RTSo) -ROUT) /FLOAT (MRUN)

ROUT=SQRT(POUT)

WRITE (6» 908) ROUT

908 FORMAT ( ///l HO » ’STANDARD DEVIATION OF RUN TIMES ='»F1P.2»

1* MILLISECONDS')

STOP

' ' END

-ILL-
oooooooooooioooooonoooooo

B.8 PROGRAM TIMEXA

C ********** TIMEXA! ARRIVAL ORIENTED CRTTFRIOm **********

c This programuses a ti mE-exT^ndFd representation tm opthF^'to

C CALCUUATF THE BEST path FROM 0 GIVEN ORIGIN To A r.iVPM n EST T f.i- C AT I ON TO ARRIVE nFFORF A SPFr I F TRD TTMF (AND DEPART AS LATE AS

C POSSIBLE). INPN T CONSISTS OF THE NORR AND ARC RATA FOR THF

C time-expanded network together with A LIST OF TRIPS ROr WHICH

C trip ITINERAPIES APE REQUIRED. OUTPUT CONSISTS OR AM ITINERARY

c For each trip# the calculation Ti«e~tn Milliseconds for each

C trip as WELL AS THE AVERAGE and standard DEVIATION of calculation

c times for all trips Tn thf list.

c

c

c

_ C NATIONAL HURRAH OF STANDARDS JULYV 1 Q76

c

c

c PARAMETER MT= 1.600 Q NUMrFR dF MINUTES

PARAMETER MAX = 100 Q NUMQFR r>F RQi I TES /PATm

PARAMETER NOOFS=MSOO D NUMPFR OF NODES

PARAMETER ARCS= 1 3000 0 NUMBER OF APRS

DIMENSION f I ( NODES) rT(NOOES) »S (MODES) » ARC (NODES) »SPTE( NODES) »NN(mT)

1 #T0( ''PCS) » PTE (ARCS) rPATHN(MAX) rPATHT(^AX) » P A THR ( MAX ) REAL ROUT

variables and arrays used in this program

NODE AMD ARC DATA

rjTl ) - StOP 'SSOC I A TED WITH "NETWORK MODE~" I

~

T ( I ) - TIME ASSOCIATED WITH NETWORK NODE I ARC (I) - LAST POSITION WHERE INFORMATION MAY RF

FO'NP FOR NODE I IN ARC LIST

TO ( J ) - ENDING MODF OF ARC IN POSITION J OF ARC LIST

RTF ( J ) - ROUTE NUMBER CORRESPONDING TO ARC IN POSITION

J 0=' ARC LIST

NN(T) - NODE CORRESPONDING To THE LAST OCCURPFNCF OF

TIME T OR EARLIER

NODE - NUMBER OF NETWORK NODES

INPUT VARIABLES FOR TRIP

ORG - DESIRF^ ORIGIN STOP OF TRI©

DST - DESIRED DESTINATION STOP OF TRIP

TIME - TIME p*Y WHICH TRIP IS To RE COMPLETED

-145-
C_ V ARIA BL ES and arrays us ed in thf algorithm

C S ( I

)

- SUCCESSOR NODE TO MODE I ALONG CURRENT PATH

C SRTE ( I ) ~ RO'lTE OUT OF NODE I AL n NG THE CURRENT PATH

C

~C~ ARRAYS USED IN PRINTING THF PATH

C

*C pathn(kT - STOP In POSITION K ALONG PATH

C PATHT(K) - TIME IN POSITION K ALONG PATH

C PATHR(K) - ROUTE IN POSITION K ALONG PATH

C _ _

C VARIABLES USED IN TIMING CALCULATIONS

C

C DIFF - CPU TIME (IN MSECS.) USED IN CALCULATING ONE TRIP

C RTIME - CUMULATIVE SUM OE DIFF»S

C RTSG - CUMULATIVE SUM OF SQUARES OF DTFF*S

C NRUN - NUMBER OF TRIPS CALCULATED

C ROUT - USED IN PRINTING AVERAGE AND" STANDARD' DEVIATION

C OF TRIP CALCULATION TIMES

C

C

C

IMPLICIT INTEGER (A-Z) _

C

C READ THE NETWORK NODE DATA. SORTED ON T. ASSUME ALL T(I) > 0.

C THE SCHEDULE TIMFS ARE GIVEN UP TO 1600 MINUTES.

C

1 = 1

IN1 = 9 0 I '.'RUT UNIT FOR MODE* DATA

100 READ ( INI » 900 » E

f> ID=103) N(I)»T(I)

900 FORMAT ( 31 S

)

IF ( T ( I ) . FQ . TT ) GO TO 102

TM=T ( I

) -1

00 101 J=TT » Tm __ _ . NN( J) =1-1

101 CONTINUE . i. _ - TT=T ( T

)

102 1=1+1

GO TO 100

103

NODE = I-l ... ... - DO 110 J=TT » 1 GOO

NN( J)=NODE

110 CONTINUE

C

c READ THE ARC DATA* SORTED BY ORIGIN NODF.

C
nor

n

n

n

r>

non

IN2=10 q input unit for arc rat a 104 READ( IN2»Q00»c'Nn = l07> T » TO ( L ) , P TF ( L ) IF(I.r.Q.K) GO TO 106

KM=I-J

DO 105 J=K»K^

ARC ( J)=L-1

105 CONTTMUE

K- I 106 L=L + 1 GO TO 104

107 DO 1C 5 J= if NO op x ' • — —

ARC ( J)=L-1

108 CONTINUE

WR I TF ( 6 f Q 1 0 ) 910 FORMAT ( 1H1

)

,'JRUN=0

RTIMF=0 ' ~

RTSQ=0

RF AD OR IGIN f DFST I N * TI ON _ANP DESIRED A PR T\/_AL_ T I wr_( ASSUMED JTO or

BETWEEN 1 AND 1440, TNCU IS* VE)

.

IN3=11 Q IU n UT UNIT FOR TRIP DATA

200 READ ( IN3 f 900 f ENP=500 ) ORG,DST,Timp

WR I TF

(

6 f 9 1 1 ) ORG » DST » TIME

911 FORMAT (//1H0» *TRIP FROM * r * To*fI5»* ARRIVING 8Y*»I5/>

IF ( T I ME . LT . 1 . OR . T I MF . GT . 1 44 C~) GO TO 405

CALL CPUSUP(STIME)

INITIALIZE SUCCESSOR ARRAY.

DO 201 1 = 1 , NOOP __

S ( I ) = 0

SRTF ( I )=0

201 CONTINUE

BEGIN CALCULATION OF ROUTES FR0 M ORG TO DSd

I F ( T I M£ . L T . 16 0 ) T I mp = T l ME+ 1 44 0

I=NN(TIMF) __

IF(I.PQ.n) 6 n TO 406

202 IF ( N ( I ) . FO . DST ) GO TO 203

1 = 1-1

IF(I.PQ.O) GO TO 406

' GO TO 202

203 S(I)=T

204 1=1-1

IF(I.EQ.O) GO TO 406

205 IF(N ( I ) . EQ.OST ) GO TO 203

L=ARC ( I -1 ) + 1 . IF(I.ro. 1) L= 1 END=APC ( I

)
o

oo

1

''

o

o

o

206 IF (END.LT «L) GO TO 204

J=TO(L)

I F ( S ( J ) . EQ . 0 ) GO TO 207

IF(RTE(L) .EQ. 9999. AND. SRTE(J) .F3.Q999) GO TO 207

sd)=j ' SRTF ( I ) =RTE ( L

)

IF ( N ( I ) . E0.ORG) GO TO 300

GO TO 204

207 L-L+

1

GO TO 206

STORE I NFORMAT I ON ABOUT SELECTED ROUTE FROM ORG TO ^st.

300 M=

I

K = 0

301 K-K+

1

"R=SRTE(M)

PATHN ( K ) =N ( M)

PATHT(K)=T(M)

PATHR(K)=R

302 Mrs (M)

IF (N(M) .EO.DST) GO TO 303

I F ( SRTE ( M ) . NE . R ) GO TO 301

GO TO 302

303 K=K+1

PATHN (K)=DST

PATHT ( K

)

= T ( M)

CALL CPUSUP(FTIME)

PRINT ROUTE I

' FORMAT I ON

.

KK = K-1 _ _ DO 304 L=1*KK

LL=L+1

IF (PATHN(L) .EQ. PATHN (LL) ) GO TO 304

WRITE (6*901 ) oatHR(L) *PATHN(L) » PATHT ( L ) * PATHN (I L) » PATHT ( LL

)

901 FORMAT ( 5X * * BOARD ROUTE**I5»* AT ST0P'*T5*» AT T I MF * r 1 5

1* ARRIVE AT STOP * * 15 * * AT TIM£»,ir)

304 CONTINUE

305 DIFFrFTIMF-STIME

NRUNr|JRUN+l

RTIMErRTIME+DiFF

RTSQ = PTSQ + r, I

fr F*DlFF

WPITF (6*902) ^IFF _ _ 90?" FORMAT"! iHO* * RUM TIME FOR TIMEXA = *»I6.* MILLISECONDS*)

GO TO 200

405 WR ITL ( 6 * 905 ) TIME

905 FORMAT ( 1 X

,

» T I ME * * 1 5 * ?X * * SHOuL n BE RETWEEN 1 AMD 1440 TRY A IGA IN ’

)

GO TO 200 _ . ..

-148-
406 CALL CPUSUP(FTIMF)

WRITE (6»906)

906 FORMAT ( IX, ’NO TRIP EXISTS From ORTWIN TO DESTINATION APRIVTNG

1WITHIM 160 MINUTES PRIOR TO Tmf REQUESTED time TRY AMOTHFP ARp

2IVAL TIME*

)

GO TO 305

500 R0UT = FL0'AT (RTIME) /FLOAT (MRUM

)

WRITE(6»907) ROUT

907 FORMAT ( ///l HO #

* AVERAGE RUM TIME =’*F1?.2»» MILLISECONDS’)

ROUT=FLOAT ( NRUN ) *R01JT ROUT

NRUN=NRUN-1

ROUT= ( FLOAT (RTSQ) -ROUT) /FLOAT (NRUN)

ROUT=SORT (ROUT)

WRITE(6»90fl) ROUT

90fl FORMAT ( ///1H0 » ’STANDARD DEVIATION OF RUN TIMES =*»F12.2»

1» MILLISECONDS’)

STOP

END

-lU9-
B.9 PROGRAM REMOVE

C THIS PROGRAM RRMO'/FS UNNECESSARY UODE r FROM A TRANSIT NETWORK, LEAVING

c orTLY Those nodes AT~wHR:Tr transferring is possible ano lTkeLy.

c PARAMETER mk|ODE 500 Q MAY NUMBER OF NODES

PARAMFTER mrte — 1000 0 MAY NUMBER OF ROUTFS

PARAMETER •'RSTOP 10 Q MAY

NOn E NUMBER OF ROUTfS STOPPING AT A parameterMSRTF z. 50 o' MAX NUmber OF" STOPES PER ROUTE*

PARAMETER MSEG - 10000 Q MAX

ONE

NUMBER

EXTRA

OF

FOR"

ROUTE SEGMENTS PLUS

EACH ROUTE

IMPLICIT INTEGER (A-Z)

LOGICAL NIN

DIMENSION SRTE(MSEG) »REND(MRTF) ,NlN(MNODF) » ORPFR (

M

mODE )

I' ~ RSTOPTMNODE»MRSTOP)VNRTE(MNODE) »TEMP(MS^TFT»

2 SOPTM(MNODE) » TIME ( MSRTE ) , INDEX ( MSRTf)

C

C

C

c arrays used in this PROGRAM

c

c

cc

c

c

cc

ccc

c

cc

cc

cc

cc

c

SRTE - STOPS ON EACH ROUTE. REND IS, USED TO INDI CATE WHI CH

SECTION OF THE ARRAY SRTE REFERS To A PARTICULAR ROUTE

REND - POSITION IN SRTE OF THE LAST STOP TN F ft CH ROUTE

NIN - IS TRUE IF NODE HaS NOT BEFN RFMOVfd fl.E. NODE IS IN)

IS F ALSE IF N ODE HA S BEEN REMOVED (T.R. NODE IS OUT)

ORDER - USED IN SORTING, GIVES THF ORIGINAL POSITION OF THE

ITH ENTRY IN SORTED OPDFR

RSTOP - ROR EACH NODE » LISTS THE ROUTES STOPPING* AT THAT NODE

NRTE - NUMBER OF ROUTES STOPPING AT EACH VODF

TEMP ~ TEMPORARY STORAGE FOR INPUT AMD OUTPUT OF MODES ON A R OUTE. AL SO USED AS A N _I NTERMEDl ATf ARR AY ST O RING THF

POSITION IN EACH ROUTF STOPPING AT A NODE, OF THAT

NODE _

SORTN - USED IN SORTING THE NODES ON Ml IMREP OF ROUTES STOPPING

AT each, stores the sorted number of routes

INITIALIZE ARRAYS

DO 1 1=1 , MMO^F

NRTE(I)=0

NIYK I) = .TRUE.

1 CONTINUE"
-pooooo,

oj

oooooooooro

fv>

<~>

o

o

o

ooooo READ ROUTES

K-0

K KEEPS TRACK OF THE CURRENT ROUTF RFAP IN

N=0

N IS THE MAXIMUM NODE MUMPER ENCOUNTERED SO FAR

NR = 0

NR IS THE NUMBER OF TOTAL STOPS IN ROUTES

MEND=0

MEND IS THE NUMBER OF MODES WHICH REGTN OR ENO A ROtjTF

REAP (7»900# EM0=4) K r NS t NT t ( TFMP ( T ) » I =1 t NS

)

00 FORMAT (2015)

DO 201 J=1 t NT

READ ( 7 » 900 ) (TIME ( I ) » 1 = 1 * NS)

01 CONTINUE

THE ROUTE INPUT IS READ IN THF FOLLOWING FORMAT - FOR EACH ROUTE - CARO If COLS. 1-5 CONTAIN THE NUMBER OF STOPS IN ThTS ROUTE

THE STOPS 0 I THE ROUTE are Ti-|Fm | ISTfd IM ORPfr » ^COLS. PER STOP.

ADDITIONAL CAROS ARE IJSEn IF NEE n EP t WITH THF DATA STARTING TM

COL. Hr AGAIN 5 COLS. PER STOP.

STORE THIS ROUTE TN THE ARRAY SRTE » CHECK MAXIMUM NODE MUMPER r ADD

THIS ROUTE TO THE ROUTES STOPPING AT FACH STOP IN the ROUTE.

DO 3 1=1 » NS

I =TFMP ( L

)

IF (I.GT.N) Nr

T

NR=NR+1

SRTE (NR) =1

NRTE ( I ) =NRTE

(

T ) +

1

NN=NRTE ( I

)

RSTOP ( I » NN ) =K

CONTINUE

REND ( K ) =NR

GO TO 2

SORT NODES ON THF NUMBER OF ROUTES STOPPING AT EACH

NRT=K

REWIND 7

CALL SORTP ( NRTE , N , SORTN » OROEP ) C NRT IS THE MUMPER OF ROUTES

- 151 -
c

C ————— cC REMOVE ALL ONE-ROUTE NODES WHICH DO MOT RFGIN OR END A ROUTF

C

EMTRY=1

C WE PROCFSS THE NODES IM THE OROER ThF* APPEAR IN Tme AORAY OPDEP.

C ENTRY IS THE CURRENT POSITION IN ORDER

5 K=OPDER (ENTRY)

C K IS The CURRENT node WHICH IS BEING t ESTFO fop RFMOVAI

M=NPTE(K)

IF (M-l) in,S»ll

6 R=PST0P(K»3)

C FIND THE STOPS Oi ROUTE R IN THE ARRAY SPTF

BEG=REND.(R-1 ) +1

IF (P.EG.l) B FG—

1

C IF K IS THE FIRST STOP ON ROUTF R, k CANNOT B r RFmovFP

IF (K.FO.SPTE (BFG) ) GO TO 9

BE6=RFG+1

END=REND(R)

C IF K IS THE LAST STOP ON ROUTF Rr K CANNOT BE REMOVED

IF (K.EQ.SPTE(END) ) GO TO 9

EnD-END-1

' ~ ' IF (END.GE.DEB) GO TO 7

C ALL ROUTES MUST HAVE AT LEAST ? STOPS

' WRITE (

6

• 991 ) K » R » BEG t END

991 "FORMAT ( *'0*** ERROR *** ' WHILE RFM0VTN3 NODF * » T S »

' FROM ROUTF

1I5»* ROUTE LIST RANGE ( • » IS f •

r

» r IB t

»

)

IS TOO SHORT*/)

GO TO 10

C REMOVE NODE K FROM ROUTE R

7 DO 8 I=BEG t E’ lo IF (SRTE(I) .t'E.K) GO TO 8 _

SRTF ( I ) =0

N I N ( K ) = • FALSF

.

GO TO 10

8 CONTINUE

C NODE K MUST APPEAR IN ROUTE R

WRITE (6»992) K»R# BEGr END

992 FORMAT ( » 6*** ERROR *** N0nE , rI5» f NOT r OUND IN P0UtE r»I5»

1* ROUTE LIST RANGE (

' » ISr *

» * » iSr *

) */)

GO TO 10

9 NEND=MENP+1

C INCREMENT THE CURRENT ENTRY I! THF LIST SORTEO BY MUMPFR OF ROUTFf

C STOPPING AT EACH UODE_ __

10 ENTRY=ENTRY+1

IF (ENTRY. LE.N) GO TO 5

-152-
OOOOIOOOO EXAMINE OTHER NODES FOR POSSIBLE REMOVAL _

L IS THE POSITION OF THE ROUTF CURRENTLY BFING EXA^INFO In THE LIFT OF

ROUTES STOPPING AT NOOF K r is the currfnt route

11 L1

12 R=RSTOP(K»_U _ _ C FIND THE POSITIONS OF RcUJF R TM THE LIST SRTF, AMn FTMD THE POSITION

C WITHIN THAT ROUTF OCCUPIED BY K

BEG=REND(P-i)'+l

IF (R.EQ.l) NEG=1

PREV=SRTE(REG)

C CHECK THAT K IS NEITHER THF FIRST NOR LAST NOOf ON ROUTE R

IF (PREV.EQ.K) GO TO 24

BEG=BFS+1

END=REND(R)

IF (SRTE(FND) .EO.K ) GO TO ?4

END=END-l

IF (END.GE.BEG) GO TO 13

C EACH ROUTE HAS At' LEAST 2 NODFS

WRITE ( 6 • 901 ) K » R » F*EG » ENO

C SEARCH FOR K AS AN INTERMEDIATE STOP ON ROUTE R

GO TO 25

13 DO 17 J=REG*Fmd

I=SRTE( J)

IF ( KEG. 0

)

Go" TO 17

IF (

I

. ME . K ) GO TO 16

NEXT=SRTE ( J + l

)

IF (NEXT. FT .0) GO TO 15

JJ= J+2

NEXT=SRTE ( JJ)

IF (NR XT . FT .0) GO TO 15

JJ=JJ+1

GO T0~ 14

15 TEMP(L)=J

GO TO 18

16 PREV=I

17 CONTINUE

C NODE K MUST RE FOUND ON ROUTE R

WRITE (6»OP2) K»P

G 0 TO 25

18 IF (L.GT.l) GO TO 2u

C STORE MINIMUM OF PREV AND NEXT IN P, MAXIMUM TM 0

IF (PREV. GT. NEXT) GO TO 1R

P=PREV

Q=NEXT

GO TO 22

-153-
19 P=['FXT

Q=PREV

GO TO 22

C TEST IF PREV AMD MEXT ARF THE SAME AS P AMD Of THAT TS WHETHFR THE

C PREVIOUS AMD riSXT NODFS ON ROUTE R ARF THf NODFS AOJACFNT TO K ON

C OTHER ROUTES

20 IF ( PREV . GT , NEXT ) GO TO 21

IF (PREV.NE.P) GO TO 25

IF ( NEXT • NF « Q ) GO TO 25

GO TO 22

21 IF ( NEXT • NF . P ) GO TO 25

IF ( PREV. ME. 0) GO _T 0 25

C CHECK NEXT ROUTE STOPPING AT K 22 L-L+l

IF (L.LE.M) GO TO 12

C REMOVE NODE Kr ZERO SR T E » AND SET NIN-FALSF

DO 23 L=1»M

J=TEMP(L)_ _ SRTE ( J)=0

MIN(K)=. FALSE.

23 CONTINUE

GO TO 25

24 NEND=NEN0+1

C CHECK NF XT NODE FOR POSSIBLE RFMOVAl

25

" ’ ENTRY=ENtRY+l

IF (ENTRY. GT.") GO TO 26

K=OPDER (ENTRY)

M=rjRTF(K)

GO TO 11

C _

cC

C print OUT NODES a/HICH have been deleted

c26 WRITE ( 6 f 90 1

)

901 FORMAT ( * 1 THE FOLLOWING NODES WERF DFLFTEo*/)

“j=o

' NOEL=0

DO 27 1 = 1 #

M

IF (NIM( I ) ) GO TO 27

J— J + 1 NDEL=NDEL+1

TEMPI J) =1

IF (J.LT.25) G 0 TO 27

-15F-
WRITE (6*992 > (TEM^( J) * J=1 *25)

902 FORMAT (5X»2M5)

J = 0

27 CONTINUE

IF (J.LT.O) 0^ TO ?fl WRITE (6*902) ( TE MP ( I ) * T = 1 » J)

WRITE (6*003) NOEL * NEND

903 FORMAT ( *0*

14* »• NOOES DELFTEU ' /

I

c * » MODES RFGTN OR FNO A ROUTER

)

C

c

C

C PRINT OUT REVISES ROUTES WITH "ELFTEO MODFS OMTTTFo

C

28 WRITE (6*904)

90 4 FORM A T ( ’T R E V T S F D R o UTFS» / / • R Te » * 1 0 X * * STOPS * /

)

END=0

DO 30 I=1*NRT

READ (7*900) TI*MS*MT

BEG=EN0+1

. __ . E[iP=REf , D(I)

K = 0

DO 29 J=BEG*E'|D _ _ _

IF ( SRTE ( J) »FQ* 0 ) GO TO 29

K = K + 1 INDEX (K)=J

TEMP ( K ) =SR_TE ( J)

29 CONTINUE

WRITE (6*905) I » (TEMPI J) * J=1*K)

905 FORMAT ( I5*2X*25I5/(7X*25IS)

)

WRITE (13*900) II *K*NT* (TFMP( J) , J=1 ,K)

DO 292 IT=1* IT READ (7*900) ( TIME ( J) * J=1 * NS_) __ DO 291 IJ=1*K

J=INDEX(IJ) _

T I ME ( IJ)=TIME( J)

291 CONTINUE

WRITE (13*900) (TIME(J) * J=1*K)

292 CONTINUE

30 'CONTINUE

END FILE 13

STOP

END

- 155-
* •

'
NBS-114A (REV 7-73)

U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO

NBSIR 78-1426

2. Gov’t Accession

No.

4. TITLE AND SUBTITLE

Comparison of the Performance of Three Algorithms for Use in an Automated Transit Information System (ATIS)

3. Recipient's Accession No.

5. Publication Date March 1978

6. Performing Organization ( ode

7. AUTHOR(S)

J. F. Gilsinn, E. Leyendecker, D. R. Shier

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

10. Pro)ect/Task / Work Unit No. 2050^02

11. Contract /Grant No.

12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP)

National Bureau of Standards

A-428, 101

Washington, DC 2023*t

13. Type of Report & Period Covered

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here.) This paper compares the performance of three algorithms for computing trip

itineraries for use in an automated transit information system. One of the approaches (TIMEXD) is based on a time-expanded network. The other two both

compute paths in a bipartite route/stop network; one algorithm (LABCOR) is

based on the label-correcting approach and the other (LABSET) on the labelsetting approach. The transit networks upon which the performance comparison is

based are of two types: a grid network with specified, possibly non-uniform,

distances between streets, and a spider web type of network. TIMEXD is fastest on all the larger networks, but it requires most computer storage and outputs

paths with more transfers. LABCOR is the slowest, but is guaranteed to produce

the best routing, since it always outputs an optimal path with fewest transfers.

Computation time estimates extrapolated to large transit networks indicate

times of 1.5 to 2.5 seconds per itinerary for TIMEXD and LABSET respectively,

well within the acceptable range for such networks.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons)

Algorithms; algorithm testing; mass transit; routing; shortest paths; transit;

transit information systems; transit routing; transportation; urban transportation.

18. AVAILABILITY ff Unlimited 19. SECURITY CLASS

(THIS REPORT)

21. NO. OF PAGES j

|

1 For Official Distribution. Do Not Release to NTIS UNCLASSIFIED

163

^ Order From Sup. of Doc., U.S. Government Printing Office Washington, D.C. 20402. SD Cat. No. Cl

3

20. SECURITY CLASS

(THIS PAGE)

22. Price

[X1 Order From National Technical Information Service (NTIS)

Springfield, Virginia 22151 UNCLASSIFIED $8.00

USCOMM-DC 29042-P74
'

.