Top

Natural Computing

Published in:

01-06-2009

A survey on metaheuristics for stochastic combinatorial optimization

Authors: Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella, Walter J. Gutjahr

Published in: Natural Computing | Issue 2/2009

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Metaheuristics are general algorithmic frameworks, often nature-inspired, designed to solve complex optimization problems, and they are a growing research area since a few decades. In recent years, metaheuristics are emerging as successful alternatives to more classical approaches also for solving optimization problems that include in their mathematical formulation uncertain, stochastic, and dynamic information. In this paper metaheuristics such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others are introduced, and their applications to the class of Stochastic Combinatorial Optimization Problems (SCOPs) is thoroughly reviewed. Issues common to all metaheuristics, open problems, and possible directions of research are proposed and discussed. In this survey, the reader familiar to metaheuristics finds also pointers to classical algorithmic approaches to optimization under uncertainty, and useful informations to start working on this problem domain, while the reader new to metaheuristics should find a good tutorial in those metaheuristics that are currently being applied to optimization under uncertainty, and motivations for interest in this field.

previous article A framework for machine learning based on dynamic physical fields

next article Negative correlation in incremental learning

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Nevertheless, a solution algorithm may use a ‘dynamic’ or ‘stochastic’ mechanism also in these cases, as, for example, the dynamic programming algorithm applied to (deterministic, static) shortest path problems, or algorithms that involve some random choice such as virtually all metaheuristics and local search procedures.

Aarts E, Korst J (1990) Simulated annealing and the Boltzmann machine. Wiley, New York, NY, USA

Albers S (2003) Online algorithms: a survey. Math Program 97(1–2):3–26MATHMathSciNet

Alkhamis TM, Ahmed MA (2004) Simulation-based optimization using simulated annealing with confidence intervals. In: Ingalls RG, Rossetti MD, Smith JS, Peters BA (eds) Proceedings of the 2004 winter simulation conference (WSC04). IEEE Press, Piscataway, NJ, USA, pp 514–518

Alkhamis TM, Ahmed MA, Kim Tuan W (1999) Simulated annealing for discrete optimization with estimation. Eur J Oper Res 116:530–544MATHCrossRef

Alrefaei MH, Andradóttir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Manag Sci 45:748–764CrossRef

Andradóttir S (1998) A review of simulation optimization techniques. In: Medeiros DJ, Watson EF, Carson JS, Manivannan MS (eds) Proceedings of the 1998 winter simulation conference (WSC98). IEEE Press, Piscataway, NJ, USA, pp 151–158

Aringhieri R (2004) Solving chance-constrained programs combining Tabu Search and simulation. In: Ribeiro CC, Martins SL (eds) Proceedings of the 3rd international workshop on experimental and efficient algorithms (WEA04), vol 3059: Lecture notes in computer science. Springer, Berlin, Germany, pp 30–41

Arnold D (2002) In Noisy optimization with evolutionary strategies, vol 8: Genetic algorithms and evolutionary computation series. Kluwer Academic Publishers, Boston, MA, USA

Bäck T, Fogel D, Michalewicz Z (eds) (1997) Handbook of evolutionary computation. Oxford University Press, Oxford, UK, and Institute of Physics Publishing, Bristol, UK

Balaprakash P, Birattari M, Stützle T, Dorigo M (2007a) Adaptive sample size and importance sampling in estimation-based local search for stochastic combinatorial optimization: a complete analysis. Technical Report TR/IRIDIA/2007-015, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, September

Balaprakash P, Birattari M, Stützle T, Dorigo M (2007b) An experimental study of estimation-based metaheuristics for the probabilistic traveling salesman problem. Technical Report TR/IRIDIA/2007-021, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium

Banks A, Vincent J, Anyakoha C (2007) A review of particle swarm optimization, part i: background and development. Nat Comput 6(4):467–484MATHMathSciNetCrossRef

Banks A, Vincent J, Anyakoha C (2008) A review of particle swarm optimization, part ii: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Nat Comput 7(1):109–124MATHMathSciNetCrossRef

Barthelemy J-FM, Haftka RT (1993) Approximation concepts for optimum structural design—a review. Struct Optim 5:129–144CrossRef

Bellman R, Zadeh LA (1970) Decision-making in a fuzzy environment. Manag Sci 17:141–161MathSciNetCrossRef

