The Shortest Covering Path Problem

Abstract

The shortest covering path (SCP) problem involves finding the shortest path between an origin node and a destination node, where the path traverses the network and passes within a maximal covering distance of all nodes of the network. This problem was originally proposed by Current, ReVelle, and Cohon. Since that time researchers have proposed both heuristic and optimal approaches for this problem as well as have developed more general forms, including the maximal covering shortest path problem. From the outset, it has been assumed that any optimal covering path would never loop or double back on itself. This assumption is examined in detail. We demonstrate that this assumption can lead to longer than necessary covering paths. We also present a new, more general construct, which can be used to generate optimal SCPs and demonstrate its use on an example problem.

Keywords

shortest covering paths location set covering facility location and design spatial optimization

Introduction

The shortest path covering problem was first proposed by Current, ReVelle, and Cohon in the Journal of Regional Science in 1984. This problem represents a special design problem that is useful in transportation planning and network design. It involves finding the shortest path between an origin and a destination that traverses the network and “covers” all network nodes by passing within a prescribed maximal distance of each node. At its basic form, it embodies the design elements of local bus service, by providing service access while keeping the route as short as possible. Current, ReVelle, and Cohon (1984) formulated this problem as an integer linear programming (LP) problem, developed an iterative solution process, and provided example solutions. Since that time, many researchers have expanded the problem scope and proposed specialized solution procedures including heuristics (Current, Pirkul, and Rolland 1994; Current and Schilling 1994). This article examines the original work of Current, ReVelle, and Cohon (1984) and questions one of the basic assumptions that is implied in their work regarding the existence of loops, embedded or attached.

The basic underlying components of this model is that of a path or route with the notion that the path needs to be as short as possible while at the same time provide access to all nodes within a maximal distance standard. Shortest paths by their very nature do not contain loops or cycles, as that would provide the opportunity to shorten the path by eliminating those arcs which form the loop or cycle. Thus, the shortest covering path (SCP) model is built with the inherent notion that a loop or cycle is neither necessary nor efficient. This assumption can be found in earlier work with regard to the traveling salesman problem (TSP), where a tour is to be found which begins at one city, travels to each and every other city exactly once, and returns to the origin city. The very definition of this problem prescribes one large cycle that visits each node exactly once, but where embedded smaller loops are also neither necessary nor efficient. Classic formulations to the traveling salesman problem explicitly prevent all subtours or cycles, except the one which includes all nodes (Dantzig, Fulkerson, and Johnson 1954; Miller, Tucker, and Zemlin 1960). In fact, the original work of Current, ReVelle, and Cohon (1984) uses constraints found in the traveling salesman problem literature to prevent subtours and embedded loops. Thus, the SCP problem and the TSP are related in the sense that embedded loops, along the path or tour, are for all intents and purposes forbidden. In this article, we question this assumption with respect to the SCP problem (SCPP) and show that the optimal solution to a SCPP may contain a loop. Because of this, we propose a new, more general formulation of the SCPP and suggest a modified form of the iterative solution process of Current, ReVelle, and Cohon (1984) to solve this new, general form.

In the next section, we discuss the background of this problem and the model of Current, ReVelle, and Cohon (1984). We describe in detail how subtours and loops are prevented along with the general integer programming solution process proposed by Current, ReVelle, and Cohon. Following that we describe two case examples, one which shows that the original model may overlook the optimal solution and the other which shows that the original model may suggest that no feasible solution exists when indeed a feasible solution does exist. Both of these conditions demonstrate that the original model of Current, ReVelle, and Cohon cannot handle, in general, all instances of the SCPP. Given this background, we present a new, more general construct for the SCPP along with a proposed solution process. We then provide an example of solving the SCP problem.

Background

The location science literature is principally concerned with the location of one or more facilities on a network or a continuous surface (e.g., a Cartesian plane) where each facility is represented as a point. There are notable exceptions to this general rule associated with the site search and land acquisition problems where a site is to be placed that involves a combination of smaller land units (see Wright, ReVelle, and Cohon 1983; Brookes 1997; Aerts et al. 2003 as examples) and where a facility may be a structure on a network like a path or a tree (Slater 1980, 1982; Current 1981). Slater was one of the first to suggest the location of a path on a network to minimize distances to all vertices. Current, ReVelle, and Cohon (1984) expanded this concept when proposing the SCPP. This problem involves finding the shortest path, starting at an origin and ending at a destination, where it traverses the network in such a manner as to pass within a maximal service distance, S, of all nodes of the network. This path can be thought of as a “path center” with respect to the coverage distance S using Slater’s terminology. Current (1981) and Slater (1982) both suggested that such problems can be applied to the design of transit and subway lines.

Current (1981) was the first to formulate the SCPP as an integer programming problem and it first appeared in Current, ReVelle, and Cohon (1984). We can formulate this model based upon that given in Current et al. using the following notation:

N = the set of nodes of the network, numbered from 1,2,3,…, n;

V = any subset of N;

$|V| = t h e c a r d i n a l i t y o f s e t V;$

