NATIONAL BUREAU OF STANDARDS REPORT

10 500#

SOME RECENT THEORETICAL WORK ON

ACCESSIBILITY IN TRANSPORTATION SYSTEMS

W. A. Horn

<2jb§>

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards 1 was established by an act of Congress March 3. 1901 . Today,

in addition to serving as the Nation's central measurement laboratory, the Bureau is a principal

focal point in the Federal Government for assuring maximum application of the physical and

engineering sciences to the advancement of technology in industry and commerce. To this end

the Bureau conducts research and provides central national services in four broad program

areas. These are: (1) basic measurements and standards, (2) materials measurements and

standards. (3) technological measurements and standards, and (4) transfer of technology.

The Bureau comprises the Institute for Basic Standards, the Institute for Materials Research, the

Institute for Applied Technology, the Center for Radiation Research, the Center for Computer

Sciences and Technology, and the Office for Information Programs.

THE INSTITUTE FOR BASIC STANDARDS provides the central basis within the United

States of a complete and consistent system of physical measurement; coordinates that system with measurement systems of other nations; and furnishes essential services leading to accurate and

uniform physical measurements throughout the Nation’s scientific community, industry, and commerce. The Institute consists of an Office of Measurement Services and the following technical

divisions:Applied Mathematics—Electricity—Metrology—Mechanics—Heat—Atomic and Molecular Physics—Radio Physics J—Radio Engineering -—Time and Frequency - —Astrophysics - —Cryogenics.

THE INSTITUTE FOR MATERIALS RESEARCH conducts materials research leading to im- proved methods of measurement standards, and data on the properties of well-characterized

materials needed by industry, commerce, educational institutions, and Government; develops,

produces, and distributes standard reference materials; relates the physical and chemical properties of materials to their behavior and their interaction with their environments; and provides

advisory and research services to other Government agencies. The Institute consists of an Office of Standard Reference Materials and the following divisions: Analytical Chemistry—Polymers—Metallurgy—Inorganic Materials—Physical Chemistry.

THE INSTITUTE FOR APPLIED TECHNOLOGY provides technical services to promote

the use of available technology and to facilitate technological innovation in industry and Government; cooperates with public and private organizations in the development of technological standards, and test methodologies; and provides advisory and research services for Federal, state, and local government agencies. The Institute consists of the following technical divisions and

offices: Engineering Standards-—Weights and Measures — Invention and Innovation — Vehicle Systems Research—Product Evaluation —Building Research—Instrument Shops—Measurement Engineering—Electronic Technology—Technical Analysis.

THE CENTER FOR RADIATION RESEARCH engages in research, measurement, and application of radiation to the solution of Bureau mission problems and the problems of other agencies and institutions. The Center consists of the following divisions: Reactor Radiation—Linac Radiation—Nuclear Radiation—Applied Radiation. THE CENTER FOR COMPUTER SCIENCES AND TECHNOLOGY conducts research and

provides technical services designed to aid Government agencies in the selection, acquisition, and effective use of automatic data processing equipment; and serves as the principal focus

for the development of Federal standards for automatic data processing equipment, techniques, and computer languages. The Center consists of the following offices and divisions: Information Processing Standards—Computer Information — Computer Services — Sys- tems Development—Information Processing Technology.

THE OFFICE FOR INFORMATION PROGRAMS promotes optimum dissemination and

accessibility of scientific information generated within NBS and other agencies of the Federal government; promotes the development of the National Standard Reference Data System and a system of information analysis centers dealing with the broader aspects of the National Measure- ment System, and provides appropriate services to ensure that the NBS staff has optimum accessibility to the scientific information of the world. The Office consists of the following

organizational units;

Office of Standard Reference Data—Clearinghouse for Federal Scientific and Technical Information ' —-Office of Technical Information and Publications—Library—Office of Public Information—Office of International Relations.

1 Headquarters and Laboratories at Gaithersburg, Maryland, unless otherwise noted; mailing address Washington, D.C. 20234.

- Located at Boulder. Colorado 80302.

1 Located at 5285 Port Royal Road, Springfield, Virginia 22151.
NATIONAL BUREAU OF STANDARDS REPORT

NBS PROJECT MBS REPORT

2050458 10 5000,

SOME RECENT THEORETICAL WORK ON

ACCESSIBILITY IN TRANSPORTATION SYSTEMS

W.A. Horn

Applied Math Division

Technical Report

to

Northeast Corridor Transportation Project

Department of Transportation

IMPORTANT NOTICE NATIONAL BUREAU OF STAf

for use within the Government. B and review. For this reason, the | whole or in part, is not authorize Bureau of Standards, Washington,

the Report has been specifically pr

accounting documents intended Anoroved for public release by the Ejected to additional evaluation \ T . , T , •

, *. c sting of this Report, either in Director of the National Institute ot

)ff , ce of the Director Natl0nal Standards and Technology (NIST) he Government agency for which on October 9, 201 5.

es tor Its own use

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

ERRATA, NBS REPORT 10 500

"SOME RECENT THEORETICAL WORK ON ACCESSIBILITY

IN TRANSPORTATION SYSTEMS"

Inner Title Page: DATE, December 1970

Abstract, line 2: reviewed ->• summarized

Page 15, line 3: constraints is -*• constraints, is

Page 16: INSERT between paragraphs 2 and 3 the following paragraph

The next step is to determine a set of subregions of the

given regions (each subregion being the intersection of

some subcollection of the collection of regions) , such

that the constraints will be satisfied if each such subregion

contains an access point.

Page 16, line 7 : regions - subregions

line 6": region -> subregion

line 2 : example. -> example,

Page 17, line 6: negligible

Page 25, line 4": 0

t t o

q q line 3~

: F(q°) - F(q*) F(q°) - F(q*)

FOOTNOTE : 1969 -> 1959

Page 37, No. 20, line 2: Amer. J. Math.

No. 21, line 5: Operations Research

SOME RECENT THEORETICAL WORK ON

ACCESSIBILITY IN TRANSPORTATION SYSTEMS

W.A. Horn

ABSTRACT

Four NECTP-sponsored papers, which have already been

published in some form, are reviewed in this paper. A fifth,

unpublished, work is also presented in its entirety. A rough

theoretical framework is constructed to define accessibility

in transportation systems, and unsolved problems of interest

are enumerated. A short bibliography of relevant work is also

