Skip to main content
Log in

Analysis of a Rollout Approach to Sequencing Problems with Stochastic Routing Applications

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The paper considers sequencing problems, the traveling salesman problem being their natural representative. It studies a rollout approach that employs a cyclic heuristic as its main base algorithm. The theoretical analysis establishes that it is guaranteed to improve (at least in a weak sense) the quality of any feasible solution to a given sequencing problem. Besides other applications, the paper shows that it is well suited for applications that are embedded in dynamic and stochastic environments. The computational performance of the approach is investigated with applications to two stochastic routing problems. The dynamic version of the heuristic appears to be the first algorithm available in the literature to approximately solve a variant of one of these problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Barr, S., B.L. Golden, J.P. Kelly, M.G.C. Resende, and W.R. Stewart. (1995). “Designing and Reporting on Computational Experiments with Heuristic Methods.” Journal of Heuristics 1, 9–32.

    Google Scholar 

  • Bertsekas, D.P. (1995). Dynamic Programming and Optimal Control. Vols. I and II Belmont: Athena Scientific.

    Google Scholar 

  • Bertsekas, D.P. (1998). Network Optimization: Continuous and Discrete Models. Belmont: Athena Scientific.

    Google Scholar 

  • Bertsekas, D.P. and D.A. Castanon. (1998). “Rollout Algorithms for Stochastic Scheduling Problems.” Journal of Heuristics 5, 89–108.

    Google Scholar 

  • Bertsekas, D.P. and J.N. Tsitsiklis. (1996). Neuro-Dynamic Programming. Belmont: Athena Scientific.

    Google Scholar 

  • Bertsekas, D.P., J.N. Tsitsiklis, and C. Wu. (1997). “Rollout Algorithms for Combinatorial Optimization.” Journal of Heuristics 3, 245–262.

    Google Scholar 

  • Bertsimas, D.J. (1992). “AVehicle Routing Problem with Stochastic Demands.” Operations Research 40, 574–585.

    Google Scholar 

  • Bertsimas, D.J., P. Chervi, and M. Peterson. (1995). “Computational Approaches to Stochastic Vehicle Routing Problems.” Transportation Science 29, 342–252.

    Google Scholar 

  • Bertsimas, D.J. and R. Demir. (2002). “An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems.” Management Science 48, 550–565.

    Google Scholar 

  • Bertsimas, D.J., P. Jaillet, and A. Odoni. (1990). “A Priori Optimization.” Operations Research 38, 1019–1033.

    Google Scholar 

  • Bertsimas, D.J. and I. Popescu. (2000). “Revenue Management in a Dynamic Network Environment.” Forthcoming in Transportation Science.

  • Bertsimas, D.J. and D. Simchi-Levi. (1996). “A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty.” Operations Research 44, 216–304.

    Google Scholar 

  • Bertsimas, D.J., C.P. Teo, and R. Vohra. (1998). “Greedy, Randomized and Approximate Dynamic Programming Algorithms for Facility Location Problems.” Technical Report, MIT, Cambridge, MA.

    Google Scholar 

  • Fisher, M. (1995). “Vehicle Routing.” In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.), Network Routing,Vol.8 of Handbooks in Operations Research and Management Science. Amsterdam: Elsevier.

    Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman.

    Google Scholar 

  • Gendreau, M., G. Laporte, and R. Séguin. (1995). “An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers.” Transportation Science 29, 143–155.

    Google Scholar 

  • Gendreau, M., G. Laporte, and R. Séguin. (1996). “Stochastic Vehicle Routing.” European Journal of Operational Research 88, 3–12.

    Google Scholar 

  • Glover, F. (1998a). Personal Communication.

  • Glover, F. (1998b). “A Template for Scatter Search and Path Relinking.” In J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers (eds.), Artificial Evolution, Lecture Notes In Computer Science, 1363. Berlin: Springer-Verlag.

    Google Scholar 

  • Glover, F. and M. Laguna. (1997). Tabu Search. Boston: Kluwer.

    Google Scholar 

  • Golden, B.L. and A.A. Assad (eds.). (1988). Vehicle Routing: Methods and Studies. Amsterdam: North-Holland.

    Google Scholar 

  • Haimovich, M. and A.H.G. Rinnooy Kan. (1985). “Bounds and Heuristics for Capacitated Routing Problems.” Mathematics of Operations Research 10, 527–542.

    Google Scholar 

  • Held, M. and R.M. Karp. (1962). “A Dynamic Programming Approach to Sequencing Problems.” Journal of the Society for Industrial and Applied Mathematics 10, 225–248.

    Google Scholar 

  • Jayawardena, T. and S. Yakowitz. (1996). “Methodology for Stochastic Graph Completion-Time Problems.” INFORMS Journal on Computing 8, 331–343.

    Google Scholar 

  • Kao, E.P.C. (1978). “A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem.” Operations Research 26, 1033–1045.

    Google Scholar 

  • Laporte, G. (1992). “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms.” European Journal of Operational Research 59, 345–358.

    Google Scholar 

  • Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (eds.). (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: Wiley.

    Google Scholar 

  • McGovern, A. and E. Moss. (1999). “Scheduling Straight-Line Code Using Reinforcement Learning and Rollouts.” Advances in Neural Information Processing Systems 11, 903–909.

    Google Scholar 

  • Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. New York: Wiley.

    Google Scholar 

  • Powell, W.B., P. Jaillet, and A. Odoni. (1995). “Stochastic and Dynamic Networks and Routing.” In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.), Network Routing, Vol. 8 of Handbooks in Operations Research and Management Science. Amsterdam: Elsevier.

    Google Scholar 

  • Psaraftis, H.N. (1995). “Dynamic Vehicle Routing.” Annals of Operations Research 61, 143–164.

    Google Scholar 

  • Savelsbergh, M.W.P. and M. Goetschalckx. (1995). “A Comparison of the Efficiency of Fixed versus Variable Vehicle Routes.” Journal of Business Logistics 16, 163–187.

    Google Scholar 

  • Secomandi, N. (1998). “Exact and Heuristic Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands.” Ph.D. Thesis, University of Houston, Houston, TX.

    Google Scholar 

  • Secomandi, N. (2000). “Comparing Neuro-Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands.” Computers and Operations Research 27, 1201–1225.

    Google Scholar 

  • Secomandi, N. (2001). “A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands.” Operations Research 49, 796–802.

    Google Scholar 

  • Stewart, W.R. and B.L. Golden. (1983). “Stochastic Vehicle Routing: A Comprehensive Approach.” European Journal of Operational Research 14, 371–385.

    Google Scholar 

  • Sutton, R. and A.S. Barto. (1998). Reinforcement Learning. Cambridge: MIT Press.

    Google Scholar 

  • Tesauro, G. and G.R. Galperin. (1997). “On-Line Policy Improvement Using Monte Carlo Search.” Advances in Neural Information Processing Systems 9, 1068–1074.

    Google Scholar 

  • Yang, W.H., K. Mathur, and R.H. Ballou. (2000). “Stochastic Vehicle Routing with Restocking.” Transportation Science 34, 99–112.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Secomandi, N. Analysis of a Rollout Approach to Sequencing Problems with Stochastic Routing Applications. Journal of Heuristics 9, 321–352 (2003). https://doi.org/10.1023/A:1025605803490

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1025605803490

Navigation