Beraldi P, Ruszczyński A (2005) Beam Search heuristic to solve stochastic integer problems under probabilistic constraints. Eur J Oper Res 167(1):35–47MATHCrossRef

Bertsekas DP (1995) Dynamic programming and optimal control, vol 1, 2. Athena Scientific, Belmont, MA, USA

Bertsekas DP (1998) Network optimization: continuous and discrete models. Athena Scientific, Belmont, MA, USAMATH

Bertsekas DP, Castañon DA (1998) Rollout algorithms for stochastic scheduling problems. J Heuristics 5:89–108CrossRef

Bertsekas DP, Tsitsiklis JN, Wu C (1997) Rollout algorithms for combinatorial optimization. J Heuristics 3(3):245–262MATHCrossRef

Beyer H-G (2000) Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Comput Meth Appl Mech Eng 186(2–4):239–267MATHCrossRef

Bianchi L (2006) Ant colony optimization and local search for the probabilistic traveling salesman problem: a case study in stochastic combinatorial optimization. PhD thesis, Université Libre de Bruxelles, Brussels, Belgium

Bianchi L, Campbell AM (2007) Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem. Eur J Oper Res 176(1):131–144MATHMathSciNetCrossRef

Bianchi L, Gambardella LM, Dorigo M (2002a) An ant colony optimization approach to the probabilistic traveling salesman problem. In: Merelo Guervós JJ, Adamidis P, Beyer H-G, Fernández-Villacañas J-L, Schwefel H-P (eds) Proceedings of the 7th international conference on parallel problem solving from nature (PPSN VII), vol 2439: Lecture notes in computer science. Springer, London, UK, pp 883–892

Bianchi L, Gambardella LM, Dorigo M (2002b) Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic. In: Dorigo M, Di Caro G, Sampels M (eds) Proceedings of the 3rd international workshop on ant algorithms (ANTS 2002), vol 2463: Lecture notes in computer science. Springer, London, UK, pp 176–187

Bianchi L, Birattari M, Chiarandini M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2004) Metaheuristics for the vehicle routing problem with stochastic demands. In: Yao X, Burke E, Lozano JA, Smith J, Merelo Guervós JJ, Bullinaria JA, Rowe J, Tiňo P, Kabán A, Schwefel H-P (eds) Proceedings of the 8th international conference on parallel problem solving from nature (PPSN VIII), vol 3242: Lecture notes in computer science. Springer, Berlin, Germany, pp 450–460

Bianchi L, Knowles J, Bowler N (2005) Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms. Eur J Oper Res 162(1):206–219MATHMathSciNetCrossRef

Bianchi L, Birattari M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2006) Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J Math Model Algorithms 5(1):91–110MATHMathSciNetCrossRef

Birattari M, Balaprakash P, Dorigo M (2005) ACO/F-Race: ant colony optimization and racing techniques for combinatorial optimization under uncertainty. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M (eds) Proceedings of the 6th metaheuristics international conference (MIC 2005), pp 107–112

Birattari M, Balaprakash P, Dorigo M (2006) The ACO/F-RACE algorithm for combinatorial optimization under uncertainty. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M (eds) Metaheuristics—progress in complex systems optimization. Operations research/computer science interfaces series. Springer, Berlin, Germany

Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer, New York, NY, USAMATH

Birnbaum ZW (1948) On random variables with comparable peakedness. Ann Math Stat 19:76–81MATHMathSciNetCrossRef

Blum C (2005) Ant colony optimization: introduction and recent trends. Phys Life Rev 2(4):353–373MathSciNetCrossRef

Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35(3):268–308CrossRef

Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge, MA, USAMATH

Bowler NE, Fink TMA, Ball RC (2003) Characterization of the probabilistic traveling salesman problem. Phys Rev E 68(036703)

Branke J (2001) Evolutionary approaches to dynamic optimization problems—updated survey. In: Beyer H-G, Cantú-Paz E, Goldberg D, Parmee IC, Spector L, Whitley D (eds) Proceedings of the genetic and evolutionary computation conference (GECCO 2001). Morgan Kaufmann, San Francisco, CA, USA, pp 27–30

Branke J (2002) Evolutionary optimization in dynamic environments. Springer, Berlin, GermanyMATH

Branke J, Guntsch M (2003) New ideas for applying ant colony optimization to the probabilistic TSP. In Proceedings of the 3rd European workshop on evolutionary computation in combinatorial optimization (EvoCOP 2003), vol 2611: Lecture notes in computer science. Springer, Berlin, Germany, pp 165–175

