la

INbS

PUBLICATIONS

A 1 1 1 E 3 4 5 fl b E

L M

INiBSiR 85-3178

Paratransit Advanced Routing and

Scheduling System Documentation:

Routing and Scheduling Dsal-A-Ride

Subsystem

How<rd K. Hung

William G. Hall

Robert E. Chapman

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Applied Mathematics

Gaithersburg, MD 20899

July 1 985

Sponsored by

U.S. Department of Transportation

Urban Mass Transportation Administration

QC 9ee of Technical Assistance

shingtcn, DC 20530

• U56

85-5178

1985

C. 2

NATIONAL BUREAU OF STANDARDS

LIBRARY

NBSIR 85-3178

PARATRANS1T ADVANCED ROUTING AND

SCHEDULING SYSTEM DOCUMENTATION:

ROUTING AND SCHEDULING DIAL-A-RJDE

SUBSYSTEM

Howard K. Hung

William G. Hall

Robert E. Chapman

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Applied Mathematics

Gaithersburg, MD 20899

July 1985

Sponsored by

U.S. Department cf Transportation

Urban Mass Transportation Administration

Office of Technicai Assistance

Washington, DC 20590

U.S. DEPARTMENT OF COMMERCE, Malcoim Baldrige, Secretary

NATIONAL BUREAU OF STANDARDS. Ernest Ambler. Director

PREFACE

This research was conducted under the sponsorship of the Paratransit

Integration Program (PTIP) , Urban Mass Transportation Administration, U.S.

Department of Transportation, by the Operations Research Division, Center for

Applied Mathematics, National Engineering Laboratory, National Bureau of

Standards. Mr. Edward G. Neigut was the UMTA program manager for the project.

The Routing/Scheduling Dial-A-Ride (RSDAR) algorithm described in this report

creates tour schedules from a file of trip requests made by dial-3-ride

patrons. A trip request consists of the number of passengers (a patron and

his party), a pickup location, a dropoff location and either a desired pickup

or dropoff time. Tour schedules created by RSDAR contain a list of locations,

times of vehicle stops, and the names of patrons boarding and alighting at

each stop.

The RSDAR is a heuristic algorithm designed for operation in a batch mode.

It can accommodate up to eight different characteristics for a patron, and up

to 15 classes of priority. Conditions such as separate limits for the number

of wheelchairs on a vehicle and economies of scale on patron dwell time are

also Included. The RSDAR is intended for use by dial-a-ride system operators

in routing and scheduling their daily trip requests.

This report is designed as a technical reference for setting up and

maintaining the RSDAR model. However, a preprocessor, CQNENV, which

constructs physical and policy enivronments , and contains trip request

information; and a post processor, GREPOR, which generates hard copy of all

necessary reports, are integral parts of the Advanced Routing and Scheduling

System. Hence, a reader should read the reports describing CONENV and

GREPOR, and the report on data structure before beginning to implement the

system.

.ii
ABSTRACT

The Advanced Routing and Scheduling System (ARSS) is a software system

designed to route and schedule patrons in a dial-a-ride environment. The

system consists of three subsystems: CONENV, a preprocessor, constructs

physical and policy environments; RSDAS routes and schedules patrons; and

GREPOR generates hard copy of all necessary reports. This report only

describes RSDAR.

The RSDAR is a heuristic algorithm. It assigns patrons to form subtours

in time intervals; these sub tours are then linked to become a tour.

Patrons are included in a subtour on the basis of best use of the

remaining time of the base trip. Subtours are included in a tour on the basis

of a measure of best productivity.

The model is written in FORTRAN and complies with the American National

Standards Institute X3. 9-1973 standard for that language.

Keywords: Dial-a-ride; heuristic algorithm; routing; scheduling

iv
Table of Contents

Page

Preface ill

Abstract iv

List of Figures vii

List of Tables viii

1. Introduction 1

2. A Heuristic Routing/Scheduling Dial-A-Ride (RSDAR) Algor it ha. . . 6

2.1 Basic Concepts 6

2.1.1 Tour, Subtour, Trip and Base Trip. 6

2.1.2 Service Quality Constraints 7 2.1.3 Pickup and Delivery Time Windows 7 2.1.4 Priority... 10

2.1.5 Productivity Measure 10

2.1.6 Dwell Time 11

2.1.7 Vehicle Capacity 12

2.1.8 Mobility Code... 12

2.2 Heuristic Approaches. 13

2.2.1 Time Interval 13

2.2.2 Maximum Remaining Time 14

2.2.3 Productivity Measure 14

2.2.4 Base Trip Matrix 15

2.2.5 Compatibility Matrix 16

2.2.6 Potential Upper Bound.. 16

2.2.7 Time and Locations of Tour Start, End, and 3reak... 17

2.2.8 Shifting.... 18

2.2.9 Call Back 19

2.3 Flow Chart 19

3. Functional Description of RSDAH..... 21

3.1 The Computer Program 21

3.1.1 Subroutine MAIN 21

3.1.2 Subroutine MNTOUR 24

3.1.3 Subroutine S3T0UR 25

3.1.4 Subroutine S3TGEN 25

3.1.5 Subroutine TRCOMB 25

3.1.6 Subroutine FESIBL 25

3.1.7 Subroutine RMTIME

3.2 Input Data Requirements 26

3.3 Parameters 28

3.4 Model Output

V
4. Operational Characteristics of RSDAR * 32

4.1 Computational Results with RSDAR 32

4.2 Computer System Configuration 37

4.3 Computer Hardware and Software Requirements 38

Appendix A: Internal Data Formats A1

Appendix B: Input Formats....... B1

Appendix C: Interface Formats Cl

Appendix D: Output Formats D1

Appendix E: Sample Input El

Appendix F: Sample Interfaces..................... FI

Appendix G: Sample Output G1

Appendix H: Subroutine Specifications HI

Appendix I: Program Listings II

Appendix J: Test Data... J1

vi
LIST OF FIGURES

Page

1.1 Schematic View of ARSS 5

2.1 Time Windows for Pickup Specified and Dropoff Specified Trips . 9

2.2 The Relative Position of Dwell Time to Scheduled Pickup Time

and Dropoff Time 12

2.3 Flow Diagram of the RSDAR Algorithm 20

3.1 Flow Diagram of Subroutines of RSDAR 23

vii
LIST OF TABLES

Page

4.1 Results of #1 Test Series (Using Productivity Measure #1

for All Patrons 34

4.2 Results of #2 Test Series (Using Productivity Measure #1

for Wheelchair Patrons and Productivity Measure #3 for

Regular Patrons 34

4.3 Tour Assignments of f?l Test Series 35

4.4 Tour Assignments of #2 Test Series 36

4.5 Test Results of Different Number of Priorities . 37

viii
1. INTRODUCTION

Many different types of paratransit systems have been in operation for

over a decade. However, most of them have been manually routed and scheduled.

The first major effort to develop a computer aided routing and scheduling

approach for demand responsive transit was the CARS (Computer Aided Routing

S_ystem) research project at the Massachusetts Institute of Technology from

1967 to 1971. Subsequently, a field demonstration was implemented in

Haddonfield, New Jersey from 1972 to 1975. During most of the demonstration

period, routing and scheduling of patrons were done manually; computer

dispatching was used towards the end of the project. The computer control

algorithm used in Haddonfield was that developed at MIT during the CARS

project. A second field demonstration was implemented in Rochester, New York

from 1975 to 1978. The computer control system used in Rochester was related

to the system developed in the CARS project, although modifications were made

to reflect the experience gained in Haddonfield. Immediate assignment of all

patrons requesting service is a common feature of these two computer control

systems. The assignment not only selects a vehicle, but also inserts the new

pickup and dropoff stops in the tour of a vehicle.

A routing and scheduling algorithm for patrons with advance reservations

was developed for the Urban Mass Transportation Administration at the

University of Maryland. The algorithm was a mathematical programming

approach, but embedded with heuristics.

When UMTA asked NBS to undertake the current project of developing a

dispatching, scheduling, and routing algorithm and supporting operational

software packages, it specified the following six basic guidelines to be

observed:

1
(1)

Products must be user oriented.

(2) Solution techniques must be simple.

(3) Products and documentation must be structured to facilitate the separation

and use of individual, self-contained segments.

(4) Programs must be portable.

(5) Programs must be executable on low cost minicomputers.

(6) Software packages must be amenable to assembly and/or integration into

systems at sites to suit the specific needs of those localities.

In consideration of the above mentioned six guidelines, NBS designed a

software package with three stand-alone, but related, subsystems. The first

of these subsystems, CONENV, constructs the physical environment and the

policy environment; reads, transforms and augments trip request information;

and creates required environmental reports. The physical environment includes

vehicle characteristics such as initial location, final location, vehicle

capabilities, capacities and dwell times; it defines geographic zones and

zone-to-zone speeds. The policy environment includes service time intervals,

policy-dictated breaks in service, definition of priority for both patron and

vehicle accommodation capability, and definition of service quality

requirements

.

The trip request input is range-checked, transformed, and augmented by

required environment information. The checking is extensive: in most case3,

a non-legitimate entry is corrected to a default value and processing

continues. When a default is Impossible, the trip is omitted. Any

abnormality generates a warning message.

2
Mandatory outputs are information (stored internally) necessary for the

execution of subsequent subsystems and monitoring/error information (CRT and

hard copy). There are also a number of independent and optional hard copy

reports

.

After reading file zc.rsd, output of the first subsystem, (i.e., CONENV),

the second subsystem, RSDAR, performs the routing and scheduling of all trip

requests. After routing and scheduling are completed, RSDAR writes results on

file zr.gre. They are used as input to the third subsystem, GREPOR. The

algorithm for the RSDAR subsystem is a collection of heuristics which will be

described in detail later in this report.

The third subsystem, GREPOR, creates the necessary hard copy reports using

as input the output from CONENV and RSDAR as well as the input file zs.gre.

There are two types of report. The first is the driver trip list, designed

specifically for the vehicle operator. The second, the dispatcher report, has

considerably more information than the driver requires and is intended for the

dispatcher/scheduler . Both report types are generalized to allow for user

specified item selection, sorting, and paging.

Figure i.l depicts the relationship between the three subsystems with

respect to input, output, and interfaces. This report is one of a sequence of

reports, focusing on the RSDAR subsystem of the Advanced Routing and

Scheduling System (ARSS).

The first report of the sequence, NBSIR 35-3174, Paratransit Advanced

Routing and Scheduling System Documentation: Functional Program and Data

Specifications , establishes the concepts upon which the software development

was based. The overall tone of that report is general; it does not address

program and data organization details such as

3
formats and specific computations. It describes the total paratransit

environment and defines the functions, ranges and accuracy requirements.

The remaining reports of the series describe the software developed. In

accordance with the aforementioned guidelines, each report is independent and

self contained. There is redundancy among the reports since each is intended

to be definitive with respect to a specific component or aspect of the system

and only descriptive of the remainder.

The series cf reports:

1 - NBSIR 85-3175 PARASSD: USES/ OPERATOR MANUAL

2 - NBSIR 85-3176 PARAS SD: DATA SPECIFICATION

3 - NBSIR 85-3177 PARASSD: ENVIRONMENT CONSTRUCTION SUBSYSTEM

A - NBSIR 85-3178 PARASSD: ROUTING AND SCHEDULING DIAL-A-RIDE

5 - NBSIR 85-3179 PARASSD: GENERALIZED REPOSTING SUBSYSTEM

* PARATRANSIT ADVANCED ROUTING AND SCHEDULING SYSTEM DOCUMENTATION.

A
J

Monitor report
2. A HEURISTIC ROUTING/SCHEDULING DIAL-A-RIDE (RSDAR) ALGORITHM

A heuristic algorithm is presented here to solve the dial-a-ride routing

and scheduling problem. The basic approach of the algorithm is to assign

patrons to tours in such a way that productivity measures of subtours are

maximized while all requirements for service quality constraints are

satisfied

.

2.1 BASIC CONCEPTS

The heuristic algorithm is based on a set of concepts specifically

developed for routing and scheduling dial-a-ride patrons. A familiarity with

these concepts, as Introduced in the following subsections, is essential to

the understanding of RSDAR.

2.1.1 Tour, Subtour, Trip and Base Trip

Some of the basic concepts used In RSDAR are those of tour, subtour, trip

and base trip. A tour Is defined as a collection of sub tours assigned to a

vehicle over a specified time interval, the elapsed time from the start to the

end of a designated work shift for a vehicle. Each time interval in a tour

during which the vehicle has at least one patron on board, (i.e., the vehicle

is not empty) is a subtour.

A trip can be defined by its three major components: (1) a patron and

his characteristics, (2) his origin and destination locations; and (3) his

desired pickup time and/or delivery time.

A base trip is tied to the concept of a base patron. In a subtour, the

first patron who boards the vehicle Is the base patron and his trip is the

base trip. All other patrons in the subtour must share some portion of the

ride with the base patron. A patron who can not share some portion of a ride

with the base patron can not be included in that subtour.

6
Tour and sub tour are associated with the vehicle, while trip and base

trip are associated with the patron.

2.1.2 Service Quality Constraints

The dial-a-ride operating authority establishes its service quality by

imposing two independent requirements: (1) patron maximum on board time; and

(2) pickup/delivery deviation allowance.

Patron maximum on board time limits the time that a patron may stay on

board a vehicle, eliminating routings where ride times become excessive.

Maximum on board time i3 the sum of an allowance for excessive ride time and

the trip exclusive ride time (i.e., the minimum time for the vehicle to go

from the patron’s origin location to his destination location). The allowance

for excessive ride time can be established by assigning a percentage of the

trip exclusive ride, and superimposing a lower bound and an upper bound on the

allowance, or it can simply be decreed as a fixed value.

The pickup/delivery deviation allowance time defines another service

quality requirement. This allowance establishes the length of a time window

within which the pickup or delivery must be made. The patron specified clock

time becomes one end point of the time window as described in the next

sections.

2.1.3 Pickup and Delivery Time Windows

Trip requests are classified either as pickup specified or as dropoff

specified. If a trip request asks for a pickup time, the trip is considered

as pickup specified. Likewise, if a trip request asks for a dropoff time, :he

trip is considered as dropoff specified. A trip request can be either pickuo

specified or dropoff- specified, but not both.

7
Two time windows are created for each trip request: one pickup window and

one dropoff window. The pickup window is the time interval between the

earliest pickup time (EP) and the latest pickup time (LP). The dropoff window

is the time interval between the earliest dropoff time (ED) and the latest

dropoff time (LD). When a pickup specified trip request calls for a pickup

after a certain time, the specified time becomes the earliest pickup time

(E?) } and the latest pickup time (LP) is the earliest pickup time plus the

deviation allowance time. However, if a pickup-specified trip request calls

for a pickup before a certain time the specified time becomes the latest

pickup time (LP), and the earliest pickup time is the latest pickup time minus

the deviation allowance time. For a pickup-specified trip request, the

earliest dropoff time (ED) is the earliest pickup time plus the trip exclusive

ride time, and the latest dropoff time (LD) is the latest pickup time plus the

maximum on board time.

For dropoff-specif ied trips, the process is reversed with the dropoff

window established first. If a trip calls for a dropoff before a certain

time, the specified time becomes the latest dropoff time (LD), and the

earliest dropoff time (ED) is the latest dropoff time minus deviation

allowance time. On the other hand, if a trip calls for a dropoff after a

certain time, the specified time becomes the earliest dropoff time (ED) and

the latest dropoff time (LD) is the earliest dropoff time plus the deviation

allowance time. The windows for pickup-specified and dropoff-specif ied trips

are illustrated in Figure 2.1.

8
Pickup-Specified Trips

p _J> ED

Pick Window Drop Window

LD

| Allowance

I-* exclusive Ride Time

•Maximum on Board TimeDropoff Specified Trips

EP

Pick Window

LP ED LD

Drop Window

