Solving two stagecoach problems with dynamic programming
Jsun Yui Wong
Using the same procedure as the last three papers, this paper easily solves two dynamic programming networks. The immediately following dynamic programming problem is from Sathyapriva, Swathy,Srivarshini, and Bhavatarini [6, pp. 344-346]. It is essential that one takes a good look of the network (picture) on p. 344 of Sathyapriva et al. [6, p. 344].
stage 1 stage 2 stage 3 stage 4 stage 5
{A} {E} {H} {K}
{B}
{X} {C} {F} {I} {L} {Y]
Input output
{D} {G} {J} {M}
Above is a simplified version of their network [6, p. 48] and is for illustration only. Some small changes shown below have been added to the original picture, Sathyapriva et al. [6, p. 344], where much more data is given there than given below; please take a good look]. P01, P02, P03, …, P15 are described in line 351 through line 497. P05, for example, stands for the shortest distance from P05 to the destination point, P15.
stage 1 stage 2 stage3 stage 4 stage 5
15+50 10+40 20+20 20+0
P11 P08 P05 P02
{A} {E} {H} {K}
10+21
P12
{B}
16+24 3+21 2+19 10+9 15+0 0
P15 P13 P09 P06 P03 P01
{X} {C} {F} {I} {L} {Y]
Input output
3+21 2+19 10+9 9+0
P14 P10 P07 P04
{D} {G} {J} {M}
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 = 20 + 0
358 P03 = 15 + 0
362 P04 = 9 + 0
369 P05 = 20 + 20
373 P06 = 10 + 9
375 P07 = 10 + 9
389 P08 = 10 + 40
397 P09 = 2 + 19
430 P10 = 2 + 19
432 P11 = 15 + 50
434 P12 = 10 + 21
475 P13 = 3 + 21
489 P14 = 3 + 21
497 P15 = 16 + 24
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, P11, P12, P13, P14, P15, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [9], and the complete output through JJJJ=-31998 is as follows:
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-32000
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-31999
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-31998
So path {P01}-{P14}, {P14}-{P10}, {P10}-{P06}, {P06}-{P04}, {P04}-{P01} is an optimal path of length 16+3+2+10+9=40.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds (or 1 second) when one counts from “Starting program…”.
Example Two
The following dynamic programming network is from Ullmann [6, pp. 48-49]. It is essential that one takes a good look of the network (picture) on p. 48 of Ullmann [7, p. 48, Figure 5-3].
{A} {D} {H}
{S} {B} {E} {I} {P}
{C} {F} {J}
{G}
Above is a simplified version of Figure 5.3 of Ullmann [7, p. 48] and is for illustration only. Some small changes shown below have been added to the original Figure 5.3,Ullmann [7, p. 48], where much more data is given there than given here; please take a good look]. P01, P02, P03, …, P12 are described in line 351 through line 434. P05, for example, stands for the shortest distance from P05 to the destination point, P01.
START STAGES FINISH
a b c
1+6 1+4 4+0
P09 P05 P02
{A} {D} {H}
2+10 5+5 2+2 2+0 0
P12 P10 P06 P03 P01
{S} {B} {E} {I} {P}
3+4
2+7 5+2 4+0
P11 P07 P04
{C} {F} {J}
2+4
P08
{G}
The following computer program also 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 = 4 + 0
358 P03 = 2 + 0
362 P04 = 4 + 0
369 P05 = 1 + 4
373 P06 = 2 + 2
378 IF RND < .5 THEN P07 = 3 + 4 ELSE P07 = 5 + 2
389 P08 = 2 + 4
397 P09 = 1 + 6
430 P10 = 5 + 5
432 P11 = 2 + 7
434 P12 = 2 + 10
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, P11, P12, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [9], and the complete output through JJJJ=-31998 is as follows:
0 4 2 4 5
4 7 6 7 10
9 12 -32000
0 4 2 4 5
4 7 6 7 10
9 12 -31999
0 4 2 4 5
4 7 6 7 10
9 12 -31998
So path {S}-{B}, {B}-{D}, {D}-{H}, {H}-{P} is an optimal path of length 2+5+1+4=12.
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 for the two examples above 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] S. Sathyapriva, S. Swathi, S. Srivarshini, P, Bhavatarini, Dynamic programming in stage coach problem and cargo loading problem, International Journal of Scientific Research in Science and Technology (www.ijsrst.com), January-February-2019: 342-348.
[7] John E. Ullmann, Theory and Problems of Quantitative Methods in Management, SCHAUM’S OUTLINE SERIES IN BUSINESS, McGRAW-HILL BOOK COMPANY, Inc. 1976.
[8] Harvey Wagner, Principles of operations research, second edition, Prentice –Hall, Inc., 1975.
[9] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
Comments