Preparing Networks for Routing Applications

1. Overview of the Network Model



     Readers of this paper must have a fundamental understanding

of the network model of ArcInfo.  This section is a review of

the basics for this subject.  Refer to Esri's documentation on

Network Analysis for an in-depth discussion on the concept of

a vector network data model.

  

     There are four components required in order to perform a

routing task in the ArcInfo Network module.  These elements are

termed network links, network nodes, turns, and stops.  Each of

these elements will also possess attributes required in the routing

process.  The network commands are invoked in the Arc/Plot module,

enabling certain ArcPlot commands to interact with the modeling

procedure.  



     Network links are simply the arcs one wishes to be eligible

as a potential part of a route.  The RESELECT command and its

counterparts (ASELECT, etc.) can be used to create a subset of

arcs representing the network links.  Arc attributes are used

in this procedure.  For example, only Interstate, U.S., and State

Highways may wish to be selected for determining routes for long

distance travel.  



     An arc attribute is also employed by the network model for

defining impedance values.  Impedance refers to the relative ease

or difficulty to traverse any given arc.  Routes are determined

by ArcInfo by the least possible impedance to go from one point

to another.  The attribute of LENGTH is used as a default, so

cumulative impedance of a route will represent the least possible

distance traveled.  Other attributes defining impedance may be

employed as an alternative to LENGTH.  For example, an impedance

may be desired of routes depicting the least amount of TIME for

travel.  One way to calculate an estimate of TIME for each arc

would be to divide LENGTH by an attribute of SPEED LIMITS.   



  

     Another element used in routing is the network node.  They

are simply the nodes defining endpoints of the network links (arcs).





 They depict both junctions connecting the links, as well as endpoints

representing dead-ends and cul-de-sacs.  If impedance wish to

be included at these points, they must be shown in a turntable,

which is an INFO file depicting all possible turns from one arc

to another.  The TURNTABLE command in ArcInfo will automatically

create this table, but will exclude an impedance attribute which

must be subsequently added and maintained by the user.  

  

     The last element required in routing are stops, which are

the node links representing the locations to be visited along

a desired route.  They are also stored as an INFO file.  Several

attributes are required in this file.  NODE# associates each stop

record with its respective node link location.  A route attribute

allows the user to separate stops into more than one route.  An

attribute of pick-up sequence is required to at least define the

starting and ending stops (nodes) for each route.  It can also

be used to force a route to pass through stops in a pre-determined

order.  Optionally, an impedance attribute may be included at

the stops as well as something called a transfer attribute.  Transfer

refers to an amount picked-up or dropped-off at a given stop (for

example, number of passengers).  

  

     The actual implementation of the routing process by the Network

module within ArcPlot is invoked using the PATH or TOUR commands.

 PATH is used if routes are to follow along a pre-determined sequence

of stops in an attempt to find the least impedance between each

successive stop.  TOUR will re-sequence each stop along the route

in its quest to find an overall least impedance, but the starting

and ending stops cannot be altered. 



     The results from PATH or TOUR will be a pair of INFO files.

 A route table will simply portray a record of codes representing

each route number.  A section table will contain in sequence each

arc belonging to its respective route number.  The stops file

will also be optionally updated with additional attributes that

report cumulative impedance, cumulative transfer, and in the case

of using the TOUR command, revised pick-up sequence.  



2. Preparation and Management of Critical Elements



     The routing capabilities of the Network module are potentially

very powerful.  On the other hand, its utilization in the workplace

can be limiting or misleading if the data elements,  described

in the previous section, are not adequately portrayed or maintained.

 Some pitfalls have been encountered by the GIS Division of the

City of Johnson City, Tennessee during the implementation of routing

tasks.  They will be brought out in this paper, along with solutions

to the problems.



     a) Maintaining Turntables



     The prime reason for creating a turntable in routing applications

is to include impedances at network nodes.  The creation and maintenance

of impedance values can be very difficult tasks.  How are turn

impedances assigned?  For example, there will be 16 records associated

with a four-way intersection; each network link entering the node

intersection has the possibility of turning left, right, straight,

or u-turn.  Impedances will change with varying intersection 

characteristics.  It takes a substantial effort to correctly assign 

impedance values to the massive number of turntable records.

     If the topology of the arc coverage changes at any time,