Branke J, Guntsch M (2004) Solving the probabilistic TSP with ant colony optimization. J Math Model Algorithms 3(4):403–425MATHMathSciNetCrossRef

Brodersen O, Schumann M (2007) Optimizing a stochastic warehouse using particle swarm optimization. In Second international conference on innovative computing (ICICIC). IEEE Press, Piscataway, NJ, USA, pp 449–452

Brusco M, Jacobs L (1993a) A simulated annealing approach to the cyclic staff-scheduling problem. Nav Res Logist 40(1):69–84MATHCrossRef

Brusco M, Jacobs L (1993b) A simulated annealing approach to the solution of flexible labour scheduling problems. J Oper Res Soc 44(12):1191–1200MATHCrossRef

Bulgak AA, Sanders JL (1988) Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimize buffer sizes in automatic assembly systems. In: Abrams M, Haigh P, Comfort J (eds) Proceedings of the 1988 winter simulation conference (WSC98). IEEE Press, Piscataway, NJ, USA, pp 684–690CrossRef

Calégari P, Coray G, Hertz A, Kobler D, Kuonen P (1999) A taxonomy of evolutionary algorithms in combinatorial optimization. J Heuristics 5:145–158MATHCrossRef

Chang HS (2004) An ant system based exploration-exploitation for reinforcement learning. In Proceedings of the IEEE conference on systems, man, and cybernetics. IEEE Press, Piscataway, NJ, USA, pp 3805–3810

Chang HS, Gutjahr WJ, Yang J, Park S (2004) An ant system approach to Markov decision processes. In Proceedings of the 23rd American control conference (ACC04), vol 4. IEEE Press, Piscataway, NJ, USA, pp 3820–3825

Chang HS, Lee H-G, Fu MC, Marcus SI (2005) Evolutionary policy iteration for solving Markov decision processes. IEEE T Automat Contr 50(11):1804–1808MathSciNetCrossRef

Cheung RK, Dongsheng X, Yongpei G (2007) A solution method for a two-dispatch delivery problem with stochastic customers. J Math Model Algorithms 6:87–107MATHMathSciNetCrossRef

Costa D, Silver EA (1998) Tabu Search when noise is present: an illustration in the context of cause and effect analysis. J Heuristics 4:5–23MATHCrossRef

Dengiz B, Alabas C (2000) Simulation optimization using Tabu Search. In: Joines JA, Barton RR, Kang K, Fishwick PA (eds) Proceedings of the 2000 winter simulation conference (WSC00). IEEE Press, Piscataway, NJ, USA, pp 805–810

Doerner K, Gutjahr WJ, Kotsis G, Polaschek M, Strauss C (2006) Enriched workflow modelling and stochastic branch-and-bound. Eur J Oper Res 175:1798–1817MATHMathSciNetCrossRef

Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344(2–3):243–278MATHMathSciNetCrossRef

Dorigo M, Gambardella LM (1997) Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1:53–66CrossRef

Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge, MA, USAMATH

Dorigo M, Maniezzo V, Colorni A (1991) The ant system: an autocatalytic optimization process. Technical Report 91-016, Department of Electronics. Politecnico di Milano, Milan, Italy

Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern—Part B 26(1):29–41CrossRef

Dorigo M, Di Caro G, Gambardella LM (1999) Ant algorithms for discrete optimization. Artif Life 5(2):137–172CrossRef

Dyer M, Stougie L (2003) Computational complexity of stochastic programming problems. Technical Report SPOR-report 2003-20. Department of Mathematics and Computer Science. Technische Universiteit Eindhoven, Eindhoven, The Netherlands

Easton F, Mansour N (1999) A distributed genetic algorithm for deterministic and stochastic labor scheduling problems. Eur J Oper Res 118(3):505–523MATHCrossRef

Easton F, Rossin D (1996) A stochastic goal program for employee scheduling. Dec Sci 27(3):541–568CrossRef

Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the IEEE international symposium on micro machine and human science (MHS’95). IEEE Press, Piscataway, NJ, USA, pp 39–43

Erel E, Sabuncuoglu I, Sekerci H (2005) Stochastic assembly line balancing using Beam Search. Int J Prod Res 43(7):1411–1426MATHCrossRef

Finke DA, Medeiros DJ, Traband M (2002) Shop scheduling using Tabu Search and simulation. In: Yücesan E, Chen CH, Snowdon JL, Charnes JM (eds) Proceedings of the 2002 winter simulation conference (WSC02). IEEE Press, Piscataway, NJ, USA, pp 1013–1017CrossRef