$i, j i n d i c e s u s e d t o r e f e r t o s p e c i f i c n o d e s o f t h e n e t w o r k, w h e r e i, j \in N;$

p = the origin node;

q = the destination node;

$A = \{(i, j) | n o d e s i a n d j a r e c o n n e c t e d b y a n a r c t h a t c a n b e t r a v e r s e d f r o m i t o j\};$

T_k = {i|(i, k) ∊ A}, the set of nodes where an arc can be traversed directly to node k;

$F_{k} = \{j | (k, j) \in A)\}, t h e s e t o f n o d e s t h a t c a n b e r e a c h e d d i r e c t l y f r o m n o d e k;$

d_ij = the distance between node i and node j where $(i, j) \in A$ ;

$S_{k} = \{j | d_{j k} \leq s\};$

s = the maximum allowable coverage distance (or time);

x_{i j} = {\begin{matrix} 1, if the path uses traverses arc (i, j) from i to j where (i, j) \in A \\ 0, otherwise \end{matrix}

Using this notation, we can formulate the SCPP as follows:

S C P M : M i n i m i z e Z = \sum_{i \in N} \sum_{j \in F_{i}} d_{i j} x_{i j}

Subject to:

\sum_{j \in F_{p}} x_{p j} = 1 f o r o r i g i n n o d e p;

\sum_{i \in T_{q}} x_{i q} = 1 f o r d e s t i n a t i o n n o d e q;

\sum_{i \in T_{k}} x_{i k} - \sum_{j \in F_{k}} x_{k j} = 0 f o r a l l n o d e s k \in N w h e r e k \neq p, q;

\sum_{j \in S_{k}} \sum_{i \in T_{j}} x_{i j} \geq 1 f o r a l l k \in N w h e r e k \neq p, q;

\sum_{i \in V} \sum_{j \in F_{i} \cap V} x_{i j} \leq |V| - 1 f o r a l l V \subset N s u c h t h a t 2 \leq |V| < n;

x_{i j} \in \{0, 1\} f o r a l l (i, j) \in A .

The objective (1) of the SCP model (SCPM) minimizes the distances of all arcs selected for the path, starting at node p and terminating at node q. Constraint (2) specifies that an arc must be taken that leads away from the origin node p. Constraint (3) requires that the path reach the desired destination node q. Constraint (4) represents the well-known “flow-balance” constraints, which require that if an arc is selected which leads to an intermediate node k, then an arc must be selected that leads away from node k. Such constraints also ensure that if a path does not enter node k, it must not leave node k when node k is not the origin or destination. Constraint (5) establishes that the path must pass through at least one node that is within the maximum allowable coverage distance of each node k of the network (except for the origin and destination nodes). This constraint is not included for the origin and destination nodes for the very fact that the path starts and ends at these nodes and will automatically be covered. Constraint (7) lists the integer restrictions for the path variables. It should be noted that constraint (6) was not explicitly listed in Current, ReVelle, and Cohon (1984) but are included here to be complete. These constraints eliminate the possibility of subtours (disconnected cycles) from appearing in a solution and have been listed in subsequent work by Current and colleagues (see e.g., Current, Pirkul, and Rolland 1994; Current and Schilling 1994). They are based upon the well-known subtour breaking constraints of Dantzig, Fulkerson, and Johnson (1954) which were proposed in a formulation of the traveling salesman problem.

Solving the previous model as a relaxed LP without constraints (5) and (6) would result in at least one connected path from the origin to the destination. If any variables were returned with fractional values, this would indicate that alternate optimal pathways exist. In such a case, any one of these pathways would be considered optimal. Including constraint (5) without constraint (6) may mean that a solution could contain one or more disconnected loops or subtours in addition to a path connecting the origin and destination. Such disconnected loops will appear if they provide node coverage at a relatively low loop cost. Disconnected loops meet the conditions established by constraint (4), so in themselves will not be prevented without some type of constraint like constraint (6). A disconnected cycle (involving integer valued variables) will involve $|V|$ arcs and connect a subset of nodes V. A cycle can be prevented from occurring in such a subset by maintaining that no more than $|V| - 1$ arcs connecting the nodes within the subset V be used in a solution. Constraint (6) establishes this condition by summing over all arcs connecting nodes that fall entirely within the set V. Unfortunately, explicitly including all constraints for all subsets V of at least two members where $V \subset N$ can be accomplished for only small networks. In general, such constraints are too numerous to use in their entirety.

The model of Current, ReVelle, and Cohon (1984) was first expanded to include the possibility of not covering all network nodes (Current, ReVelle, and Cohon 1985). This was called the maximum covering/shortest path problem. Current and Schilling (1989) extended the “structural concept” from a path structure to a salesman route (the covering salesman problem). This was further extended to a tour structure (the maximal covering tour problem; Current and Schilling 1994) as well as a tree-structured facility (Hutson and ReVelle 1989, 1993). Boffey and Narula (1998) suggested that this could be extended to a multipath covering–routing problem format and proposed a model that involved a prescribed set of origins and destination pairs, where the objective was to maximize coverage provided by the system of located paths. Laporte, Mesa, and Ortega (2000) have reviewed some of these approaches for planning rapid transit systems. More recently within the context of transit design, Wu and Murray (2005) proposed a multipath maximal covering model where network arcs were directed in such a manner as to prevent cycles. Matisziw, Murray, and Kim (2006) proposed a form of the maximal covering, shortest path problem for transit route extension, and Curtin and Biba (2011) proposed an expanded form of the maximal covering shortest path model for transit design, where coverage/access is provided by both arcs and nodes. Their formulation departed from the traditional approach in formulating a covering path problem in that they employed “staged” variables to prevent disconnected cycles or subtours. This was based upon a structure suggested by Vajda (1961) for the traveling salesman problem. Finally, Matisziw and Demir (2012) have presented a special form of the SCPM where the nodes that are covered are known in advance. They use this model as a novel way to “suggest” a path of travel along a network by covering tracking positions that do not exactly coincide with a map of the network.

The formulation of the SCPP is relatively simple and compact if it were not for the need to prevent disconnected cycles. This is the very issue that makes large traveling salesman problems difficult to solve using general purpose commercial solvers. The fact that subtours or disconnected cycles must be prevented when solving problems such as the TSP has led to the development of a number of alternate TSP formulations (Orman and Williams 2004). This includes the work of Miller, Tucker, and Zemlin (1960), Vajda (1961), Gavish and Graves (1978), Wong (1980), and Fox, Gavish, and Graves (1980). Comparisons have also been made between a number of different strategies (see e.g., Langevin, Soumis, and Desrosiers 1990; Padberg and Sung 1991; Orman and Williams 2004). Orman and Williams’ work supports the notion that an efficient approach to addressing the problem of subtours is to solve a problem sequentially. In fact, this is the tack taken by Current, ReVelle, and Cohon (1984) in the original article on the SCPP and by others (e.g., see Matisziw, Murray, and Kim 2006).

In solving the SCPP sequentially, Current, ReVelle, and Cohon (1984) first solved the models (1)–(5) and (7), that is the SCPM without the subtour elimination constraint set (6). The solution to this would likely involve one or more disconnected cycles in addition to a path. Suppose that a solution involves the subtour m, n, o, m (i.e., the subtour starts at node m, proceeds to go to n, then o, and back to m). Then, one could add the constraint:

x_{m n} + x_{n o} + x_{o m} \leq 2

to the model and re-solve. This constraint would prevent the subtour m, n, o, m from occurring in any subsequent solution. In the case of all undirected arcs or a symmetric distance matrix, traveling the circuit in the opposite direction is just as likely to occur (i.e., m, o, n, m) and this can be prevented as well by including a second constraint:

x_{m o} + x_{o n} + x_{n m} \leq 2

Thus, one could solve a problem, identify the subtours, add constraints (constraints in both directions when distances are symmetrical) to prevent the encountered subtours, and re-solve. This process is repeated till the optimal solution does not contain any subtours. The resulting solution would be optimal to the entire problem (1)–(7) without using many of the constraints of type (6). This is, in essence, the iterative solution process proposed by Current, ReVelle, and Cohon (1984). One can consider this a competitive approach today when using the IP model and commercial general-purpose solvers to solve for the SCPM, although it is important to note that other solution procedures have been proposed as well (see Current, Pirkul, and Rolland 1994).

Technically speaking, constraints (8) and (9) can be combined into one constraint as follows:

x_{m o} + x_{o m} + x_{o n} + x_{n o} + x_{n m} + x_{m n} \leq 2,

without loss of generality. This combined constraint will prevent this detached cycle being used in either direction. This fact may have been overlooked by Current (1981) in his original work, as cycles that were encountered involved only two nodes (subtours involving only two nodes are represented by only two variables and constraints (8) and (9) are exactly the same when involving a cycle of two nodes). Finally, it should be observed that the tour-breaking constraints used in Current, ReVelle, and Cohon (1984) were not as inclusive as those proposed by Dantzig, Fulkerson, and Johnson (1954) and the ones used in formulating the SCPP in later work by Current and colleagues (see e.g., Current, Pirkul, and Rolland 1994). Each constraint of type (6) actually involves all arcs connecting nodes that are members of set V; each constraint will prevent any set of internal loops connecting all nodes within the set V.

As one can observe, the SCPP has formed the basis of a subfield of location science. It has become a classic problem and fits the form of structure (path) serving points (nodes) as proposed by Slater (1981). This is a basic form that has been expanded (e.g., maximal covering) and applied (primarily in transit design and analysis). In the next section, we analyze the SCPM within the perspective of embedded cycles or loops. The major concern in past work has been directed at the need to prevent disconnected cycles or subtours. In fact, most would consider the presence of an embedded cycle to be less than optimal, as a shorter path should be able to provide coverage without the need for a cycle. We show in the next section that this perspective is false, and in fact, embedded cycles may be optimal coverage structures in a path. We also show that the formulation given previously and presented in its entirety in Current, Pirkul, and Rolland (1994) prevents all cycles, embedded or not, which may be counter to finding the optimal covering path.

A New Perspective, the Possibility of Embedded Cycles or Loops

The original work of Current, ReVelle, and Cohon (1984, 1985) and subsequent work involving the SCPP do address the issue of embedded loops. Current, Pirkul, and Rolland (1994) notes that traveling salesman type subtours may cover certain nodes for less than the cost required to cover them via nodes on a path from the origin to the destination. They further state that “the object of the SCPP is to cover all nodes via a single path” and that constraints are “necessary to prohibit subtours.” Most discussions on shortest paths do not address the issue of an embedded cycle, as it would seem counterintuitive to what a short path achieves. For if a path contains a cycle, that cycle can be removed, resulting in a shorter path. But, this view of “no embedded cycles” may actually result in a longer than necessary path when attempting to cover all nodes (or even a subset of nodes). This contradicts the very nature of being efficient, as why would one design a longer than necessary path to cover all nodes just so that the path does not contain a cycle. Thus, we argue that an efficient covering path may contain one or more cycles.

To illustrate some of the properties described previously and the iterative solution process proposed by Current, ReVelle, and Cohon (1984), consider the very simple network depicted in Figure 1A. This network contains five nodes and five arcs where all arcs are undirected. The distance for each arc is given at about the midway position on each arc. Suppose that we are interested in solving for the shortest covering path when the covering distance is zero. This means that the path must start at node 1, end at node 2, and pass through all other intermediate nodes. Solving this problem using formulation SCPM (without constraint 6) results in the solution depicted in Figure 1B. This solution and subsequent solutions depicted in Figures 1 and 2 were solved in the integrated visual environment of Xpress-Mosel, a product of the FICO Corporation and all solution times were less than .01 seconds and reported by the solver as 0 seconds. The solutions are depicted as gray-colored directed arcs. In Figure 1A, the path travels on an arc that connects node 1 and node 2, thus satisfying the condition that the path travels from the origin to the destination. Also notice that there is a subtour that travels from node 3, to node 5, to node 4, and then back to node 3. This subtour meets the “flow balance constraints” (4). Altogether, the solution passes through each node and therefore covers all nodes. To eliminate the subtour, we need to add the following subtour breaking constraint: $x_{35} + x_{54} + x_{43} \leq 2$ . If we re-solve the problem with this one subtour breaking constraint, we will obtain a solution which is essentially the same, except the subtour “3 to 5 to 4 to 3” reverses direction and travels “3 to 4 to 5 to 3” as the distances are symmetric. Thus, it makes sense to add at the same time the subtour breaking constraint, $x_{34} + x_{45} + x_{53} \leq 2$ . This nuance was described in the Background section. Knowing that subsequent solutions will merely reverse direction of previously identified subtours, when a subtour appears, we will add two constraints, one to prevent it from being used in one direction and the other to prevent it from being used in the other direction, and then re-solve. Adding these two subtour breaking constraints (3 to 5 to 4 to 3 and 3 to 4 to 5 to 3) and re-solving, we obtain the solution depicted in Figure 1C.

Figure 1.

(A) Shortest covering path sample network. (B) First iterative solution to the shortest covering path problem. (C) Second iterative solution to the shortest covering path problem. (D) Third iterative solution to the shortest covering path problem. (E) Optimal solution to the shortest path covering problem, which cannot be identified using the model SCPM.

Figure 2.

(A) An eight-node, nine-arc network. All arcs are undirected and can be traversed in either direction. (B) An initial solution generated when solving the SCPM without constraints (6). (C) A second solution generated when solving SCPM with subtour breaking constraints with a path length of 23. Note there is an attached subtour. if this was eliminated, there would be no feasible solution to SCPM. (D) An optimal shortest covering path with length 22. Note the covering distance is zero, so the path must traverse all nodes of the network.

Figure 1C involves a subtour that travels from node 3 to node 5 to node 4 to node 5 and back to node 3.¹ Adding constraint $x_{35} + x_{54} + x_{45} + x_{53} \leq 3$ to the previous set of constraints and re-solving the problem yield the solution depicted in Figure 1D. This solution also contains a cycle that can be treated as one cycle or two (3 to 4 to 3 to 5 to 3 OR 3 to 4 to 3 and 3 to 5 to 3). To break this subtour represented as one large cycle, we add the constraint $x_{35} + x_{53} + x_{34} + x_{43} \leq 3$ . Alternatively, we could add two constraints, one to break 3 to 4 to 3 and the other to break 3 to 5 to 3). Either way does not alter the final result but could alter the sequence or total number of iterations needed to solve a problem to completion. Adding the one combined constraint and re-solving yields the case where the solver indicates there is no feasible solution; that is, there is no feasible covering path for this network using model SCPM and the iterative process of Current, ReVelle, and Cohon (1984). However, this problem is quite simple and we can observe that the optimal SCP solution with an origin of node 1 and a destination of node 2 involves a path that loops back on itself, namely, 1 to 2 to 3 to 5 to 4 to 3 to 2. This optimal solution is shown in Figure 1E. This optimal solution violates constraint (3); i.e., the path enters the destination once) and one of the added subtour elimination constraints).