the turntable becomes obsolete.  All of the work required to assign

impedance values will be corrupted and will have to be re-entered!

 It is clear that a more elaborate strategy must be developed

to create turn impedance characteristics one time only, and revise

them as changes occur in the arc coverage.  







     The following data model was developed and is used by Johnson

City GIS to create and maintain turntables for the city street

network.  Turns are actually maintained NOT in the turntable,

but in two other attribute tables.  The turntable can then be

automatically updated from the other INFO files as changes occur

with the city street coverage.



	The first attribute table portrays all of the different types

of intersections and their impedance values.  Table I shows an

example of five cases.  The attributes include a verbal description

of each type of intersection, an intersection-id, and impedance

values (in minutes) for turning left, right, straight, or a u-turn.

 Values of -1 represent turns that are either not allowed or not

possible.

   

  

			    TABLE I

		    TURN INTERSECTION FILE



intersection-id   left   right  straight  u-turn  description



     1            0.2    0.2     0.13      -1     four-way stop

     2            0.3    0.2     0.26      -1     two-way stop

     3            0.1    0.05    0         -1     clear

     4           -1     -1      -1          0.15  cul-de-sac

     5           -1     -1       0         -1     pseudonode



	   Note: Impedance values are in minutes.





     The second attribute table is actually the AAT of the arc

coverage that will represent the network links; in this case the

STREET coverage.  Two additional attributes are placed in the

AAT: from-node intersection-id and to-node intersection-id.  Each

arc is then encoded with the id value associated with the ids

provided in the preceding INFO file that represent the intersection

types at its from-node and to-node.  



    Each time the turntable needs to be re-created, the AAT and

intersection tables can be used as relational databases to make

the appropriate revisions.  Appendix I is an AML program that

implements this revision in an automated fashion.



     b) One-way streets



     Johnson City contains several one-way streets within its

street system.  Routing models must of course disallow travel

in the wrong direction along such arcs.  The easiest way to include

these features is to have two impedance values in the AAT corresponding

to the direction of travel; i.e. going in the from node toward

the to-node and vice-versa.  An impedance of -1 is assigned to

the direction which is opposes the one-way direction.  For each

arc representing a two-way street, both the FROM-to-TO-node impedance

and the TO-to-FROM-node impedance are assigned the same value.





     c) "Two-pass" streets



     For streets possessing medians or for routing applications

such as street sweeping, such streets will require a route to

pass through twice and in opposing directions.  Significant modifications

must be made of the coverage in order to achieve this routing

requirement.  A copy of the coverage must be used, keeping the

original coverage unaltered and intact.







     Appendix II is an AML program that automates the process

of creating "two-pass" streets.  Streets are first coded using

an attribute that identifies them as requiring or not requiring

two passes.  If address matching is subsequently required for

determining stops within arcs (discussed later), then these arcs

are written to an ASCII file that identifies their full street

name and four address range values (i.e., min(from-node)-left,

max(to-node)-left, min(from-node)-right, and max(to-node)-right.

 



    This ASCII file is subsequently used by the AML in ArcEdit

to copy the appropriate arcs, assign correct negative from-to

and to-from impedances, and update address ranges.  (Positive

impedance values are initially assigned a value of zero in this

AML and are later given time impedance by another AML program.)

 The copy of a given arc representing the left side of the street

must have the address range for its right side "zeroed-out" and

vice-versa for the arc representing the right side of the street.



     Topology must also be maintained when making the two-pass

streets.  This is achieved in ArcEdit by turning the NODESNAP

ON, selecting the arc of interest, then COPYing it zero distance.



     d)  The "Stop-only-at-Nodes" Problem



     The routing programs of ArcInfo allows stops to occur only

at nodes.  Since most nodes are found at intersections, this presents

a problem with wanting stops to occurs at locations within street

segments.  This situation may be desirable when performing address

matching and is required for applications such as trash collection.

 In the case of street sweeping, the "stops" are conceptual, occurring

along the streets to be swept and not at node locations.



     This "stop-only-at-nodes" problem was solved in routing applications

implemented by Johnson City GIS through the use of several AML

programs and a Turbo Pascal program, whose overall sizes do not

allow them to be included as appendices.  The following description