( Allowance

Exclusive Ride Time

Maximum on Board Time

Figure 2.1 Time Windows for Pickup Specified and

Dropoff-Specified Trips

A crip’s scheduled pickup and delivery times have to fall within the

pickup and delivery windows, respectively. However, this does not guarantee

that the trip is scheduled feasibly because the windows are so constructed

that both pickup and delivery times may be within their respective windows,

but the trip time can exceed the maximum on board time. Therefore, the RSDAR

algorithm also checks the feasibility of maximum on board time.

9
2.1.4 Priority

In a dial-a-ride system, each trip is assigned a priority depending upon

the patron’s characteristics. RSDAR uses the trip priority as assigned in

CONENV. Priority (i.e., the relationship with patron characteristics) is

determined by the local dial-a-ride management system. The RSDAR algorithm is

capable of handling up to fifteen priorities. According to the precedence rules

within the assignment procedure, no patron can be assigned to a subtour if a

patron of higher priority is yet to be assigned. Thus the priorities are useful

not only for ordering, but for stratification as well. The best subtour is

selected based on the trips of highest priority. The precedence rules provide a

mechanism for implicit enumeration.

2.1.5 Productivity Measures

Productivity measures are used in the algorithm to help achieve the

optimization objectives in a dial-a-ride system.

The productivity measures that are currently defined in the RSDAR are:

1. Number cf patrons;

2. Number of trips;

3. Number of patrons per unit travel time;

4. Number of trips per unit travel time;

5. Patron exclusive ride times per unit travel time; and

6. Trip exclusive ride time per unit travel time.

All of these measures represent either work or work per unit time. Items (1)

through (4) consider the unit of work to be patrons (or trips); all patrons

10
(trips) have equal value. Items (1) and (2) are integer counts; items (3) and

(4) are utilization factors. Items (5) and (6) consider the unit of work to be

the patron (trip) exclusive ride time; the value of a trip is proportional to

its length.

2.1.6 Dwell Time

Dwell time is the time spent loading or unloading patrons to or from a

vehicle. Number of patrons, characteristics of patrons, type of vehicle and

whether it is loading or unloading, all affect vehicle dwell time at a stop.

A dwell time file is constructed for each type of vehicle. Each file has

two major headings, pickup and drop-off dwell time. Under each major heading

are three subheadings, namely, non-wheelchair (regular patrons), lift (those

patrons who need a vehicle lift to get on board a vehicle), and wheelchair

(patrons who use wheelchairs).

Empirical or estimated time values for each category are stored for each

number of patrons up to the vehicle capacity. This format is used to

accommodate observed non-linearities (e.g., n patrons can board/alight at a

single stop in less time than is required for a single patron at each of n

stops). In the routing and scheduling, numbers of each type of patron (whether

they belong to a single trip or multiple trips) at a vehicle stop are first

determined, then the dwell times are obtained for the various types. The

largest time value is considered the dwell time of this stop. Thus, with mixed

patron types, the largest dwell time is considered the total dwell time.

The pickup dwell time is included in a schedule before the scheduled pickup

time; the drop-off dwell time enters a schedule after the scheduled drop-off

time. If a number of trips in a subtour have the same stop location, the total

11
dwell time is consolidated into a single entry and is shown as the first

scheduled pickup time or as the last scheduled drop-off tine depending upon the

type of stop.

Pickup

jcd—

Pickup

Xd_

Dropoff Pickup

1=3 t=L

Dropoff Dropoff

i=L

Dwell time

Figure 2.2 The Relative Position of Dwell Time to Scheduled

Pickup Time and Dropoff Time

2.1.7 Vehicle Capacity

Vehicle capacity is defined in terms of combinations of patron types. For

example, a vehicle may accommodate both wheelchair and non wheelchair patrons

with capacity defined as:

with no wheelchairs, twelve non-wheelchair patrons;

with one wheelchair, nine non-wheelchair patrons;

with two wheelchairs, seven non-wheelchair patrons;

with three wheelchairs, three non-wheelchair patrons;

and with four wheelchairs, no non-wheelchair patrons.

2.1.8 Mobility Code

A mobility code with four levels is built in the dial-a-ride system. The

four levels are: (1) extended wheelchair; (2) wheelchair; (3) lift; and (4)

regular or non-handicapped. Each patron has a single code; for multiple riders

on a single trip, the code corresponding to the least mobile rider is used. An

extended wheelchair patron is considered less mobile than a wheelchair patron;

12
a wheelchair patron, less mobile than a lift patron; and a lift patron, less

mobile than a regular or non-handicapped one. Vehicles have multiple code

classifications which indicate capability.

The RSDAR algorithm checks the compatibility of patron mobility code with

the vehicle mobility classification code. If they are not compatible, then

the patron can not be assigned to the vehicle.

2.2 HEURISTIC APPROACHES

To facilitate understanding of the heuristic algorithm, it is appropriate

to describe some basic concepts of the algorithm before stating the

procedures.

2.2.1 Time Interval

To generate a tour, the heuristic algorithm creates subtours in time

intervals, terminating when all time intervals have been exhausted or no

patrons can be assigned to the tour. The first task is to set in the starting

and ending times of a given tour, and any scheduled breaks such as lunch,

coffee breaks, etc. The algorithm then picks the first time interval, usually

from tour starting time to the starting time of the first break. If no break

is scheduled, this time interval ends with the ending time of the tour. The

algorithm attempts to form a subtour in the interval. When a subtour is

formed, there will be two intervals, one immediately preceding and one

immediately succeeding the subtour. The algorithm attempts to create a

subtour in the first interval. If no subtour can be formed in an interval, it

is considered to have been examined and the algorithm moves to the next

interval. A tour is completed after the last interval is examined.

13
2.2.2 Maximum Remaining Time

One measure used in RSDAR to decide which patron is to be included in a

subtour is the remaining time of the base trip. The remaining time of the

base trip is obtained, first by including the patron's trip in the subtour,

then- subtracting base trip travel time from the maximum on board time of the

base trip. The underlying rationale is that the larger the remaining time of

a base trip, the greater the opportunity to add new patrons to the subtour.

In a given time interval, a base trip (a subtour of two stops) is first

tentatively chosen; the algorithm then expands this two-stop subtour by

inserting more patrons. The process of expansion adds only one patron at a

time, hence the subtour grows from two stops to four stops, then six, and so

on. At any stage of expanding a subtour from n stops to n+2 stops, the

algorithm examines all combinations of n+2 stops which do not affect the

internal order of the n stops for patrons already assigned, selecting the one

which allows the largest remaining time for the base patron, which in turn

identifies the patron to be added in the subtour. The process of expansion

will be repeated until no feasible trip can be added to the subtour. In

short, the maximum remaining time of a base trip is the selection criterion

for adding an additional patron to a subtour.

2.2.3 Productivity Measure

In a given time interval, subtours are formed based on a maximum

remaining time criterion. There are as many subtours as the number of

feasible patrons. However, only one subtour, among all possible subtours, can

be selected in a time interval. The selection criterion for a subtour is the

productivity measure.

14
In a tine interval, the first subtour formed becomes the incumbent; any

subsequently formed subtour with higher productivity will replace the

incumbent. The process of selecting a subtour in a time interval terminates

after all qualified patrons are examined.

Since each trip is assigned a priority and each priority is related to a

productivity measure, comparisons of subtours are made by their productivity

measures for the highest priority. If there is a tie, then the productivity

measures for the next highest priority will be considered.

2.2.4 Base Trip Matrix

The most time-consuming part of the algorithm is the formation of

subtours. For each subtour, a base trip is first selected, then the size of

the subtour is increased by adding one patron at a time. Every unassigned

(unscheduled) patron is examined for possible ride-sharing with the base trip

patron, and the patron providing the maximum remaining time of the base trip

is selected to be included in the subtour. The process is repeated until no

unassigned patrons can be added to the subtour.

To avoid examining every unassigned patron repetitively, the algorithm

uses the Base Trip Matrix, constructed in CONENV and updated in 3.SDA3. as tours

are constructed, which defines all pairwise ride sharing. In the Base Trip

Matrix, each row represents a base patron and each column represents a patron.

Elements of the 3ase Trip Matrix have values of one or zero. A one in an

element means that the patron can share a ride with the base patron; a zero

means that the patron can not share a ride with the base patron. The Base

Trip Matrix effectively reduces the number of patrons to be examined for every

base trip.

15
2 . 2.5 Compatibility Matrix

The Compatibility Matrix is of the same 0-1 form as the 3ase Trip Matrix,

an element of "1" meaning that the row-column patrons can 3hare a ride (be on

the same vehicle at the same time); a

" 0", that they cannot share a ride. The

Compatibility Matrix is a mechanism by which the mixing of classes of patrons

can be avoided. Criteria for making this determination are site specific;

they could include physical characteristics (elderly, mentally retarded,

juvenile, etc.) and policy characteristics (priorities, sponsoring agencies,

etc.). These are expected to be so different from one site to another that it

is not appropriate to write a general procedure for thi3 purpose.

In some instances, incompatibility can result not from patron

characteristics, but from the times and geography of origins and destinations.

For example, candidates A and B may each be potential sharing riders for base

patron C but not be able to share with each other.

The Compatibility Matrix as constructed in the current version of CQNENV

uses only geographic considerations. However, SSDAR does not require any

interpretation of the share/no share criteria. Therefore, the structure and

procedure require no internal modification.

2 . 2.6 Potential Upper Bound

Another effort to reduce the number of subtours to be built is to set a

bounding constraint in the algorithm, the productivity measure of the

incumbent sub tour. Initially, a potential upper bound is obtained for every

patron from the Base Trip Matrix. These potential upper bounds are revised as

patrons are assigned to tours. Since a subtour has a productivity measure for

each priority, the appropriate productivity measure has to be used as a

potential upper bound.

16
After an incumbent subtour is formed and its productivity measure

obtained, new base patrons are examined to form new subtours. Before starting

the process of constructing new subtours, the potential upper bounds of new

base patrons are compared with the productivity measure of the incumbent

subtour. If the potential upper bound of a base patron is smaller than the

productivity measure of the incumbent subtour, this base patron is skipped for

further investigation in the current time interval. The rationale is as

follows: if the potential upper bound of the base patron is smaller than the

productivity measure of the incumbent subtour, then this base patron can never

form a subtour with a productivity measure higher than that of the incumbent

subtour. Therefore, one can skip this base patron.

This procedure is an implicit, rather than total, enumeration. Subtour

selection is based on the highest productivity measure of the highest

priority. Subsequent insertion of lower priority tours is made in priority

order.

2.2.7 Time and Locations of Tour Start, End, and Break

Every stop in a tour has two attributes, time and location. The time and

location for stops of tour start, tour end, and tour break are input to

RSDAR.

Every tour start time, tour end time and tour break time are entered as

time windows. Stops that do not have pre-assigned time windows can simply be

assigned a 24-hour time interval. It should be pointed out that the duration

of a tour break is a necessary input to RSDAR. In terms of data storage, both

a tour start-tour end pair and break start-break end pair are equivalent to

dummy trips and appear in the patron list as such.

17
A location (the x,y coordinate) for each tour stop is generally required

in RSDAR. However, in cases of tour start, end, and break, locations are not

necessary. If the locations are not given, then the location of the stop

succeeding the tour start stop in a tour Is considered as the location for the

tour start, and the location of the stop preceding the tour break or tour end

will be considered as the location for the tour break or tour end.

The ability to have an unspecified location allows for a break in service

scheduled with respect to time, but at any location. This is useful for

coffee breaks, lunch periods, etc. It also allows for "artificial” tours;

these correspond to a hired-by-ride shared-ride taxicab. Artificial tours are

treated exactly as regular tours except that each nay have only one sub tour.

This allows for short term (one subtour) utilization of a vehicle which can

appear whenever and wherever needed and disappears after the assigned subtour

is completed.

2.2.3 Shifting

Since a sub tour is formed in a time interval, a larger time Interval

provides a better opportunity to build a larger subtour. Therefore, it is

useful to shift the two end3 of a time Interval to make the interval as large

as possible. In order to shift the two ends of an Interval, it is necessary

to shift all subtours preceding the interval to the earliest feasible time and

all subtours following the interval to the latest feasible time. The

algorithm implements the above idea by initially assigning all patrons in the

subtour being formed to the latest feasible time. After the subtour is

formed, the algorithm will examine the time interval preceding this sub tour.

If no subtour can be formed In the interval, then the algorithm will shift all

scheduled times of the subtour from latest feasible time to earliest feasible

time.

18
2.2.9 Call Back

It becomes necessary to call back a patron if his scheduled pickup time

is not in his promised pickup time interval. A patron gets a promised pickup

time interval when he calls in to make a trip request. However, this promised

pickup time interval may not be the pickup time interval that RSDAR uses to

schedule the patron. Due to the way that time windows are constructed, when a

patron specifies a pickup time, his pickup time interval will coincide with

the promised pickup time interval. However, if he specifies a dropoff time,

his pickup time interval will not necessarily be the same as the promised

pickup time interval. In this case, his scheduled time can be outside the

promised time interval.

RSDAR has a subroutine CALBCK to check every patron if a call back is

necessary. If so, affected patrons will be marked for call back and, in the

report subsystem, a call back list will be generated.

2.3 FLOW CHART

The logical flow of the RSDAR algorithm is depicted in Figure 2.3.

19
Figure 2.3 Flow Diagram of the RSDAS. Algorithm

20
3. FUNCTIONAL DESCRIPTION OF RSDAR

3.1 THE COMPUTER PROGRAM

The computer program for RSDAR consists of sixteen subroutines. Seven

form the main stream of the RSDAR algorithm, the other nine provide various

utility functions. A simple flowchart of RSDAR in terms of these seven

subroutines is depicted in Figure 3.1; descriptions of all subroutines in

RSDAR are provided in Appendix H. The complete listing of RSDAR can be found

in Appendix I. However, a more detailed description of the seven mainstream

subroutines can be found in the following sections.

3.1.1 Subroutine MAIN

Subroutine MAIN performs the following major functions: It declares

values of parameters which are sizes of various array dimensions; specifies

external unit3 for input and output files; calls Subroutine READCV to read the

input file; calls Subroutine MNTOUR to perform routing and scheduling for all

trip requests; calls Subroutine CALBCX to check the need for calling patrons;

and, finally, calls Subroutine DUMPGR to write all output results on disk

files.

A PARAMETER statement is used in Subroutine MAIN to declare values of

eleven parameters which are used as "named constants" for array dimensions

throughout RSDAR. Detailed descriptions of these parameters can be found In

Section 3.3.

The specification of external units for input and output files is another

major function of Subroutine MAIN. The Advanced Routing and Scheduling System

has three subsystems, namely, the preprocessor, CONENV, the routing and

scheduling algorithm, RSDAR, and the report generator, GREPOR. Since RSDA< is
the second subsystem, it takes output of CONENV as its input, and its output

is the input to GREPOR. Hence OPEN statements are used to bind file names

with unit numbers of external devices.

The naming convention of files used in RSDAR subsystem is compatible with

that in CONENV and GSEPOR subsystems. All file names are of the form 22. XXX.

The first letter is always z, the second letter indicates the subsystem that

produces the file. Only three letters are involved: c means CONENV, g means

GSEPOR, and r means RSDAR. The three letters after the period denote the

reading subsystem. For example, zr.gre means the file is produced by RSDAR

and is to be read as input by GSEPOR.

The input data to be read is in the file 'zc.rsd', and is assigned to

external unit 11 with a status of 'old 1 , meaning that the file should exist.

The output file is 'zr.gre* and is assigned to external unit 21 with a status

of 'new', meaning that the file cannot yet exist, but will be created.

After the input data are read, Subroutine MAIN calls Subroutine MNTOUR to

initiate routing and scheduling of all trip requests, returning to Subroutine

MAIN when the task of routing and scheduling is finished. At this time,

Subroutine MAIN will call Subroutine CAL3CK to identify those patrons whose

scheduled times are not within their promised times. Patrons on this list

must be telephoned to notify them of the change.

Finally, Subroutine MAIN will call Subroutine DUMPCC to write all RSDAR

output on file 'zr.gre', so that the report generating subsystem will be able

to process these data. Details of the output will be discussed in Section

3 . 4 .

22
Figure 3.1 Flow Diagram of Subroutines of RSDAR
3.1.2 Subroutine MNTOUR

Subroutine MNTOUR is the center of activities, performing many tasks. It

calculates initial upper bounds of productivity measures and determines the

minimum size of time interval in which the algorithm will build subtours.

The subroutine searches the patron. list and the tour list to see if there

are any unassigned patrons or tours. If both are found, the subroutine will

enter tour information, determine the time interval within which subtours will

be built, initialize the priority sought to the highest, and select an

unassigned patron with the highest estimated value of productivity measure for

the sought priority as the base patron. It then calls Subroutine SBTOUR to

build a subtour with the base patron. When Subroutine SBTOUR returns with a

subtour, Subroutine MNTOUR will search for unassigned patrons whose upper

bound of productivity measure is higher than the productivity measure of the

current subtour and send them, one at a time, to Subroutine SBTOUR to build

new subtours. The process terminates when the patron list is exhausted. If

no subtour can be built with the base patron of the highest priority within a

time interval. Subroutine MAIN then will advance the sought priority to the

next highest priority and iterate until either a subtour is built in the time

interval or the priority list is exhausted, indicating that no subtour can be

built in the time interval.

A tour is completed when the last time interval in the tour has been

examined

.

Subroutine MNTOUR returns the control to Subroutine MAIN when either all

patrons have been assigned to a tour or all available tours have been used.

24
3.1.3 Subroutine SBTOUR

The major functions of Subroutine SBTOUR are to set the stage to call

Subroutine SBTGEN for expansion of the subtour for the given base patron, and

to keep the best subtour that has been established.

3.1.4 Subroutine S3TGEN

Subroutine SBTGEN screens patrons for ridesharing with the base patrons;

then it calls Subroutine TRCOMB to conduct further investigation. Patrons are

added to the subtour one at a time.

3.1.5 Subroutine TRCOMB

Subroutine TRCOMB systematically inserts the two stops for the new patron

into the existing order of stops of the subtour. It then calls Subroutine

FESIBL to check the feasibility of the specific order of patron stops, and

Subroutine RMTIME to calculate the remaining time of the base trip.

3.1.6 Subroutine FESIBL

Subroutine FESIBL checks whether the given order of patron stops of the

subtour is feasible in terms of service quality criteria, such as time windows

and maximum on board time.

3.1.7 Subroutine RMTIME

Subroutine RMTIME calculates the remaining free time frcm the maximum

on-board time of the base patron for the currently entered tentative stop

sequence of the sub tour, saving the stop sequence with the larger remaining

time.

The complete listing of RSDAR can be found in Appendix I

.

25
3.2 INPUT DATA REQUIREMENTS

The RSDAR Subsystem assumes the existence of many data files to be read as

input. These data files are a subset of files generated by the CONENV

subsystem.

The input data to be read by RSDAR are a set of variables and a set of

arrays. The variables to be read in are PA03VX,PA03XX,PA07XX,PA10XX,PA08XX,

PA08RX,IBX and IDX. These variables are defined below:

PA03VX: Number of Vehicle Entries In Candidate Trip List (one/tour +

one/break)

.

PAQ3XX: Total Number of Entries in Candidate Trip List (Vehicles + Trips).

PA07XX: Number of Vehicle Types.

PA08RX: Number of Real Tours.

PAQ8XX: Number of Available Tours (Real + Artificial).

PA10XX: Number of Entries in Vehicle Capacity-Dwell List.

IBX: Local Index Variable for Base Trip Matrix.

IDX: Local Index Variable for Distance Matrix.

Nine arrays (namely, VTYPEL, VCADWE , TQURLI , CANDTP, BASETP, COMPAT,

DISTOO, DISTOD, and PRIQRL) are also read in as input. They are described in

the following paragraphs.

The VTYPEL array contains, for each type of vehicle, mobility and

priority types that the vehicle can accommodate, the maximum capacity for

non-wheelchair patrons, characteristics of vehicle, and a pointer to array

VCADWE

.

The VCADWE array contains information on vehicle dwell time due to

patrons boarding or debarking the vehicle. VCADWE has three patron

26
categories, non-wheelchair, lift, and wheelchair, and two types of dwell time,

pick dwell and drop dwell for each. Dwell times are indexed by the number of

non-wheelchair patrons.

The VCADWE array also provides the vehicle capacity for wheelchair

patrons. All combined capacities of wheelchair patrons and non-wheelchair

patrons can also be found there.

Dwell times of vehicle types are stored consecutively in VCADWE . For

each type, a pointer in VTYPEL indicates the corresponding first row of dwell

times

.

The TOURLI array lists information on vehicles assigned to tours. For

every available tour, this array stores the vehicle index, type, and patron

priorities that the vehicle can handle.

The CANDTP array is the candidate trip list; it contains information on a

trip required by a patron and stops required of the vehicle. For each trip

request, the CANDTP uses sixteen words to store all relevant information.

The BASETP array is a matrix used to indicate permissible ride sharing of

base trips. The BASETP rows represent base trips, columns of the matrix

represent sharing trips, and elements of the matrix are either zero or one.

If a^j * 1, trip j can share a ride with base trip i; if a

i j » 0, trip j can

not share a ride with base trip i.

BASETP also presents the number of trips, by priority, that can share a

ride with each base trip.

The COMPAT array is similar to the BASETP array: its elements, b^-,

indicate whether trip i and trip j can be assigned to the same subtour.

The DIST00 and DISTOD arrays contain distance (or equivalent travel time;

matrices. The DIST00 array stores distances from origin to origin or

27
destination to destination. The origin-to-origin distances are -stored in the

upper right part of the matrix, and the destination-to-destination distances

in the lower left part of the array. They are separated by the diagonal

elements, which are all zero

3 .

The DISTOD array contains the distance matrix of origin to destination.

A row of the matrix represents origin index, and a column of the matrix

represents destination index.

Distances are actually stored in terms of travel time (to the nearest 1/8

of a minute) at a nominal speed. Since only ten bits of storage are allocated

for this element, travel distance is limited to a maximum of 128 minutes at

nominal speed. To save memory space, three distance elements are stored in

one word in DISTOO and DISTOD.

The PRICRL array contains the assigned productivity code for each

priority, a productivity measure calculated in subroutine PRDCTY. PRIORL also

stores numbers of patrons in each priority.

3.3 PARAMETERS

The PARAMETER statement in Subroutine MAIN declares values of eleven

parameters which are used as "named constants" for array dimensions

throughout RSDAR.

Since RSDAR may be installed in different computer systems and may have

to hancle extremely diverse dial-a-ride situations, array dimensions in all

subroutines are expected to be changed to satisfy the need. Using parameter

declaration makes it easier to locate and change these values. Changes are

limited to Subroutine MAIN; other subroutines need not be recompiled.

23
1. PARM01. It dimensions arrays BASETP and COMPAT.

The minimum value should be ( (PA03PX/31)+4)*?A03PX, where PA03PX is the

number of trip requests. All divisions performed in estimating values of

parameters are rounded up to the next higher integer.

The divisor is 31 because the first bit of a 32-bit word is a sign bit.

In BASETP and COMPAT, information is stored in a single bit.

2. PARM02: It dimensions array BVECT1, and the minimum value should be

(PA03PX/ 31)+4.

3. PARM03: It dimensions array CANDTP and the minimum value is set to be

ICAX, the maximum number of entries for GANTT? . The entries for CANDTP

are of three types: tour start, tour break, and patron trip. Each tour

start, tour break, and patron trip needs an entry in CANDTP.

4. PARM04: It dimensions arrays DISTOD and DISTOO and the minimum value is

(PA03XX) 2/3

.

5. PARM05: It dimensions arrays I3SBTR, ICSBTR, ISE, and KSE . Since it is

the maximum number of stops in a sub tour, the value is estimated by an

"educated guess."

6. PARM06 : It dimensions array IVWHTR. Since it is the maximum number of

stops in a tour, the value is estimated by an "educated gue33."

7. PARM07

:

It dimensions array VTYPEL. The minimum value is the number of

vehicle types

.

8. PARM08: It dimensions array TOURLI. The minimum value i3 the number of

tours

.

9. PARM09

:

It dimensions array TSTOPL. The minimum value is 2*?A03XX.

10. PARM10: It dimensions array VCADWE . The minimum value is T (l-t-C^) where

i

C^ is the non-wheelchair capacity of vehicle type i.

11. PARM11: It dimensions array PRD3D and the minimum value is PA03PX.

29
3.4 MODEL OUTPUT

The outputs of the RSDAR model are stored in three arrays: two of them,

CANDTP and TOURLI appear in input and are augmented by RSDAR. The third file,

TSTOPL, the tour stop list, is created in RSDAR.

The following items are associated with each patron in the CANDTP array

as part of the output of RSDAR.

•jjp 1. Scheduled and expected pickup time;

2. Scheduled and expected dropoff time;

3. Tour assignment;

4. Pickup stop in the tour;

5. Dropoff stop in the tour;

6. Callback indicator; and

7 . Locations for tour stops if necessary

Two items are to be added to every tour in the TOURLI array: the number

of stops assigned to the tour, and the number of the row in TSTOPL where tour

stops begin.

The TSTOPL array contains the tour stop list, storing the following items

for every stop of each tour.

(1) Type of stop.

(A) pickup

(B) dropoff

(C) break start

(D) break end

(E) tour start

(F) tour end

•x In RSDAR, scheduled and expected times have the same value. The expected

time is included here to accommodate monitoring and ex post facto reporting

functions

.

30
(2) Dwell time. During the vehicle dwell time’ (expressed in l/8ths of a

minute) at a stop, patrons board or disembark the vehicle.

(3) Patron index. This is the candidate trip list, making accessible all

information regarding the patron in CANDTP.

(4) Number of non-wheelchair patrons on board for next leg.

(5) Number of lift patrons on board for next leg.

(6) Number of wheelchair patrons on board for next leg.

(7) Travel time. The time, expressed in minutes, to travel from this

stop to the next.

(8) Slack time. This is the time the vehicle is idle, expressed in

minutes

.

(9) Possible delay time. The difference between latest drop time and

scheduled drop time shows the possible delay time for this stop

without violating its time window.

31
4.

OPERATIONAL CHARACTERISTICS OF RSDAR

4.1 COMPUTATIONAL RESULTS WITH RSDAR

A sample problem, collected from a one-day paratransit operation, was

used for all test runs. There were 300 patron trip requests, 33 of which were

for wheelchair patrons. The data file first listed all wheelchair trip

requests, then the regular trip requests. Within each patron type, the data

were chronologically ordered. The trip request data included patron's name,

required pickup time, type of patron, number In the party, and locations (X,Y

coordinates) of trip origin and destination. Appendix J lists the complete

data file for 300 patron trip requests.

A set of external conditions influences the routing and scheduling of

patrons. As set in CONENV, these are read as input to the RSDAR subsystem,

including information on: — 1. service quality criteria;

2. productivity measures for each priority;

3. patron characteristics;

4. dwell time;

5. vehicle characteristics;

6. number of tours available;

7. tour starting, break and ending times and locations; and

3. names of patron sponsoring agency.

32
Two series of test runs were made on the development system (see section

4.3 for description). Each series had seven runs, the first run started with

25 patrons, and the number of patrons increased by 25 for each succeeding run.

The last run had 175 patrons. The two series of test runs differed in the

productivity measure used in selecting subtours. The first series of test

runs used number of patrons as the productivity measure for all patrons in the

run. The second series used number of patrons as the productivity measure for

wheelchair patrons and the ratio of number of patrons per unit time as the

productivity measure for regular patrons. The details of ran times, number of

tours, and number of patrons assigned for the two series of test run are

listed in Table 4.1 and Table 4.2 respectively; the numbers of stops in each

for every test run is listed in Table 4.3 and Table 4.4. Wheelchair patrons

were assigned a priority of 1; others were assigned a priority of 15.

From these runs, it was observed that the heuristic algorithm is very

sensitive to input data. The run time appears to vary approximately cubically

with respect to the number of patrons. That the the run time varies with the

productivity measure used can be seen in Table 4.1 and Table 4.3 for the two

series of test runs.

To explore the effect of the number of priorities on the computer running

time, eight test runs were carried out. Using 100 non-wheelchair patrons from

the data base, each run was given a number of priorities, then these 100

patrons were uniformly distributed over the number of priorities. The test

results are in Table 4.5.

33
Table 4.1 Results of #1 Test Series (Using Productivity Measure if 1

for All Patrons)

Number

Number Number of

of Run of Patrons

Patrons Time Tours Assigned

25 1:17 7 25

50 5:11 10 50

75 16:07 20 75

100 1:02:38 25 100

125 1:34:20 29 125

150 2:13:47 32 149

175 2:48:46 32 172

Table 4.2 Results of

Vrtieelchair

Patrons)

if 2 Test

Patrons

Series (Using Productivity Measure if 1 for

and Productivity Measure #3 for Regular

Number

of

Patrons

Run

Time

Number

of

Tours

Number

of

Patrons

Assigned

25 1:12 7 25

50 6:25 11 50

75 29:46 22 75

100 1:28:26 27 100

125 2:33:12 30 125

150 3:29:37 32 146

175 5:03:12 32 170

34
Table 4.3 Tour Assignments of #1 Test Series

Tour

Number Number of Patrons

1 *

2 * 3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

25 50 75 100 125 150

4 7 7

6 9 7 4 5 5

4 6 9

4 5 7 2144 3

2

4 4

3 4

3 53

3

3

3

2

2

2

2

1

1

8

76

8

7

52

5

4

4

4

4

4

3

3

3

3

3

3

3

3

3

3

l

1

8

7

6

8

8

5

7

3

4

6

5

4

4

4

4

6

4

4

3

3

3

3

3

3

2

2

2

2

9

10

6

79

5

3

5

4

8

6

8

4

5

54

6

4

3

3

3

4

3

3

4

4

3

3

2

2

2

2

10

8

6

q3

56

6

9

8

8

76

76

6

8

4

4

4

53

3

5

3

3

3

3

3

OL

o

Number of

Tours 7 10 20 25 29 32 32

Number of

Patrons

Assigned 25 50 75 100 125 149 172

xThe rirst and second tours include a mandatory break stop.

35
Table 4.4 Tour Assignments of #2 Test Series

Tour

Number Number of Patrons

1 *

2 *

3

4

5

6

78

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

25 50 75 100 125 150 175

4

6

4

4

4

2

1

8

79

5

6

75

3

6

4

6

4

5

6

5

4

3

4

2

3

3

3

2

3

3

2

2

2

1

1

9

8

8

6

8

5

6

5

8

6

5

3

6

4

4

5

5

4

3

5

3

3

3

3

5

2

3

23

2

13

10

8

8

6

8

7

6

6

8

8

8

6

5

7

5

5

54

4

4

3

5

4

3

6

6

2

3

3

2

3

2

Number of

Tours 7 11 22

Number of

Patrons

Assigned 25 50 75

27 30 32 32

100 125 146 170

*The first and second tours include a mandatory break stop.

36
Number of

Priorities Run Time

Number of

Tours

Number of

Subtours

1 2:47:28 26 34

2 1:23:20 29 40

3 1:08:48 29 37

4 1:10:18 30 40

6 59:14 31 41

8 58:45 32 41

10 1:04:36 30 39

15 1:10:13 30 38

Table 4.5 Test Results of Different Number of Priorities

Test runs were also made by perturbing the length of the time interval

for patron starting times. It was observed that both the computer run time

and the number of tours decreased monotonically as the length of the time

interval increased. For a set of 100 patrons, the starting times of all

patrons were distributed uniformly within a time interval of 100 minutes, the

RSDAR generated a schedule of 29 tours and the computer run time was about one

hour and thirty six minutes. When the time interval was increased to 400

minutes, the schedule had only 14 tours and the run time was only about twenty

minutes

.

4.2 COMPUTER SYSTEM CONFIGURATION1

All computer runs described in this report were executed on a WICAT

System 150. The processor for the WICAT System 150 is the Motorola 68000

which runs at 8 MHz and executes approximately one million instructions per

second. This processor has a 16-bit external data path, but internally it has

^"Identification of commercial products is included only to adequately specify

the test procedure. Identification does not imply recommendation or endorsement by the National Bureau of Standards.

37
32-bit registers and supports 32-bit operations. The computer system hardware

configuration has a memory size of 512 KB of dynamic RAM, a 15 MB 5 1/4"

Winchester disk drive, a 960KB 5 1/4" floppy disk drive, a cathode ray

terminal, and a 132 character/line hard copy printer.

The operating system for the WICAT-150 is a WICAT version of UNIX. A

FORTRAN 77 compiler is also a part of the system software.

4.3 COMPUTER HARDWARE AND SOFTWARE REQUIREMENTS

The minimum requirements for computer hardware to be able to run the

RSDAR subsystem are specified as follows:

1. The Central Processing Unit (CPU) requires 32-bit internal registers to

support 32-bit data operations. Lengths greater than 32-bits are

acceptable.

2. The memory size requires at least 512 kilobytes.

3. The mass storage requires a Winchester disk drive of at least 15 megabyte

capacity and at least one floppy disk drive for backup and file handling

purposes

.

4. A CRT (24 line by 80 character) which generates and displays the 96

character ASCII set.

5. A high-quality printer which has a line width of 132 characters and

handles tractor feed pages.

The computer software requirement for RSDAR are a FORTRAN complier which

implements FORTRAN-77 and an operating system with file handling and editing

capability.

38
Appendix A INTERNAL DATA FORMATS

This appendix defines all global data arrays used in RSDAR. The

specifications are given in a series of tables.^- The tables appear in

alphabetic order of variable name. Each specification includes:

2

1 - Array name (e.g., CANDTP)

2 - Dimensioning parameter (e.g., PARM03)

3 - Counts and subcounts as necessary (e.g., PA03VX, PA03RX, PA03XX)

4 - Definition (e.g., Deviation Both [i.e., patron and vehicle])

5 - Element length: bits or characters (e.g., 7 bits)

6 - Bit/word/f ield relations (e.g., bits 2-8, word 7, Deviation)

7 - Units (e.g., minutes)

8 - Range or discrete allowable values (e.g., 0-127)

9 - Coding or interpretation (e.g., not used)

^The tables are numbered consecutively for all global arrays for the system

(CONENV, RSDAR, and GREPOR) . Only those tables (A. 10 through A. 39) for

arrays in RSDaR appear in this appendix.

“Examples given in the text are based on an entry from table A. 12.

Al
Table A. 10 - EASETP BASE TriP matrix

PARMOl ,PA01XX

Name Word 1st Bit Length Units Range Coding

Priority 1 Trips 1 2 7 0-127

Priority 2 Trips 9 8 — 0-255

Priority 3 Trips 17 8 - 0-255

Priority 4 Trips 25 8 — 0-255

Priority 5 Trips 2 2 7 — 0-127

Priority 6 Trips 9 8 — 0-255

Priority 7 Trips 17 8 - 0-255

Priority 3 Trips 25 S — 0-255

Priority 9 Trips 3 2 7 — 0-127

Priority 10 Trips 9 8 — 0-255

Priority 11 Trips 17 8 — 0-255

Priority 12 Trips 25 8 — 0-255

Priority 13 Trips 4 2 7 - 0-127

Priority 14 Trips 9 8 — 0-255

Priority 15 Trips 17 3 — 0-255

All Trips 25 8

•• 0-255

Incidence Bits 5 2-32 1 - 0-1 By bit for

trips 1-31

0+not potential

sharer

Impotent ial

sharer

Words 6, 7, etc. are analagou3 to word 5 for trips 32-62, 63-93 etc, up to

total number of patrons.

There are as many replications of the sequence a3 necessary for all patron

base trips.

A

2
Table A. 11 - BVECT1: Base trip matrix row VECTor

Name Word 1st Bit Length Units Range

Priority 1 Trips 1 2 7 0-127

Priority 2 Trips 9 8 — 0-255

Priority 3 Trips 17 8 - 0-255

Priority 4 Trips 25 8 — 0-255

Priority 5 Trips 2 2 7 - 0-127

Priority 6 Trips 9 8 - 0-255

Priority 7 Trips 17 8 - 0-255

Priority 8 Trips 25 8 — 0-255

Priority 9 Trips 3 2 7 — 0-127

Priority 10 Trips 9 8 — 0-255

Priority 11 Trips 17 8 - 0-255

Priority 12 Trips 25 8 — 0-255

Priority 13 Trips 4 2 7 — 0-127

Priority 14 Trips 9 8 - 0-255

Priority 15 Trips 17 8 - 0-255

All Trips 25 8 — 0-255

Incidence Bits 5 2-32 1 — 0-1

Coding

By bit for

trips 1-31

0-*not potential

sharer

1+potential

sharer

Words 6 , 7, etc. are analagous to word 5 for trips 32-62, 63-93 etc, up to

total number of patrons.
Table

A.

12-

CANDTP

CANDidate

TrlPs

PARM03,

PA03VX,

PA03RX,

PA03XX

u

a z S-t <D a TO TO 1-4 jX 54 54 TO

T3 AJ TO TOy

y

y TO

a o 3 3 y

y

y cO

yy CJ AJ f—4 3 y JO CO

O

O AJ c f-4 O •H y c o y r-4 o TO o a H H CJ o a y c TO V4 to y f—4 y JO S3 *-4 U y

g>

*4 cO

H 03

Oy AJ t4

a Cu

y

a aj

yy AJ AJ r-4

a

y 3 3 i—4 AJ <0 to a > s <4-1 1-4 a s e H 4-1 y <A4 H i-4 o AJ •H i4 y

«3u c a) TO s ya