Fogel LJ, Owens AJ, Walsh MJ (1966) Artificial intelligence through simulated evolution. Wiley, New York, NY, USAMATH

Fox BL, Heine GW (1995) Probabilistic search with overrides. Ann Appl Probab 4:1087–1094MathSciNetCrossRef

Fu MC (2002) Optimization for simulation: theory vs. practice. INFORMS J Comput 14(3):192–215MathSciNetCrossRef

Fu MC (2003) Guest editorial of the ACM TOMACS special issue on “simulation optimization”. ACM Trans Model Comput Simul 13(2):105–107CrossRef

Gambardella LM, Dorigo M (1996) Solving symmetric and asymmetric TSPs by ant colonies. In: Proceedings of the 1996 IEEE international conference on evolutionary computation (ICEC’96). IEEE Press, Piscataway, NJ, USA, pp 622–627

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USAMATH

Gelfand SB, Mitter SK (1985) Analysis of simulated annealing for optimization. In: Proceedings of the 24th IEEE conference on decision and control (CDC’85), vol 2. IEEE Press, Piscataway, NJ, USA, pp 779–786

Gelfand SB, Mitter SK (1989) Simulated annealing with noisy or imprecise measurements. J Optim Theory Appl 69:49–62MathSciNetCrossRef

Geman D, Geman S (1984) Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. In: IEEE transactions of pattern analysis and machine intelligence, vol 6, pp 721–741

Gendreau M, Laporte G, Séguin R (1995) An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transp Sci 29(2):143–155MATHCrossRef

Gendreau M, Laporte G, Séguin R (1996) A Tabu Search heuristic for the vehicle routing problem with stochastic demands and customers. Oper Res 44(3):469–477MATHCrossRef

Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549MATHMathSciNetCrossRef

Glover F (1998) A template for scatter search and path relinking. In: Hao J-K, Lutton E, Ronald E, Schoenaurer M, Snyers D (eds) Artificial evolution, vol 1363: Lecture notes in computer science. Springer, Berlin, Germany

Glover F (2002) Tabu Search and finite convergence. Discret Appl Math 119:3–36MATHMathSciNetCrossRef

Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Publishers, Norwell, MA, USAMATH

Grimmett GR, Stirzaker DR (2001) Probability and random processes, 3rd edn. Oxford University Press, New York, NY, USA

Gutin G, Punnen A (eds) (2002) The traveling salesman problem and its variations. Kluwer Academic Publishers, Dordrecht, The NetherlandsMATH

Gutjahr WJ (2000) A graph-based ant system and its convergence. Future Gener Comput Syst 16(8):873–888CrossRef

Gutjahr WJ (2002) ACO algorithms with guaranteed convergence to the optimal solution. Inf Process Lett 82(3):145–153MATHMathSciNetCrossRef

Gutjahr WJ (2003) A converging ACO algorithm for stochastic combinatorial optimization. In: Proceedings of the 2nd symposium on stochastic algorithms, foundations and applicaions (SAGA 2003), vol 2827: Lecture notes in computer science. Springer, Berlin, Germany, pp 10–25

Gutjahr WJ (2004) S-ACO: an ant-based approach to combinatorial optimization under uncertainty. In: Proceedings of the 4th international workshop on ant colony optimization and swarm intelligence (ANTS 2004), vol 3172: Lecture notes in computer science. Springer, Berlin, Germany, pp 238–249

Gutjahr WJ, Hellmayr A, Pflug GCh (1999) Optimal stochastic single-machine tardiness scheduling by stochastic branch-and-bound. Eur J Oper Res 117:396–413MATHCrossRef

Gutjahr WJ, Katzensteiner S, Reiter P (2007) A VNS algorithm for noisy problems and its application to project portfolio analysis. In: Hromkovič J, Královič R, Nunkesser M, Widmayer P (eds) Proceedings of the 4th symposium on stochastic algorithms, foundations and applications (SAGA 2007), vol 4665: Lecture notes in computer science, pp 93–104

Gutjahr WJ, Pflug GCh (1996) Simulated annealing for noisy cost functions. J Glob Optim 8:1–13MATHMathSciNetCrossRef

Gutjahr WJ, Strauss C, Toth M (2000a) Crashing of stochastic activities by sampling and optimization. Bus Process Manag J 6:65–83CrossRef

