Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Consider a classic state-wide or country-wide roadway network. I want to create a point layer, where each point is on the roadway network. This point layer will have each point separated by its nearest neighbour by x km or y minutes.

As an addendum, Is it possible to upgrade the algorithm, so that the distance between any point and all its nearest neighbours is the same or as close to the same as possible and there for having the algorithm figure out what that magic distance is given a fixed number of points.

I'm open to suggestions on how to solve this problem. I have access to ArcGIS 9.3 (without network analyst), qgis 1.8 and postgis, python, and R. Most of my data is in SHP.

EDIT

The goal behind this exercise is to determine how far is to locate antennas, infrastructure so that it is equidistant from all points on the network

EDIT 2 to reflect whuber's comment

I am trying to plan for proposed facility locations for a certain type of equipment on the highway network, in such a way that the driving distance distance between each one is x minutes, or the driving distances is y km.

share|improve this question
1  
More guidance would help. For instance, there are trivial solutions consisting of just one point, or just a pair of points separated by y minutes. Could you tell us the original practical problem you face, in terms of the application domain itself (rather than with GIS terminology), so that the answers you get are not constrained by the particular way you are thinking about the problem? This will open the discussion to creative, and possibly much more effective, solutions. –  whuber Aug 23 '12 at 17:54
    
@whuber , is my second edit more comprehensive, or is there anything you'd like to me to add or expand upon? –  dassouki Aug 23 '12 at 19:30
    
Thanks, yes: It sounds like you're trying to create some kind of service coverage over the network, where each "node" (piece of equipment) has a given "range" or "radius", and you would like to cover the entire network at a minimum cost. (If all the equipment is identical, the cost is proportional to the number of pieces of equipment.) Is this a fair interpretation? If not, how does your problem differ from it? (If yes, it's subtly but importantly different from how the question currently stands.) –  whuber Aug 23 '12 at 19:44
    
@whuber you are correct in your assumptions and interpretation –  dassouki Aug 23 '12 at 19:50
    
Can the equipment be situated literally anywhere on the network or is it perhaps restricted to a predefined set of locations? (The latter situation is amenable to some powerful solutions, such as binary integer linear programs.) –  whuber Aug 23 '12 at 19:52

1 Answer 1

up vote 2 down vote accepted

This problem is one of optimization. As such, let's express the objective and the constraints. I will formulate this in a dual manner: rather than thinking of the objective as achieving full coverage of the network, let's consider this as a constraint and make the objective be that of minimizing the total cost to achieve that coverage.

Thus, the objective is to minimize the cost of positioning pieces of equipment.

The constraints are

  1. Every piece must be located at some point on the network.

  2. Every point on the network must be covered.

To express the second constraint, we can think of each possible equipment position x as "covering" a subset C(x) of the network at points near x (such as all those within a specified travel time of x). Full coverage is expressed by saying that the (set-theoretic) union of C(x), taking x to range over all the equipment locations, must contain every point on the network.

One approach to this problem is to discretize it. This can be done flexibly by designating two finite sets of network points: potential equipment locations and "probe" locations. Imagine checking for full coverage by placing a "probe" at every probe location. Each probe can ascertain whether or not it is covered by the equipment.

The probe locations do not need to coincide with possible equipment locations.

It will be important to keep the numbers of equipment and probe locations as small as possible. If we're clever in siting probe locations, we probably do not need many: they should go at all extreme ends of the network and at suitably spaced intermediate locations.

We can solve this problem in general by using varying numbers of equipment locations. First divide the network into approximately equal spaced points, with the spacing about equal to the range of the equipment. Solve this discrete version of the problem. Then subdivide those points and solve the problem again. After a while, the cost of the solutions should not change and we can assume that an optimal, or at the very least near-optimal, solution has been achieved.

To illustrate, consider this tiny network (shown in black lines) with a set of equipment locations (blue circles) and probe locations (white squares) already chosen.

Network diagram

Let's suppose there are unit travel times between neighboring equipment locations and the equipment range at every location is a little less than 3 but greater than 2. Then, for example, a piece of equipment located at j can cover probes 3, 5, 6, 7, and 8, but none of the others.

To get this into a form where canned computer programs can obtain the solution, we need to represent it with matrices. This is easier than it sounds, so I'll begin by displaying the coverage matrix, M, and then explaining how it is found:

    a   b   c   d   e   f   g   h   i   j   k   l   m   n
