IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v199y2009i1p98-110.html
   My bibliography  Save this article

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

Author

Listed:
  • Balaprakash, Prasanna
  • Birattari, Mauro
  • Stützle, Thomas
  • Dorigo, Marco

Abstract

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.

Suggested Citation

  • Balaprakash, Prasanna & Birattari, Mauro & Stützle, Thomas & Dorigo, Marco, 2009. "Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 199(1), pages 98-110, November.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:1:p:98-110
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00977-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bianchi, Leonora & Campbell, Ann Melissa, 2007. "Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 176(1), pages 131-144, January.
    2. Mauro Birattari & Prasanna Balaprakash & Thomas Stützle & Marco Dorigo, 2008. "Estimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 644-658, November.
    3. Jon Jouis Bentley, 1992. "Fast Algorithms for Geometric Traveling Salesman Problems," INFORMS Journal on Computing, INFORMS, vol. 4(4), pages 387-411, November.
    4. Joseph F. Pekny & Donald L. Miller, 1994. "A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph," INFORMS Journal on Computing, INFORMS, vol. 6(1), pages 68-81, February.
    5. Dimitris J. Bertsimas & Patrick Jaillet & Amedeo R. Odoni, 1990. "A Priori Optimization," Operations Research, INFORMS, vol. 38(6), pages 1019-1033, December.
    6. Bianchi, Leonora & Knowles, Joshua & Bowler, Neill, 2005. "Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms," European Journal of Operational Research, Elsevier, vol. 162(1), pages 206-219, April.
    7. W. J. Gutjahr & C. Strauss & E. Wagner, 2000. "A Stochastic Branch-and-Bound Approach to Activity Crashing in Project Management," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 125-135, May.
    8. Alkhamis, Talal M. & Ahmed, Mohamed A. & Tuan, Vu Kim, 1999. "Simulated annealing for discrete optimization with estimation," European Journal of Operational Research, Elsevier, vol. 116(3), pages 530-544, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    2. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    3. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    2. Mauro Birattari & Prasanna Balaprakash & Thomas Stützle & Marco Dorigo, 2008. "Estimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 644-658, November.
    3. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    4. Liu, Yu-Hsin, 2008. "Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 332-346, December.
    5. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.
    6. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    7. Si Chen & Bruce Golden & Richard Wong & Hongsheng Zhong, 2009. "Arc-Routing Models for Small-Package Local Routing," Transportation Science, INFORMS, vol. 43(1), pages 43-55, February.
    8. N. Bourgeois & F. Della Croce & B. Escoffier & C. Murat & V. Th. Paschos, 2009. "Probabilistic graph-coloring in bipartite and split graphs," Journal of Combinatorial Optimization, Springer, vol. 17(3), pages 274-311, April.
    9. Helena Ramalhinho-Lourenço & Olivier C. Martin & Thomas Stützle, 2000. "Iterated local search," Economics Working Papers 513, Department of Economics and Business, Universitat Pompeu Fabra.
    10. Luca Maria Gambardella & Marco Dorigo, 2000. "An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 237-255, August.
    11. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2005. "Decision Support for Consumer Direct Grocery Initiatives," Transportation Science, INFORMS, vol. 39(3), pages 313-327, August.
    12. Chen, Shih-Pin & Tsai, Ming-Jiun, 2011. "Time-cost trade-off analysis of project networks in fuzzy environments," European Journal of Operational Research, Elsevier, vol. 212(2), pages 386-397, July.
    13. Li, Haitao & Womer, Norman K., 2015. "Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 246(1), pages 20-33.
    14. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    15. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    16. Stutzle, Thomas, 2006. "Iterated local search for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1519-1539, November.
    17. William Cook & André Rohe, 1999. "Computing Minimum-Weight Perfect Matchings," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 138-148, May.
    18. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    19. Papastavrou, Jason D., 1996. "A stochastic and dynamic routing policy using branching processes with state dependent immigration," European Journal of Operational Research, Elsevier, vol. 95(1), pages 167-177, November.
    20. Albareda-Sambola, Maria & Fernández, Elena & Saldanha-da-Gama, Francisco, 2011. "The facility location problem with Bernoulli demands," Omega, Elsevier, vol. 39(3), pages 335-345, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:199:y:2009:i:1:p:98-110. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.