Gutjahr WJ, Strauss C, Wagner E (2000b) A stochastic branch-and-bound approach to activity crashing in project management. INFORMS J Comput 12:125–135MATHCrossRef

Haddock J, Mittenthal J (1992) Simulation optimization using simulated annealing. Comput Ind Eng 22:387–395CrossRef

Hajek B (1988) Cooling schedules for optimal annealing. Math Oper Res 13:311–329MATHMathSciNetCrossRef

Hanafi S (2000) On the convergence of Tabu Search. J Heuristics 7:47–58CrossRef

Haneveld WKK, van der Vlerk MH (1999) Stochastic integer programming: state of the art. Ann Oper Res 85:39–57MATHMathSciNetCrossRef

Hansen P (1986) The steepest ascent mildest descent heuristics for combinatorial programming. Talk presented at the congress on numerical methods in combinatorial optimization. Capri, Italy

Hansen P, Mladenović N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130:449–467MATHCrossRef

Haugen KK, Løkketangen A, Woodruff DL (2001) Progressive hedging as a meta-heuristic applied to stochastic lot-sizing. Eur J Oper Res 132:116–122MATHCrossRef

Haugland D, Ho SC, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. Eur J Oper Res 180:997–1010MATHMathSciNetCrossRef

Hertz A, Kobler D (2000) A framework for the description of evolutionary algorithms. Eur J Oper Res 126:1–12MATHMathSciNetCrossRef

Hertz A, Taillard E, de Werra D (1997) Tabu Search. In: Aarts EHL, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, New York, NY, USA, pp 121–136

Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Harbor, MI, USA

Homem-de-Mello T (2000) Variable-sample methods and simulated annealing for discrete stochastic optimization. Stochastic Programming E-Print Series, http://hera.rz.hu-berlin.de/speps/

Homem-de-Mello T (2003) Variable-sample methods for stochastic optimization. ACM Trans Model Comput Simul 13:108–133CrossRef

Hvattum LM, Løkketangen A (in press) Using scenario trees and progressive hedging for stochastic inventory routing problems. J Heuristics. doi:10.1007/s10732-008-9076-0

Irani S, Lu X, Regan A (2004) On-line algorithms for the dynamic traveling repair problem. J Sched 7(3):243–258MATHMathSciNetCrossRef

Jellouli O, Châtelet E (2001) Monte Carlo simulation and genetic algorithm for optimising supply chain management in a stochastic environment. In: Proceedings of the 2001 IEEE conference on systems, man, and cybernetics, vol 3. IEEE Press, Piscataway, NJ, USA, pp 1835–1839

Jin Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput 9(1):3–12CrossRef

Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments—a survey. IEEE Trans Evol Comput 9(3):303–317CrossRef

Jönsson H, Silver EA (1996) Some insights regarding selecting sets of scenarios in combinatorial stochastic problems. J Prod Econ 45:463–472CrossRef

Jovanović D, Mladenović M, Ognjanović Z (2007) Variable neighborhood search for the probabilistic satisfiability problem. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M (eds) Metaheuristics—progress in complex systems optimization, vol 39: Operations research/Computer Science Interfaces Series. Springer, New York, NY, USA, pp 173–188

Kall P, Wallace SW (1994) Stochastic programming. Wiley, Chichester, UK, 1994. Wiley has released the copyright on the book, and the authors made the text available to the scientific community: it can be downloaded for free at http://www.unizh.ch/ior/Pages/Deutsch/Mitglieder/Kall/bib/ka-wal-94.pdf

Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: Proceedings of the IEEE international conference on evolutionary computation (CEC’97). IEEE Press, Piscataway, NJ, USA, pp 303–308

Kenyon A, Morton DP (2002) A survey on stochastic location and routing problems. Central Eur J Oper Res 9:277–328MathSciNet

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680MathSciNetCrossRef

Kouvelis P, Yu G (1997) Robust discrete optimization and its applications, vol 14: Nonconvex optimization and its applications. Kluwer Academic Publishers, Dordrecht, The Netherlands

Laporte G, Louveaux F, Mercure H (1994) An exact solution for the a priori optimization of the probabilistic traveling salesman problem. Oper Res 42(3):543–549MATHMathSciNetCrossRef

Liu Y-H (2007) A hybrid scatter search for the probabilistic traveling salesman problem. Comput Oper Res 34:2949–2963MATHCrossRef