a c o «0 o a

x J3 1-1

a

a

u <A4

aa

a

TO 04

a

a > < w

G < M©© z w Z iJ

©Q c AJ AJ 4>

O

A + + 4* 4> 4* •f >i 4- + + •f 4 •f >> + + A i-4 •H

©

©

O

H cs

© -4 CM cna i-4 P-4 i-4 1-4 r-4

a .-4 1-4

H

a r-4 —4 pH z z % m lO

ym

m

001

r* CS1 CO1 t-H t-H pH t-4 i-4I i—1 p-4 ?—41 pH 1-4 i—4 pH pH cs cs r-

<8 f o 1 o ! 1 © © 1 © 1 © I © f o i 1 © © 1 © 1 © < 1 © © 1 © ! © ! O 1 © 1 © a

CO aj l4a© I

ajcccy

cs CS r4 1—4 i4 i—4 i—4'.'O i—4 i—4 C") t—4 i—4 1—4 CO CO on

ua

cs <r \oo r> co on CS CO <r <} in vo i-»

m cs cn

-4 cs

~oyoZ O

CO

J=—1 o

.a oa oa

cs co

fc4 AJ04 oa oa o

i4

Cl.

O

-4 3 AJ O a

i-4 CJ AJ —4 a u-l y -4 H O

U4 (U •H O. o a

<y

x

x

a

a

u

yy

y

©

a

y TO TO

a TO Z >4

a AJ c a

a

a TO *3 o -4y .x -i >A4 1-4 >—i a 3 TO y a y © TO a TO o o a

y

y aj

y CJ AJ t—4 3 y JO o a

y

a

a (—4 cA a a c O y t—4 O St TO y © a © y o o a >»

>» >i aj

a 14 pH

y

a AJ 3 fH -I*.

y AJ AJ 4J

HH

a —4

a a. o a •h

y

y 4J S3 —i

-X o a

a AJ

a 3 c 1-4 AJ

y UH

O i-4

y <A4 y

y 3. a a.

a c O

a o i-4X _s

y

a •H

y .Xa o O 3 C —4 1-4 <! 1—4 © © z a a z pJ AJ © a a y o a —H a AJ 54 54 o a —4 y y z a H H s a a © a ^4

A4
Table

A.

12-

CANUTP

CANDidate

TrlPa

(continued)

y

U_i «H O JJo y «h y u s y y jj jj y

OQ

u

a

a

C •ft "H )-l •H cs x y

"3 Cd

X

O o a PQ .-l 00 CO 00 oo oo 00 00 00 **xx^ "x^ 'x^ s»

~x. Xx Px. px px Px r^x px. px. m pH m pH m pH

(U rx in px pH pH <T> o o C3 O'. crs CO in CM in CM 1H pH o pH o pH o -H c pH pH i—<

CM pHm in CO <T CO <T co

cd a: 1 pH 1 pH 1 o © 1 o 1 o I o 1 o o 1 o o o

as c aG c fl 1— c c a

JJ •H *H •H •H

H •H •H xJ •H i i 1 1 I 3 3 a a a a a a a

=> 00 CO CO CO co co oo co co —.

x^ -Xx^ **xx^ pH pH pH pH pH pH pH

fi

jjCO

y CO 00 CO PX CM CM CM

m sO

n sO

m -X) Cl pH «H pH pH pH pH pH

(U

jj «H

23

m CTv PX

m CM av i-H CM px. CM px CM

H pH CM CM pH pH pH

03

-3U cn

m vO

C3 y

y

pH 22 pH

C

y o y o > •H *« u H y P* AJ u iJ Hi H ±J jj H u

HH

fty o o o y

y

y o o o o o 0 > 23 23 23 Oh > CL. 23 23 23 23 a a y3 y y

*H

y 3 3

JH

a •H •H

ffl *H

H

H

y

y £ H

y

•H

X

y o X C*

H

y •H

—< yj

y

O

a.

a

y 23

H

y

H

y

«H c y

y 2-©

H

w

My

H o y y > 3 23 T3 TJ

JJ

y —4

a

y

y

pH

y >. pH 3 c H

H

XX > >-

y

y

y

y

y •P -X o y

y

*H Sj

a •Hy pH

y

y

y -X o. jd,

H t a y y 3 y y X Q, y o y o 3 y «£* CO y o X u y X X H u z > o < > H w =3 2 td Cd 04 34 Q

A3

Deviation

both

727

minutes

0-127

Not

Used
Table

A.

12-

CANDTP

CANDidate

TriPa

(continued)

eod

•Ho

CJy

40* e

«3 aS

SI

>* uH

JO

VI

y

•h a. ® <o u

>N -f « 1-t

inm in

m

mm

m CMi r-4i | f~4i 1 H rH 1 8 o 1 o 1 o 1 o i o 1 o

co

r-.

IT)I o

CO

r*.

cnI o

oo <n

m

cn • • « • • • c c e a a c c

•m •m •H •H

a

a

a

aa

a

aa I 1 1 C0 co

CO o CO 00 oo CO

>S. "v. I"U t—4 i—t

l—l 1—4 l“1

rU

—4 f"J i—l 1—4 t—k |-*H 'T «o CO co

cn cn cn cn cn cn

m

CN

ON

<N

CN CO CN CN CN CN CN CN CN

m ON CO

m

CN

vi CO ON o CM cnm NO o r-4 i-u r«4 3 O a tH c d

d

J2 J-J JO o U o o o o > vi u V) u H Vi r* J2 j= Vi Vi Vi JO SP — o o o VI JO VI •U iJ U iJ vi U vi vi vi u

Cm CO 133 33 «3 Oi c3 o o o o O o cO <0 <0 o o

a* > Oh £3 32 C3 CQ 02 CO su su Oh 33 ca

COcou

>*y o VI

VI 3)

aya as

a

«Ha •Ha •H CU

d

i—i

•H

H

y •w

H

y o

•H

H

a

H

a TJ Viy

y

a JO J* •Ha

Hy VI

a

a o as J* y H cu o H a. aJ •H •H

•H o. Vi

y •H o Vi cu CD Oh

H

H

Vi C3 4SH Oh Vi

a CU as

a

CO CJ

a Oh

y

a o y o Vi rU r—1

o> 0)

y CJ T3 •M T3 Vi

H ViH i*U

a *o -3 •H >. 3 VI <U CU VIy

a T3 VI

y

yy o o O CM VI 2 CO rH a r-4 C aj J0 3 3

CN o o •H «H <u 3 VI

y 3 VI _y Oh

y

a

a

VI Vi a» —1 -3 COM -a CD l—U r—t

0) Cu Jrf

aC

O c rU <U

y t-Uyy V)

y j*

a

a o O o CU *H o u j3 VI Vi -C VI

a <M

yy o

03 Vi •H Vi "3 Vi JO CO

y as

y

y CO o M

a •H Vi 2 Q 3- a Mi Oh Oh w CO to .-3 2 a 2 a a

A6
Table A. 13 - COMPAT COMPATibility matrix

PARMOl ,PA01XX

Name Word 1st Bit Length Units Range Coding

Priority 1 Riders 1 2 7 0-127

Priority 2 Riders 9 8 - 0-255

Priority 3 Riders 17 8 - 0-255

Priority 4 Riders 25 8 — 0-255

Priority 5 Riders 2 2 7 — 0-127

Priority 6 Riders 9 8 - 0-255

Priority 7 Riders 17 8 - 0-255

Priority 3 Riders 25 8 — 0-255

Priority 9 Riders 3 2 7 — 0-127

Priority 10 Riders 9 8 - 0-255

Priority 11 Riders 17 8 - 0-255

Priority 12 Riders 25 8 — 0-255

Priority 13 Riders 4 2 7 — 0-127

Priority 14 Riders 9 8 - 0-255

Priority 15 Riders 17 8 - 0-255

All Riders 25 8 — 0-255

Incidence Bits 5 2-32 1 — 0-1 By bit for trips

1-31

0+not potential

sharer

1+potential

sharer

Words 6, 7, etc. are analogous to word 5 for trips 32-62, 63-93 etc, up to

total number of patrons.

There are as many replications of the sequence as necessary for all patron

base trips.

A7
Table A. 14 - DISTOD DISTance Origin-Destination

PARMQ4 , PA0*4XX

Name Word 1st Bit Length Units Range Coding

Distance Pick 1 to Drop 1 1 3 10 1/8 min. 0-127 7/8

Pick 1 to Drop 2 13 10

Pick 1 to Drop 3 23 10

DISTOD is a square matrix stored as a vector

Table A. 15 - DISTOO DISTance Origin-Origin

PARM04 , PA04XX

Name Word 1st Bit Length Units Range Coding

Distance Pick I to Pick 1 1 3 10 1/8 min. 0-127 7/8

Pick 1 to Pick 2 13 10

Pick 1 to Pick 3 23 10

DISTOO is a square matrix stored as a vector . The upper triangular portion

has pick-to-pick times; the lower triangular portion, drop-to-drop times.

A8
Table A. 17 - IBSBTR BeSt SuBTouR

PARM05

Name Word 1st Bit Length Units Range Coding

Patron index 1 2 31

Stop type 2 2 31

NWC on board 3 2 31

Lift on board 4 2 31

WC on board 5 2 31

Travel time (next leg) 6 2 31 1/8 min

Dwell time 7 2 31 1/8 min

Scheduled time 8 2 31 1/ 8 min

Number of NWC 9 2 31

Number of Lift 10 2 31

Number of WC 11 2 31

Patron priority 12 2 31

A9
Table A. 18 - ICSBTR Current SuBTouR

PARM05

Name Word 1st Bit Length Units

Patron index i 2 31

Stop type 2

' 2 31

NWC on board 3 2 31

Lift on board 4 2 31

WC on board 5 2 31

Travel time (next leg) 6 2 31 1/8 min

Dwell time 7 2 31 1/8 min

Scheduled time 8 2 31 1/ 8 min

Number of NWC 9 2 31

Number of lift 10 2 31

Number of WC 11 2 31

Coding

Patron priority 12 2 31
Table A. 20 - ISE Working Area of Subtour

PARM05

Name Word 1st Bit Length Units Range Coding

Patron index 1 2 31

Stop type 2 2 31

NWC on board 3 2 31

Lift on board 4 2 31

WC on board 5 2 31

Travel time (next leg) 6 2 31 1/8 min

Dwell time 7 2 31 1/8 min

Scheduled time 8 2 31 1/ 8 min

Number of NWC 9 2 31

Number of Lift 10 2 31

Number of WC 11 2 31

Patron priority 12 2 31

All
Table A. 21 - IVWHTR WHole TouR

PARM06

Name Word 1st Bit Length Units

Patron index 1 2 31

Stop type 2 2 31

NWC on board 3 2 31

Lift on board 4 2 31

WC on board 5 2 31

Travel time (next leg) 6 2 31 1/8 min,

Dvell time 7 2 31 1/8 min

Scheduled time 8 2 31 1/8 min

Idle time 9 2 31 1/8 min

Potential delay time 10 2 31 1/8 min

Coding

A12
Table A. 22 - KSE Storage Area of Subtour

PARM05

Name Word 1st Bit Length Units Range

Patron index 1 2 31

Stop type 2 2 31

NWC on board 3 2 31

Lift on board 4 2 31

WC on board 5 2 31

Travel time (next leg) 6 2 31 1/8 min.

Dwell time 7 2 31 1/8 min.

Scheduled time 8 2 31 1/ 8 min.

Number of NWC 9 2 31

Number of Lift 10 2 31

Number of WC 11 2 31

Patron priority 12 2 31

A13
Table A. 25 - PRDBD PRoDuctivity bounDs

PARM11

Name Word 1st Bit Length Units Range Coding

Productivity bound in

Priority #1 for patron 1

1 2 31

Productivity bound in

Priority #2 for patron 1 2 2 31

Productivity bound in

Priority £3 for patron 1

3 2 31

Productivity bound in

Priority #4 for patron 1

4 2 31

Productivity bound in

Priority # 5 for patron 1

5 2 31

Productivity bound in

Priority #6 for patron 1 6 2 31

Productivity bound in

Priority #7 for patron 1

7 2 31

Productivity bound in

Priority #8 for patron 1 8 2 31

Productivity bound in

Priority #9 for patron 1

9

n

4m 31

Productivity bound in

Priority #10 for patron 1 10 2 31

Productivity bound in

Priority #11 for patron 1 11 2 31

Productivity bound in

Priority #12 for patron 1 12 2 31

Productivity bound in

Priority #13 for patron 1 13 2 31

Productivity bound in

Priority #14 for patron 1 14 94m 31

Productivity bound in

Priority #15 for patron 1 15 2 31

There are as many replications of the sequence as necessary for ail patrons.

A14
Table A. 26 - PRDCOD PRoDuctivity CODE of priority

15,15

Name Word -1st Bits Length

Productivity code of priority #1 1 2 31

Productivity code of priority #2 2 2 31

Productivity code of priority #3 3 2 31

Productivity code of priority #4 4 2 31

Productivity code of priority #5 5 2 31

Productivity code of priority #6 6 2 31

Productivity code of priority #7 7 2 31

Productivity code of priority #8 3 2 31

Productivity code of priority #9 9 2 31

Productivity code of priority #10 10 2 31

Productivity code of priority #11 11 2 31

Productivity code of priority #12 12 2 31

Productivity code of priority #13 13 2 31

Productivity code of priority #14 14 2 31

Productivity code of priority #15 15 2 31

Units Range Coding

A15
Table A. 2 7 - PRDIE PRoDuctlvities of Best sub tour

15,15

Name Word- 1st Bits Length

Productivity of priority

for current base patron

#1 1 2 31

Productivity of priority

for current base patron

#2 2 2 31

Productivity of priority

for current base patron

#3 3 2 31

Productivity of priority

for current base patron

#4 4 2 31

productivity of priority

for current base patron

#5 5 2 31

Productivity of priority

for current base patron

#6 6 2 31

Productivity of priority

for current base patron

#7 7 2 31

Productivity of priority

for current base patron

#8 8 2 31

Productivity of priority

for current base patron

#9 9 2 31

Productivity of priority

for current base patron

#10 10 2 31

Productivity of priority

for current base patron

#11 11 2 31

Productivity of priority

for current base patron

#12 12 2 31

Productivity of priority

for current base patron

#13 13 2 31

Productivity of priority

for current base patron

#14 14 2 31

Productivity of priority

for current base patron

#15 15 2 31

Units Range Coding

A16
Table A. 28 - PRDIC PRoDuctlvities of Current subtour

15,15

Name Word 1st Bits Length

Productivity of priority

for current base patron

#1 1 2 31

Productivity of priority

for current base patron

#2 2 2 31

Productivity of priority

for current base patron

#3 3 2 31

Productivity of priority

for current base patron

#4 4 2 31

Productivity of priority

for current base patron

#5 5 2 31

Productivity of priority

for current base patron

#6 6 2 31

Productivity of priority

for current base patron

#7 7 2 31

Productivity of priority

for current base patron

#8 8 2 31

Productivity of priority

for current base patron

#9 9 2 31

Productivity of priority

for current base patron

#10 10 *> 31

Productivity of priority

for current base patron

#11 11 2 31

Productivity of priority

for current base patron

#12 12 2 31

Productivity of priority

for current base patron

#13 13 2 31

Productivity of priority

for current base patron

#14 14 2 31

Productivity of priority

for current base patron

#15 15 2 31

Units Range Coding

A17
Name

Priority

Number Advanced

Number Immediate

Productivity Code

Table A. 29 - PRIORL PRIORity List

15,15

Word 1st Bit Length Units Range Coding

Index - - - 1-15

1 2 11 - 0-2047

12 12 - 0-4095

29 4 1-15

A13
Table A. 30 - PRIOTR Priority TRuth table

15,15

Name Word 1st Bits Length Units Range Coding

Is priority #1

current tour ? accepted by 1 2 31

Is priority #2

current tour ? accepted by .2 2 31

Is priority #3

current tour ? accepted by 3 2 31

Is priority #4

current tour ? accepted by 4 2 31

Is priority #5

current tour ? accepted by 5 2 31

Is priority #6

current tour ? accepted by 6 2 31

Is priority #7

current tour ? accepted by 7 2 31

Is priority #

8

current tour ? accepted by 8 2 31

Is priority #9

current tour ? accepted by 9 2 31

Is priority #10

current tour ? accepted by 10 2 31

Is priority #11

current tour ? accepted by 11 2 31

Is priority #12

current tour ? accepted by 12 2 31

Is priority #13

current tour ? accepted by 13 2 31

Is priority #14

current tour ? accepted by 14 2 31

Is priority #15 accepted by 15 2 31

current tour ?

1 - indicates yes and 0 indicates no.

A19
Table

A.

35-

TOURLI

TOUR

List

PARM08,

PA08RX,

PA08UX,

PA8XX o So

4-> pH o a p3 4-1 T3

T3 o Oh©

4J 0)

O Co X! pH X ao H b ©

pH 0) e c/a pH ©) •h *o pH H pH C o

-Q e 4-1 pH pH pH © «H b e © 4-1 O pH © © a

0) Cu

H 4-1 pH

b

© >. pH

©

b

pH

© • b

b o ©

H3 Co 4J .. o 4_> .. o b a c 4-4 3 y

4-i

a pH pH 3 pH S ©

aq pH 3 b ca o b c ca o o "3 JO y ©

pH

y pH 0! 4-1 so

y ?p •a Co y b © © ca © y o ca © a © o m

l-p cn *s 1

© CM

m o CM

H r-4l i

r>.1 <r) ©! pH1 i © o o o © o ©

as©

pH 1 i i 1 1 1 1 i

aoc©

m CO CM MS

CM Cs CO CM

m

X©

”3

CS M

CM

CM

CO

So u

JO©

>* CU b ©

pH

u

pH

pH

©©

J3 a.

by

X!

© o © pH

©

© CU 4J 4-1

b

b T3 CU « ao c/a 3 © © C so u © pH pH -§ w H pH lb o b

So Cb o Oh

© 3 © © b 4-1 Z pH pH pH 4J b J So y y y b b © Oh y ©

©

b —4 pH

O

O -§

© c b

a 3 p JO pH Q.

H

©

©

©O

*©

©b

© 3 c/a 4?

JO z H > > Ot aS Z H o

A20
Table

A.

37

-

TSTOPL

Tour

STOP

List

PARM09

,

PA09XX

00a

•HT3O

o

U a U O

ca a) 3 h

U o u ca h u

-X CU M 5-1 O O 3 TJ TJ 3

•M M 4J C 3 JJ q « a a w

+ + ++ + h n n -j io \o

3

u

03 03

i-i T3a«o

+o

CO

1*1 o ri. u0 UO ri x: H f-4 CM uo uo CM CM sO CO

1 CS4i *—l

i r-H CM

1 CM« iTM41 t >T1 CO1 CM1 3

1 r"4

1 o1 p—

1

o

I o

I o1 O

1 o

1 o

1 O

1 O

•a a a a

a 3 3 cu a u j-i •H 1 1 r 1 1 1 3 3 3 1 1 3 00 3 3 3 3 —

*

•H «H ^4 a a a

JCu

00c

3

*J

CO CO M3 <r r>. co co n cm CM 1/1 CM

CM m co o iH CM CM oo ri CM <T\ —

'

CM O <—

l

co

"3M

o3

CM CO sr

X

3

*T33M 60 3 3 3 3 CU fH

CU —

H

4J C*4 H a H 03 4J tH «H u

<y cu iH T3 o

s o 3 3 Cu 3 u 3 3 3 2 CO Q O £d

3 3 M

M s 3

60 3 1-1 4_l 3 03 H c

-J •H 0) •M

2d 60 4_> J-i o 3 3 3 V —a s X 3 M U

O 3 u OJ 3 -4 3 «M CM a 3 2 3 03 3 4J CM 4-J M

1 3 —4 31 X o o 3 -3 •H ad O 3 cu -o lJ u ~u. 2 3 2d 3 •H U

3 4_l 3 1 > y 2 ±J •3 o

O CJ CM 3 3 3 3 3 u 2- ca ZZ M 33 3 U •H **H o 3 V 2 fJ "F a H CO X Q. CJ 36 3 —4 3 V O H 2 »v>

A21

1+Drop

Stop

2>Pick

Stop
Table

A.

38-

VCADWE

Vehicle

CApaclty

and

DWEll

PA11H10>

PA10XX oZo

.c

pH

aaaa

aa 3 5h u SH Sh S4 S4 CJ 3 05 a . a a a

>> z 3 *3 "3 *3 ”3 •3

4J z pH «H pH pH pH -H pH SH Sh u Sh Sh Sh o a pH

03 05 1 pH pH F—

pH pH

H

COa

a

M I 1 1 1 1 i c 3 3 M M M M M l-H -H O J3 a JJ JH JH Sh Sh Sh Sh o CJ O •H O O O O O O o 3 z 3 Eh pH Eh Eh Eh a

03 CO CO 03 00

a

h^ 'p

— 

H^