It should be noted here that whether we solve this problem sequentially by adding subtour elimination constraints or with a complete set of subtour elimination constraint (6), the result will be the same, no feasible solution. Thus, the formulation of Current et al. (Current, ReVelle, and Cohon 1984; Current, Pirkul, and Rolland 1994) may result in finding no feasible solution to a specific SCPP, when a feasible solution exists. The reason for this characteristic is that if a feasible solution requires an embedded loop or place where the path enters a node more than once and the subtour elimination constraints have been added to prevent the loop from being used, the resulting solution from the original model will be infeasible. The next property that we wish to explore is the case where an optimal solution uses an embedded loop. If no simple paths can cover at the same amount of distance, then the model of Current, ReVelle, and Cohon (1984) will result in finding a nonoptimal solution. To demonstrate this, consider the eight-node, nine-arc network displayed in Figure 2A where the origin is node 1 and the destination is node 8. To keep this example simple, we again use a covering distance of zero. Solving this problem using the sequential process, as was done previously, will result in an initial solution depicted in Figure 2B.This solution involves a path (1 to 2 to 3 to 7 to 8) and a subtour (4 to 6 to 5 to 4). Adding two constraints to eliminate this subtour in each direction: $x_{46} + x_{65} + x_{54} \leq 2$ and $x_{45} + x_{56} + x_{64} \leq 2$ and re-solving yields the solution displayed in Figure 2C. Notice that this route travels 1 to 2 to 3 to 7 to 3 to 4 to 5 to 6 to 8. It is a complete path; however, it does double back on itself as it goes from 3 to 7 to 3. Essentially, it involves an embedded loop. This circumstance is a bit unusual, but it does demonstrate that when constraints are not present to prevent cycles (e.g., constraint 6), a solution may naturally involve an embedded loop. The length of this path is 23. Unfortunately, it is not the optimal covering path, as a covering path exists with a distance of 22. This is displayed in Figure 2D.