Lin Z-Z, Bean JC, White CC III (2004) A hybrid genetic/optimization algorithm for finite-horizon, partially observed Markov decision processes. INFORMS J Comput 16(1):27–38MathSciNetCrossRef

Liu B, Wang L, Jin Y-H (2005) Hybrid particle swarm optimization for flow shop scheduling with stochastic processing time, vol 380: Lecture notes in computer science, pp 630–637

Liu Y-H, Jou R-C, Wang C-C, Chiu C-S (2007) An evolutionary algorithm with diversified crossover operator for the heterogeneous probabilistic TSP. In: Carbonell JG, Siekmann J (eds) Modeling decisions for artificial intelligence. 4th international conference, (MDAI 2007), vol 4617: Lecture notes in computer science. Springer, Berlin, Germany, pp 351–360

Løkketangen A, Woodruff DL (1996) Progressive hedging and Tabu Search applied to mixed integer (0,1) multistage stochastic programming. J Heuristics 2:111–128CrossRef

Lu L, Tan Q-M (2006) Hybrid particle swarm optimization algorithm for stochastic vehicle routing problem. Xi Tong Gong Cheng Yu Dian Zi Ji Shu/Syst Eng Electron 28(2):244–247MathSciNet

Lu M, Wu D-P, Zhang J-P (2006) A particle swarm optimization-based approach to tackling simulation optimization of stochastic, large-scale and complex systems, vol 3930: Lecture notes in computer science, pp 528–537

Lutz CM, Davis KR, Sun M (1998) Determining buffer location and size in production lines using Tabu Search. Eur J Oper Res 106:301–316MATHCrossRef

Mak KL, Guo ZG (2004) A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows. In: Jones MH, Patek SD, Tawney BE (eds) Proceedings of the 2004 IEEE systems and information engineering design symposium (SIEDS04). IEEE Press, Piscataway, NJ, USA, pp 183–190

Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21:1087–1092CrossRef

Miller BL, Goldberg DE (1997) Genetic algorithms, selection schemes, and the varying effects of noise. Evol Comput 4(2):113–131CrossRef

Morrison RW (2004) Designing evolutionary algorithms for dynamic environments. Springer, Berlin, GermanyMATH

Metaheuristics Network web site. http://www.metaheuristics.org/

Norkin VI, Ermoliev YM, Ruszczyński A (1998a) On optimal allocation of indivisibles under uncertainty. Oper Res 46(3):381–395MATHCrossRef

Norkin VI, Pflug GCh, Ruszczyński A (1998b) A Branch and Bound method for stochastic global optimization. Math Program 83:425–450MATH

Ólafsson S, Kim J (2002) Simulation optimization. In: Yücesan E, Chen CH, Snowdown JL, Charnes JM (eds) Proceedings of the 2002 winter simulation conference (WSC02). IEEE Press, Piscataway, NJ, USA, pp 89–84

Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization. Dover Publications, Mineola, NY, USAMATH

Pappala VS, Erlich I (2007) Management of distributed generation units under stochastic load demands using particle swarm optimization. In: Power engineering society general meeting (PES), IEEE Press, Piscataway, NJ, USA, pp 24–28

Pichitlamken J (2002) A combined procedure for optimization via simulation. PhD thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA

Pichitlamken J, Nelson LB (2001) Selection-of-the-best procedures for optimization via simulation. In: Peters BA, Smith JS, Medeiros DJ, Rohrer MW (eds) Proceedings of the 2001 winter simulation conference (WSC01). IEEE Press, Piscataway, NJ, USA, pp 401–407

Pichitlamken J, Nelson LB (2003) A combined procedure for optimization via simulation. ACM Trans Model Comput Simul 13(2):155–179CrossRef

Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization: an overview. Swarm Intell 1:33–57CrossRef

Rauner M, Brailsford SC, Gutjahr WJ, Zeppelzauer W (2005) Optimal screening policies for diabetic retinopathy using a combined discrete event simulation and ant colony optimization approach. In: Andersen JG, Katzper M (eds) Proceedings of the 15th international conference on health sciences simulation, western multiconference 2005. SCS—Society of Computer Simulation International, San Diego, CA, USA, pp 147–152

Rechenberg RI (1973) Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart, Germany

Reeves CR, Rowe JE (2003) Genetic algorithms: principles and perspectives—a guide to GA theory. Operaations Research/Computer Science Interfaces Series. Kluwer Academic Publishers, Boston, MA, USA

