Distance, Direction and Spatial Allocation

Scope
Developing network measurements / solutions with geocoded vector data in a GIS environment.

Software
ESRI ArcView GIS v3.2, Win32
Network Analyst Extension

Data Inputs

Region of Interest	City of Kanata, Ontario, Canada
Projection	UTM, zone 18, NAD 83, units meters
Coverage Data	kan_comcent Community centers
	kan_facility Facilities
	kan_fire Fire stations
	kan_police Police stations
	kan_roads2 Geocoded street network
	kan_schools Schools
	kan_water Water feature boundaries
	kan_roads Street network curb edges of roads
	kan_plybldgs Houses / other buildings
	kan_veg Vegetation
	dem_aoi Area of interest

Geocoded coverages
Coverage kan_roads2 contains the from/to nodal information, which defines the networked coverage. Distance is the default cost variable, in metres.

Distance Principles
There are many ways to define the distance between two points; the most intuitive and common definition is Euclidean distance: the straight-line distance, or as the crow flies (Euclid: fl. 370 B.C.E.).

Mathematically, we compute the differences along each axis, sum the squares of the differences, and take the square root of that sum. For two-dimensional surfaces, this is the familiar Pythagorean theorem:

d = sqrt((x1 - x0)^2 + (y1 -  y0)^2)

Another distance metric is the Manhattan distance, reflecting a rigid rectangular grid on which most of Manhattan's streets are arranged.

As far as how these two algorithms compare, good New York City cabbies think Manhattan distance. Helicopter pilots think Euclidean.

Study Area

Euclidean Distance

This was used to display distances from kan_fire to all elementary schools in the study area. Figure 1 displays a procedural flowchart:

Figure 1 - Flowchart to derive Euclidean Distance from shapefile tables

As a result, a 'distance' field is added to each record of kan_schools. Table 1 illustrates table of the results:

Table 1: Table of Distances from Kanata Fire Station to Area Schools lay loams

School Name	Distance(m)
Castlefrank Elementary School	3010.917
Earl Of March Secondary	745.230
Frederick Banting Alt. School	1015.592
Georges Vanier Catholic School	613.192
Holy Redeemer Catholic School	2854.493
Holy Trinity Inter & H.S.	2491.003
Katimavik Elementary School	2431.783
Roger St. Denis (Ecole)	2517.152
Roland Michener Public School	571.261
Stephen Leacock School	634.966
W. Erskine Johnston Public School	751.424

Distance Matrices

To determine the distances between all schools, a duplicate theme was created for kan_schools. The ESRI-supplied calcdist.ave was loaded, compiled and run against selected points from the original and duplicated kan_schools, with 'name' as the field identifier.

Table 2 illustrates the Euclidean distance matrix of all elementary schools to one another.

Considerations on Euclidean Distance

The previous operations represent Euclidean distance principles. This algorithm is questionable on the nature of the landscape, i.e.:

• What is the probability of accessibility to each school from the fire station with these distance measurements in mind?
• What implications do different barriers make (buildings, bodies of water)?
• What possible errors can occur if surrounding features to the right or left are not considered?

Enter Network / Routing Analysis

Using geographic networks, problems of distance can be solved more efficiently. Bus / transportation routing systems are a popular application using ArcView's Network Analyst.

An integral part of network analysis is that of shortest path, cheapest or most reliable path between one or more points in a network.

Dijkstra

Edsger Dijkstra, a great contributor in the realm of computational mathematics, provides his shortest path algorithm, which has been widely accepted and utilized.

The main idea of Dijkstra's algorithm is to keeping track of costs, parent node and visited nodes.

• Find cheapest path not utilized
• Record from/to information
• Update costs to node

Closest Facility

This function was used to find the closest school to 20 Windeyer Cr., Georges Vanier Catholic School. Layout 1 shows the route highlighted in blue. A table of the route instructions is shown below:

Table 2: Route Instructions for Georges Vanier Catholic School to 20 Windeyer Cr.