Consequently, whether solving in an iterative fashion or with all subtour elimination constraints at the outset (i.e., the complete set of constraint 6) may result in an infeasible solution or a nonoptimal solution. The basic issue is that subtour elimination constraints prevent solutions which involve a cycle, whether attached or not, and this may affect whether an optimal solution to the SCPP can be found. But, one may question whether this result would occur for other well-known approaches to eliminate subtours that have been developed for the traveling salesman problem (other than the adaptation of Dantzig, Fulkerson, and Johnson 1954). Simply put, the approaches of Vadja (1961), Miller, Tucker, and Zemlin (1960), and others for breaking and preventing subtours in the TSP all create the same basic issue. For the covering salesman problem, Current and Schilling (1989) suggested adding arcs to the network to represent the possible use of arcs that involve a cycle for the covering salesman problem. This has traditionally been done in the TSP by using a complete network, where all pairs of nodes are connected by an arc (see Current and Schilling [1989]). This results in a large network that contains nearly $(n^{2} - n) / 2$ arcs and $n^{2} - n$ arc variables (assuming each arc can be traversed in each direction). This is clearly not an efficient approach for dealing with the possibility of addressing embedded cycles or loops. In addition, there is another feature of the SCPM that deserves note. This involves the first two constraints of the SCPM above (constraints 2 and 3). Constraint (2) maintains that only one arc may be used to leave the origin node. This will prevent an embedded loop starting at the origin and subsequently returning to the origin, as only one arc can be used to leave that node. The same issue arises in constraint (3) as an embedded loop cannot begin at the destination node, since an embedded loop attached to the destination would mean that the destination would be approached by two arcs and not one. Consequently, the SCPM contains several features that prevent a loop from being used in a solution.

