Supporting Resources

for Lecture 16: Comprehensive Operations

Index of Resources:

• Calls for more interest in Spatial Analysis
• Examples of Location Allocation and how to solve it
• NP-Complete, mathematics of HARD problems

Spatial Analysis: a strong interest in the research community

• See UCGIS research priorities;
• University Consortium for Geographic Information Science (overall statement),
• Revised version of Research Priorities.
• NCGIA,
• Decision Support literature,
• Tim Nyerges' resources on Collaborative Decision Support,
• Gerald Rushton, 1979: Optimal location of facilities. Wentworth NH: COMPress. (a book! how archaic!)
• More?

Examples of Location Allocation

Some examples:

• ESRI Transportation Logistics, (Routing and scheduling),
• Warehousing,
• Library planning in UK (UW has a subscription to its journal, but only accessible to UW IP addresses; scroll down, the author eschews site selection but is optimistic about GIS for routing mobile services),
• Political redistricting (?)
• school districts in Iowa,
• ESRI was very proud of the Sears application (delivery and service truck routing) but that was 1997 and it has disappeared from their archive of news releases, now they describe savings at a Mattress delivery firm.
  

Solving a location allocation problem

The simple statement involves:

• A collection of fixed demand, such a consumers who might buy a product or need a certain administrative service
• A certain number of suppliers must be located to serve the demand.

NOTE: This means a RELATIONSHIP, a higher-order of information than a simple overlay or indeed most of the prior operations...

The problem can be constrained in a number of ways (after (Rushton 1979, p.33)):

1. Minimize the total distance between demand and supply
2. Minimize the maximum distance to the closest facility
3. Equalize the number assigned to each facility
4. Ensure that the number assigned is greater than a threshold
5. Ensure that the number assigned does not exceed capacity
6. Minimize the total distance subject to an upper limit on distance (combines 1&2)
7. Set the minimum number of facilities such that the maximum distance is less than some upper limit
8. Route all traffic from origin to dest. along the least cost path subject to the capacity constraints and the interaction between capacity and cost

Two general techniques

Problems 1, 2, 6 are called the 'warehousing' problem. The techniques to solve this require iterative applications of iterative network operations. The 'p-median' heuristic tries a bunch of likely starting points, and then tries neighboring starting points to see if the solution improves in that direction.

The others above can be termed the 'transportation' problem. Early solutions to these problems were done with linear optimization techniques during World War II.
Opinion piece: integrating transportation, land use and GIS;

These days, the field of urban modeling is more likely to use simulation (eg. UrbanSim) in place of optimization approaches...

Political districting fits into problem 3 with some additional geometric and locational constraints. ESRI has toned down their rhetoric about redistricting (they used to assert GIS made fair elections); Example in Texas 1996, North Carolina for 2000, Yet, some of the most horrible district proposals ever have been generated by GIS techniques... (examples deliberately excluded to protect the guilty)

Resources on NP-Complete

• A compendium of NP-Complete;
• Huge number of problems (such as minimum map coloring; just one of the set covering (and partitioning) problems;
• the fine line between assignment and big trouble
• Variants of the Traveling Sales-person Problem: [ minimum metric, minimum geometric] (or the related robotics problem; or the directed graph version - "Chinese postman problem")
  

These problems belong to a group of graph problems that may not ever be solved in 'polynomial' time (hence they are Non-Polynomial or NP). The reason is that you cannot find an iterative solution that allows you to say that the salesman MUST follow this particular path or that this particular parcel fits in that particular knapsack until everything has been fit into place. Essentially, these problems require examining all the possible combinations, a set of numbers that rise very very fast. [all the possible combinations of 59 items would require a number as large as all the baryons in the universe...]

NP problems can be approximated rather closely using iterative heuristics, just without a guarantee that the solution is optimal. In some cases, there are bounds of how close to expect an approximation.

Resources about statistical analysis and GIS

This is JUST a downpayment! Statistical analysis is highly sophisticated and developed over a long period. Geogrpahers make tangential contributions to statistics, whereas they make core contributions to GIS.

More complex models attempt to model spatially-dependent error, usually in the form of neighborhood effects (spatial autocorrelation)

Example: Buffalo: correspondence of an urban model to actual densities; regression analysis of household income and shopping behavior...

any choropleth mapping source runs into the 'Modifiable Areal Unit Problem'
See Openshaw on new census units (Zone Design);

[Census tracts can be divided at will, thus changing the statistical result; Openshaw did '10 million correlation coefficients' for Iowa, obtaining any correlation result from the same source data.] See Openshaw's harangue about spatial analysis and GIS. [We all are fragile; Stan had a stroke...]

From here: Back to Lecture 16 | Class Resources | Lectures | Exercises and Discussions |

Version of 4 November 2002