included

.

Key words: Transportation systems, transportation networks,

weighted graphs, accessibility, minimum cover problems, location theory

TABLE OF CONTENTS

1. INTRODUCTION 1

2. A SUMMARY OF NECTP- SPONSORED PAPERS 4

2.1. OPTIMAL NETWORKS JOINING N POINTS IN THE PLANE,

by W.A. Horn 4

2.2. INTERSTATION SPACINGS FOR LINE- HAUL PASSENGER

TRANSPORTATION, by VuKan R. Vuchic 6

2.3. OPTIMUM ALLOCATION OF TRANSPORTATION TERMINALS IN

URBAN AREAS, by Barton E. Cramer ....12

2.4. MINIMUM- LENGTH COVERING BY INTERSECTING INTERVALS,

by W.A. Horn 14

3. LAYOUT OF A TRANSPORTATION NETWORK WITH DOMINANT TERMINAL

COSTS, by W.A. Horn l 6

3.1. INTRODUCTION . 16

3.2. THE PRIMARY PROBLEM: MINIMIZING THE NUMBER OF

ACCESS POINTS 18

3 . 3 . THE SECONDARY FROBLEM: NETWORK LAYOUT 23

3.4. APPENDIX : THE ONE- DIMENSI ONAL PROBLEM .29

4. SUGGESTIONS FOR FUTURE WORK. 31

5- BIBLIOGRAPHY...... 35

1 . IINTRODUCTION

In the theoretical study of transportation systems, one naturally encounters the concept of accessibility . The following

is an attempt to summarize the various pieces of research relating

to accessibility performed in support of the Northeast Corridor

Transportation Project (NECTP) during the years 1967-69. Part

of the work discussed was done at the National Bureau of Standards

(NBS), and the rest was monitored or reviewed by the staff at NBS.

This paper will begin with some general comments on the types

of mathematical problems presented by the study of accessibility,

and will then turn to a description of the specific work done.

Suggestions for further research appear next, followed by a brief

bibliography.

First we define accessibility in a way which, while somewhat

general, presages certain of the mathematical problems to be

encountered. The accessibility problem, from a mathematical point

of view, concerns the geographic placement of a transportation

system, or part of a transportation system, so as to achieve the

most convenience for the users of this system at the least cost.

The system (or part of a system) in question will be the

"track" or "road-bed" on which vehicles travel, in the case of

land vehicles, or the points of entrance to and exit from the

system in the case of all types of transportation. The goal of

maximizing user convenience while minimizing cost will give rise

to three types of mathematical problems:

a) Fixed- Budget Problem . Maximize user convenience subject

to fixed cost constraints which may not be exceeded.
b) Convenience- Constrained Problem . Devise a least-cost

system which will achieve at least some minimum amount of

convenience for each user of the system.

c) Tradeoff Problem . Find a system which minimizes some weighted combination of cost and user inconvenience.

Each of these problems may involve additional, complicating

constraints. For example problem a) may have the additional

constraint that some minimum level of convenience must be attained

for each user, although the overall objective is to maximize a total convenience measure for all users. Sometimes a problem

posed in these terms has no solution (e.g., where the prescribed

budget limit is too low to permit meeting the minimum- convenience

conditions)

.

More specifically, the following problems come to mind as having significance in the area of accessibility.

1) Determine the location of a limited number of terminals

(or access points) for a system in such a way that total time spent

in getting to the nearest terminal is minimized.

2) Same as l), but minimize total time in getting to terminal

plus time to destination.

3) Determine the number and placement of terminals so as to

require no more than a given amount of time loss to each user in

getting to the system.

4) Determine the locations of a given number of terminals

so as to minimize the greatest access time loss suffered by any user.

2 -
5) Any of problems l), 2), or 4) with a tradeoff for cost

of system.

6 ) Given a set of terminal locations, determine the

configuration of a system which minimizes construction cost.

7) Same as 6 ), but add in tradeoff factor for inconvenience

of using a given system.

8 ) Find a set of terminal locations and a configuration of

the system which minimizes some weighted sum of cost and inconvenience.

9) Same as 3).> but also determine the rest of the system,

given the placement of terminals, so as to minimize some cost/

inconvenience function.

Four of the five papers discussed in this report (and

supported by the NECTP) fall under categories l), 5 ) > l)

>

and 9)>

while a fifth is too theoretical to be readily put in a specific

category. Four of the above papers have been published already in some form and are summarized in section 2. Another paper, un- published, is presented in full in section 3 *

Section 4 contains recommendations for possible future work,

while section 5 lists the bibliography of reference cited, and

also some other literature of possible interest to one working in

the field of accessibility. For example [18], fl9]> [21] and T221

