Estimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem

References

• Bentley J. L. Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. (1992) 4:387–411Link, Google Scholar
• Bertsimas D. Probabilistic combinatorial optimization problems. (1988) . Ph.D. thesis, Massachusetts Institute of Technology, CambridgeGoogle Scholar
• Bertsimas D., Jaillet P., Odoni A. A priori optimization. Oper. Res. (1990) 38:1019–1033Link, Google Scholar
• Bianchi L. Ant colony optimization and local search for the probabilistic traveling salesman problem: A case study in stochastic combinatorial optimization. (2006) . Ph.D. thesis, Université Libre de Bruxelles, Brussels, BelgiumGoogle Scholar
• Bianchi L., Campbell A. Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem. Eur. J. Oper. Res. (2007) 176:131–144Crossref, Google Scholar
• Bianchi L., Knowles J., Bowler N. Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms. Eur. J. Oper. Res. (2005) 162:206–219Crossref, Google Scholar
• Bianchi L., Birattari M., Chiarandini M., Manfrin M., Mastrolilli M., Paquete L., Rossi-Doria O., Schiavinotto T. Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J. Math. Model. Algorithms (2006) 5:91–110Crossref, Google Scholar
• Birattari M., Balaprakash P., Stützle T., Dorigo M. Extended empirical analysis of estimation-based local search for stochastic combinatorial optimization. (2007) . IRIDIA Supplementary page, http://iridia.ulb.ac.be/supp/IridiaSupp2007-001/Google Scholar
• Chervi P. A computational approach to probabilistic vehicle routing problems. (1988) . Master's thesis, Massachusetts Institute of Technology, CambridgeGoogle Scholar
• Fousse L., Hanrot G., Lefèvre V., Pélissier P., Zimmermann P. MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Software (2007) 33:1–15Crossref, Google Scholar
• Fu M. C. Optimization via simulation: A review. Ann. Oper. Res. (1994) 53:199–248Crossref, Google Scholar
• Fu M. C. Optimization for simulation: Theory vs. practice. INFORMS J. Comput. (2002) 14:192–215Link, Google Scholar
• Griffith A.GCC: The Complete Reference (2002) (McGraw Hill/Osborne Media, San Francisco) Google Scholar
• Gutjahr W. J., Albrecht A., Steinhofl K. A converging ACO algorithm for stochastic combinatorial optimization. Stochastic Algorithms: Foundations and Applications, Lecture Notes in Computer Science (2003) 2827(Springer-Verlag, Berlin) 10–25Crossref, Google Scholar
• Gutjahr W. J., Dorigo M., Birattari M., Blum C., Gambardella L. M., Mondada F., Stützle T. S-ACO: An ant based approach to combinatorial optimization under uncertainity. Ant Colony Optimization and Swarm Intelligence, 5th International Workshop, ANTS 2004, Lecture Notes in Computer Science (2004) 3172(Springer-Verlag, Berlin) 238–249Crossref, Google Scholar
• Hoos H., Stützle T.Stochastic Local Search: Foundations and Applications (2005) (Morgan Kaufmann, San Francisco) Google Scholar
• IEEE IEEE standard for binary floating-point arithmetic. (1985) (Institute of Electrical and Electronics Engineers, New York) Google Scholar
• Jaillet P. Probabilistic traveling salesman problems. (1985) . Ph.D. thesis, Massachusetts Institute of Technology, CambridgeGoogle Scholar
• Johnson D. S., McGeoch L. A., Aarts E. H. L., Lenstra J. K. The travelling salesman problem: A case study in local optimization. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, UK) 215–310Google Scholar
• Johnson D. S., McGeoch L. A., Rego C., Glover F. 8th DIMACS implementation challenge. (2001) . Retrieved January 2007, http://www.research.att.com/∼dsj/chtsp/Google Scholar
• Kleywegt A. J., Shapiro A., Homem de Mello T. The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. (2002) 12:479–502Crossref, Google Scholar
• Lourenço H. R., Martin O., Stützle T., Glover F., Kochenberger G. Iterated local search. Handbook of Metaheuristics, International Series in Operation Research and Management Science (2002) 57(Kluwer Academic Publishers, Norwell, MA) 321–353Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Penky J. F., Miller D. L. A staged primal-dual algorithm for finding a minimum cost perfect two-matching in an undirected graph. ORSA J. Comput. (1994) 6:68–81Link, Google Scholar
• Pichitlamken J., Nelson B. L. A combined procedure for optimization via simulation. ACM Trans. Model. Comput. Simulation (2003) 13:155–179Crossref, Google Scholar
• Verweij B., Ahmed S., Kleywegt A. J., Nemhauser G., Shapiro A. The sample average approximation method applied to stochastic routing problems: A computational study. Comput. Optim. Appl. (2003) 24:289–333Crossref, Google Scholar