A fast method for solving the stagecoach problem of Harvey Wagner [4] illustrated with a prototype  example for dynamic programming  from F. Hillier and G. Lieberman [3], Second Edition

Jsun Yui Wong

 Here is an illustration for solving Wagner’s stagecoach problem (a prototype example for dynamic programming [3, Hillier and Lieberman], pp. 425-430).  All the good ideas in the present paper are from the five References listed below: Anderson et al. [1, pp. 820-829], Ecker and Kupferschmid [2 , pp. 347-352], Hillier and Lieberman [3, pp. 424-433], Wagner [4, pp.  262-270], and Wikipedia [5].

Please excuse this paper’s digression from the present blog. 

Please disregard the following two pictures and the four dotes.

Please disregard the expression Title of Article: and the three dots just above the second last picture and the expression References: shown below the last picture (figure).

Please add the numbers just above the nodes of the second last picture [3, Hillier, p. 426, Figure 10.1] to the corresponding small long rectangles of the last picture.  Then the number inside each of the small rectangle above each node stands for the minimal (optimal) cost from that node to the final node, which is node 10 (note J or T), the destination.  Thus, the last two pictures show that the optimal routes are A-D-E-H-J, A-D-F-I-J, and A-C-E-H-J for the minimum total cost of 11; see Hillier and Lieberman [3, pp. 429-439].

A first step towards a computer version of the procedure above is shown below:

0 DEFINT J, K, B, X, A, N

2 DIM A(3513), X(3513), N(55)

81 FOR JJJJ = -32000 TO -31999

    89 RANDOMIZE JJJJ

    90 M = -1.5D+38

    177 N(10) = 0

    178 N(8) = 3 + 0

    179 N(9) = 4 + 0

    184 N(5) = 1 + 3

    186 N(6) = 3 + 4

    189 N(7) = 3 + 3

    192 N(2) = 4 + 7

    194 N(2) = 7 + 4

    196 N(3) = 3 + 4

    198 N(4) = 4 + 4

    199 N(4) = 1 + 7

    201 N(1) = 4 + 7

    203 N(1) = 3 + 8

    1888 PRINT N(1), N(2), N(3), N(4), N(5), N(6), N(7), N(8), N(9), N(10), JJJJ

1999 NEXT JJJJ

This BASIC computer program was run with qbv1000-win [5], and the corresponding output through JJJJ=-31999 is as follows:

11       11      7      8      4

7      6      3      4    0

-32000

11       11      7      8      4

7      6      3      4      0

-31999

The output above was obtained in one second of wall-clock time.

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] Harvey Wagner, Principles of operations research, second edition, Prentice –Hall, Inc., 1975.

[5] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.