pertain to categories 1 ) and 4), [17] to category 2 ), and [201 and

[231 to category 3 ).

- 3-
2 . A SUMMARY OF NECTP- SPONSORED PAPERS

2 . 1 . OPTIMAL NETWORKS JOINING n POINTS

IN THE PLANE, by W.A. Horn

The report version of this paper was sent to D.O.T.,

and a condensed form has been published [10] in the

Proceedings of the Fourth International Symposium on the Theory

of Traffic Flow, held in the summer of 1968 in Karlsruhe, Germany.

An expanded version will be published in the NBS Journal of Research

at a later date.

The paper deals with the following problem. Given a (finite)

set of n initial points in the plane, find a network N connecting

these points which minimizes the function

f(N) = M(N) + £ \

^(P, J , i,j J 1J

where /(N) is the total length of all arcs of N , Jt(P. . ) is the

J length of some shortest path P. . in N connecting initial points

1 j

i and j , and \ and X. . are, respectively, positive and non1

J

negative parameters . With reference to the discussion of section 1 , this problem is of type 7 )? where A, represents construction cost

per unit length of arcs in the network and A, . represents the

"inconvenience" per unit length for travelers using the network from i

to j ; thus X. . is generally taken as proportional to the number

J of travelers between i and ,1 .

This paper is more theoretical than directly-applicable,

although the problem is solved completely for n=3 and a solution

algorithm is suggested for larger n, which might be feasible on a computer for values of n not much larger than 3 - However, the

main contribution of the paper is to determine characteristics of

such networks for general n. The following are the chief results

obtained.

- 4 -
1. An optimal network consists of a connected set of straight

line segments each of which is contained in the convex hull of

the original set of points ( initial nodes) and must be a part of some minimal (shortest) path P. . under any possible assignment

J of minimal paths within the optimal network.

2. The n initial nodes of an optimal network are of order

at most n-1, while all other ( auxiliary ) nodes are of order at

most n . Furthermore, every arc incident at an initial node

must carry at least one minimal path from that node to some other

initial node in any possible assignment of minimal paths within

the network.

3- The angles made by arcs at any auxiliary node are dependent

on the weights (sum of \ and of all X. . for which minimal

path P. . lies on the arc) of the arcs. Thus if the k-th arc

ij

at a given auxiliary node has weight w^ and makes an angle

with some fixed ray emanating from the auxiliary node, then we have

Vk C0S CTk

= 0 .

4. There exists an optimal network for any set of n initial

nodes, and any such optimal network contains at most

Jn(n-l) (n-2)

auxiliary nodes.

5 . The only possible optimal networks on 3 initial nodes are

of the topological type shown in Figure 1, where configuration (e)

need not be considered since its existence implies the existence

also of one of the other types as optimal.

- 5 -
(d) (e) (f)

Figure 1. Six possible optimal networks for n=3

5(a)
6. If V(k+ZA,. .) > a/2-1 , then any optimal network contains

J no nodes of order greater than 3 and. no triangles or quadrilaterals

therefore every auxiliary node is of order 3 •

Other results concerning specific configurations are given to

aid in determining the optimal networks for small n .

2.2. INTERSTATION SPACINGS FOR LINE- HAUL PASSENGER

TRANSPORTATION, by Vukan R. Vuchic

The following is a brief account of the most valuable

contributions to be found in Vuchic 's paper [14]. Some liberty

has been taken in generalizing certain of the ideas and in

modifying the solution procedure to provide what is hoped to be

a more useful approach. The paper is of type 5)*

Assumptions for the model are these: A single transportation

line is planned along a fixed route of given length, to serve customers along the line and in its surrounding area who wish to

travel to a central business district (CBD) at the end of the line.

The form of transportation used is considered to be rail, with a limited number of access points (stations). It is assumed that

all passengers ride to the end of the line (CBD) after boarding.

The population desiring to use this system is fixed, and the

density function of its geographic distribution is known. In

addition it is assumed that there is a "nearest" or "most desired"

point of access to the system for each user, such that this user

\p will enter the system at this point, ^occupied by a station, and

otherwise at one of the two station locations which are nearest

this point in either direction along the line.
[This last condition was achieved in [14] in the following way.

It was assumed that the line itself rims along the x-axis of a coordinate system, while access travel must be performed at constant

speed along roads parallel to the x- or y-axis. With total travel

time as the criterion for selection of the access point for an individual traveler, it is clear that the traveler must choose one of the two stations with x- coordinate closest to his own. For

he first travels in a y- direction to the line and then must head

toward or away from the CBD. If he travels away, it is clear

that the first station he comes to is best for access, while if

he travels toward the CBD the first station encountered must also

be the best in that direction, since otherwise one could go from

this station to some later station by means of the access road in

shorter time than by taking the train, implying the uselessness,

and hence lack of need for, this station.]
A further assumption for the model is that the average speed

of the train is not necessarily the same between different pairs

of stations, but is a monotonic increasing function of the distance

of travel between stations, which approaches the cruising speed of

the train asymptotically. This is due to acceleration- deceleration

effects at the stations. The assumption gives rise to a minimum

distance between stations tj^low which train speed is less than

access- road speed.

The objective function, to be minimized, for the above model is

the total cost for the system, consisting of a construction cost for

road bed (variable with the positioning of the first station), a cost

for stations, and a cost for total time spent by all users of the

system. This objective function is taken from Chapter IV of [14],

although the method of solution described below will be an adaptation

of the methods of Chapter III

.

Measuring distance along the proposed line, from an origin

at the end of the line farthest from the CBD, let

X-,

l

k

s

k

P

n

T

P

= distance of the first station from the origin,

= cost per unit length of line,

= cost per station.

= cost per unit of passenger time spent in travel,

= number of stations,

= total passenger time.

- 8 -
Then an appropriate objective function is

C = -kx.,+kn + kT , i 1 s p P

where the first term arises because no roadbed need be put between

0 and x on the line.

A dynamic program which is an adaptation of the recursion

formula of Chapter III of [14] will be used to solve this problem.

We assume that there are a number of locations L.,,L^, ...,L 12 m

along the line, with respective distances d^, d^, . . . , d^ from the

origin, where it is possible to locate a station. Let

IL = region in which each user has a nearest point on the line

with coordinate lying between 0 and d^ , inclusive

.

That is, if d(p) is the distance from the origin to the desired

access point for a passenger at p ,

R

i = [P :0 < d (p) ^

d

i}

*

Let

C.(i) = minimum cost for travel time and for construction

J of stations and line, for the portion of the

system from 0 to d^ and for all passengers

in IL , assuming station j is located at L_^ and all prior stations (l through j-l) are located

optimally along the strip [0,d ]

. (The "initial

condition" is C (i)=0 .

)

o

- 9 -
That is, if xn is the location of station 1 and if is the

total passenger time spent in travel up jto the point d^ by passengers

in Ih (all of whom have boarded the system by d^), assuming

station j is located at and stations 1 through j-1 are located optimally, then

C . (i ) = -kx + k j + k T'? . J X 1 s° pi

Note that C (i)

J later stations,

does not in any way depend on the location of

and hence is well defined as given.

Now let be the number of people living in R and let

t(i,k) be the time required for a train to go from a station at

to a station at . Let be the total waiting time

for all passengers in - IL to arrive at point , assuming

stations are at and L^ with none in between. Then we have

the recursion relation

cj+i

(k) q““1

fc

j

(1) + h

+ yqhi,*) + s1)k ])

It should be noted at this point that the quantity S. will in

i, K

general involve some assumption as to how the residents in R^-R^

would choose between the stations at and for access to

the system. It will be assumed that this choice depends only on

the values of i and k , as is the case in Chapter III of [1^] , where minimum time to arrive at a station is the sole criterion

for each user.

The total cost for n stations, the last of which is located

at the CBD (also designated L ), is then

C = C (m) . n' '

10 -
Of course , if n is not fixed then we look for an n which

minimizes C (m) . n'

Some of the calculations in the recursion step may be omitted