1:  1   1   0   0   1   0   0   0   0   0   0   0   0   0
2:  0   0   1   1   1   0   0   0   0   0   0   0   0   0
3:  1   1   1   1   1   1   1   1   0   1   0   0   0   0
4:  0   0   0   0   1   1   1   0   1   0   0   1   0   0
5:  0   0   0   0   1   0   0   1   0   1   1   1   1   1
6:  0   0   0   0   0   0   1   0   1   1   1   1   1   1
7:  0   0   0   0   0   0   0   0   0   1   1   1   1   1
8:  0   0   0   0   0   0   0   0   0   1   1   1   1   1

The columns give the coverage of each possible equipment location while the rows correspond to the probes. Down each column a one indicates whether equipment at that location covers the corresponding probe; zeros indicate no coverage. For example, column j is the (transpose of the) vector (0,0,1,0,1,1,1,1). The ones occur in places 3, 5, 6, 7, and 8: precisely the coverage noted earlier. Checking a few other columns against the diagram will help you intuit this mechanism for encoding the coverages.

A solution x is a collection of equipment locations. This is indicated by a vector of 14 zeros and ones, corresponding to the equipment locations (a,b,c, ..., n). A one indicates the equipment is present at that location; a zero, that it is not present. Matrix multiplication of x by M gives a vector of 8 values corresponding to the probe coverage achieved by the equipment. (In fact, Mx counts the number of pieces of equipment covering each probe.) We will see, and interpret, a solution shortly.

The objective is to minimize the total number of pieces of equipment. That's just the sum of the entries in x, conveniently written as the matrix product cx where c is a vector of 14 ones (one entry for each piece of equipment). (If the cost of placing equipment varies from one location to another, putting the costs in the vector c makes cx equal the total cost: this is a powerful generalization of the original problem.)

Finally, the constraint of achieving full coverage is that each probe must be covered by at least one piece of equipment: that is, each entry in Mx must equal or exceed 1. So, we create a vector b consisting of 8 1's and, in conventional shorthand, we require that Mx >= b.

Abstractly, then, the problem is this:

Minimize cx

Subject to

  • Mx >= b
  • All entries of x are either 0 or 1.

This is known as a "binary (or 0-1) integer linear program." You can search for software (open source and commercial solutions exist) that accepts the matrices M, b, and c as input and returns a solution.

The computation is not easy. It's much easier and faster to drop the second constraint and require only that the entries of x be non-negative (but possibly not whole numbers). This turns it into a standard linear programming problem. Modern software can handle such problems with hundreds of thousands of possible equipment locations and tens of thousands of probes. (If that's not enough, subdivide the network, solve the problem on each subnetwork, and reassemble the solutions. The overall solution might not be perfect but it should be awfully good.) We can hope that the solution to the linear program might give us a good start on solving the binary integer program. If not, we might have to wait longer for a solution to come out of the computer.

In this case, I invoked Mathematica's LinearProgramming function:

LinearProgramming[c,m,b]

Its (instantaneous) output was

{0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0}

The ones correspond to equipment locations e and j. Sure enough (as you might already have guessed by visual inspection of the network), placing one piece of equipment at each of these nodes achieves full coverage. You have probably also noted that other solutions are possible: linear programming only returns a solution, not all solutions (of which there may be a huge number).

(A variation of this formulation allows one to weight the coverage to account for distances between equipment and probes in situations where multiple pieces of equipment available to a probe can combine their coverage.)

It still takes work to use this solution: with the GIS you need to create the equipment locations by discretizing the network (but note that the distances between the equipment locations do not have to be constant or even approximately equal) and by identifying appropriate probe locations (which should include all ends, perhaps all vertices, and be roughly equally spaced along all remaining segments). This information has to be converted into the matrix formulation, which requires once more using the GIS to identify which probes are covered by each and every equipment location. (That's a service-area type calculation.) Then, finally, the linear programming solution--which obviously is not going to be computed by the GIS, but by specialized software--needs to be mapped to the set of equipment locations it designates.

share|improve this answer
    
This is absolutely awesome. –  dassouki Aug 24 '12 at 12:06
    
Another example of a linear programming solution to a GIS problem is at gis.stackexchange.com/a/27678. This is a remarkably powerful tool once you learn to recognize many GIS tasks as optimization problems: find the best site, find the best route, find the most efficient service area, find the fairest reallocation of land, etc. –  whuber Aug 24 '12 at 13:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.