Ph PH rn fH PH PH 3

CO LO un pH pH pH pH pH pH

so f—4 1 pH C3 en <r>

n oo cn

08 1 1 ! ! 1 i l l l DC o O O O O o o o • • • • • • c a c a c c

pH pH pH pH pH 3 a a a a a

a

•U pH 1 » I CO CO CO co co

a c 'H. M SM H.

=5 pH pH i—4 i—4 pH

J_i CO rn 1 ph co co CO 8 8 a Caa

hi pH

CQ CM 1 CM ON PH

m ON pH

m

U pH CM pH CM a5

c—»

"3u *4 cm pH CM o3

/<~S pHt

En

xj pHU3 a

a

a 35

a

aa 3 3 pH a a pH

a 0 pH H e H H s H pH H pH Uppp pH H pH H

pH pH pH t—1 z pH a pH pH a pH

05 3 pH

a 3 pH

>> CM >* 3 aa 3 aa

•LJ I HI

Q 3 a 3

pH

M -H pp

a

a

O w- CJ

a

a o 3 3 O a -* O )H

a

a.

m a. pH

a 45 Sh

a o 3 3 <3 a pH a Sh -3 cj Hi a u a

Sh

u CJ 04O 1H

45

O cjO CJ 3 pH CJ Z pH o a u 3 o 3 z a 3 z a 3

ns 45 3 Z oc pH*

A22
50C

1-4 T3O

CJ

4)to

Ml c

as «!

fid CM 00 X mi H •HC

ou 3

r-4O

XX

X

a 0 mi > < 50

PMC j « O

fid r>. nJ

CM

O » 2 H> <

CM Ml 1 iH

JO ON

cn Ml • 00 <d r 0

rH

M3X 53 H MlO3 m

I—4 IIIIX«

T3X

CO 53 0 4) •H X

mi 4)

00 50 00 H a i-4 Ml Xi V Ml

Ml

X

O Ml

u

(3 T-l 0

Ml

XXX 1—4

•Ml CO Ml Ml Ml •H X i-t •H •H J3 Ed O .H iH c0 3 4) •H •H H a Q a

ai

x

X J3 co < >>

V 0 0 CO

u CJ Ml

Ml CU CM CM + >

J= « CO CO p-H 41 mi a CJ 0 U

pPfi l“M Ml O

Ml - —

—

O 1-1

a

X 3 m3 « X

M - —

—

O 4) *H -f + + >* H >

P&4 «-* 1—4 i—4 « X m <r N H1 1 H• ?—4

r“4 1 vO1 1 1 O O O 1 O 1 1 O I O I I I I II I

C*1 i—4 i—I

<r co sO

mn cn «?

m o>X X Ml

Ml •H

•H ?—4 O iM

C3 M3

CM

X

c0 CM

CJ

X

CJ TJ

4) CJ

M

41 cm i-4

X

4J T3

a Ml Ml CM O CO 0

IP

X CJ

O •H 1-4

H •H

M

O

X •a 0 CMl 41 Ml Ml

i—4

H

X CJ fid

41

O r-4

—

X

•H •H Ml

Q s X M3 S3 X < CO 41 O O CJ 2 > 2 2 CJ >

A23
'
APPENDIX B INPUT FORMATS

Appendix B, within this series of reports, is reserved for input formats.

Since RSDAR uses no input, Appendix B is empty.

31

APPENDIX C * INTERFACE FORMATS

This appendix defines the use, content, and format of the files which are

interfaces to RSDAR. Content is as extracted from a FORTRAN READ/WRITE

statement. The format specification is as extracted from a FORMAT statement.

To avoid confusion between the number 0 and the letter 0 representing an octal

FORMAT, a lower case o will be used.

Cl
1. File zc.rsd

This file is created by CONENV for input to PJ3DAB.. Its content is those

global variables required for execution of RSDAR plus several variables used

for setting read specifications. The content, format and example reference

are as follows:

1 - Outer loop - none

Content - PA01XX, PA02XX, PA03XX, PA04XX, PA05XS, PAO6 XX, PA07XX,

PA08XX, PA09XX, PA10XX, PA11XX, PA12XX, PA13XX, PA14XX,

PA15XX, PA16XX, PA17XX, PA18XX, PA03VX, PA08RX, IBX, IDX.

IBX is the number of words/base trip

IDX = PA04XX

Format - (20o6)

2 - Outer loop - none

Content - ( VTYPEL [I], 1=1, PA07XX)

Format - (8ol2)

3 - Outer loop - (1=1, PA10XX)

Content - (I,VCADWE [I,J], J=l,2)

Format - (15, 2ol2)

4 - Outer loop - (1=1, PA08XX)

Content - (I, TOURLI [I,J], J=l,3)

Format - (I5,3ol2)

5 - Outer loop - (1=1, PA03XX)

Content - (I,CANDTP [I,J], J=l,16)

Format - (15 ,8ol2/5X,8ol2)

6 - Outer loop - (1=1, PA03XX-PA03VX)

Content - (I.BASETP [I,Jj, J=l, I3X)

( I , COMPAT [I,J], J=l, IBX)

Format - (15 ,8ol2/5X,8ol2) for each write

7 - Outer loop - (1=1, IDX)

Content - (I,DISTOO [I], DISTOD [I])

Format - (I5,2ol2)

8 - Outer loop - (1=1,15)

Content - (I, PRIORL [I])

Format - (I5,ol2)

C2
2. File zr.gre

This file is created by RSDAR for input to GREPOR. Its content is some

global variables created by RSDAR and some from zc.rsd whose values have been

modified by RSDAR. The content, format, and example reference are as follows:

1 - Outer loop - none

Content - PA09XX, PA08UX

Format - (2012)

2 - Outer loop - (1=1, PA03XX)

Content - (CANDTP [I,JJ, J=l,16)

Format - (8012)

3 - Outer loop - (1=1, PA09XX)

Content - (TSTOPL [I,J] ,. J=1 ,4)

Format - (3012)

4 - Outer loop - (1=1, PA08UX)

Content - (TOURLI [I,J], J-1,3)

Format (8012)

C3
'

:

.

.
APPENDIX D OUTPUT FORMATS

Appendix D, within this set of reports, is reserved for output formats.

RSDAR produces no output, this appendix is empty.

Since

Dl
APPENDIX E SAMPLE INPUT

Appendix E, within this series of reports, is reserved for a sample Input set.

The sample input is never referenced in the RSDAR exposition; therefore this

appendix is empty.

El
APPENDIX F SAMPEL INTERFACES

Appendix F, in this series of reports is reserved for listings of interface

files produced by execution of CONENV and RSDAR with the sample Input of

Appendix E. Since the sample input is not referenced in the RSDAR exposition,

this appendix is empty.

FI
APPENDIX G SAMPLE OUTPUT

Appendix G, in this series of

There is no ouput from RSDAS;

reports, is reserved for a sample output set.

this appendix is empty.

G1
APPENDIX E SUBROUTINE SPE Cl FI CATIONS

This appendix provides a brief description of all subroutines in the model.

For the MAIN program, a more detailed description by functional block is given

in Chapter 3. The appendix is arranged in alphabetical order by subroutine

name. Each subroutine is described on a single program summary sheet. This

summary sheet includes: (a) the name of the subroutine; (b) the mnemonic of

the subroutine; (c) the purpose of the subroutine; (d) the called routines;

(e) the arguments used; (f) the calling routines; (g) input from file storage;

(h) output to file storage. The information provided on these summary sheets

in conjunction with the model flowchart shown in Chapter 3 should facilitate

the programmer's task of effectively maintaining the model. The interactions

among subroutines which are explicitly stated on the summary sheets should

also assist the programmer in making any modifications to the source code

dictated by user needs or peculiarities of the operating system.

HI
Subroutine CALBCK - CALi BaCK

Purpose Mark those patron who need a call back because the scheduled

pickup time is outside the promised time window.

Called by MAIN

Arguments CANDTP PA03VX PA03XX

Calls FIELD

H2
Subroutine DUMPGR - DUMP to GRepor

Purpose Write output of RSDAR on a disk file, zr.gre.

Called by MAIN

Arguments PA03XX PA08UX PA09XX CANDTP TOURLI TSTOPL PARM03 PARM08

PARM09

Calls None

Output zr.gre interface to GREPOR

H3
Subroutine DWELL! - DWELL Time

Purpose Obtain appropriate dwell time from VCADWE array

Called by TRCOMB

Arguments VCADWE FARM10

II: Number of non-wheelchair patrons to pickup

12: Number of lift patrons to pickup

13: Number of wheelchair patrons to pickup

14: Number of non-wheelchair patrons to drop off

15: Number of lift patrons to drop off

16: Number of wheelchair patrons to drop off

Jl: Starting row in VTYPEL

DWT : Dwell Time

Calls FIELD

H4
Subroutine

Purpose

Called by

Arguments

Calls

FESIBL - FEaSIBiLity check

Check if the subtour is feasible

TRCOMB

CANDTP , DI ST OD , DISTOO , PARM03 , PA03XX , PARM04 , PARM05 , PARH06

IK2: Number of stops in subtour.

IFLAG1: =1 : subtour is feasible.

=0 : subtour is not feasible.

IFLAG5: =1 : subtour cut short due to end of interval

=0 : otherwise.

IVWHTR: Whole tour of a vehicle.

KSE: Storage area of sub tour.

IBGNP: Patron at the beginning of time interval.

IBGNS: Stop at the beginning of time interval.

IENDP: Patron at the end of time interval.

IENDS: Stop at the end of time interval.

None

H5
Subroutine FIELD - store or fetch FIELD

Purpose Pack or unpack bits information into or from a word.

Called by CALBCK DWELLT MNTOUR PREPRD RMTIME SBTGEN SBTOUR TFETCH

TRC0M3

Arguments I: 1=1 means unpacking

1=2 means packing

J: Packed argument

K: Unpacked argument

11: First bit position in packed argument

12: Number of bits

Calls None

H6
Subroutine MAIN

Purpose Initialize the run. Call READCV to read input tile; MNTOUR

to create tours, and DUMPGR to write output file.

Called by None

Arguments None

Calls SEADCC MNTOUR CALBCK DUMPCC

Parameters PARM01 , PARM02 , PARM03 , PARM04 , PARM05 , PARH06 , PARM07 , PARM08 , PARMO 9 , PARM1 0 , PARMl

1

H7
Subroutine MNTOUR - MaiN TOUR

Purpose 1. Calculate productivity upper bounds

2. Read in starting, ending, and break time of a tour, then

call SBTOUR to generate subtours for the tour.

3. Repeat step 2 until either all patrons are assigned or all available tours are exhausted.

Called by MAIN

Arguments BASET? , CANDTP , COM?AT , DI STOD , DI STOO , PA03PX

,

PA03VX , PA03XX ,PA03R , PRIORL

,

TOURLI ,TSTOPL,VCADWE , VTYPEL

BVECT1: A row vector from BASETP

IBSBTR: Best subtour in existence

IC3BTR: Current subtour

IWHTR: Whole tour of a vehicle

ISE: Working area of subtour

XSE: Storage area of subtour

PRIOTR: Priority truth table

PRDI3: Productivities of the best subtour

PRDIC: Productivities of the current subtour

PRDBD: Productivity bounds

PRIOSM: Priority sum

FRDCOD: Productivity code of priority

Calls FIELD PRDCTY SHIFT TFETCH SBTOUR

H8
Subroutine PRDCTY - PRoDuCtiviTY calculation

Purpose Calculate value of productivity

Called by PREPRD MNTOUR

Arguments IPCODE: Productivity code

PATRN: Number of patrons

TRIP: Number of trips

PATRT: Sum of patron ride time

TRPRT: Sum of trip ride time

TIME: Total elapsed time of the subtour

PRDV: Productivity value

Calls None

H9
Subroutine PRE PRD - PREpare for PRoDuctivity

Purpose Prepare for calculating value of productivity

Called by SBTOUR

Arguments CANDTP , PRDCOD , PARMQ3 , PARM05

IP: Priority

ICSBTR: Current sub tour

PRDIC: Productivity of current subtour

ISCTP: Number of stops in th current sub tour

Calls PRDCTY FIELD

H10
Subroutine READCV - READ ConenV interface

Purpose Read input data from disk file

Called by MAIN

Arguments BASETP , CANDT? , COMPAT , DI STOD , DI STOO , PHI ORL , TOURLI

,

VCADWE , VTIPEL,PARM03 ,PARM08 ,PARM10

PA03PX: Number of all trip enties in CANDTP

PA03VX: Number of all vehicle entries in CANDTP

PA03XX: Number of all entries in CANDTP

PA08RX: Number of real tour entries in TOURLI

PA08XX: Number of all tour entries in TOURLI

Calls None

Input zc.rsd interface from CONENV

Hll
Subroutine RMTIME - ReMaining TIME

Purpose Calculate the remaining free time of base patron

Called by TRCOMB

Arguments CANDTP , IK2 , I SE , KSE , PARM03 , PARM05

IA: New patron to be inserted

JK: Number of stops in the subtour;

IFLAG2: =1: A better subtour of IK2 stops is found,

=0 otherwise

IC1: Base patron

IC2: Scratch

RTB: Remaining time of the best sub tour

RTS: Remaining tme of subtour

SHTB: Shortest travel time of the best subtour

SETS: Shortest travel time of subtour

Calls FIELD

H12
Subroutine SBTGEN - SuBTour GENerator

Purpose Generate subtours

Called by SBTOUR

Arguments IFLAG2 I FLAG5 BVECT1 CANDTP COMPAT DISTOD DISTOO

ICSBTR ISE IVWHTR KSE VCADWE IBGNP IBGNS IC1 PA03XX ICSTP

IENDP LENDS PA03PX PA03VX PA08UX PARM03 PARM04 PARM05 PARM06

PARM10

JA: Base patron

IP1: Priority

JRDWT: VCADWE pointer

HCVC: Vehicle Mobility Code

NWCAP: Non-wheelchair capacity

Calls FIELD TRCOMB

H13
Subroutine SBTOUR - SuBTOUR for base patron

Purpose Obtain the best subtour for the given base patron

Called by MNTOUR

Arguments IFLAG5 BVECT1 CANDTP COMPAT DISTOD DISTOO IBSBTR ICSBTR ISE

IWHIR KSE PRDCOD PRIOTR VCADWE PRDIB PRDIC IBGNP IBGNS

PA03XX IENDP LENDS PA03PX PA03VX JRDWT MCVC PA08UX NWCAP

PARM03 PAEM04 PARM05 PARM06 PARM10

JA: Scratch

TA1SB: Arrival time to sub tour

IFLAG3: =1 : a new sub tour is made,

®0 : otherwise

3IPR: Scratch

IPRIOP: Patron priority

IPRIOT: Tour priority

IBSTP: Number of stops in the best subtour.

Calls FIELD S3TGEN PRE PRD
Subroutine SHIFT

Purpose Shift a sub tour to the earliest feasible time

Called by MNTOUR

Arguments CANDTP , I VWHTR , I BGNS , PARMQ3 , PARM06

NSTPTR: Number of stops in the tour.

Calls None

H15
Subroutine TFETCH - Time FETCH

Purpose Obtain travel time between two stops

Called by MNTOUR TS.COMB

Arguments I: Travel time

J: Candidate row

K: Candidate column

IV: DISTOD or DISTOO

Calls FIELD

H16
Subroutine TRCOMB - TouR COMBination

Purpose Generate orders of patron stops to form a subtour

Called by SBTGEN

Arguments I FLAG2 IFLAG5 CANDTP DISTOD DISTOO ISE ICSBTR

IA: New patron to be inserted

JK: Number of stops in the subtour

Calls FIELD TFETCH DWELLT FESIBL KMTIME

HI 7

APPENDIX I PROGRAM LISTINGS

This appendix contains program listings of all subroutines used in RSDAR.

II
Nov 20 14:26 1984 calbck.f Page 1

SUBROUT 3 NE CALBCK I CAM)TP , PA03VX , PA03XX , PARM03 ) IMPLICIT INTEGER ( B-Y ) DIMENSION CAM)TP( PARMQ3, 1 ) PSH1FT =24

PGAP=240

I VAX1=PA03VX+

1

DO 200 11=1 VAX 1 , PA03XX

CALL FIELD! 1, CANDTPl 11,11,12,15,1)

IF ( 12.EO.O ) GO TO 200

PTL=CAM)TP( 11,12) -PSHIFT

PTE=PTL-PGAP

IF (CANDTPl 31,11). GT.PTL) GO TO 100

IF (CANDTPl 11, 11) .LT. PTE) GO TO 100

GO TO 200

100 CALL FIELD! 2, CANDTPl 11,1), 1,14,1)

200 CONTINUE

RETURN

END

12
Dec 11 14:01 1984 dumpgr.f Page 1

SUBROUTINE DUMPGR! PA03XX , PA08UX , PA09XX , CANDTP , TOURL1

,

1 rSTOPL , PARM03 , PARM08 , PARM09

)

IMPLICIT INTEGER I B-Y

)

DIMENSION CANDTP! PARM03, 1 ) ,TOURLI ( PARM08 , 1 ) .TSTOPL! PARM09 , 1 ) NAG = -

1

WRITE! 21, 100 ) PA09XX , PA08UX

100 FORMAT! 8012)

DO 150 1=1, PA03XX

WRI TE! 21 , 100 ) tCAJSDTP! 1 , J ) , J = l, 16 ) 150 CONTINUE

WRITE! 21, 100 ) NAG , ! CAMDTP! 1,JJ,J=2,16)

DO 250 1=1, PA09XX

WRI TE! 21 , 100 ) ! TSTOPL! 1 , J ) , J=l,4 ) 250 CONTINUE

WRITE! 21, 100 ) NAG, ! TSTOPL! 1 , J ) , J = 2 , 4 S DO 350 1=1, PA08UX

WRITE! 21, 100 ) < TOURL1 1 1 , J ) , J = l,3 ) 350 CONTINUE

WRITE! 21, 100 ) NAG , ( T OURL

1

\ 1,J),J=2,3)

RETURN

END

13
oooooooo

Apr 20 09:13 1984 dwe 1 1 t . f Page 1

SUBROUTINE DWELLTI 11, 12, 13, 14, 15, 16, Ji, DWT , VCADWE , PARM 1 0

IMPLICIT INTEGER ( B-Y

DIMENSION VCADWE ( PARM 10 , 1

II .-NUMBER OF NWC TO PICK

1 2 : NUMBER OF LIFT TO PICK

1 3 : NUMBER OF WC TO PICK

14: NUMBER OF NWC TO DROP

1 5 : NUMBER OF LIST TO DROP

16 .-NUMBER OF WC TO DROP

Jl: STARTING ROW (FROM VTYPEL

}

DWT: DWELL TIME

DWT = 0

tpi=o

TD1 = 0

IF i I3.EQ.0 5 GO TO 100

J2=J1+ 13

CALL FIELD! 1 , VCADWE ( J2 , 1 ) , TP2 , 25 , 8

IF (TP2.GT.TP1) TP1=TP2

100 IF ( 12. EG. 0 ) GO TO 200

J2=J1+ 12

CALL F2ELD< 1 , VCADWE! J2 , 1 ) , TP2 , 17 , 8

IF (TP2.GT.TP1) TP1=TP2

200 IF ! I1.EQ.0) GO TO 300

J2=J1+ 1

CALL FIELD! 1 , VCADWE! J2 , 1 )

, TP2 , 9 , 8

IF ! TP2 . GT . TP1 ) TP1=TP2

300 DWT = TP1

IF (TP1.GT.0) RETURN

IF ! 16.EQ.0 ) GO TO 400

J2=J1+ 16

CALL FIELD! 1 , VCADWE I J2 , 2 ) , TD2 , 25 , 8

IF ( TD2.GT . TD1 ) TD1=TD2

400 IF ( 15.EQ.0 ) GO TO 500

J2=J1+ 15

CALL FIELD! 1 , VCADWE! J2 , 2 ), TD2 , 17 , 8

IF ! TD2.GT . TD1 ) TD1=TD2

500 IF ( 14.EQ. 0 ) GO TO 60 0

J2= J 1 + 1

CALL FIELD! 1 , VCADWE ! J2 , 2 )

, TD2 , 9 , 8

IF (TD2.GT.TDl) TD1=TD2

600 DWT=TD1

RETURN

END

14
Nov 20 14:38 1984 fesibl.f Page 1

SUBROUT 1NE FES I BL ( 1 K2 , I FLAG 1 , 1 FLAG5

1 CANDTP,D1ST0D, DISTOO, IVWHTR,KSE,

2 IBGNP , IBGNS , PA03XX , 1ENDP , 1ENDS,

3 PARM03 , PARM04 , PARM05 , PARM06 ) IMPLICIT INTEGER I B-Y

}

DIMENSION CANDTPI PARM03, 1 ), DISTOO! 1 ), DISTOO! 1

DIMENSION I VWHTR( PARM06 , 1 ) , KSE! PARM05, 1 ) C CHECK ROUTING IN KSE FOR FEASIBLE SCHEDULE

G 1 FLAG1= 1 : ROUTING IS FEASIBLE; =0:NOT FEASIBLE

IFLAG1=0

IFLAG5=0

DIFLA=0

D1FLB=0

D1FUA=0

DIFUB=0

PDWEL=0

DOWEL =0

C SEARCH FOR LARGEST DIFLB AND D1FUB

DO 100 1 1= 1 , 3K2

J1=KSE( 11,1)

J2=KSE ( 11,2)

X1=KSE( 11,8)

IF ( J2.NE. 1 ) GO TO 20

X4=CANDTP( Jl , 10 ) X5=CANDTP( Jl, 12)

IF ( 1 l.NE. 1 ) GO TO 40

CALL TFETCHI TPD , PA03XX , Jl , IBGNP, DISTOO

PDWEL=KSE ( 11,7)

X6= 1 VWHTR( I BGNS , 8 ) + 1 VWHTR ( IBGNS , 7 ) +TPD+PDWEL

IF (X6.GT.X4) X4=X6

GO TO 40

20 CONTINUE

X4=CANOTP( Jl,13)

X5=CA>NDTP( Jl,15)

IF 1 ll.NE.iK2) GO TO 40

CALL TFETCHI TPD, PA03XX, I ENDP , Jl , DISTOO ) DOWEL =KSE! 31,7)

X6= I VWHl'Ri 1 EMDS , 8 )-IVWHTR( IENDS,7 ) -TPD-DGWEL

IF IX6.LT.X5) X5=X6

40 CONTINUE

IF ( X1.GE.X4 ) GO TO 60

DIFLA=X4-X1

IF ( D1 FLA. GT.0. AND. DIFUB.LT. 0 ) RETURN

IF (D1FLA. GT. DIFLB 1 D1FL3=Q1FLA

GO TO 100

60 IF (X1.LE.X5) GO TO 100

DIFUA=X5-X1

IF ( DIFLB.GT . 0 .AND.DIFUA. LT . 0 ) RETURN

IF ( D1FUA.LT.D1FUB ) DIFU8=D1FUA

100 CONTINUE

IF (DIFLB. EQ.0) GO TO 200

C SHIFT TO THE RIGHT

DO 150 11=1, 1K2

J1=KSE( 11,1)

J2=KSE( 11,2)

KSE( 11,11 ) =KSEi 1 1,8 J+D1FLB
Nov 20 14 : 36 1984 fesibl.f Page 2

IF IJ2.NE.il GO TO 120

IF IKSEI 11, 8). LT.CANDTPI Jl,10) ) RETURN

IF IKSEi 1 1,8 } .GT.CANDTPJ Jl, 12 ) ) RETURN

GO TO 140

120 CONTINUE

IF IKSEI 11,8). LT.CANDTPI Jl, 13) ) RETURN

IF IKSEI 1 1,8). GT.CANDTPI Jl, 15) ) RETURN

140 CONTINUE

IF I 11.NE.1K2) GO TO 150

IF (J2.EG.1) GO TO 150

CALL TFETCHi TPO , PA03XX , IENDP , Jl , D1STOQ ) X6 = I VWHTR I I ENDS , 8 ) - I VWHTRI I ENDS , 7 ) -TPD-DDWEL

IF IKSEI 1 1,8 ) .GT.X6 ) GO TO 400

150 CONTINUE

GO TO 300

200 IF (D1FUB.EQ.0) GO TO 300

C SHIFT TO THE LEFT

DO 250 11=1, IK2

J1=KSE( 11,1)

J2=KSE( 11,2)

KSEI 11,8) =KSE( 11,8) +01FUB

IF IJ2.NE.1) GO TO 220

IF IKSEI 1 1,8 ! .LT.CANDTPI Jl, 10 ) I RETURN

IF IKSEI 11,8 ) .GT.CANDTPI Jl, 12) ) RETURN

GO TO 240

220 CONTINUE

IF IKSEI 11, 8). LT.CANDTPI Jl, 13) ) RETURN