by stipulating , for example, a minimum distance between successive

stations

.

It seems that the above method should prove feasible for

solving problems of reasonable size on the computer.

Finally, it should be noted that Vuchic found, using a uniformly

distributed population and objective function based on waiting time

only, that station spacing should increase as one nears the CBD.

This corresponds to what seems logical, because of the increasing

number of riders as the train progresses.

11
2.3 OPTIMUM ALLOCATION OF TRANSPORTATION

TERMINALS IN URBAN AREAS

by Barton E. Cramer

The following problem is considered in this paper [A]. Given

a city which is circular in shape, and given the number of terminals

for a transportation network which is to serve the city, place

these terminals so as to minimize total access time between users and nearest terminals. This is of type l) of section 1.

The assumption is made that, in the circular city, population

density is a function only of distance from the center, as is also

speed of travel, which increases monotonically with distance from

the center, approaching asymptotically some fixed value. Furthermore,

the only configurations of terminals allowed are the following:

a possible terminal at the center plus one or two concentric rings

of equally spaced terminals. In the event that two rings of

terminals are considered, the outer ring is assumed to contain the

same number of terminals as the inner ring, spaced angularly between

them. That is, if the terminals of the inner ring are placed at

angles 0, 0, 20, . .

. , (n-l) 0, then the terminals of the outer ring

have angular coordinates 0/2, 30/2, 50/2, . .

• , (2n-l)0/2 .

Computer results are derived in this paper, but their possible

significance is nullified by errors in the underlying algebra. Thus

we must evaluate the paper on its approach to the problem rather than

its results, perhaps a more appropriate criterion for this type of

paper (a master's thesis) anyway.

Probably the greatest merit of the approach taken lies in the

fact that, because of the restricted nature of possible solutions,

it should not be too difficult to obtain a computer optimization

12 -
of the problem. If the assumptions about population density and

travel speed are reasonably accurate, it might happen that the

answer obtained in this way would compare favorably with that

obtained by more elaborate methods. On the other hand, there

may be other models of a similar order of complexity which yield

more practical solutions, such as a model which presents a limited

number of choices for terminal sites and chooses an optimum subset

of these for the actual locations. Such a model could also condider

the finer points of locating a set of terminals in a real-life

siutation (such as real estate cost, neighborhood opposition or approval, etc.), while retaining the advantages of a restricted

set from which to select terminals.

13 -
2.L MINIMUM- LENGTH COVERING BY INTERSECTING

INTERVALS, by W.A. Horn

This paper was published [9 ] in the NBS Journal of Research

and so it will be merely summarized here. Because of its theoretical

nature it cannot easily be placed in one of the nice categories

of section 1, although ^as discussed in [9])it arose from a problem

of type 6), namely that of finding a shortest- length network of

"vertical" and "horizontal" lines connecting a set of points

consisting of several well- separated "clusters", each on a vertical

line. The problem considered is the following. Given a sequence

[Ipjp of intervals on the real axis, find a sequence [Jpjp of

closed intervals which minimizes the sum of lengths

subject to the constraints

Ip c J

± (i=l,2, . . .,n) ,

Jb H Jp+q ^ ^ (i=l, 2, . .

. ,n-l) .

An algorithm which provides an optimal solution is the following.

Set J-. = I, . Given fj.}^ , J. , is found as follows:

1 1

1 j

J l l+l

(a) If 1 n l+i * * , set J

i+1 I i+1

(b) If max J . < min

l I i+1 , set

J

i+i = [max Jp ,max I i+1 ]

.

fc) If max l+i < min J.

l

, set

min J. 1 . J 1 J 1+i

= C“n H+i'
The paper also notes that the problem

min S = r

n a

i |J.

|

, (a. > 0)

subject to the previous constraints is easily solvable by a linear

program whose variables are the endpoints of the . Thus if

J1 = [A , B ] , and I = [a^,b_^] , the problem becomes

min S = y

U^

a. (B.-A. ) i i 1

subject to

A. < a. . B. > b. (i=l,2. . .

. ,n) , i — 1

3 x—i

A. < B.,, , B. > A. , (i=l,2, . . .,n-l) . l — l+l ’ l — l+l v 7 ’

- 15 -
3- LAYOUT OF A TRANSPORTATION NETWORK WITH DOMINANT

TERMINAL COSTS by W.A. Horn

3-1 INTRODUCTION

The problem of planning both the layout of a transportation

network, and the locations of its access points, is complicated

by the need to look at both factors simultaneously . This paper

considers the problem under a basic assumption which permits a simplifying sequential treatment. The assumption is that the

"per access point" portion of total variable system cost is so dominant, that the first consideration is to minimize the number

of access points.

This minimization must, of course, be subject to constraints

which ensure adequate access to the network. Such constraints will

be expressed, below, by specifying a list of (overlapping) regions,

each of which is required to have at least one access point located

within it. These regions might be defined in terms of lying "close

enough" to some population concentration to be serviced by the

system, but are open to other interpretations.

Once a set of regions has been determined, the remaining

secondary problem is to locate specific points (one per region)

and connect these points by a transportation network so as to

minimize the total cost of such a network. This cost might be

idealized as proportional to the length of the network or, for

example, might also include a component based on the expected

use of the network between points.

16
The topological configuration of such a network assumed for

this paper is that of a single path consisting of straight line

segment between access points, starting at one such point and

passing through all other access points to end at some final access

point. In using this topology, we are, in effect, assuming that

the cost of the network itself is neigligible compared to transportation

costs, so that it is always economical to install a direct path

between two adjoining access points in a given ordering.

On the other hand, one might make the assumption that only the

length of the network is important, thereby giving rise to a Steiner-minimal-tree problem. (This is the problem of 2.1, with all

A =0.) A more complex alternative gives weights to both the

ij

length of the network and the lengths of individual paths between

points. This problem is much more complex, and is related to, but

not the same as, the general problem of 2.1.

The mathematical procedure described leads naturally to a computer program for solving both the primary and secondary problems

in a reasonable computation time. The particular methods outlined

are in fact of an essentially brute- force type, but this should not

be troublesome in the context of likely applications, involving a relatively small number of constraint regions (perhaps about 20

)

and thus a small minimized number of access points (hopefully, only

5 to 10 ) . Trial computations should be helpful in indicating the

problem sizes for which the proposed method becomes ineffectual

and more powerful procedures must be sought.