provides the reader with a conceptual framework.   



     Pseudonodes were added in the middle of the arcs where stops

were required.  In the case of the trash collection application,

customer addresses were first matched, then the STATISTICS command

invoked to determine the number of customers occurring along each

street-id (street segment), then a Turbo Pascal program was written

and run to compute and create an ASCII file of the x,y coordinates

needed to split the arcs of interest.  



     A separate AML program then was used in Arc/Edit to invoke

the splitting of arcs, thus creating the pseudonodes, and creating

a stops file at these pseudonodes.  Impedance ID values were also

added to the pseudonodes, which purposefully disallows the subsequent

TOUR command to make u-turns at these locations, i.e., the routes

are forced to pass through an entire street segment, which is

now comprised of a pair of arcs separated by a pseudonode representing

a stop.  In the case of the sweeping application, the stop at

each pseudonode contains the transfer attribute of the length

of street that needs to be swept.



     When streets possess a two-pass characteristic, it is especially

important in ArcEdit to turn the NODESNAP OFF.  Otherwise, when

arcs are split the pseudonode can connect both sides of the street

instead of only one side, which is topologically incorrect.  



     e) Defining Zones for Determining Multiple Routes



     It is common for applications to require the partitioning





of stops to subsequently create a system of multiple routes. 

How can this partitioning be achieved?  ArcInfo has a spatial

allocation capability using the commands SPATIALORDER and COLLOCATE

to automatically group stops for the eventual creation of a multiple

route system.



     Unfortunately these commands were found to be inadequate

for the Johnson City routing applications due to two principal

reasons.  First, the routines do not finish defining a group until

it has reached some user-defined transfer capacity, i.e., variable

capacities are not allowed.  This inhibits the creation of a route

bounded by logical features such as major streets or clearly defined

neighborhoods.  Second, the grouping occurs according to the relationship

of stops based upon Euclidean distance instead of along network

links (arcs).  Given the irregular street network of Johnson City

imposed by its hilly terrain, it was not uncommon for the spatial

allocation to group stops whose streets were not in reality connected.

 



	Instead of a fully-automated technique offered by the network

module, a user-interactive approach can be utilized  to group

stops for creating a multiple route system.  An AML is written

with ArcEdit which allows the user to draw a polygon on-screen

around any portion of the city street network and its nodes containing

the transfer values.   A STATISTICS command is invoked which sums

the cumulative transfer within the polygon.  The user can then

proceed to accept or adjust the size of the polygon.  The final

extent is determined by the user's knowledge of the city with

regard to the complex spatial elements described in the previous

paragraph.  The nodes located within the final polygon are assigned

an unique route-id and saved in a stops file.  This allows the

subsequent PATH or TOUR command to create a separate route for

each id.



3. Conclusion



Johnson City GIS was confronted with several difficulties in developing

and implementing various route modeling applications.  Solutions

were found to these problems by modifying the basic data model

and writing computer programs to compliment existing ArcInfo

network and editing routines.  Alternative approaches may exist

to solve these problems in a more efficient manner.  The purpose

of this paper is to inform the reader of the challenges that will

be presented when attempting to model routes for real-world applications

and how they can be confronted and solved. 





			APPENDIX I

	       PROGRAM TO REVISE TURNTABLE FILE