IF IKSEi 11,8) .GT.CANDTPI Jl, 15) ) RETURN

240 CONTINUE

IF I ll.NE.ll GO TO 250

IF IJ2.EQ.2! GO TO 250

CALL TFETCHI TPO , PA03XX , J 1 , 1 BGNP , DI STOO

)

X6= I VWHTRI 18GNS , 8 ) + 1 VWHTRI 1BGNS , 7 ) +TPO+PDWEL

IF IKSEI 11,8) .LT.X6) RETURN

250 CONTINUE

300 CONTINUE

C NOT TO EXCEED THE MAXIMUM ON BOARD TIME

DO 350 1 1=1, 1K2

TD = 0

IF IKSEI 11,2). EO. 2) GO TO 350

J1=KSEI 11,1)

12=11+1

DO 340 13=12, 1K2

IF IKSEI 13,1). EQ.J1. AND. KSEI 13,2). EQ. 2) J3=I3

340 CONTI WE

TD=KSEi J3 , 3 ) -KSEI 11,8)

CALL FIELD! 1,CANDTP( Jl , 3 ) ,TMX08,21, 12

)

IF I TD.GT . TMX06 5 RETURN

350 CONTINUE

IFLAG1=1

RETURN

400 CONTINUE

C IFLAG5= 1 : SUBTOUR CUT SHORT DUE TO END INTERVAL

C I F LAGS = 0 : OTHERWISE

I FLAG5=

1

RETURN
Nov 20 14:38 1984 fesibl.f Page 3

END

.

'

1

*

17
May 25 10:52 1984 field. f Page 1

SUBROUTINE FIELDl 1 , J,K, 1 1, 12

)

- DIMENSION NVI 32

)

* POWERS OF 2 TABLE

DATA NV 71,2,4,8, 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 , 4096 , 8192

,

* 16384 , 32768 , 65536 , 131072 , 262144-, 524288 , 1048576,2097152,

* 4194304,8388608, 16777216,33554432,67108864, 134217728,

* 268435456,536870912, 1073741824,2147483648/

* 13=34-11-12

J 1= J/NV (13)

14=12+1

IF 1 I . EQ.2 ) GO TO 100

*

* UNPACK 1 NG

K -\J

IF f 14. GE. 32) RETURN

J2=J1/NV( 14

)

K=J1- J2*NV( 14

)

RETURN

*

* PACKING

100 J2=0

J3=0

IF iJ4.GE.32) GO TO 110

J3=NV( 14

)

J2=J1/J3

110 J=J- J1*NV( 13 ) + ( J2*J3+K )*NV( 13)

RETURN

END

13
OOOOOOOOO

0,0

O

0.0

o

o

o

o

o

Oec 11 14:04 1984 main.f Page 1

PROGRAM RSDAR

MAXIMUM CAPACITY: PA03XX <= 349; PA03PX <=217

CALCULATION OF ARRAY SIZES

(NOTE: ALL NUMBERS SHOULD BE ROUNDED TO NEXT HIGHER INTEGER)

PARM01: ( ( PA03PX/31 1+4 )*PAQ3PX: BASETP , COMPAT

PARM02 : ( PA03PX/31 ) +4 : BVECT1

PARM03 : PA03XX : CANDTP: MAX NUMBER OF ENTRIES FOR CANDTP

PARM04 : I PA03XX**2 ) /3 : D1ST0D,DIST00

PARM05 : GUESS: IBSBTR , ICSBTR , 1 SE , KSE : MAX NUMBER OF STOPS

IN A SUBTOUR

PARM06 : GUESS: IVWHTR: MAX NUMBER OF STOPS IN A TOUR

PARM07 : INFORMATION OR GUESS: VTYPEL

PARM08 : INFORMATION OR GUESS: T0URL1 : MAX NUMBER OF TOURS

PARM09: 2*PA03XX: TSTOPL

PARM10 : INFORMATION OR GUESS: VCADWE

PARM11: PRDBD

C

IMPLICIT INTEGER (B-Y)

PARAMETER! PARM01=2387, PARM02=11, PARM03=249, PARM04=20667

,

1 PARM05=40, PARM06=80 , PARM07=15, PARMQ8=50, PARM09=498

2 PARM10=50 , PARM11=217)

DIMENSION BASETP I PARM01 ) ,BVECTl( PARM02 ) , CANDTP! PARM03 , 16 ) COMPAT! PARM01 ) ,D1STOO< PARM04 ) ,D1STOO( PARM04 ) IBSBTR! PARM05, 12 ) , ICSBTR! PARM05 , 12

)

; ISE! PARM05 , 12 ) IVWHTR! PARM06, 10

)

, KSE! PARMOB, 12

)

, PRDCOD! 15 ) PR10RL! 15 )

, PR10TR! 15 ) , T0URL1 ! PARM08,3 ) TSTOPL! PARM09 , 4 )

, VCADWE! PARM10,2 )

, VTYPEL 1 PARM07 ) PRD I B ! 15 ) , PRDIC! 15 )

, PRDBD! PARM11 , 15 ) OPEN! ll,FILE='zc .rsd' , STATUS* ' OLD'

)

OPEN! 21 ,FILE= ' zr.gre' , STATUS= 'NEW' ) CALL READCV l PA03XX , PA03PX , PA08XX , PA08RX , PA03VX # BASETP . CANDTP , 1 COMPAT , D1STC0,DIST00,PR10RL , T0URL1 , VCADWE ( VTYPEL

2 PARM03 , PARM08 , PARM10

)

DIMENSION

DIMENSION

DIMENSION

DIMENSION

DIMENSION

DIMENSION

CALL NSMTOUR ! BASETP ( BVECT 1 , CANDTP , COMPAT , D1 STOO . D I STOO

,

1 IBSBTR , PA03XX , ICSBTR , PA 03PX , ISE , PA08RX , PA03VX , IVWHTR, KSE , PRDCCO, PR] ORL , PR 10TR , T0URL1 , TSTOPL , VCADWE VTYPEL*

PRDIB , PRDIC, PRDBD , PA08UX , PA09XX

,

PARM03 , PARM04 # PARM05 , PARM06 , PARM08

,

PARM09 , PARM10 , FARM 11 ) CALL CALBCK! CANDTP , PA03VX , PA03XX, PARM03

)

CALL DUMPGR! PA03XX , PA08UX , PA09XX , CANDTP , TOURL I

,

1 TSTOPL , PARM03 , PARM08 , PARM09 ) CLOSE! 11 ) CLOSE! 21

)

STOP

END

19
\
Jan 31 15:48 1985 mntour.f Page 1

SUBROUTINE MNTOURI BASETP , BVECT

1

; CANOTP , COMPAT , DI STOO , DI STOO

,

1 I BSBTR , PA03XX , ICSBTR , PA03PX , 1SE , PA08RX , PA03VX , 1VWHTR,

2 KSE , PRDCOO, PRIORL , PRIOTR , TOURL1 , TSTOPL , VCADWE , VTYPEL

,

3 PRD I B , PRD 1 C , PRD8D , PA08UX , PA09XX

,

4 PARM03 , PARM04 , PARM05 , PARM06 , PARM08

,

5 PARM09 , PARM10 , PARM1 1 ) IMPLICIT INTEGER ( B-Y

)

DIMENSION BASETP ( 1 ) ,BVECT1I 1 ) , CANDTPI PARM03 , 1 ) ,COMPAT( 1 ) DIMENSION D1STODI 1

)

; DISTOO( 1 ) , 1BSBTRI PARM05 , 1 ) , 1CSBTR1 PARM05 , 1 ) DIMENSION 1SEI PARM05 , 1 ) , 1VWKTRI PARM06 , 1 ) ,KSE( PARM05 , 1 ) ,PRDCOO( 1 ) DIMENSION PRIORL ( 1 ) , PRIOTR! 1

J

; TOURLl ( PARM08 , 1 ) , TSTOPL ( PARM09 , 1

)

DIMENSION VCADWE ( PARM10, 1 ) ,VTYPEL( 1 ) , PRDIBi 1

)

; PRD1C! 1 ) DIMENSION PRDBDI PARM11, 1 ) ,PR10SM( 15)

DO 130 11=1,15

CALL FIELD! 1, PRIORL! II ) ,PRIOSM! 111,1,12)

CALL FIELD! 1, PRIORL! 1 1 ) ,PRDCOO< 1 1 ) , 29 , 4 ) 130 CONTINUE

PA08UX = 0

PA09XX=0

I VAX1 =PA03VX+

1

I VTYP=0

C ** CALCULATE UPPER BOUNDS 44

DO 170 J4= 1 , 15

IF IPRIOSM! J41.EQ.0) GO TO 160

DO 155 J5= I VAX1 , PA03XX

1 1= J5-PA03VX

I4=PA03PX/31

I 5=PA03PX-3l4 1

4

IF ( 15.NE.0 ) 14=14+1

14=14+4

Jl=J4/4

J2=J4-44 J

1

IF (J2.EQ.0) J2=4

IF (J2.NE.4) J1=J1+1

J2=! J2-1 )48+l

J3 = I44( 31-1) +J1

CALL FIELD! 1 , BASETP! J3 ), TR3 P , J2 , 8

)

IF < TRIP . EQ. 0 ) GO TO 150

CALL FIELD! 1,CCMPAT! J3 ) , PATRN , J2 , 8

)

CALL FIELD! 1 , CAMDTP! J5 , 3 ) , TIME, 9, 12)

PATRT =PATRN4 T I ME

TRPRT= TRIP* TIME

CALL PRDCTY ! PRDCOO! J4 )

, PATRN , TR1 P , PATRT , TRPRT , T 1 ME , PRDV

)

PRDBDI 11, J4 )=PRDV

GO TO 155

150 PRD6D! 1 1, J4 )=0

155 CONTINUE

GO TO 170

160 DO 165 J3= 1 , PA03PX

PRDBDI J3 , J4 ) =0

165 CONTINUE

170 CONTINUE

DO 190 1 = 1 VAX1 , PA03XX

CANDTP! 1 ,*4 ) =0

190 CC^JTIINUE

110
oooo

Jan 31 15:48 1985 mntour.f Page 2

C ARE ALL PATRONS ASSIGNED ? 200 CONTINUE

DO 210 11= I VAX1 , PA03XX

CALL FIELD! 1,CANDTP( 1 1 , 1 ) , 1 2 , 6 , 1 ) IF ! 12.EQ.0 ) GO TO 220

210 CONTINUE

RETURN

C 4* NEW TOUR**

220 CONTINUE

GPS1 ZE=99000

DO 240 1 1 = IVAX1 , PA03XX

CALL FIELD! 1,CAN0TP! 11,1), 12,6,1)

IF ( 12.GT.0) GO TO 240

CALL FIELD! 1,CANDTP( 11,31,12,9,12)

IF IGPSIZE.GT. 12) GPS1ZE=12

240 CONTINUE

GPSIZE=GPSI ZE+80

DO 255 11=1, PARM06

IVWHTR! 11,9 )=0

255 CCNT 1 NUE

ISU8TR=0

NSTPTR=

1

I BGNS =

1

IVTYPA= I VTYP

PA08UX=PA08UX+

1

I TCUR=PA08UX

IF ( PA08UX . LE . PA08RX ) GO TO 260

ISUBTR=

1

260 CONTINUE

C **PR10TR( I ) : PRIORITY ACCEPTED BY CURRENT TOUR**

DO 270 11=1,15

12=11+17

CALL FIELD! 1,TCURLI! 1 TOUR , 1 ) , PRIOTR! 31), 12,1)

270 CONTINUE

1V1DX: VEHICLE INDEX

I VTYP : VEHICLE TYPE

MCVC: MOBILITY CHARACTERISTICS OF VEHICLE

NWCAP : NON WHEEL CHAIR CAPACITY

CALL FIELD! l,TOURLll 3 TOUR , 1 ) , 1 V1DX , 1 , 8 ) CALL FIELD! l,TOURLI( 1 TOUR , 1 ) , 1 VTYP , 9 , 4 ) CALL FIELD! l,VTYPELl I VTYP ) , MCVC , 1 , 4

)

CALL FIELD! 1,VTYPEL( 1VTYP )

, NWCAP, 5, 4

)

IF l 1VTYP.EQ. 1VTYPA) GO TO 290

C ** STORE DWELL TIME IN KSE ** CALL FIELD! 1,VTYPEL! 1 VTYP ! , RCWVCA , 17 , 16 ) DO 275 11=1, NWCAP

I2=RCWVCA+ 1

1

DO 275 Jl= 1 ,

3

J2=J1*8+

1

CALL FIELD! 1,VCADWEI 12,1), KSE! 11,J1),J2,8)

J3= Jl+3

CALL FIELD! 1,VCADWE! 12,2) ,KSE! 11,03) ,J2,8)

275 CONTINUE

C ** CONSTRUCT DWELL TIME ** DO 285 1 1 = 1 VAX1 , PA03XX

CALL FIELD! 1,CANDTP( 11,11,12,6,1)

111

I
Jan 31 15:48 1985 mntour. f Page 3

IF I 12. EQ. 1 ) GO TO 2S5

PT = 0

DT = 0

DO 280 13=1,3

14=4* 13+1

CALL F IELD( 1,CANDTP! 11,16),J1,14,4)

IF IPT.LT.KSE! J1 , 1 3 J ) PT=KSE( J1 , 13 ) 15=1 3+3

IF IDT.LT.KSE! J1,I5J ) DT =KSE( J1 , 15

)

280 CONTINUE

CALL FIELD(2,CANDTP! 1 1 , 16 ) , PT , 17 , 8 ) CALL FIELD! 2 ,CANDTP! 1 1 , 16 ) , DT ; 25 , 8 ) 285 CONTINUE

290 CONTINUE

C ENTER TOUR STARTING TIME

DO 300 11=1, PA03VX

C CHECK TYPE OF BREAK

CALL FIELD! 1,CANDTP( 11,1), 12, 1,3)

IF ! I2.NE.2) GO TO 300

CALL FIELD! l,CANDTPl 11, 1 ), 12,6, 1 ) IF ( 12.NE.0) GO TO 300

CALL FIELD! 1,CANDTP! 11,21,12,25,8)

IF ! 12.NE.IVIDX) GO TO 300

C SET TOUR STARTING POINT AMS TIME

CALL FIELD(2,CANDTP! 11,1), 1,6,1)

I8GNP= 1

1

JLAST = 11

TLAST=CANDTP! 11,12)

IVWHTR! 1,11 = 11

IVWHTR! 1 , 2 ) =6

IVWHTR! 1,8) =CANDTP( 11,13)

CALL FIELD! 1,CAM3TP! 1 1 , 16 ), IVWHTR! 1,7), 17, 8)

IVWHTR! 1 , 3 ) = 0

IVWHTR! 1,4 )=0

IVWHTR! 1 , 5 ) =0

GO TO 310

300 CONTINUE

RETURN

* 310 CONTINUE

C ENTER TOUR BREAK TIME

DO 330 11=1, PA03VX

CALL FIELD! 1 , CAMDTP! 1 1 , 1 ) , 12 , 1 , 3 ) IF ( 12. NE. 1 ) GO TO 330

CALL FIELD! 1,CANDTP! 11,1), 12, 6,1)

IF ! 12.NE.0) GO TO 330

CALL FIELD! 1 , CAMSTP! 11,21,12, 25 ,8)

IF ! I2.NE. 1VIDX ) GO TO 330

I4=NSTPTR+

1

I5=NSTPTR+2

NSTPTR= 1

5

IVWHTR! 1 4 , 1 ) = 1

1

IVWHTR! 1 4 , 2 ) =3

IVWHTR! 15, 1 ) =11

IVWHTR! 15,2 )=4

IVWHTR! 14,31=0

IVWHTR! 14,4 )=0

112
Jan 31 15:48 1985 mntour. f Page 4

IVWHTRl 14,51=0

IVWHTRI 15,3 )=0

IWHTRI 15,4 )=0

IVWHTRI 15,51=0

CALL FIELDI 2 , CANDTPI 11,11,1,6,1}

CALL FIELDI 1, CANDTPI 1 1 ,3 ) # IVWHTRI 14,61,9,13)

CALL FIELDI 1,CANDTP( 1 1 , 16 1 , IVWHTRI 14,71,17,3)

CALL FIELDI 1,CANDTP( 1 1 , 16 1 , IVWHTRI 15,71,35,81

IVWHTRI 14,8) =CAf\DTPI 11,13)

IVWHTRI 15,8) =CANDTPl 11,15)

330 CONTINUE

NSTPTR=NSTPTR+1

IVWHTRI NSTPTR , 1 ) =JLAST

IVWHTRI NSTPTR , 3 ) =5

IVWHTRI NSTPTR, 3 1=0

IVWHTRI NSTPTR, 4 )=0

IVWHTRI NSTPTR , 5 ) =0

IVWHTRI NSTPTR, 6 )=0

IVWHTRI NSTPTR , 7 ) =0

IVWHTRI NSTPTR, 8 )=TLAST

C *#NEW GAP***NEW SU8T0UR

350 CONTINUE

IFLAG3=0

C SEARCH GAP FOR INSERTION

1 1 = IVWHTRI J BGNS , 3

)

IF I Il.EQ.l) GO TO 395

IF I 11.EQ.3) GO TO 360

IF I 11.EQ.4 ) GO TO 370

IF I 11.EQ.5) GO TO 700

I BGNP= IVWHTRI 1 BGNS, 1 ) GO TO 380

C SHIFT TO THE LEFT

360 CONTINUE

CALL SHIFT! CAMD TP , 1 VWHTR , 1 BGNS , NSTPTR , PARM03 , PARM06

)

I BGNS =1 BGNS +1

I BRK = 0

GO TO 350

370 CONTINUE

I BGNP= IVWHTRI I BGNS, 1

)

IF (1BRK.EQ.1) 18GNP= 1BRKP

I8RKP= IBGNP

CALL FIELDI l,CANDTPl IBGNP , 5 ) , DRPX , 17 , 16

)

IF IDRPX.NE.0) GO TO 380

CALL FIELDI 1,CANDTPI IBGNP , 6 I , DRPY , 17 , 16

)

IF (DRPY.NE.0) GO TO 380

I ENDS = I BGNS +

1

13= 1 BGNS -2

13= IVWHTRI 12,1)

I ENDP= IVWHTRI I ENDS, 1

)

CALL TFETCHI TPD , PA03XX , IENDP , 1 3 , DISTOO

)

IVWHTRI 1BGNS , 6 ) =TPD

CANOTPI 1 BGNP , 5 ) =CANDTP I 13,5

)

CANDTPI 1BGNP,6)=CANDTPI 13,61

CALL FIELDI 1 , CANOTPI 13 , 5 ) , 1 TEMP , 17 , 16

)

CALL FIELDI 2, CANDTPI IBGNP , 5 1 , I TEMP , 1 , 16

)

CALL FIELDI 1, CANDTPI 13,6') , ITEMP, 17,16)

113
Jan 31 15:48 1985 mntour.f Page 5

CALL FIELD! 2 , CANDTP! IBGNP , 6 ) , 1 TEMP , 1 , 16

)

IBRK=1

IBRKP= I 3

GO TO 390

365 CONTINUE

C **TRAVEL TIME**

11=1 BGNS

12=1 BGNS +

1

14=1 VWHTRI 11,1)

IF ( 1VWHTRI 11,2). EQ. 4) 14=IBRKP

13= IVWHTRI 12,1 I CALL TFETCHI TPD , PA03XX , 1 3 , 1 4 , D1STOD

)

I VWHTRI 1 1,6 )=TPD

GO TO 395

380 1 ENDS= 1 BGNS +

1

IENDP= IVWHTRI 1 ENDS , 1 ) CALL TFETCHI TPD , PA03XX , IENDP , IBGNP , D1 STCO ) 1 1 = 1 BGNS

12=1 BGNS +

1

390 OPEN1 = IVWHTRI IENDS , 8 ) - I VWHTRI 1BGNS,3)-TPD

1 -IVWHTRI IENDS , 7 ) - 1 VWHTRI 1 BGNS , 7 ) IF I OPENI .GE.GPSIZE ) GO TO 400

395 1 BGNS = 1 BGNS +

1

IBRK=0

CALL SHIFT! CANDTP , 1 VWHTR , I BGNS , NSTPTR , PARM03 , PARM06 ) C ** IDLE TIME**

IVWHTRI 11,9) = IVWHTRI 12 , 8 )- IVWHTRI 1 1 , 8 ) -IVWHTRI 11,7)

1 -IVWHTRI 12,7) -IVWHTRI 11,6)

GO TO 350

400 CONTINUE

C TOUR PRIORITY SETTING

IPRIOT = 0

410 1 PR I OT = 1 PR I OT +

1

IF I IPRIOT. GT. 15) GO TO 365

IF I PRIOTRl IPRIOT I.EQ.0) GO TO 410

IF I PRIOSMI IPRIOT ) .EQ. 0 ) GO TO 410

DO 420 11=1,15

PRD1BI 11)=0

420 CONTINUE

B1PR=0

DO 430 J5=1VAX1 , PA03XX

CALL FIELD! 1, CANDTPI J5,1),J6, 6,1)

IF I J6.NE. 0 ) GO TO 430

CANDTPI J5 , 4 ) =0

430 CONTINUE

440 CONTINUE

JA = 0

IFLAG3=0

IFLAG5=0

PRDMX=0

C SEARCH FOR THE PATRON WITH THE HIGHEST UPBCUND

DO 450 1 1 = 1VAX1 , PA03XX

CALL FIELD! 1, CANDTPI 11,1), 12, 6,1)

IF ! 12.NE.0) GO TO 450

IF I CANDTP! 11,4) .LT.O ) GO TO 450

12=1 1-PA03VX

114
Jan 31 15:48 1985 mntour. f Page 6

PRDV=PRDBDI 12, IPR10T ) IF < PRDMX . GE . PRDV ) GO TO 450

PRDMX = PRD

V

JA = 1

1

450 CONTINUE

IF (PRDMX. LE.BIPR) GO TO 500

C

NNWC8=0

NWCO8=0

C MCPA: MOBILITY. CHARACTERISTICS OF PATRON

CALL F1ELD( 1 , CANDTPl JA , 1 ) ,MCPA, 11,3)

IF ( MCPA . GT . MCVC ) GO TO 460

CALL FIELD! 1, CANDTPl JA,2) , 1PR10P,5,4

)

C CHECK FOR CCMPATIBLE TOUR PRIORITY

IF IPRIOTRI IPRICPJ.NE.l) GO TO 460

C CHECK TIME WINDOWS

CALL FIELDI 1, CANDTPl JA,3 ) , 1CS8TRI 1,6 ) ,9,12 I CALL FIELDI 1 , CANDTPl JA , 16 ), ICSBTRI 1,7), 17, 8)

IF I 1 WHTR I 1 BGNS , 2 ) . EQ . 4 ) 1BGNP= IBRKP

CALL TFETCH I TPD , PA03XX , JA , 1 BGNP , D 1 STOO ) TALS8= IVWHTRI 1BGNS , 8 ) + TPD + ICSBTRI 1,7 J + 1VWHTRI 1 BGNS, 7 ) IF I TALSB . GT . CANDTPl JA , 12 ) ) GO TO 460

ICSBTRI 1,8 )=CANDTPI JA, 12

)

ICSBTRI 2,8)= ICSBTRI 1,8)+1CSBTRI 1,6)

CALL TFETCH! ICSBTRI 2 , 6 ) , PA03XX , 1 ENDP , JA , D1 STOD

)

CALL FIELDI 1, CANDTPl JA, 16 ) , ICSBTRI 2,7 ) ,25,8 ) T 1 = ICS8TRI 2,8) + ICSBTRI 2,6) + ICSBTRI 2,7) + 1 VWHTRI 1 ENDS, 7)

IF I Tl.LE. 1VWHTRI 1ENDS,8) ) GO TO 455

T2 = T 1-IVWHTRI 1 ENDS , 8 ) ICSBTRI 2,8) = ICSBTRI 2 , 8 ) -T2

ICSBTRI 1,8) = ICSBTRI 1,8)-T2

IF I ICSBTRI 1,8) . LT. CANDTPl JA, 10) ) GO TO 460

IF I 1CS8TRI 2,8). LT. CANDTPl JA, 13) ) GO TO 460

455 CONTINUE

C CHECK VEHICLE CAPACITY

CALL FIELDI 1,VTYPELI I VTYP ) , JRDWT ,17,16)

CALL FIELDI 1 , CANDTPl JA , 16 ) ,NNWP, 1,8)

CALL FIELDI 1 , CANDTPl JA, 16 ) ,NLFP ,9 , 4 ) NA=MSVC8+!\NWP+NLFP

IF l NA . GT . NWCAP ) GO TO 460

CALL FIELDI 1, CANDTPl JA, 16 ) ,NWCP, 13,4 ) N<9 = NWCC8 + NWCP