We have now established the fact that the SCPM is constructed in such a manner as to prevent loops, even when loops may represent features of an optimal route. In the next section, we present a new, revised formulation for the SCP which can be used to solve for the optimal SCP which neither encourages nor prevents embedded cycles (attached subtours).

A New, Revised SCPM

One of the main objectives of this article is to formulate a general form of the SCPP where loops or embedded cycles are allowed. In the previous section, it was demonstrated that optimal SCPs may involve such nuances and without a model that can accommodate such structures, resulting solutions may not be optimal. Consider first the following change in decision variables:

$x_{i j} = t h e n u m b e r o f t i m e s a r c (i, j) i s t r a v e r s e d i n t h e d i r e c t i o n o f i t o j .$

In general, it may be that an arc will be traversed more than once in the same direction, depending on the nature of the network. In most cases, the path decision variable, x_ij , will conform to the original constraint (7), but there are pathological cases in which the optimal covering path may double back along an arc in the same direction. Accordingly, we need to account for this possibility in the definition of path variables.

Given this variable modification and all other notation defined previously, we can formulate the more general form of the SCPM as follows:

N R - S C P M : M i n i m i z e Z = \sum_{i \in N} \sum_{j \in F_{i}} d_{i j} x_{i j}

Subject to:

\sum_{j \in F_{p}} x_{p j} - \sum_{i \in T_{p}} x_{i p} = 1 f o r o r i g i n n o d e p