17
3.2. THE PRIMARY PROBLEM: MINIMI ZING THE NUMBER OF ACCESS POINTS

The mathematical formulation of this problem is as follows.

Given a collection {R^}^ °f n regions in the plane, find, sets

P = fp(j)j of points in the plane, containing as few points as possible, such that each R^ contains at least one p(j) . The

R^ , which need not be disjoint, correspond to the regions to be

served; the p ( j

)

represent the access points.

The problem can be translated into an equivalent purely

combinatorial form. For this purpose, let N^ denote the set

[1,2, ...,nj of integers, and let £ denote the family of all

subsets of N of the form

n

S = fieN :xeR.

}

(x eij n

R. )

• x ' n i

J u

q i'

Note that T. is necessarily finite, and is a cover of N^ in the sense that UE = N^ . The problem of finding a minimum set P of access points will now be shown equivalent to the minimum cover problem of finding among those subfamilies £ of £ which, like

o E , are covers of N^ , a subfamily with as few members as possible.

First, consider any P = (p(j)

jTM such that each R^ contains

at least one p(j) • This last condition is equivalent to the

assertion that the subfamily f S

p (j)} p

of £ is a cover of N

n

> and hence a candidate to solve the minimum cover problem.

On the other hand, any subfamily T. of £ can be written

o in the form

,m S

o = fSp(j) } l .

for some set of points [p(j)} p

in (j nR

i ,

- 18 -
and requiring Z to be a cover of is equivalent to

requiring that each Ft contain at least one p(j) .

Therefore, the set of all minimum covers ZQ a F gives rise

to all minimum sets P = fp(j)

}

of access points, and conversely.

The minimum cover problem is a well known and difficult topic

in combinatorial optimization. Sophisticated solution methods

have been developed for larger problems ([6], [13]). For present

purposes, however, it seems simplest to recall (proof to follow)

that minimum cover problems are a special case of integer linear

programming problems, and to rely upon the methods [1] developed

for the latter broader class of problems. Whatever method is

employed, the following two elementary devices for preliminary

simplification may prove helpful. To describe them, we suppose an k K enumeration {S of £ is at hand:

k i (a) If two members of £ , S and S

d

, are such that

k i k

S c , then S can be discarded without prejudice to the goal

of finding a solution to the minimum cover problem. (This may

however affect the secondary problem, as will be discussed later.)

(b) There may be "clusters" of regions Ih which are disjoint from all other regionsj in this case the problem admits

a corresponding decomposition. Specifically, suppose there is a partition

p = fT ] m

of the set of integers N , 1 u

J n where

i e Tu , jeT^ , u f v

implies that R. and R. are disjoint in the plane. Then it is

1 J

}£ not hard to show that any minimum cover £ = fS } can be partitioned

into a set of subsets {£^} of £ i n suc^- a way that £^ is a

minimum cover for T . Conversely any solutions to the minimum

cover problem for the subsets T

u can be amalgamated to yield a solution to the original problem.

19 -
The reformulation of the minimum-cover problem involving N

. 1c K

n and as an integer linear programming problem goes as

follows. Let f x ) be a set of 0-1 variables corresponding to

the sets S in y , with the interpretation that x = 1 if S

K

is part of a solution (minimum cover) and x. =0 otherwise. Let

(a t1 ) be an nXK matrix defined by a. =1 if igS and

ik' ik

a = 0 otherwise. Then the requirement of covering is

expressed by the constraints

(i=l,2, . . .,n) ( 1 )

while the desire for a minimum cover is expressed by the objective

minimize (2)

This integer linear program can be solved by whatever method

is implemented in a conveniently available computer code. Such a method might be of the "cutting- plane" type, an extension to

procedures for solving continuous- variable linear programs, or might be of the "branch and bound" variety, here involving implicit

enumeration of all covers contained in r together with tests

which eliminate more and more alternatives from full examination as the search for a minimum proceeds. It should be noted, however,

that all of these methods aim mainly at finding one optimal solution,

whereas for use with the secondary problem we should prefer to find

all such optima or at least a reasonable sample of them. Thus

some addition to or modification of a standard method seems to be

called for.

If the problem is small enough (as we assume here), then the following

brute- force recursive procedure is useful for finding all minimum

covers. Consider a row of the matrix (a.., ) which has the least

ik

number of non- zero a., . If this number is 1, then clearly that

ik

x, = 1 for which a., = 1 , since otherwise constraint (l) is not

k ik

20
satisfied for row i . If the non- zero a., total more than 1, ik ' choose some a^ = 1 and set the corresponding x^ = 1 . Now

eliminate column k and all rows i such that a., = 1 . jk

Solve this subproblem by a repetition of the above methods

and combine a solution of the subproblem with x = 1 . This

gives a minimum cover over the subset of all covers including . Thus the final step in the procedure is to choose all k such that

a^ = 1 and such that a cover containing S which is minimum

for all such covers is minimum over the class of all covers (including those not containing S

k

) . This procedure produces

all minimum covers.

Before ending this discussion of the primary problem (finding

a minimum set of access points), two more topics require treatment.

First , we have not as yet described a good practical way to find

the family F from the given set of planar regions. Two

approaches seem plausible here. In the first, a grid of points x

is superimposed on the area under consideration. For each

point x in turn, the set is determined, and is added to the

list of F-members if it duplicates no current member of that list,

(if it is a proper subset of some current member, it might also be

discarded, in view of the simplification step (a) noted earlier.)

For an alternative approach, define a subset S of N^ to be

allowable if

fl {R.:ieS} ^ j> ,

and to be maximal if it is allowable but adding any element of N^-

S

to it destroys allowability. Then one might seek to generate all

maximal subsets of N : these will not constitute all of y , but

n the missing members would be eliminable by simplification step (a)

anyhow

.

21
Second, some justification should be given for the repeated

suggestion that the primary problem is only of moderate size,

hence tractable to solution methods of a relatively brute- force

hind. There are two parameters which roughly indicate the computational

complexity of a minimum- cover problem. One is the size of the set

to be covered; here that set is N , of size n , and we have

already indicated n = 20 as an anticipated typical value. The

other is the size of the family £ from which the minimum cover

is to be chosen. To estimate this parameter, assume n = 20.

The maximum number of sets intersecting any given set will

vary, of course, with the size and shape of the Ph . However,

the number 5 as an average does not seem too far off for reasonable

