Finding shortest routes in staged acyclic networks
Jsun Yui Wong
The following example is a shortest route problem from Murty [5, pp. 473-475], a staged acyclic network, Murty [5, p. 475]. It is essential that one appreciates the network (picture) on p. 475 [5; please take a look]. This illustration is similar to Wagner’s stagecoach problem , a prototype example for dynamic programming, Hillier and Lieberman [3, pp. 425-430]. Anderson et al. [1, pp. 820-829], Ecker and Kupferschmid [2 , pp. 347-352], and Wagner [5, pp. 262-270] are also very informative.
{5}
{2} {9}
{6} {12}
{1} {3} {10} {14}
{7} {13}
{4} {11}
{8}
Figure 12.7 Network Example for Dynamic Programming, from Murty [5, p. 475], simplified for illustration only.
Some small changes shown below have been added to the original Figure 12.7, Murty [5, p. 475], where much more data is given than given here; please take a look], P01, P02, P03, …, P14, which are described in line 351 through line 430. P05, for example, stands for the shortest distance from P05 to the destination point, P01.
P07
{5}
P11 P04
{2} {9}
P08 P02
{6} {12}
P14 P12 P05 P01
{1} {3} {10} {14}
P09 P03
{7} {13}
P13 P06
{4} {11}
P{10}
{8}
P01 to P14 are described in line 351 to line 430.
To solve the problem above, the following computer program uses the Principle of Optimality of Dynamic Programming, which is “If a particular node is on the optimal route, then the shortest path from that node to the end is also on the optimal route, “ Anderson, Sweeney, and Williams [1, p. 821].
0 REM DEFDBL A-Z
1 REM DEFINT I, J, K
2 DIM B(99), N(99), A(2002), G(128), J44(222), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J(99), AA(99), HR(32), HHR(32), LHS(44), PLHS(44), LB(22), UB(22), PX(44), PN(22), NN(22)
85 FOR JJJJ = -32000 TO 32000
88 RANDOMIZE JJJJ
351 P01 = 0
355 P02 = 14 + 0
358 P03 = 13 + 0
362 P04 = 8 + 13
369 P05 = 14 + 13
373 P06 = 12 + 13
378 P07 = 12 + 21
389 P08 = 6 + 21
397 P09 = 3 + 27
423 P10 = 7 + 25
425 P11 = 4 + 27
427 P12 = 4 + 30
429 P13 = 7 + 30
430 P14 = 3 + 34
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, P11, P12, P13, P14, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [7], and the complete output through JJJJ=-31998 is as follows:
0 14 13 21 27
25 33 27 30 32
31 34 37 37 -32000
0 14 13 21 27
25 33 27 30 32
31 34 37 37 -31999
0 14 13 21 27
25 33 27 30 32
31 34 37 37 -31998
So path {1}-{3}, {3}-{7}, {7}-{10}, {10}-{13}, {13}-{14} is an optimal path of length 37.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds when one counts from “Starting program…”. The computer system used here is the same as that used by the preceding paper.
References
[1] D.R. Anderson, D. J. Sweeney, I. A. Williams, An introduction to management science: quantitative approaches to decision science, ninth edition, South-Western College Publishing, 2000.
[2] J. G. Ecker, M. Kupferschmid, Introduction to operations research, John Wiley and Sons, Inc., 1988.
[3] F. S. Hillier, G. J. Lieberman, Introduction to operations research, sixth edition, McGraw Hill, Inc.
[4] Paul A. Jensen, Microsolve/Operations Research, Holden-Day, Oakland, California.
[5] Katta G. Murty, Operations research, Prentice –Hall, Inc., 1995.
[6] Harvey Wagner, Principles of operations research, second edition, Prentice –Hall, Inc., 1975.
[7] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
Comments