Nl=JRDWT +NA

CALL FIELDI 1 , VCADWEI N1 , 1 ) ,NWCCP, 1,8)

IF (NB.LE.NWCCP) GO TO 470

460 CANDTPl JA , 4 ) =-PRDBD( JA-PA03VX, 1PRIOT ) GO TO 440

470 CONTINUE

I4=PA03PX/31

1 5=PA03PX-31# 1

4

IF I 15.NE.0 ) 14=14+1

14=14+4

1 6 = JA-PA03VX

DO 490 11=1,14

12=14*1 16-1 >+11

BV5CTK II )=BASETPI 12 )

115
o

o

o

Jan 31 15:48 1985 mntour. f Page 7

490 CONTINUE

CALL SBTOURI JA , TALSB , 1PRIOP, I FLAG3 , I FLAGS , B1 PR

,

1 BVECT 1 , CANDTP , COMPAT , D 1 STOO , D 1 STOO , 1 BSBTR , 1 CSBTR , 1 SE

,

2 I VWH T R , KSE , PRDCOO , PR I OTR , VCADWE , PRD 1 B , PRD 1 C

,

3 1BGNP , 1BGNS , 1BSTP , PA03XX , IENDP , 1ENDS , PA03PX , IPRIOT , PA03VX , JRDWT

,

4 MCVC,PA08UX,NWCAP,

5 PARM03 , PARM04 , PARM05 , PARM06 , PARM10 )

I FLAG3= 1 : A BETTER SUBTOUR IS FOUND

I FLAG3= 0 : OTHERWISE

SEE FES1BL FOR I FLAGS

IF I IFLAG5.EQ. 1 ) GO TO 495

PRDBD( JA-PA03VX , IPRIOT )=B1PR

495 CONTINUE

IF ( IFLAG3.EQ. 1 ) 1FLAG4=1

C I FLAG4 = 1 IF 1FLAG3=

1

GO TO 440

500 IF 1 1FLAG4 . EQ. 0 ) GO TO 410

IFLAG3=0

I FLAG4 = 0

600 CONTINUE

C ##UPDATE BASETP AMD COMPAT I SUM AMD RIDE SHARES)

DO 620 11=1,1 BSTP

IF ( 1BSBTRI 11,2) .NE. 1 ) GO TO 620

12= 1BSBTRI 11,1)

CALL FIELD! 2, CANDTP! 12,1), 1,6,1)

CANDTP ( 12,4 ) = 1

12= I2-PA03VX

13=12/31

14=12-31* 1

3

IF I 14.EQ.0 ) 14=31

IF I 14.NE.31 ) 13=13+1

13=13+4

14=14+1

J3=PA03PX/31

J4=PA03PX-31* J3

IF (J4.NE.0) J3=J3+

1

J3= J3+4

IPR= IBSSTR) 11,12)

PR1CSM( I PR ) =PRIOSM( 1 PR ) -

1

J6 = 1 PR/4

J7=1PR-4*J6

IF (J7.EQ.0) J7 =4

IF ( J7 . NE o 4 ) J6 = J6+1

J7=( J7-1 )*8+l

DO 620 Kl= 1 VAX1 , PA03XX

K2=K1-PA03VX

K3= ( K2- 1 !*J3+I3

CALL FIELD! 1 , BASETP < K3 ) , LI , 14 , 1

)

IF (L1.EQ.0) GO TO 620

CALL FIELD! 2, BASETP ( K3 ) ,0, 14, 1

)

K3= ( K2- 1 I * J3+ J6

CALL FIELD! 1 , BASETP! K3 )

, LI , J7 , 8

)

L1=L1-1

CALL FIELD! 2 , BASETP! K3 )

, LI , J7 , 8

)

CALL FIELD! 1 , COMPAT I K3 ) , LI , J7 , 8

)

L1 = L1- 1 BSBTR! 11,9) - 1 BSBTR I 1 1 , 10 I - 1BSBTRI 11,11)

116
Jan 31 15:43 1985 mntour.f Page 8

CALL F I ELD I 2 , COMPAT I K3 ) , L 1 , J7 , 8

)

620 CONTINUE

NSTPTR=NSTPTR+ I BSTP

C SHIFTING POINTERS FOR PREVIOUSLY ASSIGNED STOPS

1 1= 1BGNS+ IBSTP+

1

DO 640 I2=NSTPTR ,11,-1

13= 12- 1BSTP

CO 640 14=1,8

IVWHTRI 12,14) = IVWHTRI 13,14 ) 640 CONTINUE

C FILLING IN POINTERS FOR NEW STOPS

1 1 = I8GNS+

1

12= 1BGNS+ 1BSTP

DO 660 13=11,12

I4=13-1BGNS

DO 660 15=1,8

IVWHTRI 13,15) = 1BSBTRI 14,15)

660 CONTINUE

C ***IDLE TIME***

11=1 BGNS

12= 1BGNS+

1

1 4 = I VWHTRI 11,1)

1 3 = IVWHTRI 12,1)

IF I IVWHTRI 12,2) .EQ. 5) GO TO 670

IF I IVWHTRI 11,2). EQ. 4) 14=iBRKP

CALL TFETCHI TPD,PA03XX, 13,14, DISTOD)

IVWHTRI 11,6) =TPD

IVWHTRI 1 1,9 ) = 1 VWHTRI 12 , 8 )- IVWHTRI 1 1 , 8 )- IVWHTRI 11,7)

1 -IVWHTRI 12,7) -IVWHTRI 11,6)

670 CONTINUE

IF I 1SUBTR. EQ. 0 ) GO TO 350

I i=NSTPTR1

I2=NSTPTR

GO TO 710

700 CONTINUE

C ***SH1FT ENDING TIME TO THE LEFT***

11=1 BGNS -

1

12= 2 BGNS

710 CCNT1NUE

I3=IVWHTRl 12,1

)

IVWHTRI 12,10 ) =CANDTP( 13 , 12 1 - IVWHTRI 12,8)

14= 1 VWHTRI 1 1, 1

)

IF I IVWHTRI 11,2 ) .EG. 4 ) 14 = 1BRKP

CALL TFETCHI TPD, PA03XX, 13,14 ,DlSTCO

)

I VWHTRI 11,6 )=TPD

IVWHTRI 12,8 ) = IVWHTRI 1 1 , 8 ) + IVWHTRI 11,6) + IVWHTRI 11,7)

1 + IVWHTRI 12,7 ) IF (CANDTPi 13, 10 ) .GT. IVWHTRI 12,8) ) I VWHTRI 12 , 8 ! =CANDTP( 13 , 10 ) C *** IDLE TIME***

IVWHTRI 11,9 1 = 1VWHTRI 1 2 , 8 ) - 1 VWHTRI 11,8)- IVWHTRI 11,7)

1 -IVWHTRI 1 1,6 ) -IVWHTRI 12,7 ) C **SH1 FT STARTING TIME TO THE RIGHT**

I I = 1 VWHTRI 1,1)

IVWHTRI 1,10 JsCANDTPI 1 1 , 15 )- IVWHTRI 1,8!

n= IVWHTRI 2,8 ) -IVWHTRI.1,6) -IVWHTRI 2,7 ) IF ITi. LE. CANDTPI 11,12) ) 1 VWHTRI 1 , 8 ! =T

1

117
Jan 31 15:48 1985 mntour.f Page 9

C.

C

IF I Tl.GT.CANDTPI 1 1, 15) ) 1 VWHTRI 1,8) =CANDTP( 11,15)

IVWHTRI 1,9 ) = 1 VWHTRI 2, 8 1-1 VWHTRI 1,8)

1 -IVWHTRI 1,6 1 -IVWHTRI 2, 7

)

DO 740 11=1, NSTPTR

12=1 VWHTRI 11,1)

TRIP STATUS

CALL FIELD! 2, CANDTPI 12,11,1,6,1)

TOUR

CALL F I ELD I 2 , CANDTP I 12,3), PA08UX , 1-, 8 ) 13=1 VWHTRI 11,2)

IF I I3.EQ.2 ) GO TO 730

IF I I3.EQ.4 ) GO TO 730

IF I I3.EQ.6 ) GO TO 730

CALL F I ELDI 2 , CANDTPI 12,11,11,17,8)

CALL FIELD! 2, CANDTPI 12 , 4 ), IVWHTRI 1 1 , 8 )

, 1 , 16 ) CANDTPI 12, 11 )=1VWHTR( 11,8)

IVWHTRI 11,10 )=CANDTP( 12 , 12 ) -CANDTPI 12, 11 ) GO TO 740

730 CANDTPI 12,14) = IVWHTRI 11,8)

IVWHTRI 11,10) =CANDTP( 12 , 15 ) -CANDTPI 12,14)

CALL FIELDI 2, CANDTPI 12,11,11,25,8)

CALL FIELDI 2, CANDTPI 12 , 4 ), I VWHTRI 11, 8), 17, 16) 740 CONTINUE

750

770

DO 750 11=1, NSTPTR

I2=PA09XX+ 1

1

CALL FIELDI 2, TSTOPLI 12,1), IVWHTRI 11,2) , 1,4 J CALL FIELDI 2, TSTOPLI 12 , 1 ), IVWHTRI 1 1,7), 5, 8)

CALL FIELDI 2, TSTOPLI 12, 1 ), IVWHTRI 11,1), 13, 16

CALL FIELDI 2, TSTOPLI 12 , 2 ), IVWHTRI 1 1,3), 1,8) CALL FIELDI 2, TSTOPLI 1 2 , 2 )

, 1 VWHTRI 11, 4), 9, 8) CALL FIELDI 2, TSTOPLI 12,2) , IVWHTRI 11,5) , 17,8 ) I3=1VWHTRI 11,61/8

CALL FIELDI 2, TSTOPLI 3 2 , 3 )

, 13 , 1 , 8 ) 13= IVWHTRI 1 1 , 9 )/8

CALL FIELDI 2, TSTOPLI 12,31,13,9,12)

I3=IVWHTRi 11,10 )/8

CALL FIELDI 2, TSTOPLI 12 , 3 ) , 13 , 21 , 12

)

CONTINUE

CALL FIELDI 2, TOURLI ( PA08UX,2 ) , NSTPTR, 5, 12)

I 1=PA09XX+

1

CALL FIELDI 2, TOURLI I PA08UX,2 ) ,11,17,16)

WR1 TEI 6 , 770 ) PA08UX , NSTPTR

FORMAT I ' TOUR 3 ',13,' IS COMPLETED : ',14 ' PA09XX=PA09XX+NSTPTR

GO TO 200

STOPS' )

END

118
Jun 12 13:21 1984 prdcty.f Page 1

SUBROUTINE PRDCTY ( 1 PCOOE , PATRN , TRIP , PATRT , TRPRT , T 1 ME , PRDV ) IMPLICIT INTEGER I B-Y ) IF I 1PCODE.EQ. 1 ) GO TO 100

IF ( I PCOOE . EQ . 2 ) GO TO 200

IF I 1 PCOOE . EQ . 3 ) GO TO 300

IF ( 1PCOOE.EQ.4 ) GO TO 400

IF ! I PCOOE . EQ . 5 1 GO TO 500

IF ( IPCOOE.EQ.6) GO TO 600

100 PRDV = PATRN

RETURN

200 PRDV=TRI

P

RETURN

300 PRDV= I PATRN* 3840 J/TIME

RETURN

400 PRDV = ( TRIP* 384 0 I/TIME

RETURN

500 PRDV=( PATRT*480 l/TIME

RETURN

600 PRDV=i TRPRT4480 J/TIME

RETURN

END

119
O

O

O

O

O

DO

Jun 12 13:31 1984 preprd.f Page 1

SUBROUTINE PREPRDI 1P,CANDTP, 1 CSBTR , PRDCOQ , PRO 1 C , 1CSTP , PARM03

1 PARM05

)

IMPLICIT INTEGER ( B-Y

)

DIMENSION CANDTPI PARM03, 1 i , ICSBTRI PARM05, 1 ), PRDCODI 1 ) ,PRDICI 1

)

PRDCODI IP):

1: NUMBER OF PATRONS WITH PRIORITY IP

2 : NUMBER OF TRIPS WITH PRIORITY IP

3: PATRONS PER UNIT TIME

4 : TRI PS PER UNIT TIME

5: I PATRN*ERT I/TIME

6: ( TR1P*ERT I/TIME

PATRN=0

TRI P=0

PATRT = 0

TRPRT = 0

1 1 = PRDCODI IP)

IF l Il.EQ.l) GO TO 100

IF I 11.EQ.2) GO TO 200

IF ( 1 1.EQ.3 ) GO TO 300

IF ( 1 1.EQ.4 ) GO TO 400

IF ( 11.EQ.5 ) GO TO 500

IF ( 1 1.EQ.6 ) GO TO 600

100 CONTINUE

DO 150 12 = 1 , ICSTP

IF I 1 CSBTR ( 12, 12 ) .NE . IP ) GO TO 150

IF I I CSBTR I 1 2 , 2 ) . NE . 1 ) GO TO 150

PATRN=PATRN+ ICSBTRI 12,9 I + 1CSBTRI 12 , 10 ) + ICSBTRI 12,11)

150 CONTINUE

CALL PRDCTYI II, PATRN, TRIP, PATRT, TRPRT, TIME, PRD1CI IP) ) RETURN

200 CONTINUE

DO 250 12=1, ICSTP

IF I 1 CSBTR

I

1 2

,

12 ) . NE . 1 P ) GO TO 250

IF ( I CSBTR! 12,2 ) .NE . 1 ) GO TO 250

TRI P=TRIP+

1

250 CONTINUE

CALLrPRDOTY! 1 1 , PATRN , TRIP , PATRT , TRPRT , TIME , PRD1C! IP ) )

' 300 CONTINUE

DO 350 12=1, ICSTP

IF ( I CSBTR I 12, 12 ) .NE . IP ) GO TO 350

IF ! ICSBTRI 12, 2 ) .NE . 1 ) GO TO 350

350 CONT^NUE

TRN+1CSBTRI I2 ' 9| + 1CSBTRI 12,1° 1 + 1CSBTRI 12,111

T1ME = ICSBTRI ICSTP, 8 ) -ICSBTRI 1,8 ) ?£!:

L PRDCTYI II

/

pATRN, TRIP, PATRT, TRPRT, T1ME,PRDIC I IP) ) RETURN

400 CONTINUE

DO 450 12=1, ICSTP

IF I ICSBTRI 12,12). NE. IP) GO TO 450

IF I ICSBTRI 12,2 ) .NE. 1 ) GO TO 450

TRI P=TR1 P+

1

450 CONTINUE

T 1 ME = ICSBTRI ICSTP, 8) -ICSBTRI 1,8)

CALL PRDCTYI 1 1 , PATRN , TRI P , PATRT , TRPRT , TIME,PRDIC( IP ) i

120
Jun 12 13:31 1984 preprd.f Page 2

500 CONTINUE

DO 550 12=1, ICSTP

IF ( ICSBTRI 12,12 ).NE. IP) GO TO 550

IF ( ICSBTRI 12,2). NE.l) GO TO 550

1 3= ICS8TRI 12,9) + ICSBTRI 12 , 10 ) + 1CS3TRI 12,11)

J1 = ICS8TR( 12,1

)

CALL FI ELD I 1,CANDTPI Jl, 3), 14, 9, 12)

PATRT = PATRT + 13*14

550 CONTINUE

T I ME = ICSBTRI ICSTP , 8 )- ICSBTRI 1,8)

CALL PRDCTYI 1 1 , PATRN , TRIP , PATRT , TRPRT , TIME , PRD1CI IP) ) RETURN

600 CO 650 12=1, ICSTP

IF I ICSBTRI 12, 12) .NE. IP) GO TO 650

IF I ICSBTRI 12,2) .NE. 1 ) GO TO 650

Jl= ICSBTRI 12,1

)

CALL FIELD! 1 ,CANDTPI Jl ,3 ) , 13,9, 12

)

TRPRT = TRPRT + 13

650 CONTINUE

T1ME= ICSBTRI ICSTP, 8) -ICSBTRI 1,8)

CALL PRDCTYI 1 1 , PATRN , TRIP , PATRT , TRPRT , TIME , PRD1CJ IP)

)

RETURN

EMD

121
Dec 11 13:56 1984 readcv. f Page 1

SUBROUTINE READCV ( PA03XX , PA03PX , PA08XX , PA08RX

1 CANDTP , COMPAT , DISTOD , DISTOO, PR30RL , TOURL3

' 2 VCADWE , VI YPEL , PARM03 , PARM08 , PARM10

)

IMPLICIT INTEGER ( B-Y

)

DIMENSION BASETP! 1 ) , CANDTP ( PARM03, 1

)

DIMENSION COMPAT ( 1 J ,DlSTOO( 1 ) , DISTOO! 1

)

DIMENSION PRIORLI 1 ) , TOURL1 ( PARM08 , 1

)

DIMENSION VCADWE ( PARM 10 , 1 ) , VTYPEL! 1

)

READ! 11 , 1001 ) 1,1, PA03XX ,3,1,1, PA07XX , PA08XX ,

I

1 1,1, 1,1, 1,1, 1,1, PA03VX , PA08RX , I BX , 1 DX

1001 FORMAT (2006)

PA03PX=PA03XX-PA03VX

READ! 11,1071) (VTYPELI 1 ),]=!, PA07XX i 1071 FORMAT! 8012)

DO 1080 1=1, PA10XX

READ! 11 , 1081 ) Ml, ( VCADWE < 1 , J ) , J = 1 , 2 ) 1080 CONTINUE

1081 FORMAT! 15, 8012/5X, 8012)

DO 1110 1=1, PA08XX

READ! 11, 1081 ) Ml, (TOURLK l,J),J = i,3) 1110 CONTINUE ' DO 1140 1=1, PA03XX

READ! 11, 1081 ) Ml, (CANDTP! 1,01,0=1 ,16) 1140 CONTINUE ' 11 = 1

I2=1BX

DO 1170 1=1, PA03PX

READ! 11 , 1081 ) Ml, I BASETP! J )

, J= 1 1 12) READ! 11, 1081 ) Ml, ( COMPAT (J),J = 11I2) 11=11+1 8X

12=12+1 BX

1170 CONTINUE

DO 1200 1=1, IDX

READ! 11,1081 ) Ml,

1200 CONTINUE

D1STOO! I ) ,D1STOO! 1 ) DO 1220 1=1,15

READ! 11, 1081 ) Ml,

1220 CONTINUE

PRIORLI I ) RETURN

END

PA03VX, BASETP,

, PA10XX

,

122
Jan 17 1 4:49 1985 rmtime.f Page 1

SUBROUTINE RMT I ME I 2 A , 1K2 , JK , IFLAG2

,

1 CANDTP , 1SE , KSE , 1C1 , 1C2 , RTB , RTS , SHTB , SHTS

,

2 PARM03 , PARM05 ) IMPLICIT INTEGER I B-Y ) DIMENSION CANDTPI PARM03 , 1 ) , 1SEI PARM05, 1 ) , KSEi PARM05 , 1

)

C

C I FLAGS = 1 : A BETTER SUBTOUR OF IK2 STOPS IS FOUND

C I FLAG2=0 : OTHERWISE

DO 100 11=1, IK2

IF (KSEI 11,1). EQ.IC1. AND. KSEI 11,21. EQ.l) 12=11

IF (KSEI 11,11. EQ.IC1. AND. KSEI 11,2). EQ. 2) 13=11

100 CONTINUE

CALL FIELDI 1,CA!\0TP( I C 1 , 3 ) , TMXOB ,21,12)

RTS = TMX08 - ( KSE ( 13, 8) -KSEI 12,8)1

SHT3=KSE( IK2 , 8 ) -KSEI 1,8)

IF IRTB-RTS) 300,200,500

200 IF I SHTB. LE. SHTS) GO TO 500

300 R16=RT3

SHTB=SH7S

IFLAG2=

1

JK=1K2

IC2= 1

A

DO 400 11=1, 1K2

DO 400 12=1,12

ISEl 11,12 5 =KSEI 11,12)

400 CONTINUE

500 CONTINUE

RETURN

END

123
Nov 20 15:33 1984 sbtgen.f Page 1

SUBROUTINE SBTOENI JA , 1P1 , 1FLAG2 , IFLAG5

,

1 BVECT 1 , CANDTP , COMPAT , DISTOO , DISTOO, ICSBTR , 3 SE , 1 VWHTR

,

2 KSE , VCADWE

,

3 IBGNP , IBGNS , 1C1 , PA03XX , 1CSTP , 3 ENDP , 1ENDS , PA03PX , PA03VX

,

4 JRDWT , MCVC , PA08UX , NWCAP , 5 PARM03 , PARM04 , PARM05 , PARM06 , PARM10

)

IMPLICIT INTEGER I B-Y

)

DIMENSION BVECT 1 1 1 ) ,CAN3TP( PARM03 , 1 ) ,COMPATI 1

)

DIMENSION DISTCDI 1 ) , DISTOO! 1 )

, ICSBTR! PARM05, 1

)

DIMENSION 1SEI PARM05 , 1 ) , IWHTRl PARM06 , 1 ) , KSE( PARM05 , 1

)

DIMENSION VCADWE ( PARM 10,1)

DIMENSION BVECT2I 20

)

JK = 0

IVAX1=PA03VX+

1

200 1FLAG2=0

IC2 = 0

RTS = 0

RTB = 0

SHTS=99999

SHTB=99999

C SEARCH A PATRON FOR RIDE SHARING

DO 290 JB= 1 VAX1 , PA03XX

IF iJB.EQ.JA) GO TO 290

CALL FIELD! 1,CAM3TP( JB, 1 )

, 1 1 , 6 , 1

)

IF I 11.NE.0 ) GO TO 290

CALL FIELD! 1 , CAMDTP! JB , 1 ) , MCPA , 1 1 , 3

)

IF I MCPA . GT . MCVC ) GO TO 290

CALL FIELD! 1 , CANDTP! JB , 2 ) , I PRIOP ,

5

f 4

)

IF ! 1PRIOP.NE. IP1 ) GO TO 290

C CAN THE PATRON SHARE RIDE WITH THE BASE TRIP?

I 1=JB-PA03VX

J 1=1 1/31

J2=I 1-31*J1

IF ! J2 . EQ . 0 ) J2=31

IF tJ2.NE.31) JlsJl+1

Jl= Jl+4

J2=J2+

1

CALL F 1 ELD I 1 , BVECT 1(J1) < I2,J2,1)

IF ( 12. EQ. 0 ) GO TO 290

C 4* TRANSFER COMPATIBILITY MATRIX**

I4=PA03PX/31

I5=PA03PX-31* 14

IF ! 15. NE. 0 ) 14=14+1

15=14+4

I3=JB-PA03VX

DO 240 11=1,14

12=15*1 13- 1 ) + 1 1+4

BVECT2! 1 1 ) =COMPAT ( 12)

240 CONT 1 NUE

C **TEST FOR RIDE COMPAB1 LI TY**

DO 280 11=1, 1CSTP

IF ( ICSBTR! 11,1). EQ.JA) GO TO 280

IF ( ICSBTR! II, 1 > .EQ.JB) GO TO 280

IF ! ICSBTR! 11,2) .NE. 1 ) GO TO 280

I2 = 1CSBTR{ 11,1) -PA03VX

Jl= 12/31

124
Nov 20 15:33 1984 sbtgen.f Page 2

J2=12-31*J1

IF (J2.EQ.0) J2=31

IF (J2.NE.31) J1=J1+1

J2= J2+

1

CALL FIELD! 1,BVECT2( J1 ), 13, J2, 1

)

IF ! 13.EQ.0 ) GO TO 290

280 CONTINUE

CALL TRCOMB! JB, JK, IFLAG2, 1FLA65,

1 CANDTP , DISTOD , D1STOO , 1SE , ICSBTR , I VWHTR , KSE , VCADWE

,

2 IBGNP, IBGNS, 1C1, IC2,PA03XX, 1CSTP, 1 ENDP , I EMDS , JRDWT

,

3 NWCAP , RT8 , RTS , SHTB , SHTS

,

4 PARM03 , PARM04 , PARM05 , PARM06 , PARM10

!

290 CONTINUE

IF UFLAG2.EQ.0i RETURN

ICSTP= JK

DO 400 11=1, JK

DO 400 12=1,12

ICSBTR! 11, I 2 ) = 1 SB ( 11,12)

400 CONTINUE

C REMOVE 1 FROM BVECT1

1 1 = IC2-PA03VX

Jl= 1 1/31

J2=11-31*J1

IF (J2.EQ.0) J2=31

IF (J2.NE.31) J1=J1+1

J 1 = J 1+4

J2= J2+

1

CALL F 3 ELD ( 2 , BVECT 1(J1),0,J2,1)