shapes and sizes. Thus for getting a rather rough estimate of the

number of S^'s , we assume that each Ft intersects exactly 5 other R. ' s . l

In this case, there will be

containing any given igN

n

5°q

If we count the

S ’ s of cardinality q

+ 1

S ' s by considering

each igN and its associated

n S 's k then each S of cardinality

q + 1 will be counted q + 1 times. Since there are (presumably)

20 such i , our total number of S, is

k

5 20 Z ( C )/(q+l) = 210 . q=o

^ yThis gives a rough idea of the number of S for a reasonable size

K. problem and hence indicates the difficulty with an integer program

solution.

As a final remark, we note that the problem admits an easy

solution in one dimension. This is given in the Appendix, 3*^*

Considering a given problem to be one- dimensi onal might be a realistic simplification, for example, if one is dealing with a corridor- shaped area in which the R_^ are as wide, or almost as wide, as the area itself.

22 -
3-3 THE SECONDARY PROBLEM: NETWORK LAYOUT

The approach described in the preceding section provides

us with solutions = {S.}!^ of the minimum cover problem.

To each there corresponds the region

C. = n {R.tieS^}

in the plane. Any choice of points p(j)sC. leads to a minimal

in ^ set P = fp(j)}-, which meets every R^ .

Thus for the secondary problem, we assume given a collection

of disjoint sets • F°r the methods of this section, each

C . will be assumed to be a convex polygon; this will automatically

J be true if all R. '

s

were such polygons, but otherwise C. will

J be approximated by a polygon contained in, and having vertices

on the boundary of, the original C . We are to find an ordering

d of the C.'s , and points p(j)eC. , so as to minimize some function

J J dependent both on the ordering and on the sum of distances between

p(j)'s adjacent in the ordering. This function is intended to

\ express costs for connecting the set of points p(j) in the given

order. If an ordering is represented by a permutation n of

[1,2, ...,m} , where is to be the j-th member of the ordering

then the function to be minimized takes the form

f(ff) = g(«) + I

x"

lh

3t (j)jt (j +i)( |pU(j +1 )) ' P(«( J ) ) I ) ;

where ) p- p

j denotes the distance between points p and p' .

Our approach to this problem, too, is essentially a brute

force technique. It consists of optimizing the placements

p(j)eC separately for each permutation jt , and then comparing

d the resulting minimum values to find the best rc . Since the number

23 -
of permutations n is (mi)/2 (the factor 1/2 being present because

reversing the ordering yields the same solution), this method depends

for its practicality on the minimized number (m) of access points

being fairly small. On the other hand, for the roughly linear

configuration of a Corridor- type area, relatively few of the possible

permutations n will represent plausible candidates corresponding

to reasonable network configurations.

For a given permutation jt , let

h

j \(i)«(3+l) ’ q

J = p(,t(j)) ' A

j - C*(j)

•

Then the problem to be solved is that of choosing

to minimize

'(»> - ^VlwaJ)

subject to q.gA. for j = 1,2, ...,m

J J

Since tm(x) represents the cost associated with a link of

length x between polygons A. and A, , it is reasonable to

J J J- assume that each function h. is monotone increasing. We shall

J also assume it convex and continuously differentiable. This

implies that F(q) is also convex, since if q' and q" are any two values of q , if i < j m > and-

^ a ' an<^ a " are

non- negative numbers summing to unity, then

* hjb a '(4'

J+1-qp + a "(^'+1-<lj

, )l)

- a

' h

j

(,<1ll' <1j

l) + a

”h

j

(

l 9j+l' 9

j

l) •

2k -
The convexity of F(q) can be used to justify the following

solution method by cyclic minimization. The variables q. are

estimate

considered in cyclic order. At the t-th stage, one has a current

q^^ of the solution. If q. is the distinguished

J variable at this stage, then hold all other variables fq :J^j]

( ) (t,) ^ q^ ' in q

v

' , so that F(q) becomes a

J fixed at their values

function of q . alone; find q.eA. to minimize this function,

(t+i) „(t) J J form q from q by changing the j-th coordinate to q. and proceed to the next stage.

That this process converges to some point q can be proved

by an appropriate modification of a known method

+ for the case in

which variables q. are one- dimensional rather than two-dimensional.

J

( t ) The basic idea of the argument is that the sequence F(q' ) is non- increasing and bounded from below, and therefore has a limit.

By the compactness of the region in which q varies, the sequence

(t) * / q has at least one limit point q for which F(q ) is the

ft) * limit of F(qv )

. It is only necessary to show that q gives

the minimum for F(q) , as will now be done.

, 0\ / ^ \ O

Suppose, to the contrary, that F(q ) < F(q ) where q is a point with all q.eA.

J J Then convexity implies that for 0 < t < 1 ,

F(t° + (l-t)q ) < tF(q°) + (l-t)F(q ) ,

which implies that

rF(q*+t(q°-q*)) - F(q*)]/t < F(q°) _

P(q*) < 0

Since each function h. is continuously differentiable, F is also.

J

+ D'Esopo, D., "A Convex Programming Procedure", Naval Research

Logistics Quarterly, vol. 6, no. 1, March, 1969* PP» 33- ^2.

25 -
(gradjF) • (q°-q*) < F(q°) - F(q*) < 0

-#

/ o *\ where the gradients are evaluated at a point q + 0 t(q -q ) with 0 < 0 < 1 . Since the gradients are continuous, we can let t

-—^(0 ) and conclude that the inequality also holds with

the gradients evaluated at q . Thus for at least one j ,

(gradjF) *

• (q?-q*) < 0 ,

so that F can be decreased bv keenins all variables fn !,l^il

But then q is not stable under the cyclic minimization

process, and so could not arise as the limit of this process,

contrary to hypothesis.

The preceding argument shows that the cyclic minimization

method is theoretically adequate to solve our minimization problem.

What makes it especially attractive here is that the sequence of

two-dimensional minimization problems, to which it reduces the

original problem, is of a special form facilitating solution. Let

q. be the distinguished variable at the t-th stage.

J

If j = 1 , then the minimizing q^ = q|^

+^^ should clearly

be chosen as a point on the boundary of polygon which is

closest to q^^ > similarly if j = m , then q^ = q^

t+^ should

be chosen as a point on the boundary of polygon A which is

( t ) m

closest to q^

J

