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
Every piece must be located at some point on the network.
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.
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.