\sum_{i \in T_{q}} x_{i q} - \sum_{j \in F_{q}} x_{q j} = 1 f o r d e s t i n a t i o n n o d e q

\sum_{i \in T_{k}} x_{i k} - \sum_{j \in F_{k}} x_{k j} = 0 f o r a l l n o d e s k \in N w h e r e k \neq p, q

\sum_{j \in S_{k}} \sum_{i \in T_{j}} x_{i j} \geq 1 f o r a l l k \in N w h e r e k \neq p, q

x_{i j} + x_{j i} - \sum_{k \in T_{i} - \{j\}} x_{k i} - \sum_{k \in T_{j} - \{i\}} x_{k j} \leq 1 f o r e a c h (i, j) \in A (i, j) \in A

x_{i j} + x_{j i} - \sum_{k \in F_{i} - \{j\}} x_{i k} - \sum_{k \in F_{j} - \{i\}} x_{j k} \leq 1

x_{i j} \geq 0, i n t e g e r f o r a l l (i, j) \in A .

This model is called the new revised SCPM (NR-SCPM). The objective function (11) minimizes the length of the designated path and is the same as that in the original formulation SCPM. Constraint (12) specifies that the path departs from the origin node, p, exactly one time more than the path enters the origin node. To understand why this is necessary, the optimal covering path may first depart from the origin, loop through several nodes, and return to the origin and then depart again. This constraint is written so that we can account for such a nuance. In the next section, we provide an example where this nuance is encountered in the optimal solution. Constraint (13) specifies that the path terminates at the destination node, q. To account for the fact that there may be an embedded loop of the path attached to the destination node, this constraint ensures that the path enters the destination node exactly one time more than it leaves.² Constraint (14) is a balance constraint that is the same as that found in the SCPM. This constraint ensures that for every intermediate node, the number of times a path enters a node is equivalent to the number of times a path leaves that node. Constraint (15) maintains that the path traverses within the maximal covering distance of each node k, ensuring that each node k is covered. Constraints (16) and (17) are forms of simple tour attachment constraints. These constraints allow a simple loop to occur as long as it is attached to the path. They also prevent a simple subtour from being independent of the path. We call these eliminate or attach subtour (EAST) constraints. In solving a SCPP, subtours often occur in an initial solution which involve a simple arc traversal in both directions, that is, a subtour that travels from one node to another node and back to the previous node (i.e., i → j→ i). For any arc, if x_ij = 1and x_ji = 1, then there is a simple loop going from i to j and back to i. Constraint (16) prevents such a loop from occurring unless an arc from some other node (not i or j) is used to reach node i or node j. Constraint (17) ensures the opposite, that is, a loop from i to j and back to i cannot be used in the solution unless there is an arc in the path which leads away from this loop to some other node (not i or j). Thus, constraints (16) and (17) do not prevent simple loops involving two nodes from occurring as long as they are attached to other path elements (one leading to and the other leading away). The EAST constraints can be generalized for a set of arcs connecting a subset V of nodes in following way:

\sum_{i \in V} \sum_{j \in F_{i} \cap V} x_{i j} - \sum_{i \in V} \sum_{\binom{k \in T_{i}}{k \notin V}} x_{k i} \leq |V| - 1 f o r a s u b s e t o f n o d e s V .

\sum_{i \in V} \sum_{j \in F_{i} \cap V} x_{i j} - \sum_{i \in V} \sum_{\binom{k \in F_{i}}{k \notin V}} x_{i k} \leq |V| - 1 f o r a s u b s e t o f n o d e s V .

These constraints prevent a subtour connecting all nodes in set V, without an arc being used to lead away from the subtour/cycle to a node outside of set V (constraint 19). Constraint (2) prevents a loop or subtour from occurring, without an arc being traversed towards a node in V from a node that is not in V. Altogether, such constraints allow a loop to be used as long as it is attached to a path. One can think of this type of constraint as a generalized form of the Dantzig, Fulkerson, and Johnson TSP subtour elimination constraints, except they don’t prohibit a subtour as long as it is attached to the path.

EAST constraints can be included for all connected subsets V of N where $2 \leq |V| < n - 1$ . Unfortunately, the number of such subsets V will tend to grow exponentially as a function of n. Consequently, such constraints should be used sparingly, just as suggested for subtour elimination constraints for the TSP like constraint (6). Therefore, it seems reasonable to first solve the NR-SCPM given previously. If the solution contains any disconnected subtours, we can append a pair of EAST constraints (19 and 20) for the set of nodes involved in each encountered subtour and re-solve. The resulting solution is then checked for the presence of any additional independent subtours, EAST constraints are added for those subtours and then the problem is again re-solved. The process continues until the resulting solution contains no unattached subtours, which means that an optimal solution to the SCPP has been identified. Thus, we propose an iterative process that is similar to what Current et al. demonstrated for the SCPM, except that we employ the NR-SCPM and generalized EAST constraints (19 and 20).