, Suppose now that 1 < j < m , so that

(t+1) chosen to minimize

26 -
If the line segment joining q

v

. and q(^ meets A , — J f j

then q. should clearly be chosen on the segment If ' fj A. , J J since any other choice in A. could be replaced by its projection

(t) 3 on In 7 with a reduction in the arguments of both h, , and h,

(t) (t) J" 1 J in G

v (q )

. For the same reason, if In ; does not meet A

_ J J then q. must be sought on those boundary segments of A. which

J

( t ) 3 face" L . Thus in any case, the two-dimensional minimization

problem arising at the t-th stage reduces to one or more one- dimensional

problems, with range either l/^ HA. or a boundary segment of A. . J J

The calculations described so far, it will be recalled, are to be performed for each permutation xt of [1,2, ...,m} , or at

least for all rc corresponding to "reasonable" network configurations.

We might refer to such a set of calculations (over all reasonable n) as a single secondary computation . Such a secondary computation,

however, should in principle be carried out for each solution

°f the primary problem. Thus either there must not

be too many such sets, or else the "principle" must be compromised

and the process carried out only for a subset of the primary problem's

/ solutions

.

It should be noted at this point that the solution method for

the primary problem, given in Section 2, may not be capable of

yielding all minimum covers y This is because of the reduction

step (a), which eliminates a member S if it is a proper subset

K. of some S ey . While such a deletion is useful in searching for a

SL single minimum cover, it certainly rules out discovering those

minimum covers which include S.k Such minimum covers may in fact

exist, and if so it would really have been better for the secondary

problem to have S, rather than S at hand, since this would

leave one free to locate an access point anywhere in the larger set

fl [R. :ieS, j rather than the smaller fj [R. :ieS ) . 1 i k

J 1 l i

27 -
This complication may present a real difficulty. One could

keep track of all applications of the reduction step, then go back

after a minimum cover is found and consider the effects of "undoing"

each of them, but this could prove quite complex unless the number

of applications was small. One could omit use of the reduction

step, but then the size of the minimum- cover problem might grow

considerably. A third possibility begins with using the reduction

step to arrive at a single minimum cover. Knowing the number m

of members in this cover, one would then try without use of the

reduction step to find all other covers with exactly m members.

28 -
3-4. APPENDIX. THE ONE- DIMENSIONAL PROBLEM

We consider here a simpler version of the problem discussed

in 3.2, above, -where the R are closed, finite intervals on the real line. It is again desired to find a point set P = (p(j)}

of minimum cardinality which meets every one of the R. . The problem

is easily solved in one dimension.

'The first step in the solution of this problem is to eliminate

all sets R^ such that there exists , k ^ i , with R^ cz R^ • For if p(j)eR^ then p(j)eR^ , so that a solution to the reduced

problem is a solution of the original. The elimination of all

such R. then leaves us with a linear set of R. , in the sense that if R. = [a.,b. ] and R, = fa, ,b, 1 , then either a. < a, l

L l l

J k

L k' k

J lk

and b. < b, or a. > a, and b. > b,

i k i k i k

Thus the R_^ may be

renumbered so that a„ < a^ < ... < a and b, < b^ < ... < b n 1 n where R. = fa. ,b.

]

i

L i l

J

The second step in the solution is to apply a recursive

algorithm for locating p(j) . The recursion step is now given.

ALGORITHM. Given an ordered set as described above, the

following procedure locates the p(j) optimally. Let p(l) = b^ . Eliminate from [Rj_}p aH R^ for which p(l)eR • Repeat the

procedure on the reduced set

.

THEOREM. The above algorithm produces a minimal- cardinality set P .

PROOF. The proof is by induction on n , the number of R^ . Since the proof is obvious for n = 1 , we prove it for general n , assuming its truth for values 1,2,3> • • *,n-l.

29 -
Given a set fR^}^ an^ a feasible set P = fp(j)j , there

must be at least one p(j)eR^ • Pick one such point and, relabeling

if necessary, call it p(l) . If P is optimal, then the set

P' formed by replacing p(l) with b^ , if p(l) ^ b^ , is also

optimal. For P' is feasible, since if p(l)efh for any i then

b^eR^ , by the linear ordering of the Ih . Also |P| = | P

'

I

. Thus there exists an optimal P for which p(l) = b^ .

The proof then follows from the induction step by noting

that P - {p(l)} is a minimum cover for the set

{R.:p(l) £ R.} ,

a set of cardinality less than n .
4. SUGGESTIONS FOR FUTURE WORK

The mathematical problems which arise in large geometrical

positioning problems, such as those occurring in the papers

presented in subsection 2.1 and section 3> have not been solved

by any simple and/or quick mathematical methods. In general,

one must look to heuristic, or partially heuristic methods in

order to come up with near- optimal solutions to such problems.

Therefore any research which facilitates the solution of such

theoretical problems, especially when of a large size, would

have applications to many practical situations.

Some, but not all, of the problems which come to mind for

further effort in this respect are the following.

1. Traveling Salesman Problem. Given a set of n points