Resende MGC, Ribeiro CC (2003) In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. vol 57: International series in operations research & management, chapter Greedy randomized adaptive search procedures. Kluwer Academic Publishers, Boston, USA, pp 219–249

Rockafellar RT, Wets RJ-B (1991) Scenarios and policy aggregation in optimization under uncertainty. Math Oper Res 16:119–147MATHMathSciNetCrossRef

Roenko N (1990) Simulated annealing under uncertainty. Technical report, Institute for Operations Research, University of Zurich, Switzerland

Rosen SL, Harmonosky CM (2005) An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Comput Oper Res 32(2):343–358MATHMathSciNet

Rubinstein RY (1981) Simulation and the Monte Carlo method. Wiley, New York, NY, USAMATHCrossRef

Rudolph G (1996) Convergence of evolutionary algorithms in general search spaces. In: Proceedings of the IEEE international conference on evolutionary computation (ICEC’96). IEEE Press, Piscataway, NJ, USA, pp 50–54

Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput Oper Res 27(5):1171–1200

Secomandi N (2001) A rollout policy for the vehicle routing problem with stochastic demands. Oper Res 49(5):796–802CrossRef

Secomandi N (2003) Analysis of a rollout approach to sequencing problems with stochastic routing applications. J Heuristics 9:321–352MATHCrossRef

Shi L, Ólafsson S (2000) Nested partitions method for global optimization. Oper Res 48(3):390–407MATHMathSciNetCrossRef

Stochastic Programming Community Homepage. http://stoprog.org/

Stützle T, Dorigo M (2002) A short convergence proof for a class of ACO algorithms. IEEE Trans Evol Comput 6(4):358–365CrossRef

Sudhir Ryan Daniel J, Rajendran C (2005) A simulation-based genetic algorithm for inventory optimization in a serial supply chain. Int Trans Oper Res 12(1):101–127CrossRef

Swisher JR, Jacobson SH, Yücesan E (2003) Discrete-event simulation optimization using ranking, selection, multiple comparison procedures: a survey. ACM Trans Model Comput Simul 13(2):134–154CrossRef

Teodorović D, Pavković G (1992) A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand. Transp Plan Technol 16:261–273CrossRef

Tesauro G, Galperin GR (1997) On-line policy improvement using monte carlo search. Adv Neural Inf Process Syst 9:1068–1074

van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. D. Reidel Publishing Company, Dordrecht, The Netherlands

Vose M (1999) The simple genetic algorithm: foundations and theory. The MIT Press, Cambridge, MA, USAMATH

Wang L, Singh C (2008) Stochastic economic emission load dispatch through a modified particle swarm optimization algorithm. Electr Pow Syst Res 78(8):1466–1476CrossRef

Wang K-J, Wang S-M, Chen J-C (2008) A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm. Eur J Oper Res 184:327–340MATHCrossRef

Watson JP, Rana S, Whitley LD, Howe AE (1999) The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling. J Sched 2(2):79–98MATHMathSciNetCrossRef

Yang W, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34(1):99–112MATHCrossRef

Yoshitomi Y (2002) A genetic algorithm approach to solving stochastic job-shop scheduling problems. Int Trans Oper Res 9(4):479–495MATHMathSciNetCrossRef

Yoshitomi Y, Yamaguchi R (2003) A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling. Int Trans Oper Res 10(6):577–596MATHMathSciNetCrossRef

Zhao P-X (2007) Improved particle swarm optimization algorithm for the stochastic loader problem. In: Second IEEE conference on industrial electronics and applications (ICIEA 2007). IEEE Press, Piscataway, NJ, USA, pp 773–776

Zimmermann HJ (1991) Fuzzy set theory and its application, 2nd edn. Kluwer Academic Publishers, Boston, MA, USA

Title: A survey on metaheuristics for stochastic combinatorial optimization
Authors: Leonora Bianchi
Marco Dorigo
Luca Maria Gambardella
Walter J. Gutjahr
Publication date: 01-06-2009
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2009
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-008-9098-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2009

Successful preparation and analysis of a 5-site 2-variable DNA library

Integrative connectionist learning systems inspired by nature: current models, future trends and challenges

Negative correlation in incremental learning

Autopoiesis, the immune system, and adaptive information filtering

Nature-inspired learning and adaptive systems

Competition and evolution in virtual plant communities: a new modeling approach

Premium Partner