Directions	Distance
Turn right onto VARLEY DR
Travel on VARLEY DR	663.5388 m
Turn right onto BEAVERBROOK RD
Travel on BEAVERBROOK RD	553.1408 m
Turn left onto WESLOCK WA
Travel on WESLOCK WA	136.4751 m
Turn right onto KNUDSON DR
Travel on KNUDSON DR	480.2838 m
Turn left onto SHAUGHNESSY CR
Travel on SHAUGHNESSY CR	464.6854 m
Turn left onto WINDEYER CR
Travel on WINDEYER CR	58.3355 m
Turn left into 20 WINDEYER CR
Total distance travelled	2356.4595 m

The software derived the closest facility (school) to the given address argument, using the kan_roads2 geocoded coverage. Given the routing information embedded in the coverage, the function took into account direction (what is to the right or left of the line feature), and calculated the real-time distance in this fashion. The output route uses kan_roads2 as the method of accessibility for more intelligent analysis.

Closest Facility Revisited

When one views the route map output, it is evident that the route does not actually travel to the correct school. Upon further investigation, it was found that the point that represented Stephen Leacock School was closer but was positioned incorrectly in geographic space.

When the point was edited (moving closer to network vector), and the analysis rerun, the route represented Stephen Leacock to 20 Windeyer Cr. Figure 2 shows the new route outlined in brown:

Figure 2: Closest Route from Stephen Leacock School to 20 Windeyer Cr.

..which results in a shorter, more concise route. Table 3 shows the new routing instructions.

Table 3: Route Instructions for Stephen Leacock School to 20 Windeyer Cr.

Directions	Distance
Turn right onto LEACOCK DR
Travel on LEACOCK DR	327.2755 m
Turn left onto BEAVERBROOK RD
Travel on BEAVERBROOK RD	553.1408 m
Turn left onto WESLOCK WA
Travel on WESLOCK WA	136.4751 m
Turn right onto KNUDSON DR
Travel on KNUDSON DR	480.2838 m
Turn left onto SHAUGHNESSY CR
Travel on SHAUGHNESSY CR	464.6854 m
Turn left onto WINDEYER CR
Travel on WINDEYER CR	58.3355 m
Turn left into 20 WINDEYER CR
Total distance travelled	2020.1960 m

Though network analysis can be powerful in making complex analysis, it should be noted that data integrity (both of street networks and stop /landmark information) must be examined thoroughly to ensure that distance calculation algorithms take into account correct / desired inputs as variables. User discretion is highly recommended.

Routing (Travelling Salesman Scenario)

An ArcView routing function was performed to decipher the best possible route from Georges Vanier School (40 Varley Dr).

Layout 2 displays a bus route path, which originates and returns to Georges Vanier School, picking up all stops from the kids coverage in between in the most efficient manner. Again, this follows the Dijkstra algorithm, starting from the school, it looks for the cheapest node (distance) to it along its stop list, picks it up and updates its from/to information for the route. The algorithm loops until it returns to the origin, completing the output route.

Table 4 shows the routing information.

Service / Trade Area Analysis

This function assesses a service area based on given points as central nodes or points (2stores). The output service area (sarea) and service network displayed, based on 2stores, shows service areas for both points with resulting overlap, as shown in figure 3.

Figure 3: Area of Overlap from Trade Area Analysis

As the overlap indicates, some houses in the area (kan_plybldgs) would have equal trade area access between the two points. A procedure was then devised to assess the number of houses that fall within the area of overlap in the trade areas. Here is a description of the procedure to derive this value:

• Query derived service area to extract site_id1 and site_id2 zones in separate coverages from sarea
• Clip site_id1 based on site_id2 to extract sarea_overlap, representing overlap of service areas between the two zones
• Select by Theme of kan_plybldgs completely within sarea_overlap, extract to house_overlap
• Examine table for results

As a result, the number of houses falling within both trade areas is 727, verified by a table | field statistics call to ArcView. Figure 4 shows a flowchart of operations:

Figure 4: Flowhart of Operations