{p^.j with a matrix D = {d.^ ^ } of distances between

point pairs, find an ordering of the p to minimize

i£

[dj_j : Pj_ immediately follows in the ordering} .

(See [2] for more information on this problem.)

2. Given a set {p.} of points in the plane, find a

J finite set S of points, of a given cardinality,

so that

Ubd(pr

s) (a. > 0)

J

is minimized, where d(p.,S) is the minimum distance

d from p. to S • (See for example ["16"!.)

J

- 31 -
3.

Given a matrix A = [a_J of O's and l's , find a 0-1 integer solution vector X to

the problem

min I X |

subject to

AX > B ,

where J X J is the sum of the components of X , and

B = (1,1,1, ... ,l) . (This is the problem of section 3*)

(See [6] .

)

4.

Same as 3> above, but A is now restricted merely to

have non- negative entries, as is also B , and the

objective is to

min CX

where C is also non- negative . (See [1].)

5. The problem of 2.4 for more general sets (than line segments).

6. More results on the network layout problem of 2.1, in

the form stated.

7 . A variation of 2.1 in which the Manhattan metric is used

(i.e., distance between any two points (x,y) and (z,w)

is given by |x-zj+|y-w|) .

- 32 -
8. The following variation of 2.1. Given a network N in

the plane and a set of n points S , construct a new connected network W containing N and S which

minimizes the sum

W(N'-N) + S. X..l( P. .) ,

T - 1

where ,>0,l is the length function,

i J and P is a shortest path between the i-th and j-th

1

J

points of S in N’ .

OR construct a new network N’ containing S which

minimizes the sum

M(r-N) + V(MN) + S. 1, ,i(P, .) , lj

where X' > 0 , in addition to the above conditions.

9- "Build" a network of the type in 2.1, one stage at a

time, possibly starting from a given network, so that

the sum V(NtK

is minimized, where N, is the network in its t-th

stage, d^ is a discount factor, and f is some function of the network such as that given in 6,7, or

8, above. Constraints would be consistent with the

particular problem.

10. Any of the above problems with more complex or general

objective functions or constraints.

- 33 “
The above problems represent only a few of the mathematically

difficult situations occurring in the study of accessibility. We

may also mention some practical problems worthy of study.

1. A better determination of the connection between ready

accessibility of the system to the user and the level

of patronage.

2. Better data collection methods to use when the mathematical

problems have been solved.

3- Better ways of allocating costs to projects and a more realistic determination of benefits (from a governmental

point of view) than the somewhat intractable concept of

"utility".

- 3l -

5 . BIBLIOGRAPHY

The following is a list, by no means exhaustive, of

references which might be of value to one desiring to explore

further the field of accessibility. Many of the references will

contain references of their own, which will then lead an interested

party to a widening knowledge of previous work in the field.

[1]

Balinski, M.L., "Integer Programming : Methods, Uses, Computation,

Management Sci , vol. 12, #13* 1965? pp* 253-313*

[2] Bellmore, N., and G.L. Nemhauser, "The Traveling Salesman

Problem: A Survey", Operations Research , vol. 16, /3 , May- June, 1968, pp. 538-558.

[3] Cooper, Leon, "Solutions of Generalized Locational Equilibrium

Models", J. Reg. Sci . (U.S.), vol. 7> /l, Summer 1967 , pp.l-l8 .

f4] Cramer, Barton E., "Optimum Allocation of Transportation

Terminals in Urban Areas", MIT Research Rpt. R66-60,

Clearinghouse No. PB 173684.

[5] Czamanski, Stanislaw, "Effects of Public Investments on Urban Land Values", J. Amer . Inst . of Planners , vol. 32,

ffk, July, 1966, pp. 204- 217.

[6] Edmonds, Jack, "Covers and Packings in a Family of Sets",

Bull . Amer. Math. Soc . , vol. 68, 1962, pp. 494-499*

f7] Hogg, Jane M., "The Siting of Fire Stations", Operational

Research Quart. (U.K.), vol. 19, #3, Sept., 1968, pp. 275- 289 .

‘ 35 '
[8 ] Holroyd, E.M., "Polar and Rectangular Road Networks for Cities",

Trans. Scl . , vol. 3, #L, Feb., 1969 , p. 86 .

[9] Horn, W.A., "Minimum- Length Covering by Intersecting Intervals",

J. Res . of the Nat. Bur. of Standards, vol. 73B, /l,

Jan. -Mar., 1969 , pp.49-51*

[10] Horn, W.A., "Optimal Networks Joining n Points in the Plane",

Strassenbau und Strassenverkehrstechnik, 1969 , vol. 86, pp. 160- 166.

[11] Kansky, Karel J., "Travel Patterns of Urban Residents",

Trans . Sci . , vol. 1, #4, Nov., 1967 , pp.26l-285»

[12] Miller, Alan J., "On Spiral Networks", Trans Sci . , vol. 1,

/2, May, 1967 , pp. 109- 125-

[13] Ray- Chadhuri , D., "An Algorithm for a Minimum Cover of an Abstract Complex", Canad. J. Math. , vol. 15 , 1963 , pp.11-24.

[14] Vuchic, Vukan R«, Xnterstation Spacings for Line Haul Passenger

Transportation", Graduate Report, Inst, of Transportation and

Traffic Engineering, University of California, Berkeley(l966)

.

[15] Webb, M.H., "Cost Functions in the Location of Depots for

Multiple- Delivery Journeys", Op. Res . Quart . (U.K.), vol. 19,

Sept., 1968, pp. 311- 321.

- 36 -
ri6l L. Cooper, "Location- Allocation Problems", Operations

Research, vol. 11, No. 3 , May- June, 1963 * pp. 331-3^3*

Also "Heuristic Methods for Location- Allocation Problems",

SIAM Review , vol. 6, No.l, January, 1964, pp. 37-53-

[171 Goldman, A. J., "Optimal Locations for Centers in Networks", prans. Sci. vol. 3> No. 4, Nov., 1969, pp. 352-

360 .

[18] Hakimi, S. L., "Optimum Locations of Switching Centers

and the Absolute Centers and Medians of a Graph", Operations

Research, vol. 12, No. 3 , May- June, 1964, pp. 450-459* Also

"Optimal Distribution of Switching Centers in a Communication

Network and Some Related Graph Theoretic Problems," Operations

Research, vol. 13 , No. 3 , May- June, 1965 * PP* 462-475*

T19] Levy, Joseph, "An Extended Theorem for Location on a Network",

Operational Research Quart . (U.K.), vol. 18, No. 4, Dec., 1967 , PP* 433-^2.

[20] Kerschner, Richard, "Ergodic Curves and the Ergodic Function,"

Amer. J. Math, vol. 62, No. 2, April, 1940, pp. 325-3^5*

521] Rosenthal, M. R., "The Weighted 1-Center Problem", Operations

Research, vol. l6 . Supplement 2, Fall 1968 , p. B-264 (Abstract).

Also Rosenthal, M. R. and Smith, S. B., "Solution of the 1-

Center Problem, the M- Center Problem, and the Location- Allocation Problem", Operations Research, vol. 15, Supplement 2,

Spring 1967 , p* B-66 (Abstract).

[221 Singer, Sidney, "Multi- Center and Multi- Medians of a Graph

with an Application to Optimal Warehouse Location," Operations

Research, vol. 16, Supplement 1, Spring 1968, p. B-87 (Abstract).

- 37-
[-231 Zahn, C. To, "Black Box Maximization of Circular Coverage",

J. Res . Nat. Bureau of Standards , vol. 66b, No.t, Oct. -Dec.,

1962, pp. 181-216.

USC OMM-NBS-DC

- 38-

!Jf1