Substance

Solving two stagecoach examples with dynamic programming

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.

Finding shortest routes in Harvey M. Wagner's stagecoach problems

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.

 

 

Finding shortest routes in staged acyclic networks

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.

 

An attempt to obtain a unified algorithm for dynamic programming

An attempt to obtain a unified algorithm for dynamic programming

Jsun Yui Wong

The followimg example is the stagecoach problem (the shortest route problem ) from Jensen [4, pp. 102-103].  It is essential that  one appreciates the network (picture) on p. 102 [4].  This illustration is similar to Wagner’s stagecoach problem (a prototype example for dynamic programming except that stages are not used in the present paper [3, Hillier and Lieberman, pp. 425-430].  Anderson et al. [1, pp. 820-829], Ecker and Kupferschmid [2 , pp. 347-352], Hillier and Lieberman [3, pp. 424-433], Wagner [5, pp.  262-270], and Wikipedia [6] are also very informative.

                  {6}

             {3}          {8}

      {1}         {5}            {9}

             {2}          {7}

                     {4}

Figure 5.1 Road Network Example for Dynamic Programming, from [4, p. 102], (simplified for illustration only) 

Some small changes shown below have been added to the original Figure 5.1 [4, p. 102], P01, P02, P03, …, P09, which are described in line 351 through line 397.  P05, for example, stands for the shortest distance from P05 to the destination point, P01.

                  P04

                   {6}

            P07        P02

            {3}         {8}

      P09      P05          P01

      {1}         {5}            {9}

            P08        P03

            {2}         {7}

                    P06

                    {4}

P01 to P09 are described in line 351 to line 397.

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 = 9 + 0

    358 P03 = 6 + 0

    362 P04 = 2 + 9

    369 P05 = 5 + 6

    373 P06 = 9 + 6

    378 P07 = 3 + 11

    389 P08 = 7 + 11

    397 P09 = 8 + 14

    2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, JJJJ

2222 NEXT JJJJ

This BASIC computer program was run with qbv1000-win [6], and the complete output through JJJJ=-31998 is as follows:

0   9   6   11   11

15   14   18   22   -32000

0   9   6   11   11

15   14   18   22   -31999

0   9   6   11   11

15   14   18   22   -31998

So path {1}-{3}, {3}-{5}, {5}-{7}, {7}-{9} is an optimal path of length 22. 

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

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