An Example Comparing NR-SCPM and the Original SCPM

We solved both the SCPM and NR-SCPMs using the Lingo modeling language with its proprietary solver. We designed a visualization tool and programmed it in VB.net using Microsoft’s Visual Studio 2008. We solve the two models on a 104-arc network derived from the well-known Swain data set. This network is shown in Figure 3. We chose node 27 as the origin node and node 21 as the destination node for our example. The main goal here is to provide an example that involves a comparison between the original model, SCPM, and the new model, NR-SCPM. We do not provide an exhaustive computational study here, as the major goal was to explore the nuances of the original model and provide a new, revised approach for the SCP problem. We leave to future work the development of efficient algorithms for this new model. We solved for the SCP for a set of maximal service distances (2.5, 5.0, 7.5, 10.0, 12.5, and 15.0). The solutions to the NR-SCPM differed from those of the SCPM in four of the six cases. For the maximal service distance of 7.5 and 15.0, the solutions to the two different models were the same. Figure 4 presents the optimal SCP solution associated with a coverage distance of 10.0. This solution was generated by the classic model of Current, ReVelle, and Cohon (1984) and presented previously as SCPM. The length of this path is 162.69 distance units. Figure 5 presents the optimal SCP solution for the same maximal coverage distance of 10.0. This second solution was generated by the NR-SCPM. The length of this path is 155.72 distance units.³ Note that the distance of the second path is slightly shorter than the classic path and that this was made possible by the use of three loops, one at the origin and two along the route. These loops are as follows: 27 to 16 and back to 27; 53 to 50 and back to 53; and 29 to 23 to 17 to 23 and back to 29. Although the distances of the two solutions are quite similar (NR-SCPM path is 4.3 percent better than the SCPM path) for our example, such a case may not always be true in general.

Figure 3.

Hypothetical Swain network containing 55 nodes and 104 arcs. The arc distances are computed as Euclidean distances between points.

Figure 4.

An optimal shortest covering path solution generated by the model of Current, ReVelle, and Cohon (1984) using the iterative solution process of Current et al. The origin is node 27 and the destination is node 21. The covering distance is 10.0 and the length of the path is 162.69 distance units.

Figure 5.

An optimal shortest covering path solution generated by the new model, new revised shortest covering path model, using an iterative solution process whereby constraints (16) and (17) are added until independent loops or subtours do not exist. The covering distance is 10.0, and the length of the path is 155.72 distance units. Note the origin is node 27 and the destination is node 21. There are three attached loops in the solution: node 27 to node 16 and back to node 27; node 53 to node 50 and back to node 53; and node 29 to node 23 to node 17 to node 23 and back to node 29. This route with loops is shorter than the one given in Figure 4 involving the classic model and the same data and coverage values.

Conclusions

This article has addressed the shortest path covering problem, originally proposed by Current, ReVelle, and Cohon (1984). This model and its companion, the maximal covering shortest path problem, have formed the basis of an important class of location problems, involving the location/design of a structure to provide service across an area or region. It has formed the basis for a number of models developed for the purpose of designing transit routes, communication systems, and specialized networks. The original work of Current, ReVelle, and Cohon (1984) and subsequent work was formed with the implied assumption that optimal covering paths would not contain a loop or embedded cycle. In this article, we have reviewed this implied assumption with respect to two simple example networks. The first we used to demonstrate that the original model of Current (1981) may preclude any solution from being identified, when a covering path exists and the other was used to demonstrate that an optimal solution may be prevented when using the original model, as the optimal solution involved the use of an attached loop. Both examples were used to underscore the fact that embedded loops may be used in an optimal SCP.

As a second major goal, we proposed a new, revised formulation for the SCPP (NR-SCPM) that can be used to solve for the SCP that neither encourages nor eliminates the use of loops. This new, revised form overcomes the features of the original model SCPM. As a third element of the article, we provide an example network and solve both the NR-SCPM and the original SCPM for several maximal coverage distances. In the six different coverage distances tested, four solutions involved attached loops at optimality, which demonstrate that solutions with embedded loops can frequently outperform simple paths without loops.

The impetus for this work concerns the design of transit routes for small to medium-sized cities. Often transit planners use loops in their designs to provide a suitable trade-off between coverage and route distance. Some routes are shaped like lollipops and others are shaped like barbells. The work of Current, ReVelle, and Cohon (1984) and others places such design features (i.e., the presence of a loop) into question, as it is logical to use the original SCPM for designing such routes. The original model and extensions of their model that have been used in transit design all prevent loops from being used. In this article, we demonstrate that path design with loops may indeed be optimal depending upon the circumstances of the network layout. There are numerous implications of this work when developing route design models for transit and other passenger systems.

Footnotes

Acknowledgments

We wish to acknowledge the support of the University of California Transportation Center for the support of this research under contract number 00007914. We also want to express our appreciation for helpful comments from our colleagues Kostas Goulias and Stuart Sweeney.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The authors received a generous grant from the University of California Transportation Center under contract number 00007914.

