×

A survey on metaheuristics for stochastic combinatorial optimization. (English) Zbl 1162.90591

Summary: 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.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aarts E, Korst J (1990) Simulated annealing and the Boltzmann machine. Wiley, New York, NY, USA · Zbl 0674.90059
[2] Albers S (2003) Online algorithms: a survey. Math Program 97(1–2):3–26 · Zbl 1035.68136
[3] 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
[4] Alkhamis TM, Ahmed MA, Kim Tuan W (1999) Simulated annealing for discrete optimization with estimation. Eur J Oper Res 116:530–544 · Zbl 1009.90076
[5] Alrefaei MH, Andradóttir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Manag Sci 45:748–764 · Zbl 1231.90315
[6] 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
[7] 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
[8] Arnold D (2002) In Noisy optimization with evolutionary strategies, vol 8: Genetic algorithms and evolutionary computation series. Kluwer Academic Publishers, Boston, MA, USA
[9] 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 · Zbl 0883.68001
[10] 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 · Zbl 1176.90479
[11] 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 · Zbl 1188.90208
[12] Banks A, Vincent J, Anyakoha C (2007) A review of particle swarm optimization, part i: background and development. Nat Comput 6(4):467–484 · Zbl 1125.90065
[13] 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–124 · Zbl 1148.68375
[14] Barthelemy J-FM, Haftka RT (1993) Approximation concepts for optimum structural design–a review. Struct Optim 5:129–144
[15] Bellman R, Zadeh LA (1970) Decision-making in a fuzzy environment. Manag Sci 17:141–161 · Zbl 0224.90032
[16] Beraldi P, Ruszczyński A (2005) Beam Search heuristic to solve stochastic integer problems under probabilistic constraints. Eur J Oper Res 167(1):35–47 · Zbl 1074.90031
[17] Bertsekas DP (1995) Dynamic programming and optimal control, vol 1, 2. Athena Scientific, Belmont, MA, USA · Zbl 0904.90170
[18] Bertsekas DP (1998) Network optimization: continuous and discrete models. Athena Scientific, Belmont, MA, USA · Zbl 0997.90505
[19] Bertsekas DP, Castañon DA (1998) Rollout algorithms for stochastic scheduling problems. J Heuristics 5:89–108 · Zbl 0997.90037
[20] Bertsekas DP, Tsitsiklis JN, Wu C (1997) Rollout algorithms for combinatorial optimization. J Heuristics 3(3):245–262 · Zbl 1071.90571
[21] Beyer H-G (2000) Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Comput Meth Appl Mech Eng 186(2–4):239–267 · Zbl 1064.90574
[22] 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
[23] 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–144 · Zbl 1137.90686
[24] 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
[25] 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
[26] 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
[27] 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–219 · Zbl 1132.90364
[28] 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–110 · Zbl 1099.90505
[29] 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
[30] 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
[31] Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer, New York, NY, USA · Zbl 0892.90142
[32] Birnbaum ZW (1948) On random variables with comparable peakedness. Ann Math Stat 19:76–81 · Zbl 0031.36801
[33] Blum C (2005) Ant colony optimization: introduction and recent trends. Phys Life Rev 2(4):353–373
[34] Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35(3):268–308
[35] Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge, MA, USA · Zbl 0931.68015
[36] Bowler NE, Fink TMA, Ball RC (2003) Characterization of the probabilistic traveling salesman problem. Phys Rev E 68(036703)
[37] 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
[38] Branke J (2002) Evolutionary optimization in dynamic environments. Springer, Berlin, Germany · Zbl 1047.68160
[39] 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 · Zbl 1033.90516
[40] Branke J, Guntsch M (2004) Solving the probabilistic TSP with ant colony optimization. J Math Model Algorithms 3(4):403–425 · Zbl 1079.90169
[41] 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
[42] Brusco M, Jacobs L (1993a) A simulated annealing approach to the cyclic staff-scheduling problem. Nav Res Logist 40(1):69–84 · Zbl 0769.90056
[43] Brusco M, Jacobs L (1993b) A simulated annealing approach to the solution of flexible labour scheduling problems. J Oper Res Soc 44(12):1191–1200 · Zbl 0800.90572
[44] 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–690
[45] Calégari P, Coray G, Hertz A, Kobler D, Kuonen P (1999) A taxonomy of evolutionary algorithms in combinatorial optimization. J Heuristics 5:145–158 · Zbl 1071.90572
[46] 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
[47] 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
[48] 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–1808 · Zbl 1365.90258
[49] 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–107 · Zbl 1145.90323
[50] 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–23 · Zbl 0913.90221
[51] 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
[52] 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–1817 · Zbl 1142.90507
[53] Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344(2–3):243–278 · Zbl 1154.90626
[54] Dorigo M, Gambardella LM (1997) Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1:53–66 · Zbl 05451865
[55] Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge, MA, USA · Zbl 1092.90066
[56] 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 · Zbl 0912.90240
[57] 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–41
[58] Dorigo M, Di Caro G, Gambardella LM (1999) Ant algorithms for discrete optimization. Artif Life 5(2):137–172
[59] 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 · Zbl 1134.90027
[60] Easton F, Mansour N (1999) A distributed genetic algorithm for deterministic and stochastic labor scheduling problems. Eur J Oper Res 118(3):505–523 · Zbl 0933.90028
[61] Easton F, Rossin D (1996) A stochastic goal program for employee scheduling. Dec Sci 27(3):541–568
[62] 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
[63] Erel E, Sabuncuoglu I, Sekerci H (2005) Stochastic assembly line balancing using Beam Search. Int J Prod Res 43(7):1411–1426 · Zbl 1068.90045
[64] 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–1017
[65] Fogel LJ, Owens AJ, Walsh MJ (1966) Artificial intelligence through simulated evolution. Wiley, New York, NY, USA · Zbl 0148.40701
[66] Fox BL, Heine GW (1995) Probabilistic search with overrides. Ann Appl Probab 4:1087–1094 · Zbl 0851.60069
[67] Fu MC (2002) Optimization for simulation: theory vs. practice. INFORMS J Comput 14(3):192–215 · Zbl 1238.90001
[68] Fu MC (2003) Guest editorial of the ACM TOMACS special issue on ”simulation optimization”. ACM Trans Model Comput Simul 13(2):105–107
[69] 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
[70] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA · Zbl 0411.68039
[71] 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
[72] Gelfand SB, Mitter SK (1989) Simulated annealing with noisy or imprecise measurements. J Optim Theory Appl 69:49–62 · Zbl 0651.90059
[73] 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 · Zbl 0573.62030
[74] 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–155 · Zbl 0860.90051
[75] 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–477 · Zbl 0864.90043
[76] Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549 · Zbl 0615.90083
[77] 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
[78] Glover F (2002) Tabu Search and finite convergence. Discret Appl Math 119:3–36 · Zbl 0994.90116
[79] Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA · Zbl 0930.90083
[80] Grimmett GR, Stirzaker DR (2001) Probability and random processes, 3rd edn. Oxford University Press, New York, NY, USA · Zbl 1015.60002
[81] Gutin G, Punnen A (eds) (2002) The traveling salesman problem and its variations. Kluwer Academic Publishers, Dordrecht, The Netherlands · Zbl 0996.00026
[82] Gutjahr WJ (2000) A graph-based ant system and its convergence. Future Gener Comput Syst 16(8):873–888
[83] Gutjahr WJ (2002) ACO algorithms with guaranteed convergence to the optimal solution. Inf Process Lett 82(3):145–153 · Zbl 1013.68092
[84] 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
[85] 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
[86] Gutjahr WJ, Hellmayr A, Pflug GCh (1999) Optimal stochastic single-machine tardiness scheduling by stochastic branch-and-bound. Eur J Oper Res 117:396–413 · Zbl 0998.90040
[87] 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 · Zbl 1175.90330
[88] Gutjahr WJ, Pflug GCh (1996) Simulated annealing for noisy cost functions. J Glob Optim 8:1–13 · Zbl 0857.90095
[89] Gutjahr WJ, Strauss C, Toth M (2000a) Crashing of stochastic activities by sampling and optimization. Bus Process Manag J 6:65–83
[90] Gutjahr WJ, Strauss C, Wagner E (2000b) A stochastic branch-and-bound approach to activity crashing in project management. INFORMS J Comput 12:125–135 · Zbl 1034.90005
[91] Haddock J, Mittenthal J (1992) Simulation optimization using simulated annealing. Comput Ind Eng 22:387–395
[92] Hajek B (1988) Cooling schedules for optimal annealing. Math Oper Res 13:311–329 · Zbl 0652.65050
[93] Hanafi S (2000) On the convergence of Tabu Search. J Heuristics 7:47–58 · Zbl 0967.90054
[94] Haneveld WKK, van der Vlerk MH (1999) Stochastic integer programming: state of the art. Ann Oper Res 85:39–57 · Zbl 0920.90110
[95] 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
[96] Hansen P, Mladenović N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130:449–467 · Zbl 0981.90063
[97] 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–122 · Zbl 0990.90087
[98] Haugland D, Ho SC, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. Eur J Oper Res 180:997–1010 · Zbl 1121.90021
[99] Hertz A, Kobler D (2000) A framework for the description of evolutionary algorithms. Eur J Oper Res 126:1–12 · Zbl 0970.90122
[100] 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 · Zbl 0932.90031
[101] Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Harbor, MI, USA
[102] 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/
[103] Homem-de-Mello T (2003) Variable-sample methods for stochastic optimization. ACM Trans Model Comput Simul 13:108–133
[104] 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 · Zbl 1176.90025
[105] Irani S, Lu X, Regan A (2004) On-line algorithms for the dynamic traveling repair problem. J Sched 7(3):243–258 · Zbl 1154.90461
[106] 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
[107] Jin Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput 9(1):3–12 · Zbl 05036836
[108] Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments–a survey. IEEE Trans Evol Comput 9(3):303–317 · Zbl 05452035
[109] Jönsson H, Silver EA (1996) Some insights regarding selecting sets of scenarios in combinatorial stochastic problems. J Prod Econ 45:463–472
[110] 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
[111] 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
[112] 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
[113] Kenyon A, Morton DP (2002) A survey on stochastic location and routing problems. Central Eur J Oper Res 9:277–328 · Zbl 1036.90044
[114] Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680 · Zbl 1225.90162
[115] Kouvelis P, Yu G (1997) Robust discrete optimization and its applications, vol 14: Nonconvex optimization and its applications. Kluwer Academic Publishers, Dordrecht, The Netherlands · Zbl 0873.90071
[116] 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–549 · Zbl 0810.90124
[117] Liu Y-H (2007) A hybrid scatter search for the probabilistic traveling salesman problem. Comput Oper Res 34:2949–2963 · Zbl 1185.90162
[118] 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–38 · Zbl 1239.90102
[119] 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
[120] 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
[121] Løkketangen A, Woodruff DL (1996) Progressive hedging and Tabu Search applied to mixed integer (0,1) multistage stochastic programming. J Heuristics 2:111–128 · Zbl 0869.90056
[122] 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–247
[123] 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
[124] Lutz CM, Davis KR, Sun M (1998) Determining buffer location and size in production lines using Tabu Search. Eur J Oper Res 106:301–316 · Zbl 0991.90046
[125] 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
[126] Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21:1087–1092
[127] Miller BL, Goldberg DE (1997) Genetic algorithms, selection schemes, and the varying effects of noise. Evol Comput 4(2):113–131 · Zbl 05412777
[128] Morrison RW (2004) Designing evolutionary algorithms for dynamic environments. Springer, Berlin, Germany · Zbl 1070.68130
[129] Metaheuristics Network web site. http://www.metaheuristics.org/
[130] Norkin VI, Ermoliev YM, Ruszczyński A (1998a) On optimal allocation of indivisibles under uncertainty. Oper Res 46(3):381–395 · Zbl 0987.90064
[131] Norkin VI, Pflug GCh, Ruszczyński A (1998b) A Branch and Bound method for stochastic global optimization. Math Program 83:425–450
[132] Ó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
[133] Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization. Dover Publications, Mineola, NY, USA · Zbl 0503.90060
[134] 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
[135] Pichitlamken J (2002) A combined procedure for optimization via simulation. PhD thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA · Zbl 1390.65024
[136] 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
[137] Pichitlamken J, Nelson LB (2003) A combined procedure for optimization via simulation. ACM Trans Model Comput Simul 13(2):155–179
[138] Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization: an overview. Swarm Intell 1:33–57
[139] 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
[140] Rechenberg RI (1973) Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart, Germany
[141] 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
[142] 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
[143] Rockafellar RT, Wets RJ-B (1991) Scenarios and policy aggregation in optimization under uncertainty. Math Oper Res 16:119–147 · Zbl 0729.90067
[144] Roenko N (1990) Simulated annealing under uncertainty. Technical report, Institute for Operations Research, University of Zurich, Switzerland
[145] Rosen SL, Harmonosky CM (2005) An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Comput Oper Res 32(2):343–358 · Zbl 1073.90026
[146] Rubinstein RY (1981) Simulation and the Monte Carlo method. Wiley, New York, NY, USA · Zbl 0529.68076
[147] 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
[148] Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput Oper Res 27(5):1171–1200 · Zbl 0962.90010
[149] Secomandi N (2001) A rollout policy for the vehicle routing problem with stochastic demands. Oper Res 49(5):796–802 · Zbl 1163.90373
[150] Secomandi N (2003) Analysis of a rollout approach to sequencing problems with stochastic routing applications. J Heuristics 9:321–352 · Zbl 1043.90032
[151] Shi L, Ólafsson S (2000) Nested partitions method for global optimization. Oper Res 48(3):390–407 · Zbl 1106.90368
[152] Stochastic Programming Community Homepage. http://stoprog.org/
[153] Stützle T, Dorigo M (2002) A short convergence proof for a class of ACO algorithms. IEEE Trans Evol Comput 6(4):358–365 · Zbl 05452159
[154] 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–127 · Zbl 1060.90006
[155] 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–154
[156] 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–273
[157] Tesauro G, Galperin GR (1997) On-line policy improvement using monte carlo search. Adv Neural Inf Process Syst 9:1068–1074
[158] van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. D. Reidel Publishing Company, Dordrecht, The Netherlands · Zbl 0643.65028
[159] Vose M (1999) The simple genetic algorithm: foundations and theory. The MIT Press, Cambridge, MA, USA · Zbl 0952.65048
[160] Wang L, Singh C (2008) Stochastic economic emission load dispatch through a modified particle swarm optimization algorithm. Electr Pow Syst Res 78(8):1466–1476
[161] 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–340 · Zbl 1147.91034
[162] 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–98 · Zbl 0973.90036
[163] Yang W, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34(1):99–112 · Zbl 1014.90020
[164] Yoshitomi Y (2002) A genetic algorithm approach to solving stochastic job-shop scheduling problems. Int Trans Oper Res 9(4):479–495 · Zbl 1008.90026
[165] 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–596 · Zbl 1108.90317
[166] 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
[167] Zimmermann HJ (1991) Fuzzy set theory and its application, 2nd edn. Kluwer Academic Publishers, Boston, MA, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.