Some Constrained Shortest-Route Problems By C. P. BAJAJ,New Delhi 1) Eingegangen am 25. August 1970
Summary: This paper treats five constrained shortest-route problems: 1) determining the shortest route when it is constrained to pass through a given set of specified nodes; 2) determining the shortest route when it is constrained to pass through a given set of specified nodes and the specified nodes are to be visited in a fixed order; 3) finding an optimal route for the travelling-salesman problem; 4) determining the shortest route through K sets of specified nodes when at least one node of every set of specified nodes is to occur on the shortest route; and 5) finding the shortest route through the sets of specified nodes when at least one node of every set of specified nodes is to occur on the shortest route and the sets of specified nodes are to be visited in a fixed order. The functional equation technique of dynamic programming is employed to solve problems t), 3), and 4), while problems 2) and 5) are solved through simpler algorithms. The methods are illustrated by examples.
Zusammenfassung: Es werden fiinf Kiirzeste-Wege-Probleme mit besonderen Bedingungen behandelt: 1) Bestimmung des kiirzesten Weges unter der Bedingung, dab die in einer gegebenen Menge spezifizierten Knoten passiert werden mfissen, 2) Bestimmung des kfirzesten Weges, wobei die in einer gegebenen Menge spezifizierten Knoten in einer bestimmten Reihenfolge passiert werden miissen, 3) Ermittlung der optimalen Rundreise im Travelling-Salesman Problem, 4) Bestimmung des kiirzesten Weges duTch K Mengen yon spezifizierten Knoten, wobei aus jeder Menge wenigstens ein Knoten passiert werden muB, und 5) Bestimmung des kiirzesten Weges duTch Mengen yon spezifizierten Knoten, wobei aus jeder Menge wenigstens ein Knoten passiert und die Mengen in einer vorgegebenen Reihenfolge aufgesucht werden miissen. Zur L~Ssung der Probleme 1), 3) und 4) wird die Technik der dynamischen Optimierung angewandt, w~ihrend die Probleme 2) und 5) mit einfacheren Algorithmen behandelt werden. Die Methoden werden an Beispielen erl~tutert.
1. Introduction In recent years, the problem of finding the shortest routes between all pairs of nodes of a network has received a considerable attention because of its wide practical utility. SmMBEL [1954] was the earliest to publish a 'matrix' solution to this problem. DANTZlG [1957] used linear programming and BELLMAN[1958] applied the functional equation technique of dynamic programming to solve the problem. These authors and several others (DREYFUS[1969], FARBEV,LAND, MURCHLAND [1967], LAND, STAIRS [1967], MILLS [1966], PEART, RANDOLPH, BARTLETT [ 1 9 6 0 ] , POLLACK, WIEBENSON [1960]) have dealt with the problem of finding a shortest route, between every pair of nodes of a network, without making it obligatory to pass through any other specified node. KALABA1-1960] pointed out the importance of finding out the optimal route when it is constrained to pass i) Dr. C. P. BmAJ, Department of Mathematics, Rajdhani College, University of Delhi, New Delhi-15, India.
288
c.P. BAJAJ
through a given number of specified nodes. A solution to this problem was reported by SAKSENAand KUMAR [t966]. Unfortunately, the algorithm given by SAKSENA and KUMAR is basically wrong and it cannot be corrected without introducing essential modifications. In the next section, the essential modifications to the algorithm, given by SAKSENAand KUMAR,are provided and in the third section, we study the problem of finding out a shortest route through a set of specified nodes when the specified nodes are to be visited in a fixed order. The algorithm, given in the second section, has further been modified by SINHA and BAJAJ [1969] to solve the problem of maximum capacity route through a set of specified nodes. In the fourth section, the well-known travelling-salesman problem is viewed as a constrained shortestroute problem and the method of the second section is suitably modified to solve this problem. The method, like the method of the second section, is distinguished by the fact that it is a method of exhaustion, i.e., it converges after a finite number of iterations, bounded in advance. In the fifth section, the method of the second section is extended to find a shortest route through sets of specified nodes, when at least one node of every set of specified nodes is to occur on the shortest route and in the sixth section, an algorithm is mentioned for a simplified version of the problem, mainly when the sets of specified nodes are to be visited in a given order. The interest in the problems, treated in the fifth and sixth sections, stems from the routine requirements of, say, optimal scheduling of clients through welfare agencies (sets of specified nodes) when the clients are to visit the welfare agencies in any order and in a specified order. The solution to any of the four shortest-route problems, treated in sections 2, 3, 5 and 6, may have loops not only at the final stage but even at the intermediate stages. Sections 7 and 8 are devoted to numerical experience and the computational aspects of the dynamic programming algorithms developed. 2. The Shortest Route Through a Set of Specified Nodes 2.1 Dynamic Programming Formulation of the Problem and its Solution
Consider a network consisting of (N + 1) nodes, which for convenience are denoted by the set R = {0,1,2,...,N - 1,N}. Let 0 denote the origin and N the destination. Let the length of the arc joining nodes i and j be denoted by Dij, (i,j ~ R), where Dij need not be symmetric - that is, Dij is not necessarily equal to Dji. It is assumed that all arc lengths are non-negative (that is D~ > 0) and that D, = 0 for all i ~ R. The length D~j = oo, if no link exists between nodes i and j. Let the set of specified nodes, through which the shortest route must necessarily pass, be S = {1,2,...,K}, which is a definite subset of R. We define the sets So = {0} and T = So to S. Let the length of a shortest route between the ordered pair of nodes (p,q), (p e T, q E S), be denoted by Dr(p,q), where the index r merely indicates that r
Some Constrained Shortest-Route Problems
289
distinct nodes of S - {p,q} happen to lie on this shortest route, r = 0,1,2, ..., (K - 1) when p e s o and r = 0,1,2, ... ,(K - 2) when p ~ S . The lengths/Y'(p,q) are to be calculated in advance by any method of solution of the ordinary shortestroute problem, taking p to be the starting point and q the destination z). Let V denote the set of nodes p, q and those r distinct nodes of S - {p,q}, which happen to lie on the shortest route from p to q. Although the original question is that of tracing the shortest path, from 0 to N, which passes at least once through each node of S, we imbed this problem within the family of problems requiring the determination of shortest paths from a generic node p to the destination N and passing through at least ¢ distinct nodes ofS - {p}, where ~ = 0,1,2 . . . . . K. This apparent complication of the problem enables us to employ functional equations. Let us define, f e ; , - 1 = the length of a shortest route from the node q, (q ~ S, p e T), to the final destination N by passing through at least ~ - r - 1 distinct nodes o f S - V. r _< ~ - 1, ~ = 0,1,2 .... ,K. (1) Thus we have fv¢ = the length of a shortest route starting 3) from the node p to the final destination N by passing through at least ~ distinct nodes ofS - {p}. (2) and f~q,p = the length of a shortest route from the node q to the final destination N, without obligation of passing through any other specified node, when at least ¢ - 1 distinct nodes of S - {p,q} happen to lie on the shortest route from p to q. (3) Observe now that if the initial node is p and if the initial decision is to go by the shortest route from p to q when r distinct nodes of S - {p,q} happen to lie on this (shortest) route, then the remainder of the route must certainly be selected as to be of shortest length and to be having at least ~ - r - 1 distinct nodes of S - V so that the complete route from p to N is optimal and includes at least ~ distinct nodes of S - {p}. This is an application of the general principle of optimality in the theory of dynamic programming [BELLMAN,DREYFUS,1962; KAUFMANN, CRUON, 1965]. Then as a consequence of the above observation, we get, f ~ = minq [Dr(p,q) + f ~ ; r - 1 ] ,
(r < ¢ - I, q ~ S - {p})
(4)
and fp~ = minq [D'(p,q) + fop-],
(r > ~ - 1, q ~ S - {p}).
(5)
Equations (4) and (5) are true provided that a specified node is counted only once, even though it recurs, on the optimal route between p and q and between q 2) The values of r, however, are recorded in a separate matrix. 3) With single suscript, we mean that no path is consideredbefore the node at the subscript.
290
C.P. BAJAJ
and the destination N. The complete route from p to N, as per definition (2), contains at least ~ distinct nodes of S - {p}. A route, satisfying this condition, will be called a feasible route. Our problem, therefore, is to select a feasible route for which the distance travelled is minimum. From (4) and (5), we get the initial step of iteration as: f ~ = minq [D'(p,q) + fqop],
(q ~ S - {p}).
(6)
2.2 Calculation of~,~'-1 It is easily seen that if ~ - r - 1 < 0, then f q ! ; ' - 1 = f~o. The values off~°p can be calculated by applying one of the existing methods of solution of the ordinary shortest-route problem, taking q to be the starting point and N the destination. This, in turn, through equation (6) yieldsflp. T o calculate fq~-,-i for ~ - r - 1 > 1, we proceed as follows: The table of f~, where ( = ~ - r - 1, consists of (K - 1) values, over the S - {p} specified nodes, and these values are ranked in the order of increasing lengths. The quantityf~p, may easily be obtained from the table off~, as it is the route from q to the final destination N with an extra condition that it must pass through at least ( distinct nodes of S - V. For this we may be required to scan (starting from the value off~ and then going upwards), all the entries 4) in the table off~ that have already been evaluated. However, if none of the (K - 1) values, in the table off~, gives the value (with a feasible route) for f~p, we consider q to be the new starting point and transform equations (4) and (5) accordingly to determine the r e q u i r e d f ~ . This will be quite clear, if we outline the procedure as follows: Let/3 "1(q, x) be the length of a shortest route between the ordered pair of nodes q and x, (q,x ~ S), when rl distinct nodes of S - {x} w V happen to occur on the (shortest) route. The quantity D'~(q,x) can be easily obtained from the table of Dr(p,@ Let V1 denote the set of nodes q,x and those r 1 distinct nodes, o f S - {x} u V, which happen to lie on the shortest route from q to x. Define, fx;-'1 ,q|P -~ = the length of a shortest route from the node x, (q,x ~ S, p ~ T), to the final destination N by passing through at least ( - r I - t distinct nodes of S - V w V1. (7) Thus we have f ~ = the length of a shortest route from the node x to the final destination N by passing through at least ( distinct nodes of S - V. (8) and O f~.qlp = the length of a shortest route from the node x to the final destination 4) That is why we do ranking in the order of increasing lengths.
Some Constrained Shortest-Route Problems
291
N, without obligation of passing through any other specified node, when at least ~ - 1 distinct nodes of S - V u {x) happen to lie on the shortest route from q to x. (9) Another application of the principle of optimality leads to the relations: fq~p = minx [/3~,(q,x) + f~,],~-l],
(r 1 < ~ - 1, x e S
-
V)
(10)
and ~,p = min, [br'(q,x) + fx°qlp],
(rl >_ ~ - 1, x ~ S - V ) .
(11)
Equations (10) and (11) are true under conditions similar to those stated above for the validity of equations (4) and (5). The quantityf~lp, where p = ~ - rl - 1, is determined in the fashion outlined above for the computation offq¢,p. The above backtracking process of dynamic programming will be terminated when the value (with a feasible route) corresponding to f~p is obtained. The value (with a feasible route) for f~p, if it exists, is bound to be reached in this manner. The values offq!p are to be calculated for all q ~ S - {p} as required in the functional equations (4) and (5). In determiningf~p through equations (10) and (I 1) we include at least one node different from those lying on the path corresponding to the value off~. It is clear from this physical interpretation of the iterative scheme that at most K iterations are required for the method to converge to the solution. In order to solve the problem, we proceed as follows: (i) Calculate Dr(p,q) and record the values of r in a matrix Rv. Each of these will be in the form of a matrix of order (K + 1, K). Reference to these matrices would be necessary in the construction of succeeding tables. (ii) Calculate fq°p. (iii) Using equations (4), (5) and (6) obtain, by the iterative procedure, the values off~; ~ = 1,2, ... ,(K - 1). (iv) Finally, calculate fo~ and the required shortest route.
3. Ordering o f Nodes - A Simplified Version of the Problem
So far, we have imposed no restrictions on the order in which the specified nodes are to be entered. The objective was that all the specified nodes must be visited in some way. Now we take the case when the specified nodes are to be visited in a specified order. Once the order is fixed, the problem becomes much easier. We suppose that the specified nodes are to be visited in the order 1,2, ..., K - that is, first the node 1 is to be visited, then the node 2, then the node 3 and so on. The problem, therefore, is to obtain the shortest route, from 0 to N, which passes through the nodes 1,2,..., K in this order.
292
C.P. BAJAJ
3.1 Method of Solution An algorithm, developed for solving the above simplified problem, is described below: Let/st(x,y) be the length of a shortest route between the ordered pair of nodes (x,y) where (i) x ~ T, y e s (ii) the index t merely indicates that t distinct nodes of S happen to lie, in the prescribed order, on this shortest route from x to y such that (a) the nodes x,y are taken into consideration only for having the fixed order and not for calculating the value of t (b) a node which is not in the specified order is overlooked while finding the value of t (c) t = 0 , 1 , 2 , . . . , ( K - i) when xeSo and t = 0,1,2 .... , (K - 2) when x e S. We define f2 = the length of a shortest route from the node x, x e T, to the final destination N, by passing through either at least r/distinct nodes in the order 1 , 2 , . . . , ~/ of S, if t / < x or at least 0 / + 1) distinct nodes in the order 1,2 .... , x - t, x, x + 1 .... ,q + 1 of S, ifq > x; a node, occurring on the optimal route, which is not in the prescribed order being ignored while calculating the value of t/. = 0,1,2 . . . . . K when x s S o and r / = 0,1,2 . . . . . (K - 1) when x e S . It then follows that fff = the length of a shortest route from the node x to the final destination N, without obligation of passing through any other specified node.
3.2 The Algorithm As we have to enter the specified nodes in a fixed order, i.e., we have to go from node x to x + 1 any other specified node occurring on the optimal route between x and x + 1 is not to be counted. Therefore, for DS(x,x + 1), we shall have s = 0 for all x ~ T. Also the shortest route between the nodes (x - 1) and (x + I) via node x is composed of shortest routes between (x - 1) and x and x and (x + 1), because otherwise replacement of these routes by shorter ones would yield a shorter overall route from (x - 1) to (x + 1) via x. Based on these notions, the algorithm can be stated as under:
Step 1. Calculate the values of/5°(0,1),/5°(1,2),/50(2,3) . . . . . /5(K - 1,K) a n d f °. Step 2. Calculate bx-l(O,K) =/5°(0,1) +/5°(1,2) +/5°(2,3) + ... + b ° ( K - l , g ) . Step 3. Finally, calculate fox = b K - a ( 0 , K ) + f o and the required shortest route.
Some Constrained Shortest-Route Problems
293
4. The Travelling-Salesman Problem - Functional Equations and Their Solution
Consider the network consisting of (N + 1) nodes (cities) as given in the second section. With no loss in generality, since the tour is a round trip, fix the origin at some city, say, 0. We define the set G = (1,2 . . . . . N) so that R = So u G. Thus the travelling-salesman problem can be framed in the above notations as follows: "Given a network consisting o f ( N + 1) nodes, one has to start from 0, pass through each node (city) of G, once and only once, and then return to 0 in such a way so that the total distance travelled is minimum." The method of the second section can be suitably modified to solve this problem. Corresponding to the functional equations (4) and (5) for the shortest route through S, we get the following functional equations for the travelling-salesman problem: F~ = min~ [ B " ( p , q ) + F ~ " - 1], [m < ~ - 1, q ~ G - (p}] (12) and F~~t = m i n q [ B ' ( p , q )
o + F~,p],
[m >_ ~t - I, q e G - (p}] (13) where B " ( p , q ) = the length of a shortest route between the ordered pair of nodes (p,q), (p e R, q ~ G), when each of m distinct nodes of G - {p,q} happens to lie, once and only once, on this (shortest) route; Fa- rn-1 = the length of a shortest route from the node q, (q ~ G), to the origin 0 q,p by passing, once and only once, through each of at least ~ - m - 1 nodes of G - C; 5) the length of a shortest route starting from the node p to the origin 0 by passing, once and only once, through each of at least ~ nodes of =
-
(p};
and Fq°p = the length of a shortest route from the node q to the origin 0, without obligation of passing through any other node and without passing through any node of C, when each of at least ~ - 1 distinct nodes of G - {p,q} happens to lie, once and only once, on the shortest route from p to q.
T o calculate F°,p, we first find the length of the shortest route, from q to 0, which with usual notations may be denoted by B~(q,O). Let M denote the set of n nodes of G - {q,0} corresponding to B"(q,O). If C n M = q~, then evidently Bn(q,0) = F°,p. If C n M :~ q~, let C n M = A. Now, consider the nodes in the set A and put the length of each arc, connecting nodes of A to other nodes of the network,
5) C denotes the set of nodes p, q and those m distinct nodes, of G - {p,q}, which happen to lie on the shortest route from p to q.
294
C . P . BAJAJ
equal to infinity. In this network, calculate the shortest distance between q and 0. This shortest distance gives the required ft/,p' 0 Equations (12) and (13) can be solved in the similar way as we solved equations (4) and (5). 5. The Shortest Route Through Sets of Specified Nodes - Dynamic Programming Formulation of the Problem and its Solution Consider a community centre 0 and let S~, (i = 1,2 .... , K), denote sets of welfare agencies to which people are referred from this community centre. Let there be m~ agencies in the set Sv Let i.j denote the j-th agency of the i-th set. Further, let each agency in the set Si cater to only one need Nv Besides these t< mi agencies located at different places, there are (N - 1) other places also i=1
through which a client may pass, if necessary. Distances between different agencies and also between places other than the agencies are known. A client comes to 0 with a set, A = { N 1 , N 2 , . . . , N x } , of K different needs, how should he be scheduled so as to meet all his needs and finally reach his destination N in such a way so that the total distance travelled is minimum ? This motivates the following definitions 6):
(
Suppose a network consisting of N + 1 + ~ m i nodes, which for convenience i=l
I
are denoted by the set R * = {0, i . j , I , 2 , . . . , N - 1 , N : j = 1,2, ... ,mi; i = l , 2, ..., K}. Let 0 denote the origin and N the destination. Let the sets of specified nodes be S~ = {i . j :j = 1,2 . . . . . mi}, (i = 1,2 . . . . . K), which are definite subsets of R*. We define the sets S* = { $ 1 , $ 2 . . . . . S x } , u S = S 1 u S 2 u ... u S x , S O = {i " j : i = 0,j = 0} = {0} and T* = S O u S 1 w S 2 u ... u S ~ . These definitions may be illustrated by reference to the undirected network shown in Fig. 1, in which the number on an arc denotes the distance between the pair of nodes connected by it. Here S 1 = {1.1,1.2}, S 2 = {2.1,2.2,2.3}, S 3 = {3.1,3.2} so that K = 3, m 1 = 2, m 2 = 3, m 3 = 2.
Thus R* = {0,1.1,1.2,2.1,2.2,2.3,3.1,3.2,1,2,N} = {O,i.j,l,2,N:j = 1 . . . . . m i ; i = 1,2,3}, S, = { i . j : j = 1 . . . . . m~}, (i = 1,2,3), S* = {{1.1,1.2}, {2.1,2.2,2.3}, {3.1,3.2}}, w S = {1.1,1.2,2.1,2.2,2.3,3.1,3.2}, 6) The mathematical model developed can be applied in many physical situations other than the one described here. The sets of specified nodes may represent sets of warehouses, sets of factories, sets of machines, sets of airports or sets of cities, etc. with correspondingly varied interpretations of the problem.
Some Constrained Shortest-Route Problems
295
10
and
Fig. 1
T* = {0,1.1,1.2,2.1,2.2,2.3,3.1,3.2}. The problem is to start from 0, pass through at least one node of every set of specified nodes and than reach the final destination N in such a way so that the total distance travelled is minimized. It is obligatory to pass through one node of every set of specified nodes; but if it is in the interest of minimizing the distance travelled we may pass through more than one node or more than once through a node of any set. The method of the second section can be extended to solve this problem. Corresponding to the functional equations (4) and (5), we get the following functional equations for solving this problem: S¢(p .q) = min [ D ' ( p . q , x . y ) ~"
+ S¢-'-l(x.y,p.q)], [~ < ¢ -
1, ~ - y ~ ~ ( s * -
{s~})]
(14)
{s~))]
(15)
and S¢(p" q) = min [D'(p- q , x " y) + S ° ( x . y , p . q)] , [~ > ¢ -
x,
1, ~ . y ~ ~ ( s * -
where Dr(p . q , x . y) = the length of a shortest route between the ordered pair of nodes (p. q , x " y) of two distinct sets, (p. q ~ T * , x . y ~ w S),
the index r merely indicates that r distinct members of S* - {Sn, Sx} happen to have at least one node each on this shortest route from p- q to x . y; S C-r- 1(x. y, p- q) = the length of a shortest route from the node x" y, (x" y ~ u S), to the final destination N, by passing through at least one node from each of at least ~ - r - 1 distinct member of S* - F ; 7) 7) F denotes the family of sets Sp, Sx and those r distinct members, of $* - {Sp,Sx}, which happen to have at least one node each on the shortest route from p . q to x- y.
296
C.P. BAJAJ
S ~ ( p . q ) = the length of a shortest route starting 8) from the node p. q
to the final destination N, by passing through at least one node from each of at least ~ distinct members of S* - {Sp}; and S o (x" y,p" q) = the length of a shortest route from the node x" y to the final destination N, without obligation of passing through any node of any other set of specified nodes, when at least ~ - 1 distinct members of S* - {Sp,Sx} happen to have at least one node each on the shortest route from p. q to x" y. Equations (14) and (t5) can be solved on the lines adopted to solve equations (4) and (5). 6. Ordering of Sets - A Simplified Version of the Problem So far, we have imposed no restrictions on the order in which the sets St are entered, that is, the order in which the needs N~ are satisfied. The objective was that all sets S~ must be visited in some way, i.e., all needs N~ must be satisfied in some way. In practice, it can be the case that the general medical examination of a client can be done if his blood test and X-Ray reports are available. Here, the general medical examination, b l o o d test and X-Ray reports are the different needs. This leads us to consider the case when the sets Si are to be visited in a specified order. Once the order is fixed, the problem becomes much easier. We suppose that the sets are to be visited in the order $I, $2 ..... SK - that is, first $1 is to be visited, then $2, then $3 and so on. The problem, therefore, is to obtain the shortest route from 0 to N, which passes through at least one node of each of the sets $1,$2, ... ,SK in this order. The algorithm presented in section 3 can be extended to solve this problem.
7. Numerical Experience 7.1 Example Consider the network shown in Fig. 2, in which the number on an arc denotes the distance between the pair of nodes connected by it, and the arrowhead indicates the direction of its orientation. Here R = {0,1,2 .... ,8,N} and S = {1,2,3,4}. The problem is to find the shortest route, from 0 to N and passing through all nodes of S. Numbers in the parentheses ( ), occurring in the tables below and hereafter, denote the nodes that lie on the path. For Tables (3-4), the values, obtained while calculating f~, have been ranked in the order of increasing lengths on the right hand side. The entry ranked 1 represents the value off~, ~ = 1,2. s) With single node in the parentheses ( ) , we mean that no path is considered before the node in the parentheses,
Some Constrained Shortest-Route Problems
/'~'-,,jo
297
7
Fig. 2 H e r e R = {0,1,2,. . . . . 8,N} a n d S = {1;2,3,4}. Table 1 (To) nodes D'(p,q)
0
(From) 1 Nodes 2 3 4
R v
1
2
3
4
18 (5) 0 30 (3) 15 42 (2,3)
21 (6) 30 (3) 0 15 12
33 (5,1) 15 15 0 27 (2)
17 (6) 42 (3, 2) 12 27 (2) 0
p q
1
2
3
0 1 2 3 4
0 1 0 2
0
1
1
0
0 0
0 1
Table 2
q
IL
1 2 3 4
23 (3) 8 8 15
The table for f ] can be constructed on the lines adopted to construct Table 4. Using equations (4) and (5), we get, fo4 = min [75(5,1,3,2,4),98(6,2,4,2,3,1,3),75(5,1,3,2,4),82(6,4,2,3,1,3)] = 75(5,1,3,2,4) The optimal path is thus: 0 ~ 5 --' 1 -~ 3 ~ 2 --' 4--* N . 7.2
Example
Again consider the directed network shown in Fig. 2. The problem is to determine the shortest route, from 0 to N, on which the nodes 1, 2, 3, 4 occur in this order.
298
C.P. B ~ Table 3 Ranks
rain [ - , 38 (3,2), 23 (3), 57 (3,2,4)] rain [53 (3,1,3), - , 23 (3), 27 (4)] min [38 (1,3), 23 (2), - , 42 (2,4)] rain [65 (2, 3,1, 3), 20 (2), 35 (2,3), - ]
1
2
3
23 (3)
38 (3,2)
57 (3,2,4)
23 (3)
27 (4)
53 (3,1,3)
23 (2)
38 (1,3)
42 (2,4)
20 (2)
35 (2, 3)
65 (2, 3,1, 3)
- = Not calculated, because of equation (6).
Table 4 Ranks 1
min [ - , 38 (3,2), 38 (3,2), 57 (3,2,4)] rain [53 (3,1,3), - , 53 (3,1,3), 47 (4, 2, 3)] 87 (3,1,3,2,4), -
-
2
38 (3,2)
57 (3,2,4)
47(4,2,3)
53 (3,1,3)
77(4,2,3,1,3)
87(3,1,3,2,4)
42 (2,4)
53 (1,3,2)
72(1,3,2,4)
92 (2,4,2,3,1,3)
35 (2,3)
65 (2,3,1,3)
77(4,2,3,1,3) rain [53 (1,3,2), 42 (2,4), - , 42 (2, 4)] 72 (1,3,2,4), -- , - , 92 (2,4,2,3,1,3) min [65 (2,3,1,3), 35 (2, 3), 35 (2,3), - ] --
....
= Not calculated, because of equations (4) and (5), and (10) and (11). The value obtained by using equations (10) and (11), to g e t f ~ for the table off~, as all the entries in the able off~ fail to give the desired value (with a feasible route) for f ~ r
Some Constrained Shortest-Route Problems
299
Applying the algorithm of section 3 it can be easily seen that the desired shortest route is 0~5~1--,3~2~3~2~4~N of length 105.
7.3 Travelling-Salesman Problems The method presented in section 4 has been tested on a large number of travelling-salesman problems. The most prominent of these were: a 6-city problem given in DANTZIG, FULKERSON, JOHNSON [1954] and FLOOD [1956], a 20-city problem in CROES [1958], a 25-city problem in HELD, KARP [1962], a 33-city problem in KARG, TrIo~n'soN [1964] and a 42-city problem in Dnt,~TZm, FULI~RSObr, JOHNSON [1954]. These problems were solved by hand in approximately 15 minutes, 20 hours, 25 hours, 30 hours and 40 hours respectively. The solving times mentioned above were determined the honest way: all the work involved was done by hand. 7.4 Examples Consider the network shown in Fig. 1. The problem is to find the shortest route, from 0 to N, on which the sets S 1, $2,$3 have got at least one node each. Using equations (14) and (15) ,it can be seen that the Optimal path is: 0 ~ 1 " 2 ~ 1 "1 --'3"1 ~ 2"2--* 2"3 ~ 1 ~ N of length 14. The shortest route, from 0 to N, on which the sets $1,$2,$3 have got at least one node each, in this order, is seen to be 0~ 1.2~
1.1 ~ 2 . 2 ~
3.1-,2-2~2"3
~ 1 --* N
or,
0--* 1"2 ~ 1 ' 1 ~
3" 1 ~ 2"2 - 3"1 --* 2 " 2 - * 2"3 ~ 1 ~ N
of length 16.
8. Computational Aspects For each f~, we require Dr(p,q) and the column j of the table of fq~-r-1; j,q = 1,2,..., K subject to the extra condition that there must be at least ~ - r - 1 distinct nodes of S - V on the path from q to N, (j is so chosen as to satisfy this extra condition for which we may have to apply the procedure represented through equations (10) and (11)). Hence, the memory requirement for a digital computer is small and the iterative procedure is a feasible method for either hand or machine computation for values of K of the order of magnitude of 30 or 40. The same can be said for the method for the travelling-salesman problem (see sub-
300
C.P. BAJAJ
section 7.3). It is easily seen that the iterative scheme discussed in the fifth section K
is a feasible m e t h o d for either h a n d or machine c o m p u t a t i o n for values of ~ mi of the order of m a g n i t u d e of 30 or 40. ~= 1 It m a y be observed here that BELLMAN'S m e t h o d [1962], for solving the travelling-salesman p r o b l e m , e m p l o y i n g the functional e q u a t i o n technique of d y n a m i c p r o g r a m m i n g is c o m p u t a t i o n a l l y feasible for p r o b l e m s up to 17 cities. HELD and KARP [1962] have used d y n a m i c p r o g r a m m i n g with partitioning to give an a p p r o x i m a t e algorithm for solving the p r o b l e m up to 48 cities. M a k i n g conclusions on the existing techniques for solving this problem, BELLMORE and NEMHAUSER [1968] r e c o m m e n d d y n a m i c p r o g r a m m i n g for p r o b l e m s up to 13 cities. W e have shown that the functional e q u a t i o n technique of d y n a m i c p r o g r a m m i n g , c o m b i n e d with an efficient shortest-path algorithm, yields a m e t h o d which is readily accessible to either h a n d or machine c o m p u t a t i o n for p r o b l e m s of realistic magnitude. T h e m e t h o d is distinguished by the fact that it is a m e t h o d of exhaustion, i.e., it converges after a finite n u m b e r of iterations, b o u n d e d in advance. Acknowledgement
The a u t h o r wishes to express his indebtedness to Dr. S, M. SINHA, Reader in O p e r a t i o n s Research, University of Delhi, for his valuable guidance, encouragem e n t and helpful suggestions. References
BELLMAN,R. E.: On a Routing Problem, Quart. AppL Math., Vol. 16, 1958, p. 87-90.
: Dynamic Programming Treatment of the Travelling Salesman Problem, Journal of ACM, Vol. 9, 1962, p. 61-63. BELLMAN, R. E., and S. DREYtqJS: Applied Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1962. BELLMORE,M., and G. L. NEMHAUSER:The Travelling Salesman Problem: A Survey, Opns. Res., Vol. 16, No. 3, 1968, p. 538-558. CROES, G. A.: A Method for solving Traveling Salesman Problems, Opns. Res., Vol. 6, 1958, p. 791-812. DANTZIG,G. B. : Discrete-Variable Extremum Problems, Opns. Res., Vol. 5, 1957, p. 266-277. DANTZlG,G. B, D. R. FULr~RSONand S. M. JOrtNSON:Solution of a Large-Scale Travelling Salesman Problem, Opns. Res., Vol. 2, 1954, p. 393-410. - : On a Linear Programming Combinatorial Approach to the Travelling Salesman Problem, Opns. Res., Vol. 7, 1959, p. 58-66. DgEYF~S, S. E. : An Appraisal of Some Shortest-Path Algorithms, Opns. Res., Vol. 17, No. 3, 1969, p. 395-412. FARBEY,B. A., A. H. LAND,and J. D. MURCHLAND:The Cascade Algorithm for finding all Shortest Distances in a Directed Graph, Management Science, Vol. 14, No. t, September, 1967, p. 19-28. FLOOD,M. M.: The Travelling-Salesman Problem, Opns. Res., Vol. 4, No. 1, 1956, p. 61-75. HELD, M., and R. M. KARP: A Dynamic Programming Approach to Sequencing Problems, SIAM, Vol. 10, 1962, p. 196-210. KALABA,R,: On Some Communication Network Problems, Combinatorial Analysis, Proc. Syrup. Appl. Math., Vol. 10, 1960, p. 261-280. KARG,R. L., and G. L. THOMPSON:A Heuristic Approach to Traveling Salesman Problems, Management Sci., Vol 10, 1964, p. 225-248. -
Some Constrained Shortest-Route Problems
301
KAUFMANN,A., and R. CRUON: La Programmation Dynamique: Gestion Scientifique Sequentielle, Dunod, Paris, 1965. LAND, A. H., and S. W. STAIRS:The Extension of the Cascade Algorithm to Large Graphs, Management Science, Vol. 14, No. 1, September, 1967, p. 29-33. MILLS, G. : A Decomposition Algorithm for the Shortest-Route Problem, Opns. Res., Vol. 14, 1966, p. 279-291. PEART, R. M., P. H. RANDOLPH, and T. E. BARTLETT;The Shortest-Route Problem, Opns. Res., Vol. 8, 1960, p. 866-868. POLLACK, M., and W. WIEBENSON:Solutions of the Shortest-Route Problem - A Review, Opns. Res., Vol. 8, 1960, p. 224-230. SAKSENA)J, P., and S. KUMAR:The Routing Problem with 'K' Specified Nodes, Opns. Res., Vol. 14, 1966, p. 909-913. SHIMBEL,A. : Structure in Communication Nets, Proceedings of the Symposium on Information Networks, Polytechnic Institute of Brooklyn, April 12-14, 1954. SINHA, S. M., and C. P. BAJAJ: The Maximum Capacity Route Through A Set of Specified Nodes, Cahiers du Centre d'Etudes de Recherche Op6rationnelle, Vol. 11, No. 3, 1969, p. 133-138,