Notes

References

Aerts

J. C. J. H.

Eisinger

Heuvelink

G. B. M.

Stewart

T. J.

. 2003. “Using Linear Integer Programming for Multi-site Land-use Allocation.” Geographical Analysis 35:148–69.

Boffey

Narula

S. C.

. 1998. “Models for Multi-path Covering Routing Problems.” Annals of Operations Research 82:331–42.

Brookes

C. J.

1997. “A Parameterized Region Growing Programme for Site Allocation on Raster Suitability Maps.” International Journal of Geographical Information Science 11:375–96.

Current

1981. “Multiobjective Design of Transportation Networks.” PhD Dissertation, Department of Geography and Environmental Engineering, Johns Hopkins University, Baltimore, MD.

Current

Pirkul

Rolland

. 1994. “Efficient Algorithms for Solving the Shortest Covering Path Problem.” Transportation Science 28:317–27.

Current

ReVelle

Cohon

. 1984. “The Shortest Covering Path Problem: An Application of Locational Constraints to Network Design.” Journal of Regional Science 24:161–83.

Current

J. R.

ReVelle

C. S.

Cohon

J. L.

. 1985. “The Maximum Covering/Shortest Path Problem: A Multiobjective Network Design and Routing Formulation.” European Journal of Operational Research 21:189–99.

Current

J. R.

Schilling

D. A.

. 1989. “The Covering Salesman Problem.” Transportation Science 23:208–12.

Current

J. R.

Schilling

D. A.

. 1994. “The Median Tour and Maximal Covering Tour Problems: Formulations and Heuristics.” European Journal of Operational Research 73:114–26.

10.

Curtin

K. M.

Biba

. 2011. “The Transit Route Arc-node Service Maximization Problem.” European Journal of Operational Research 208:46–56.

11.

Dantzig

Fulkerson

Johnson

. 1954. “Solution of a Large-scale Traveling Salesman Problem.” Journal of the Operations Research Society 2:393–410.

12.

Fox

K. R.

Gavish

Graves

S. C.

. 1980. “An n-constraint Formulation of the Time Dependent Travelling Salesman Problem.” Operations Research 28:1018–21.

13.

Gavish

Graves

S. C.

. 1978. “The Travelling Salesman Problem and Related Problems.” Working paper OR-078-78, Operations Research Center, MIT, Cambridge, MA.

14.

Hutson

ReVelle

. 1989. “Maximal Direct Covering Tree Problems.” Transportation Science 23:288–99.

15.

Hutson

ReVelle

. 1993. “Indirect Covering Tree Problems on Spanning Tree Networks.” European Journal of Operations Research 65:20–32.

16.

Langevin

A. F.

Soumis

Desrosiers

. 1990. “Classification of Travelling Salesman Formulations.” OR Letters 9:127–32.

17.

Laporte

Mesa

Ortega

. 2000. “Optimization Methods for the Planning of Rapid Transit Systems.” European Journal of Operations Research 122:1–10.

18.

Matisziw

T. C.

Demir

. 2012. “Inferring Network Paths from Point Observations.” International Journal of Geographical Information Science 26:1979–96.

19.

Matisziw

T. C.

Murray

A. T.

Kim

. 2006. “Strategic Route Extension in Transit Networks.” European Journal of Operations Research 171:661–73.

20.

Miller

C. E.

Tucker

A. W.

Zemlin

R. A.

. 1960. “Integer Programming Formulation of Travelling Salesman Problems.” Journal of the ACM 7:326–29.

21.

Orman

A. J.

Williams

H. P.

. 2004. “A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem.” Working Paper LSEOR 04.67, The Department of Operational Research, The London School of Economics and Political Science, London, UK.

22.

Padberg

Sung

T.-Y.

. 1991. “An Analytical Comparison of Different Formulations of the Travelling Salesman Problem.” Mathematical Programming 52:315–58.

23.

Slater

P. J.

1980. Centrality of Paths and Vertices in a Graph: Cores and Pits. SAND-80-1140C. Albuquerque, NM: Sandia National Labs.

24.

Slater

P. J.

1981. “On Locating a Facility to Service Areas within a Network.” Operations Research 29:523–531.

25.

Slater

P. J.

1982. “Locating Central Paths in a Graph.” Transportation Science 16:1–18.

26.

Vajda

1961. Mathematical Programming. London, UK: Addison-Wesley.

27.

Wong

R. T.

1980. “Integer Programming Formulations of the Travelling Salesman Problem.” Proceedings IEEE Conference on Circuits and Computers: 149–52.

28.

Wright

ReVelle

Cohon

. 1983. “A Multiobjective Integer Programming Model for the Land Acquisition Problem.” Regional Science and Urban Economics 13:31–53.

29.

Murray

A. T.

. 2005. “Optimizing Public Transit Quality and System Access: The Multiple-route, Maximal Covering/Shortest-path Problem.” Environment and Planning 32:163–78.