/* REVISETURNS.AML     /jcgis1a/washington

/*  

/*  Written by GAP 2 Jun 95

/*

/*  Program to revise turntable of any transportation coverage

/*  from the coverage's AAT items of TURNSFROM and TURNSTO



&type 'Program: REVISETURNS.AML'

&type ''

&type 'AML must be run from workspace containing the transportation

coverage'

&type ''

&setvar covname [response 'Enter name of coverage']



tables

kill %covname%.trn





q



build %covname% node

build %covname% line



display 0

ae

ec %covname%

ef arc

sel all

calc %covname%-id = %covname%#

ef node

sel all

calc %covname%-id = %covname%#

q y



turntable %covname%

additem %covname%.trn %covname%.trn time_impedance 5 5 n 2



relate add

arcturn

%covname%.aat

info

arc1#

arc1#

link

ro

fromimps

/jcgis1a/washington/turnimp.ids

info

turnsfrom

id

ordered

ro

toimps

/jcgis1a/washington/turnimp.ids

info

turnsto

id

ordered

ro

[unquote ' ']



tables

sel %covname%.trn     

&type 'Transferring Impedances for U-Turns'

reselect angle = 180  /* U-Turns

calc time_impedance = arcturn//toimps//u-turn

resel node# = arcturn//fnode#

calc time_impedance = arcturn//fromimps//u-turn      



&type 'Transferring Impedances for Left Turns'

nselect

reselect angle >= 45 and angle < 180

calc time_impedance = arcturn//toimps//left

resel node# = arcturn//fnode#

calc time_impedance = arcturn//fromimps//left       



&type 'Transferring Impedances for Right Turns'

nselect

reselect angle <= -45 and angle > -180

calc time_impedance = arcturn//toimps//right

resel node# = arcturn//fnode#

calc time_impedance = arcturn//fromimps//right      



&type 'Transferring Impedances for Proceeding Straight'





nselect

reselect angle > -45 and angle < 45 

calc time_impedance = arcturn//toimps//straight

resel node# = arcturn//fnode#

calc time_impedance = arcturn//fromimps//straight



&type 'Deleting Zero Impedances'

aselect

reselect time_impedance = 0

purge

y



quit 

&type 'Done'

&return





			APPENDIX II

	UPDATE COVERAGE TO INCLUDE TWO-PASS STREETS



/* TWOPASS.AML      /jcgis5b/sanitation

/* This AML duplicates street segments that require          

    

/* trash pickup using two passes (one-way & two-way streets)



/* files: /JCGIS5B/SANITATION/TWOPASS.DAT contains data

/*     of street segments to be converted.  Each street segment

/*     consists of seven lines of data, as follows:

/*

/*    ''       street direction                         .dir

/*    ''      name of street                         .sname

/*    ''      street type                            .stype

/*         min address number 

/*                  on left side of street               .minleft

/*         max address number 

/*                  on left side of street               .maxleft

/*         min address number 

/*                  on right side of street             .minright

/*         max address number 

/*                  on right side of street             .maxright

     



&setvar .covname [response 'Enter name of road coverage']

display 0

additem %.covname%.aat %.covname%.aat blocklength 4 6 f 0

ae

ec %.covname%

ef arc

nodesnap first 1

weedtolerance 0.1

grain 0.1

 

&setvar .textfile = [OPEN /jcgis5b/sanitation/twopass.dat open$stat

-READ]

&setvar .dir = [READ %.textfile% read$stat]

&setvar .sname = [READ %.textfile% read$stat]

&setvar .stype = [READ %.textfile% read$stat]

&setvar .minleft = [READ %.textfile% read$stat]

&setvar .maxleft = [READ %.textfile% read$stat]

&setvar .minright = [READ %.textfile% read$stat]

&setvar .maxright = [READ %.textfile% read$stat]



&do &while %read$stat% = 0

  &lv .sname

  asel pd = %.dir% and name = %.sname% and type = %.stype% ~

       and ( ( lfa >= %.minleft% and lta <= %.maxleft% ) ~





	or ( rfa >= %.minright% and rta <= %.maxright% ) )

  &setvar .dir = [READ %.textfile% read$stat]

  &setvar .sname = [READ %.textfile% read$stat]

  &setvar .stype = [READ %.textfile% read$stat]

  &setvar .minleft = [READ %.textfile% read$stat]

  &setvar .maxleft = [READ %.textfile% read$stat]

  &setvar .minright = [READ %.textfile% read$stat]

  &setvar .maxright = [READ %.textfile% read$stat]

  &type ''

  &end /*do



calc blocklength = -1

copy parallel 0



calc blocklength = 0   /*alter addresses & impedances for duplicated

streets

calc lfa = 0

calc lta = 0

calc tfi = -1

resel fti = -1  /*one-way streets going opposite direction

&setvar .selnum = [show number select]

&if %.selnum% > 0 &then calc tfi = 0  



sel blocklength = -1  /*alter addresses & impedances for orig.

dupe. streets

calc blocklength = 0

calc rfa = 0

calc rta = 0

calc fti = -1

resel tfi = -1  /*one-way streets going opposite direction

&setvar .selnum = [show number select]

&if %.selnum% > 0 &then calc fti = 0



q y

&return