C REMOVE 1 FROM PRIORITY SUM FROM BVECT

1

Jl=lPl/4

J2= IP1-4* J1

IF (J2.EQ.0) J2=4

IF (J2.NE.4) J1=J1+1

IF (J2.EQ.4) BVECT 1 ! J 1 ) =BVECT 1 ( J 1

) -

1

IF (J2.EQ.3) BVECT 1! J 1 ) =BVECT 1 1 J 1

) -256

IF (J2.EQ.2) BVECT 1 ( J 1 ) =8VECT 1 ! J 1

) -65536

IF (J2.EQ.1) BVECT 1 ( J1 )=BVECT1( J1 )- 16777216

GO TO 200

END
Jan 14:45 1985 sbtour.f Page 1

SUBROUT 1 NE SBTOUR I JA , TALSB , I PR 3 OP ,3 FLAGS , 1FLAG5 , B I PR

,

1 BVECT 1 , CANDTP , COMPAT , D1STOD , DISTOO , 1BSBTR , ICSBTR, 1SE,

2 I VWHTR , KSE , PRDCOO , PR I OTR , VCADWE , PRD I B , PRD 1 C

,

3 1BGNP, 1BGNS , 1BSTP , PA03XX , 1ENDP , I ENDS , PA03PX , IPRIOT , PA03VX , JRDWT

,

4 MCVC , PA08UX , NWCAP

,

5 PARM03 , PARM04 , PARM05 , PARM 06 , PARM10

)

IMPLICIT INTEGER (B-Y)

DIMENSION BVECT 1 1 1 )

, CANDTP ( PARM03 , 1 )

, COMPAT! 1 ) ,DlSTOO( 1 ) DIMENSION DISTOOI 1 ) , IBSBTRI PARM05 , 1 )

, ICSBTRI PARM05 , 1

)

DIMENSION 1SEI PARM05 , 1 ), 1VWHTRI PARM06 , 1 ) ,KSE( PARM05 , 1 ) DIMENSION PRDCOO ( 1 ) ,PR10TRI 1 )

, VCADWE I PARM10 , 1 ) DIMENSION PRD 1 8 ( 1 ) , PRD 1 C ( 1 ) ICSTP=2

IC1= JA

I Pl= I PRIOT

DO 80 11=1,15

PRD 1C I II ) = 0

80 CONTINUE

ICSBTRI 1, 1 )=JA

ICSBTRl 1 2)=1

CALL F1ELD( 1 , CANDTP ( JA , 16 J, ICSBTRI 1,9), 1,8)

CALL F1ELD( 1, CANDTP! JA , 16 ) , ICSBTRI 1,101,9,4)

CALL FIELD! 1 , CANDTP! JA , 16 ), 1CSBTR! 1,11), 13,4)

ICSBTRI 1,3) = ICSBTRI 1,9)

ICSBTRI 1,4) = 1CS8TR! 1,10)

ICSBTRI 1,5) = ICSBTRI 1,11)

ICSBTRI 1, 12)=1PR10P

ICS8TRI 2,1) =JA

ICSBTRI 2 , 2 ) =2

CALL FIELD! 1, CANDTP! JA , 16 )

, ICSBTRI 2,7 ) ,25,8 ) ICS8TRI 2 , 3 ) =0

ICSBTRI 2,4 ) =0

ICSBTRI 2 , 5 ) = 0

ICSBTRI 2,9) = ICSBTRI 1,9)

ICSBTRI 2,10) = ICSBTRI 1,10)

ICSBTRI 2, 11)= ICSBTRI 1,11)

ICSBTRI 2, 12 ) =1CS8TR< 1,12)

X1=CANDTPI JA, 13 ) -ICSBTRI 1,6)

IF I TALSB. GT. XI) X1=TALS8

CALL FIELD! 1 , CANDTP! JA , 3 ) ,EMXRT,21, 12)

X2=CANDTP I JA, 15 l-EMXRT

IF I TALSB. GT.X2) EMXRT=CANDTPI JA , 15 ) -tALSB

' 100 CONTINUE

C CALL SUBTOUR GENERATOR

CALL SBTGENI J A , I P 1 , 1 FLAG2 , 1 FLAG5

,

1 BVECT 1, CANDTP, COMPAT, DISTOO,D1STOO, ICS8TR , 1SE, 1 VWHTR,

2 KSE, VCADWE,

3 1BGNP, IBGNS, 1C1 , PA03XX , ICSTP , 1ENDP , 1 ENDS , PA03PX , PA03VX

,

4 JRDWT, MCVC, PA08UX, NWCAP,

5 PARM03 , PARM04 , PARM05 , PARM06 , PARM10 ) C CALCULATE PRODUCTIVITY OF ICSBTR

CALL PREPRDI I PI, CANDTP, ICSBTR , PRDCOO , PRD1C , 1 CSTP , PARM03

,

1 PARM05

)

IF I PRD1CI 1P1 1-PRD1BI IP1 ) ) 600,140,200

140 IF I IP1.NE. 1PRIOT ) GO TO 160

150 IF I PRDIBI 1P1 ) .EQ. O') RETURN

126
Jan 1*4 14:45 1985 sbtour. f Page 2

160 1P1=1P1+1

IF ( 1P1.GT.15) GO TO 600

IF I PRIOTRI IP1 ) .NE. 1 ) GO TO 160

GO TO 100

200 CONTINUE

DO 220 1 1 = I PR 1 OT , 1 P

1

PRDIBI 1 1 ) =PRDICI ID

220 CONTINUE

B1PR=PRD1C( IPRIOT

)

IPD1P1 + 1

IF ( IP1.GT. 15) GO TO 320

DO 300 1P2=1P1,15

IF I PRIOTRI IP2J.NE.1) GO TO 300

JD1P2/4

J2=IP2-4*J1

IF IJ2.EQ.0) J2=4

IF IJ2.NE.4) J1=J1+1

J2=( J2-1 1*8+1

CALL FIELD! 1,BVECT1( J1 ) , 1 1, J2,8

)

IF ( 11.EQ.0 ) GO TO 300

CALL SBTGENI JA , 1 P2 4 I FLAG2 , 1 FLAG5

,

1 SVECT 1 , CANDTP , COMPAT , D1STCO , D1STOO , 1CSBTR , 1SE , 1 VWHTR , 2 KSE , VCADWE

,

3 IBGNP , 1BGNS , IC1 , PA03XX , ICSTP , 1ENDP , 3 ENDS , PA03PX , PA03VX

,

4 JRDWT , MCVC , PA08UX , NWCAP

,

5 PARM03 , PARM04 , PARM05 , PARM06 , PARM1 0 I CALL PREPRD! 1P2, CANDTP, 1CSBTR , PRDCOO , PRDIC , ICSTP , PARM03 , 1 PARM05

)

PRDIBI 1P2)=PRDIC( IP2)

300 CONTINUE

C A SUBTOUR IS MADE

320 IBSTP=1CSTP

IFLAG3=1

DO 400 11=1, ICSTP

DO 400 12=1,12

IBSBTR! 1 1 , 12 ) = 1CSBTR! 11,12)

400 CONTINUE

IENDP=1 VWHTR! I ENDS, 1 )

1 1 = 1CSBTR1 ICSTP, 1 ) CALL TFETCH I TPD , PA03XX , 1 ENDP , 1 1 , DI 3T00 ) ICSBTR! ICSTP, 6)=TPD

600 RETURN

END

127
Oct 9 10:59 1984 shift.f Page 1

C

C

cr

350

360

400

C

420

430

450

500

* 600

SUBROUTINE SHIFT! CANDTP , 1VWHTR , I BGNS , NSTPTR , PARM03 , PARM06 ) IMPLICIT INTEGER (B-Y)

DIMENSION CANDTP! PARM03 , 1 ) , IVWHTRl PARM06 , 1 ) SHIFT TO THE LEFT

IS THE SHIFTING POSSIBLE?

1 1 = 1 BGNS -

1

12=1 BGNS

Ll= IVWHTRl 11,8) + IVWHTRl 1 1 , 6 ) + IVWHTRl 1 1 , 7 ) + IVWHTRl

DELTM= IVWHTRl 12.8J-L1

DETERMINE SUBTOUR'S LENGTH

DO 350 13=12, NSTPTR

IF I IVWHTRl 13,2). EQ.l) GO TO 350

IF I IVWHTRl 13,2). EQ. 3) GO TO 360

IF I IVWHTRl 13,2). EQ. 4) GO TO 400

IF I IVWHTRl 13,2) .EQ. 5) GO TO 400

IF I IVWHTRl 13,3) .NE.O ) GO TO 350

IF I IVWHTRl 13, 4). NE.O) GO TO 350

IF I IVWHTRl 13,5) .NE.O ) GO TO 350

GO TO 400

CONTINUE

RETURN

13=13+1

CONTINUE

14=13-12

IF IDELTM.LE.O) GO TO 600

SHIFT TO THE LEFT

DO 450 Jl=12, 13

J2= IVWHTRl Jl, 1 I J3= IVWHTRl Jl ,2

)

IF IJ3.EQ.2) GO TO 420

IF IJ3.EQ.4) GO TO 420

IF IJ3.EQ.6) GO TO 420

DELTA= IVWHTRl Jl , 8 ) -CANDTP t J2 , 10

)

GO TO 430

DELTA= IVWHTRl Jl , 8 ) -CANDTP! J2 , 13 5 CONTINUE

IF ( DELTA. GE.DELTM) GO TO 450

DELTM=DELTA

CONTINUE

DO 500 Jl=12, 13

IVWHTRl Jl , 8 ) = IVWHTRl Jl , 8 ) -DELTM

CONTINUE

I BGNS = I BGNS +14

RETURN

END

12,7 )

128
Apr 16 11:09 1984 tfetch.f Page 1

SUBROUTINE TFETCH (1,J,K,L,1V)

DIMENSION 1V(1)

Ll = ( K-l 14J + L

L2=Ll/3

L3=L1-3*L.2

IF IL3.NE.0) L2=L2+

1

IF (L3.EQ.0) L3=3

L3= 10#L3-7

CALL FIELD ( 1 , I VI L2 ) , I , L3 , 10

)

RETURN

END

129
Nov 20 15:41 1984 trcomb.f Page 1

SUBROUTINE TRCOMB! 1A, JK, 1FLAG2, 1 FLAGS

,

1 CANDTP , D 1 STOO , D I STOO , 1 SE , 1 CSBTR , 1 VWHTR , KSE , VCADWE

,

2 I BGNP , IBGNS, IC1, 1 02 , PA03XX , I CSTP , 1 ENDP , I ENDS , JRDWT

,

3 NWCAP , RTB , RTS , SHTB , SHTS

,

4 PARM03 , PARM04 , PARM05 , PARM06 # PARM10 ) IMPLICIT INTEGER ( B-Y

)

DIMENSION CANDTP ( PARM03 , 1 ) ,D1STOOI 1 J, D1STOOI 1)

DIMENSION 1SEI PARM05 , 1 ) , 1CSBTR( PARM05 , 1 ) , IVWHTRI PARM06 , 1 ) DIMENSION KSE I PARM05 , 1 )

, VCADWE! PARM10, 1 )

I K= 1CSTP

IK1=1K+1

IK2= 1K+2

DO 100 11=1, IK

12= ICSBTRI 11,1)

13= ICSBTRI 11,2)

IF ( 12.EQ. 1C1.AND. I3.EQ.2) 10=11

100 CONTINUE

11=2

I L = 3

IM= 1K2

C PICK LIMIT

DO 500 J7 = 1 1 , IJ

C DROP LIMIT

DO 400 J8=IL, IM

IF (J7.GE.J8) GO TO 400

KSEI 1K1, 1 ) = I

A

KSE( IK1 , 2 ) =

1

KSEI I K2 , 1 ) = I

A

KSEI 1K2 , 2 ) =2

CALL F1ELDI 1, CANDTP! 3 A , 2 }

, KPRIO , 5,4)

CALL FIELD! 1, CANDTP! 3 A , 16 ) , NNWP , 1 , 8 ) CALL FIELD! 1, CANDTP! 1 A , 16 ) , NLFP , 9 , 4 ) CALL FIELD! 1, CANDTP! I A , 16 )

, NWCP , 13 , 4 ) KSE! 1K2 , 9 ) =NNWP

KSE! IK2 , 10 ) =NLFP

KSE! IK2, 11 )=NWCP

KSE! IK2, 12 ) =KPRIC

KSEI 1K1 , 12 ) =KPRIO

J3= 1

DO 130 J4= 1 , IK

IF IJ7.NE.J4) GO TO 110

IF (J7.EQ.IK1.AND.J8.EQ.IK2) GO TO 120

KSEI J3 , 1 1 =1

A

KSEI J3 , 2 ) =

1

KSE! J3 , 9 ) =NNWP

KSE! J3,10)=NLFP

KSE! J3, 11 )=NWCP

KSE! J3,12)=KPRI0

J3= J3+

1

110 IF IJ8.NE.J4+1) GO TO 120

KSE! J3 , 1 ) = 1

A

KSEI J3, 2) =2

KSE! J3 , 9 ) =NNWP

KSEI J3, 10 )=NLFP

KSE! J3 , 11 ) =NWCP

KSE! J3,12)=KPRIO

130
Nov 20 15:41 1984 trcomb.f Page 2

J3= J3+

1

120 KSE ! J3 , 1 ) = 1 CSBTR ! J4 , 1 } KSE( J3 ,2 ) = 1 CSBTR ( J4,2 ) KSE ( J3 , 9 ) = ICSBTR! J4 , 9 ) KSE! J3 , 10 ) = I CSBTR I J4 , 10 J KSE! J3, 11 J = 1CSBTR( J4, 11 ) KSE! J3, 12 ) = I CSBTR 1 J4 , 12)

J3= J3+

1

130 CONTINUE

CALCULATE NUMBER OF PATRON ON BOARD

J2 = 0

DO 180 Jl=l, 1K2

IF I J1 .N£. 1 ) GO TO 150

KSE! J1,3I*KSE( Jl # 9)

KSE! Jl,4 )=KSE! 01,10)

KSE (01,5) =KSE 101,11)

GO TO 180

150 CONTINUE

J2= J2+

1

J3=KSE( Jl,2)

IF ( J3.E0.2 ) GO TO 170

KSE (01,3) =KSE ( 02 , 3 ) +KSE (01,5*)

KSE! J1 ,4 )=KSE! J2,4 l+KSEI J1 , 10

)

K1=KSE! J1,3)+KSE( Jl,4

)

IF ! Kl.GT.NWCAP ) GO TO 400

KSE (01,5) =KSE ( 02 , 5 ) +KSE (01,11

)

N1 =JRDWT +K1

CALL FIELD! 1,VCADWE!N1, 1 ) ,NWCCP, 1,8)

IF ( KSE ( J 1 , 5 ) . GT . NWCCP ) GO TO 400

GO TO 180

170 KSE ( 01,3) =KSE ( 02 , 3 ) -KSE (01,9)

KSE I J 1 , 4 ) =KSE ! J2 , 4 ) -KSE ! J 1 , 1 0

)

KSE (01,5) =KSE ( 02 , 5 ) -KSE ! J 1 , 1 1

)

180 CONTINUE

CALCULATE NEXT LEG TRAVEL TIME

J2 = l

DO 270 Jl=l, 1K2

J2= J2+

1

K1=KSE( 01,1)

K2=KSE! Jl,2)

IF ! Jl.EQ. IK2 ) GO TO 200

K3=KSEI J2 , 1

)

K4=KSE! 02,2)

GO TO 210

200 CONTINUE

K3= IENDP

K4 = 1 210 CONTINUE

IF (K2.EQ.K4I GO TO 230

IF { K2.EQ.2 ) GO TO 220

CALL TFETCHI KSE! J1 , 6 ) , PA03XX , K1 , K3 , DISTOO ) GO T O 27 0

220 CALL TF5TCH! KSE! J1 , 6

)

; PA03XX , K3 , K1 , DISTOO

)

GO TO 270

230 IF (K2.EQ.2) GO TO 240

IF (K1.GT.K3) GO TO 260
Nov 20 15:^1 1984 trcomb.f Page 3

GO TO 250

240 IF* IK1.LT.K3) GO TO 260

250 CALL TFETCH(KSE( Jl,6) , PA03XX , K1 , K3 , DISTOO

)

GO TO 270

260 CALL TFETCHIKSEI J1 ,6) , PA03XX , K3 , K1 , DISTOO)

‘ 270 CONTINUE

C CALCULATE DWELL TIME

J1 = 0

* 278 J1=J1+1

IF I Jl.GT. 1K2 ) GO TO 300

I9=KSE( J1 , 9

)

1 10=KSE( J1 , 10 ) 111 =KSE I J 1 , 1 1 ) IF I KSEI Jl,2 ) .EQ.2 ) GO TO 286

IF I KSEI Jl,6 ) .EQ. 0 ) GO TO 280

I1=KSE( Jl,l)

CALL FIELD! 1,CANDTP( 11 , 16 ), KSEI 01,7), 17 , 8 ) GO- TO 278

280 CONTINUE

J2=J1

282 J 1=J1+1

IF (KSEI J1,2).EQ.2) GO TO 284

KSEI Jl,7)=0

19= 19+KSEI 01,9)

1 10=1 10+KSEI 01,10)

111 = 111 +KSE I J 1- , 1 1

)

IF (KSEI J1,6).EQ.0) GO TO 282

284 CALL DWELLTI 19, 110, 111, 0,0,0, JRDWT , KSEI J2 , 7 ), VCADWE , PARM1 0 ) GO TO 278

286 IF I KSEI Jl,6 ) .EQ. 0 ) GO TO 290

287 I 1=KSE( 01,1)

288 CALL FIELD! 1 , CANDTPI 11,16), KSEI J1 , 7 ) , 25 , 8 1 GO TO 278

290 CONTINUE

IF I J1+1.GT.IK2) GO TO 287

J2= J

1

292 J1=J1+1

IF I KSEI J1 , 2 ) . EG) . 1 ) GO TO 294

KSEI J2 , 7 ) =0

19= 19+KSEI Jl,9

)

1 10 = 1 10+KSEI 01,10)

111 = 111 +KSE 101,11)

IF ( KSEI J1 , 6 ) . EQ. 0 ) GO TO 292

294 CALL DWELLTI 0,0,0,19,110, 1 11 , JRDWT , KSEI Jl,7 ) , VCADWE , PARM 10 ) GO TO 278

300 CONTINUE

C ASSIGN THE SCHEDULED TIME

KSEI 1,8)= 1CSBTRI 1,8)

DO 370 Jl=2, IK2

IF l KSEI J1 , 2 ) . EQ . 2 ) GO TO 340

IF I KSEI Jl-1,2 ) .EQ. 2 ) GO TO 330

KSEI J1 ,8 )=KSEI Jl-1 ,8 )+KSEI Jl-1 ,6 ) +KSEI J1 ,7 ) GO TO 370

330 KSEI J1 , 8 ) =KSEI Jl-1, 8 l+KSEI Jl-1,6 l+KSEI Jl-1 ,7 ) 1 +KSEI J1 ,7 ) GO TO 370
Nov 20 15:41 1984 trcomb.f Page 4

340 CONTINUE

IF |KSEIJ1-1,2).EQ.2) GO TO 350 KSEjJl^a l=KSE( Jl- 1 , 8 ) +KSEI Jl-1,6 )

CALL FES 1 BL ( IK2, 1 FLAG 1, I FLAG5,

1 CAMJTP , DISTOO , DISTCO , I VWHTR , KSE

2 I BGNP , I BGNS , PA03XX , I ENDP , 1 ENDS

3 PARM03 , PARM04 ; PARM05 , PARM06 ) IF ( IFLAG1.EQ. 0 ) GO TO 400

