Finding shortest routes in Harvey M. Wagner's stagecoach problems
Jsun Yui Wong
The following example is a shortest route problem from Wagner [6, pp. 265-270], a prototype example for dynamic programming, Hillier and Lieberman [3, pp. 425-430]. It is essential that one takes a good look of the network (picture) on p. 266 of Wagner [6, p. 266]. Anderson et al. [1, pp. 820-829] and Ecker and Kupferschmid [2 , pp. 347-352], Jensen [4, pp. 99-103], and Murty [5, pp. 473-475 ] are very informative as well.
{2} {5} {8}
{1} {3} {6} {10}
{4} {7} {9}
Figure 8.1 Stagecoach Problem, from Wagner [6, p. 266], simplified for illustration only.
Some small changes shown below have been added to the original Figure 8.1, Wagner [6, p. 266], where much more data is given there than given here; please take a good look]. P01, P02, P03, …, P10 are described in line 351 through line 430. P05, for example, stands for the shortest distance from P05 to the destination point, P01.
P07 P04 P02
{2} {5} {8}
P10 P08 P05 P01
{1} {3} {6} {10}
P09 P06 P03
{4} {7} {9}
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 = 1
358 P03 = 4
362 P04 = 8
369 P05 = 4
373 P06 = 5
378 P07 = 16
389 P08 = 12
397 P09 = 18
430 P10 = 17
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, 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 1 4 8 4
5 16 12 18 17
-32000
0 1 4 8 4
5 16 12 18 17
-31999
0 1 4 8 4
5 16 12 18 17
-31998
So path {1}-{3}, {3}-{7}, {7}-{9}, {9}-{10} is an optimal path of length 5+7+1+4=17.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds (or 1 second) 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