CALL RMTIME( I A , 1K2 , JK , IFLAG2

,

2 PARM03 i PARMo|

E ' 3 C

1

' 3 C2 ' ^, RTS , SHTB , SHTS

,

400 CONTI WE

500 CONTINUE

RETURN

END

133
APPENDIX J TEST DATA

This appendix contains data on trip information used in test runs. Trip

information are real. The meaning of columns are stated below. Trip data are

reproduced as exactly as they were received. The data format and the contents

are not necessarily the same as used in the RSDAR.

Column

1 Patron name

2 Trip number

3

‘ Request time (hhmm)

4 Service code

5 Agency

6 Patron type

7 Number of regular patron

8 Number of wheelchair patron

9 X-coordinate of the origin

10 Y-coordinate of the origin

11 X-coordinate of the destination

12 Y-coordinate of the destination

J1
Sep 6 13:05 1984

FERRANTE THELMA

HERSEY MARGIE

MERLER MURIEL

80RKAN JENNIE

PRUCHA MARY

HUNTER ROBERT

SANDS JOHN

HELM GLORIA

JIM1NEZ ROSE AIMEE

ALEMAN NIRIC

VAZQUEZ OSVALDO

ALVAREZ ARMANDO

ROJAS MANUAL

CANTY DENISE

LEVENSON MILDRED

WHITE SUSAN

CLEMENCON HELEN

RODRIGUEZ GILBERTO

SIMAKOW NANCY

EISAMAN PAMELA

VAZQUEZ OSVALDO

ALVAR 1 NO JESUS

KRIV1T DOROTHY

KALMUS IRENE

ALEMAN NIRIO

LEVENSON MILDRED

WHITE SUSAN

MAXWELL WILLIE

SIM1KON NANCY

TURNER LEONARD

CLEMENCCN HELEN

KALMUS IRENE

KRESS JOAN

HUNTER BEVERLY

PERKINS JAMES

PALMER RCN

MCNALLY JOHN

LEVINE HARRIET

SUAREZ HILDA

DE HARVE EDWARD

GARCIA ALBERT

WILCOX ELIZABETH

GORDON JIM

KENDRICK DENISE

DAY DANIEL

MALL IE ELEANOR

CRUZ ELSA

FIELDS LINDA

WHITE AL

BYRD FRED

KAZMARK RONALD

FERGUSON GRANVILLE

DOWNER RICHARD

LEVINE ROSS

GODWIN FLORA

WALLIS JEFFREY

m300.d Page 1 1 615 1 1 3 0 1 15 23 15 21 3 645 1 1 3 0 1 11 24 15 21 3 700 1 1 3 0 1 10 20 17 21 4 700 1 1 3 0 1 17 21 16 26 b 700 1 1 3 0 1 9 14 14 19 6 700 1 1 3' 0 1 12 18 10 17 7 700 1 1 3 0 1 10 15 9 15 8 700 1 1 3 0 1 16 25 13 22 9 730 1 1 2 0 1 12 20 15 21

10 730 1 1 2 0 1 15 21 15 21

11 745 1 1 3 0 1 17 21 15 21

13 800 1 1 2 0 1 14 20 10 17

13 830 1 1 3 0 1 13 20 18 23

14 830 1 1 2 0 1 14 22 15 21

15 845 1 1 2 0 1 18 23 15 20

16 900 1 1 2 0 1 12 20 15 20

17 900 1 1 3 0 1 17 21 17 21

18 1000 1 1 2 0 1 14 20 15 21

19 1000 1 1 2 0 1 15 24 16 26

30 1000 1 1 2 0 1 11 20 11 24

31 1100 1 1 2 0 1 15 21 17 21

33 1100 1 1 2 0 1 13 20 11 24

33 1100 1 1 2 a 1 18 23 18 23

34 1130 1 1 2 0 1 17 21 18 25

35 1130 1 1 2 0 1 15 21 14 21

36 1130 1 1 2 0 1 15 20 14 24

37 1130 1 1 2 0 1 15 20 12 20

38 1145 1 1 2 0 1 14 25 15 21

39 1145 1 1 2 0 1 16 26 15 24

30 1300 1 1 2 0 1 15 23 11 24

31 1330 1 1 2 0 1 17 21 17 21

33 1330 1 1 2 0 1 18 25 17 21

33 1330 1 1 2 0 1 8 20 9 19

34 600 1 1 1 1 0 14 26 15 20

35 600 1 1 1 1 0 14 27 15 21

36 600 1 1 1 1 0 14 27 15 20

37 600 1 1 1 1 0 16 26 15 20

38 600 1 1 1 1 0 16 26 17 21

39 600 1 1 1 1 0 14 21 13 IS

40 600 1 1 1 1 0 12 24 15 21

41 600 1 1 i 1 0 11 19 12 20

43 600 1 1 . 1 1 0 15 22 15 21

43 600 1 1 1 1 0 14 22 15 21

44 600 1 1 1 1 0 14 23 15 22

45 600 1 1 1 1 0 12 20 15 21

46 615 1 1 1 1 0 15 20 15 21

47 615 1 1 1 1 0 13 23 15 20

48 615 1 1 1 1 0 13 24 17 23

49 615 1 1 1 1 0 16 26 14 21

50 635 1 1 1 1 0 15 23 17 22

51 630 1 1 1 1 0 13 19 15 20

53 630 1 1 1 1 0 14 25 15 21

53 630 1 1 1 1 0 15 27 16 25

54 630 1 1 1 1 0 15 27 13 25

55 630 i

Jk 1 ' 1 1 0 16 25 15 21

56 635 1 1 1 1 0 16 22 15 20

J2
Sep 6 13:05 1984 m300.d Page 2

BURRIS CLARK 57 645 1

WEBSTER GEORGE 58 645 1 CLETZKY MARSHALL 59 700 1

BLIER MARK 60 700 1

KING CAROL 61 700 1

POTTER RAYMOUND 62 700

AX

OENRUBE MALLARY 63 700 1

CERNCBORT LINDA 64 700 1

RENDELL JUDY 65 700 1

RICE JOEL 66 700 1

YUBASZ HELENE 67 700 1

HEMPHILL BETTY 68 700 1

BLIER ARLYS HALL 69 700 1

WARDLE VIOLA 70 700 1

WILKAT1S JOE 71 700 1

BUFKE MARION 72 700 1 TURRIN1 LAWRENCE 73 700 1

NABUTOVSKY BARBARA 74 700 1

LEEDS LOMA 75 700 1

LAIDLOW THOMAS 76 705 1

SHELDON MARTHA 77 705 1

CANN ELAINE 78 710 1

MCKENZIE ANNE 79 710 1

THOMAS ANNELY 80 710 1

JOHNSON ANN 81 715 1

SILVERO HAYDEE 82 715 1

CAMP CHARLOTTE 83 715 1

GODFREY ROSEANN 84 715 1

MATHIS GREGORY 85 715 1

DIAZ SARAH 86 715 1

RANDOLF ANNIE MAE 87 715 1

CAMERON GLORIA 88 715 1

SIPPIO JANICE 89 720 1

MILLER BRUCE 90 720 1

LAATSCH JUDY

A 91 725 1 LEVIT IDA 92 730 1

PRYCR JANET 93 730 1

ALTMAN RUTH 94 730 1

CALDERON WILMA 95 730 1

JAMES MAGGIE 96 730 1 CONDARES GEORGE 97 730 1

GREENWALD JAY 98 730 1

WILLIAMS JOSEPH 99 730 1

CLEARY ENID 100 730 1 PHINNEY DONALD 101 730 1 FINKEL RONALD 102 730 1 JIM INEZ ROSE 103 730 1 GILMORE FRANCES 104 730 1 ZAMORA OTTO 105 730 1 BLANCO JERONIMO 106 730 1 HAJ FAREED 107 730 1 SANCHEZ ANNA L 108 745 1 DCNLEY DALE A 109 745 1 gray lorna 110 745 1

FIX COLEEN

M 111 745 1

SANCMAN MILDRED 112 745 1 1 1 1 0 14 19 17 1 1 1 0 14 22 15 1 1 1 0 17 25 15 1 1 1 0 14 20 17 1 1 1 0 17 22 12 1 1 1 0 14 26 10 4X 1 1 0 17 22 12 i 1 1 0 16 25 17 l 1 1 0 14 27 11 1 1 1 0 11 17 10 A± 1 1 0 13 24 15 1 1 1 0 10 17 14 1 1 1 0 14 20 15 1 1 1 0 16 26 15 1 1 1 0 13 19 13 1 1 1 0 16 26 14 1 1 1 0 15 21 10 1 1 1 0 11 18 10 1 1 1 0 6 9 14 1 1 1 0 13 22 17 1 1 1 0 16 25 15 1 1 1 0 15 23 14 1 1 1 0 lb 21 15 1 1 1 0 15 22 15 1 1 1 0 13 25 11 1 1 1 0 17 21 15 1 1 1 0 13 21 ' 11 1 1 1 0 9 18 17 1 1 1 0 17 19 17 1 1 1 0 13 24 13 1 1 1 0 15 23 14 1 1 1 0 14 21 15 1 1 1 0 14 22 15 1 1 1 0 11 20 14 1 1 1 0 13 21 15 1 1 1 0 16 21 15 1 1 1 0 16 22 15 1 1 1 0 10 18 10 1 1 1 0 13 23 14 1 1 1 0 14 24 14 1 1 1 0 14 19 14 1 ‘ 1 1 0 16 21 15 1 1 1 0 14 23 15 1 1 1 0 12 20 13 1 1 1 0 13 20 15 1 1 1 0 17 27 14 1 1 1 0 12 20 15 1 1 1 0 14 22 : - 1 1 1 0 8 20 10 1 1 1 0 15 20 14 1 1 1 0 12 19 12 1 1 1 0 9 14 12 1 1 1 0 15 24 12 1 1 1 0 9 14 10 1 1 1 0 16 24 1 ^ 1 1 1 0 17 22 18

J3

(X'

rx'

rv

rx'

rx'

fX'

fX'

rx'

rx»

rxx

rx'

rx'

ru

rx'

rx1

rx'

»-»

rx'

•-»

t-*

ro

fX'

rx'

rx'

fX'

rx'

rx'

-»

»-*

*-»

rx'

rv

rx'

rx'

rx'
Sep 6 13:05 1984

GALLARDO PEDRO

m300 . d

113

Page 3

750 1 1 1 1 0 11 18 10 i!j1 17

PARSONS RUTH 114 800 1 1 1 1 0 18 23 18 . 22

GUSMAN AUGUST 1NA 115 800 i 1 1 1 0 10 19 15 22

STONE RITA 116 800 1 1 1 1 0 17 23 14 24

WEBER RUTH 117 800 1 1 1 1 0 3 18 15 20

HERNANDEZ ELENA 118 800 1 1 1 1 0 12 20 15 21

PEREZ SALOMON 119 800 1 1 1 1 0 17 20 15 21

KWASN1CK1 VICTORIA 120 800 1 1 1 1 0 11 25 9 18}

LONDON PATRICIA 121 800 . 1 1 1 1 0 13 22 15 2 1 • REGGVINT 1 THERESA 122 800 1 1 1 1 0 14 25 13 2*3 i MELN1CK ALBERT 123 810 1 1 1 1 0 11 19 9 18!

WINTERS THERESA 124 810 1 1 1 1 0 13 22 9 18 ( SCHWARTZ SETH 125 815 1 1 1 1 0 18 22 15 21!

Z1NGARO MARION 126 815 1

J. 1 1 1 0 14 20 15 20!

FALDOSK 1 JENNIE 127 815 1 1 1 1 0 14 27 15 25!

ALLEN JAMES

F 128 815 1 1 1 1 0 10 17 13 26!

GORMAN FRANK 129 815 1 1

J. 1 1 0 15 26 13 20)

K1MBRO EOLYN 130 820 1 1 1 1 0 14 24 15 211

DE COSTE 131 825 1 i 1 1 0 11 16 9 18/

HARTNETT PATRICIA 132 825 1 1 1 1 0 10 19 9 18J

SCHAUR HAROLD 133 825 1 1 1 1 0 9 19 9 18!

LEFF BEN 134 830 1 1 1 1 0 16 24 18 22!

BUTTA JOSEPH 135 830 1 1 1 1 0 8 18 12 18.

SIMON HARRIET 136 830 1 1 1 1 0 13 27 15 20!

GUI NONES MARIA 137 830 1 1 1 1 0 14 20 16 170

FERNANDEZ JOSE 138 830 1 1 1 1 0 12 20 15 22

RINGER ANN 139 830 1 1 1 1 0 17 25 18 23'

BILL1NGTGN MARK 140 830 1 1 1 1 0 10 18 9 18 - SP1NELLI WILLIAM 141 830 1 1 1 1 0 16 25 13 26'

CALDERON CECILIA 142 830 1 1 1 1 0 9 14 17 25!

WEST SUSAN

M 143 830 1 1 1 1 0 11 18 9 18 1. WILSON MARTHA J 144 830 1 1 1 1 0 13 19 13 19'

RAMONDAS RASA 145 835 1 1 1 1 0 10 18 9 18!

DIRUME SELIO 146 835 1 1 1 1 0 11 18 9 18-

YOCHIM ARTHUR 147 840 1 1 1 1 0 10 19 11 19r

HUGGINS RONALD 148 840 1 1 1 1 0 9 19 9 13

FIX COLLEEN

M 149 845 1 1 1 1 0 16 24 15 20

DAPONTE DALE 150 845 1 1 1 1 0 14 21 15 20

SPERRAZZ 1 LEONARD 151 845 1 1 1 1 0 16 26 15 20 4 LEON BETSY 152 845 1 1 1 1 0 12 25 13 26

THOMAS RICHARD 153 845 1 1 1 1 0 15 21 15 21

APARDO SOCCRRO 154 900 1 1 1 1 1 0 15 23 15 21

FEDER ISAAC 155 900 1 A1 1 1 0 18 23 17 21

MCCOLLISTER JAMES 156 900 1 1 1 1 0 14 27 16 25

HERRERA MARIA 157 900 1 1 1 1 0 14 22 13 19’

MEND I OLA DULCE 158 900 1 1 1 1 0 9 14 14 19

RAMIREZ BEATRICE 159 900 1 1 1 1 0 13 19 15 2D

BARNES EDITH 160 900 1 1 1 1 0 15 23 15 20

DUNN ARTHUR 161 900 1 1 1 1 0 13 19 14 211

HARDEN DOROTHY 162 900 1 1 1 AX 0 14 19 11 24'

MORALES 1SHMAEL 163 900 1 1 1 1 0 15 21 15 2l!

LANTZ MICHAEL 164 900 1 1 1 1 0 12 19 11 16'

WALKER NANCY 165 900 i 1 1 1 0 13 27 14 265

DRESSLER DOROTHY 166 900 1 1 1 1 0 12 18 12 17

SCHWARTZ BEATR 167 900 1 1 1 1 0 17 22 17 21 l SILVERS THIN MINA 168 900 1 1 1 1 0 18 22 17 21-
Sep 6 13:05 1984 m300 . d Page 4

AKERMAN CYNTHIA 169 900 1

DOUGLAS TOM 170 905 1

BARON FRED 171 915 1 HEARN BONNIE 172 915 1

ZAVAC JEFF 173 915 1

PHANG ANGELA 174 930 1 REE LEE 175 930 1

AROOIS ANAM 176 930 1

MICHAUD DAVID 177 930 1

HENDRICK AIDA 178 930 1

M1LGROM HELEN 179 930 1

M1LLEY SADIE 180 930 1 YOUNG PAMELA M 181 930 1 LOMBARDI MINERVA 182 945 1

SPRAYGREEN GERTRUDE 183 945 1

S1EBEL MATHILDA 184 945 1 CASH RUTH 185 1000 1

BRYAN JAMES

M 186 1000 1

WASSERMAN FANNIE 187 1000 1

DALTON CLARA SMITH 188 1000 1 FR1EH CORA 189 1000 1

GLOVIN ETHEL 190 1000 1

LINARES VIOLETTA 191 1000 1

SAMPEDRO EULALITA 192 1000 1 BL0M8ERG LEE 193 1000 1

TURNER JOHANN 194 1000 1 RINGER ANN 195 1000 1

HOROWITZ ESTELLA 196 1000 1

S1GMAN SIDNEY 197 1000 1

CAMP 1 CM GRACE 198 1030 1

CHONSKY ANNA 199 1030 1 MIKUC1CN1S BOBERT 200 1030 1 BITINER SOPHIE 201 1030 1

HEALY LILLIE 202 1030 1

MEYERS EUGENE 203 1030 1 ALLEN MOE 204 1030 1 WILLIAMS ROSE MAE 205 1030 1 GREENFIELD EDITH 206 1045 4± MEYER ROSE 207 1045 1 MARGULTES GUSSIE 208 1045 1 SIEGEL MATHILDA 209 1045 1 SCHWARTZ SETH 210 1100 1

CHATLOS RUTH 211 1100 1

ROSS MARY 212 1100 1

KRAUSS PEARL 213 1100 1 WILLIAMS PATTY 214 1100 1 ROSENTHAL DAISY 215 1100 1

HARDEN DOROTHY 216 1100 1 DEANE WANDA 217 1100 1 DAVIS FANNIE 218 1100 1 WOODARD ELBERTA 219 1100 1

LEEDS LCMA 220 1100 1 NEUBERO LEAH G 221 1100 1 CAUSO ANA 222 HOC 1 KURTZ ELL1E 223 1100 1 LEVICX MICHAEL 22* 1115 1 1 1 1 0 13 23 13 23 1 1 1 0 14 19 17 27 1 1 1 0 17 20 15 20 1 1 1 0 14 22 12 19 1 1 1 0 12 19 14 23 1 1 1 0 11 20 13 19 1 1 1 0 14 24 14 24 1 1 1 0 10 20 12 20 1 1 1 0 11 25 13 26 1 1 1 0 14 24 14 24 1 1 1 0 11 18 11 15 1 1 1 0 18 22 18 23 1 1 1 0 IS 22 14 24 1 1 1 0 16 23 14 22 1 1 1 0 14 23 17 21 1 1 1 0 16 26 15 26 1 1 1 0 17 21 15 21 1 1 1 0 17 21 13 21 1 1 1 0 16 21 15 26 1 1 1 0 11 14 13 19 1 1 1 0 11 14 10 15 1 1 1 0 15 20 11 24 1 1 1 0 13 23 13 23 1 1 1 0 10 19 15 19 1 1 1 0 11 18 13 20 1 1 1 0 13 19 10 18 1 1 1 0 18 23 15 20 1 1 1 0 8 18 11 17 1 1 1 0 17 23 17 25 1 1 1 0 14 21 15 21 1 1 1 0 17 23 13 20 1 1 1 0 15 25 13 23 1 1 1 0 11 26 15 21 1 1 1 0 14 19 13 20 1 1 1 0 14 19 14 21 1 1 1 0 16 27 16 26 1 1 1 0 14 22 13 23 1 1 1 0 16 26 17 COu u 1 1 1 0 17 23 11 20 1 1 1 0 14 20 15 u

Dj

O\J 1 1 l 0 15 26 16 26 1 ‘ 1 1 Q 15 21 18 22 1 1 1 0 14 21 15 21 1 1 AX 0 11 19 10 41 I 1 1 1 0 17 27 18 22 1 1 1 0 14 25 15 26 1 1 A1 0 15 20 15 20 1 1 1 0 11 24 14 JL 7 1 1 1 0 16 26 15 2 1 1A 1 1 0 12 21 17 23 1 1 1 0 13 20 13 1 1 1 0 14 23 6 1 1 1 0 18 26 17 2 4 1 1 1 0 15 20 2 ^ J 1 1 1 0 15 25 16 25 1 1 1 0 16 21 14

J5
Sep 6 13:05 1984 m300.d Page 5

CAPLAN BERNARD 325 1115

BOWLES E C 226 1115

BRYAN JAMESM 227 1130

NE1MAN MORRIS 228 1130

STONE RITA 229 1130

FIX COLLEENM 230 1130

GRAY LORNA 231 1130

KAUFMAN RUTH 232 1130

ZAMORA OTTO 233 1130

BARNES EDITH 234 1130

MICHAUD DAVID 235 1130

REGGVINT1 THERESA 236 1130

CALDERON WILMA 237 1200

HERRERRA MARIA 238 1200

CHARBONNEAU WILFRED 239 1200

BARNES EDITH 240 1200

MEYER ROSE 241 1200

KF.E LEE 242 1200

TURNER JOHANN 243 1200

HOROWITZ ESTELLE 244 1200

ZLOCKOWER BERNARD 245 1200

RINGER ANN 246 1200

WALKER NANCY 247 1200

RICK SARA 248 1200

PEREZ SALOMON 249 1200

DAVIS EUGENEH 250 1200

POND FRANK 251 1215

MCKENSIE ANNE 252 1215

WEBER RUTH 253 1215

ARFISKY IDA 254 1215

WOODWARD ELBERTA 255 1215

HIRSCH DEBORAH 256 1230

FEDER ISAAC 257 1230

GARFUNOEL HELEN 258 1230

GORDON DORA 259 1230

LOMBARDI MINERVA 260 1230

WELLS GLADYS 261 1230

WILLIAMS PATTY 262 1230

CASTRO AMA 263 1230

SHAVER ANDREW 264 1230

CARLYSLE MAE 265 1230

ALLEN MCE 266 1230

S1GMAN SIDNEY 267 1230

GONZOLAS ROSA 268 1230

SCHWARTZCACH BEAT 269 1230

PARROTTA ANNA 270 1230

SPRAYGREEN GERTRUDE 271 1245

LLOYD FLORENCE

M 272 1300

S1LVERO HAYDEE LOPE 273 1300

LOPEZ MARTIN 274 1300

WEBSTER GEORGE 275 1300

MORALES 1SHMAEL 276 1300

GORDON JIM 277 1300

HOROWITZ CLARA 278 1300

PROJANSKY SARAH 279 1300

LONDON PATRICIA 280 1300 1 1 1 0 18 23 15 1 1 1 0 15 23 15 i 1 1 0 13 21 17 1 1 1 0 18 25 17 1 1 1 0 14 24 17 1 1 1 0 15 20 9 1 1 1 0 10 17 9 1 1 1 0 16 24 15 1 1 1 0 10 16 8 1 1 1 0 15 20 17 1 1 1 0 13 26 11 1 1 1 0 13 25 14 1 1 1 0 14 24 13 1 1 1 0 13 19 14 1 1 1 0 15 19 15 1 1 1 0 15 23 17 1 1 1 0 11 20 17 1 1 1 0 14 24 14 1 1 1 0 10 18 13 1 1 1 0 11 17 8 1 1 1 0 15 26 15 1 1 1 0 15 20 17 1 1 1 0 14 26 13 1 1 1 0 16 21 17 1 1 1 0 15 21 13 1 1 1 0 14 21 14 1 1 1 0 9 19 13 1 1 1 0 15 21 15 1 1 1 0 15 20 15 1 1 1 0 18 23 17 1 1 1 0 13 19 13 1 1 1 0 18 23 17 1 1 1 0 17 21 18 1 1 1 0 14 20 15 1 1 1 0 17 21 16 1 1 1 0 14 22 16 1 1 1 0 18 26 15 1 1 1 0 15 26 14 1 1 1 0 11 24 17 1 1 A1 0 12 20 10 1 1 1 0 16 22 14 1 “ 1 1 0 16 26 16 1 1 1 0 17 25 17 1 1 1 0 13 21 15 1 1 1 0 17 21 17 1 1 1 0 18 26 18 1 1 1 0 17 21 14 1 1 1 0 17 21 15 1 1 1 0 15 21 17 1 1 1 0 15 20 15 1 1 1 0 15 21 14 1 1 1 0 15 21 15 1 1 1 0 15 21 14 1 1 1 0 16 25 16 1 1 1 0 16 26 16 1 1 1 0 15 21 13 11111111111111111111111111111111111111111111111111111111
Sep 6 13:05 1984 m300.d Page 6

BYRD FRED 381 1300 1 1 1 1 0 17 22 15 23

CALDERON CECILIA 383 1300 1 1 1 1 0 17 25 9 14

KURTZ ELL IE 383 1300 1 1 1 1 0 16 25 15 25

MARTELL LOIS 384 1300 1 1 1 1 0 12 25 11 25

LEACH JANICE 385 1315 1 1 1 1 0 17 21 16 24

WILLIAMS JOSEPH 386 1315 1 1 1 1 0 15 26 14 23

2AVAC JEFF 387 1315 1 1 1 1 0 14 23 12 19

EATON RUTH 388 1315 1 1 1 1 0 10 17 8 11

MOTES ETTA 389 1330 1 1 1 1 0 12 21 12 18

BLY PATSY 390 1330 1 1 1 1 0 15 24 15 21

D1ELH T1LL1E 391 1330 1 1 1 1 0 12 19 15 21

ALTMAN RUTH

R 392 1330 1 1 1 1 0 14 19 10 18

CASTELLANOS ARCHIE 293 1330 1 1 1 1 0 9 19 14 20

GILMORE FRANCIS 294 1330 1 1 1 1 0 14 24 14 22

SAMET WILLIAM 295 1330 1 1 1 1 0 8 12 13 21 SAMET LILLIAN 296 1330 1 1 1 1 0 8 12 13 21 SANDMAN MILDRED 297 1330 1 1 1 1 0 18 22 17 25 QUINONES MARIA 298 1330 1 1 1 1 0 14 21 14 20 SP 1 NELL 1 WILLIAM 299 1330 1 1 1 1 0 13 26 16 25 JESSEL MARGARET 300 1345 1 1 1 1 0 15 21 13 19

FEDERAL INFORMATION PROCESSING STANDARD SOFTWARE SUMMARY

03. Summary action New Replacement Deletion a

Previous Internal Software ID

07.

L

Intemai Software ID

01. Summary date! 02. Summary prepared by (Name and Phone) ^ Howard K. Hung (301) 921-3855 Yr.

, 8 5 0 ? 0 5 I 05. Software title 04. Software date Routing and Scheduling Dial-A-Ride (RSDAR)

Yr. Mo. Day

18 5 0 2 Q 5

—t)6. Short title 03. Software type 09. Processing mode 10. Application area General

< Automated Data Computer Systems Management/

| j System | | Interactive j [ Support/ Utility Business TV Computer Program NX Scientific/Engineering j~ Process Control

• | Subroutine/ Module [

| Combination ; j Bibliographic/Textuat Other

Specific

Dial-A-Ride

11.

Submitting organization and address

12.

Technical contact(s) ana phone

Center for Applied Mathematics

National Bureau of Standards

Gaithersburg, MD 20399

13.

Narrative

Howard K. Hung

William G. Hall

Robert E. Chapman

(301) 921-3855

The RSDAR is a heuristic algorithm. It assigns patrons to form subtours in time

intervals, and subtours are linked to become a tour. Patrons are chosen to be

included in a subtour on the basis of the best remaining time of the base trip.

Subtours are selected to be included in a tour on the basis of the best productivity

measure.

i

I

i

14.

Keywords

Dial-a-ride; heuristic algorithm; routing; scheduling

15. Computer manufr and model 16. Computer operating system

UNIX

!

17. Programing language(s) 18. Numoer of source program statei merits FORTRAN 77 , .... Appx 14 CO

19. Computer memory requirements ] 20. Tape drives 512K Bytes

i > !

21. Disk/Drum units 22. Terminals 15 MB Winchester

Disk Drive

23. Other operational requirements

! 24. Software availability

Available Limited In-house only

S

1

25. Documentation availability

Available Inadequate In house oruy 0

26. FOR SUBMITTING ORGANIZATION USE

j

1

xas-ioi Standard Form 183 1974 July

SBS-1J4A 'REV. 2-4C) U.S. OEPT. D OF COMM.

BIBLIOGRAPHIC DATA

1. PUBLICATION OR

REPORT NO.

2. Performing Organ. Report No. 3. Publication Date

SHEET (See instructions) NBSIR 85-3178 1 JULY 1985

4. TITLE AND SUBTITLE

Paratransit Advanced Routing and Scheduling System Documentation: Routing

and Scheduling Dial-A-Ride Subsystem

5. author(S) Howard Hungj William G. Hall, Robert E. Chapman

S. PERFORMING ORGANIZATION (If joint or other than NBS, see instructions) 7. Contract/Grant No. NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

8. Type of Report & Period Covered

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street. City. State, ZIP)

U.S. Department of Transportation

Urban Mass Transportation Administration

400 7th Street S.W.

Washington, D.C. 20390

10. SUPPLEMENTARY NOTES

[~T3 Document describes a computer program; SF-185, FIPS Software Summary, is attached

11. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a si gnificant

bibliography or literature survey, mention it here)

The Advanced Routing and Scheduling System (ARSS) is a software system designed to

route and schedule patrons in a dial-a-ride environment. The system consists of

three subsystems: CONENV, a preprocessor which constructs physical and policy

environments; RSDAR, which routes and schedules patrons; and GREPOR, which generates

hard copy of all necessary reports. This report provides a description of RSDAR.

The RSDAR is a heuristic algorithm. It assigns patrons to form subtours in time

intervals, and these subtcurs are linked to become a tour.

Patrons are chosen to be included in a subtour on the basis of the best remaining

time of the base trip. Subtours are selected to be included in a tour on the basis

of the best productivity measure.

The model is written in FORTRAN and complies with the American National StandardInstitute X3. 9-1978 standard for that language.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate < ey Dial-a-ride; heuristic algorithm; routing; scheduling

words ov semicolon i)

13. AVAILABILITY

v 1 Unlimited

I j For Official Distribution. Do Not Release to NTIS

1 \ Order From Superintendent of Documents, U.S. Government Printing Office, iVash.n»:en, Z.Z. 20402.

'X Order From National Technical Information Service (NTIS), Springfield. VA. 22 1 £ •

14. NO. OF

PRINTED PACES

15. Price

S14 . 50