Abstract
Iterated Local Search (ILS) is one of the most popular single-solution-based metaheuristics. ILS is recognized by many authors as a relatively simple yet efficient framework able to deal with complex combinatorial optimization problems (COPs). ILS-based algorithms have been successfully applied to provide near-optimal solutions to different COPs in logistics, transportation, production, etc. However, ILS is designed to solve COPs under deterministic scenarios. In some real-life applications where uncertainty is present, the deterministic assumption makes the model less accurate since it does not reflect the real stochastic nature of the system. This paper presents the SimILS framework that extends ILS by integrating simulation to be able to cope with Stochastic COPs in a natural way. The paper also describes several tested applications that illustrate the main concepts behind SimILS and give rise to a new brand of ILS-based algorithms.
Similar content being viewed by others
References
Altiparmak F, Dengiz B and Bulgak AA (2002). Optimization of buffer sizes in assembly systems using intelligent techniques. In: Yucesan E, Chen C-H, Snowdon JL and Chames JM (eds). Proceedings of the 2002 Winter Simulation Conference. IEEE Press: San Diego, CA, 8–11 December, pp 1157–1162.
April J, Glover F, Kelly JP and Laguna M (2003). Simulation-based optimization: Practical introduction to simulation optimization. In: Chick S, Sánchez PJ, Ferrin D and Morrice DJ (eds). Proceedings of the 2003 Winter Simulation Conference. IEEE Press: New Orleans, LA, 7–10 December, pp 71–78.
Arreola-Risa A, Giménez-García VM and Martínez-Parra JL (2011). Optimizing stochastic production-inventory systems: A heuristic based on simulation and regression analysis. European Journal of Operational Research 213 (1): 107–118.
Baker KR and Altheimer D (2012). Heuristic solution methods for the stochastic flow shop problem. European Journal of Operational Research 216 (1): 172–177.
Balasubramanian H, Banerjee R, Gregg M and Denton BT (2007). Improving primary care access using simulation optimization. In: Henderson SG, Biller B, Hsieh M-H, Shortle J, Tew JD and Barton RR (eds). Proceedings of the 2007 Winter Simulation Conference. IEEE Press: Washington DC, 9–12 December, pp 1494–1500.
Banerjee BP (1965). Single facility sequencing with random execution times. Operations Research 13 (3): 358–364.
Beraldi P and Ruszczyński A (2002). The probabilistic set-covering problem. Operations Research 50 (6): 956–967.
Bertsimas DJ (1992). A vehicle routing problem with stochastic demand. Operations Research 40 (3): 574–585.
Bianchi L et al (2006). Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms 5 (1): 91–110.
Bianchi L, Dorigo M, Gambardella LM and Gutjahr WJ (2009). A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing 8 (2): 239–287.
Burke E et al (2010). Iterated local search vs. hyper-heuristics: Towards general-purpose search algorithms. In: IEEE Congress on Evolutionary Computation. IEEE Press: Barcelona, Spain, pp 3073–3080.
Cabrera G, Juan AA, Lázaro D, Marquès JM and Proskurnia I (2014). A simulation-optimization approach to deploy internet services in large-scale systems with user-provided resources. Simulation: Transactions of the Society for Modeling and Simulation International 90 (6): 644–659.
Chiang W-C, Russell R, Xu X and Zepeda D (2009). A simulation/metaheuristic approach to newspaper production and distribution supply chain problems. International Journal of Production Economics 121 (2): 752–767.
Christiansen CH and Lysgaard J (2007). A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters 35 (6): 773–781.
Christiansen CH, Lysgaard J and Wøhlk S (2009). A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands. Operations Research Letters 37 (6): 392–398.
Cordeau JF, Gendreau M, Laporte G, Potvin J-Y and Semet F (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society 53 (5): 512–522.
Delévacq A, Delisle P and Krajecki M (2012). Parallel GPU implementation of iterated local search for the travelling salesman problem. In: Hamadi Y and Schoenauer M (eds). Learning and Intelligent Optimization. Lecture Notes in Computer Science. Springer-Verlag: Berlin/Heidelberg, pp 372–377.
Dengiz B and Alabas C (2000). Simulation optimization using tabu search. In: Joines JA, Barton RR, Kang K and Fishwick PA (eds). Proceedings of the 2000 Winter Simulation Conference. IEEE Press: Orlando, FL, 10–13 December, pp 805–810.
Dong X, Chen P, Huang H and Nowak M (2013). A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time. Computers and Operations Research 40 (2): 627–632.
Dorigo M (1992). Optimization, learning and natural algorithms (in Italian). PhD Thesis, Politecnico di Milano, Italy.
Federgruen A and Zipkin P (1984). A combined vehicle routing and inventory allocation problem. Operations Research 32 (5): 1019–1037.
Fleury G, Lacomme P, Prins C and Ramdane-Chérif W (2002). Robustness evaluation of solutions for the capacitated arc routing problem. In: Conference, AI Simulation and Planning in High Autonomy Systems, Lisboa, Portugal, pp 290–295.
Fleury G, Lacomme P, Prins C and Ramdane-Chérif W (2005). Improving robustness of solutions to arc routing problems. Journal of the Operational Research Society 56 (5): 526–538.
Fu MC et al (2000). Integrating optimization and simulation: Research and practice. In: Joines JA, Barton RR, Kang K and Fishwick PA (eds). Proceedings of the 2000 Winter Simulation Conference. IEEE Press: Orlando, FL, 10–13 December, pp 610–616.
Gendreau M, Laporte G and Séguin R (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science 29 (2): 143–155.
Gendreau M, Laporte G and Séguin R (1996a). A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research 44 (3): 469–477.
Gendreau M, Laporte G and Séguin R (1996b). Stochastic vehicle routing. European Journal of Operational Research 88 (1): 3–12.
Glover F (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences 8 (1): 156–166.
Glover F (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13 (5): 533–549.
Glover F, Kelly JP and Laguna M (1996). New advances and applications of combining simulation and optimization. In: Charnes JM, Morrice DJ, Brunner DT and Swain JJ (eds). Proceedings of the 1996 Winter Simulation Conference. IEEE Press: Coronado, CA, 8–11 December, pp 144–152.
González S, Riera D, Juan AA, Elizondo MG and Fonseca P (2012). Sim-randsharp: A hybrid algorithm for solving the arc routing problem with stochastic demands. In: Laroque C, Himmelspach J, Pasupathy R, Rose O and Uhrmacher AM (eds). Proceedings of the 2012 Winter Simulation Conference. IEEE Press: Berlin, Germany, 9–12 December, pp 1–11.
Gutjahr W (2004). S-ACO: An ant-based approach to combinatorial optimization under uncertainty. In: Dorigo M, Birattari M, Blum C, Gambardella L, Mondada F and Stützle T (eds) Ant Colony Optimization and Swarm Intelligence. Lecture Notes in Computer Science Springer-Verlag: Berlin/Heidelberg: pp 238–249.
Gutjahr WJ, Strauss C and Wagner E (2000). A stochastic branch-and-bound approach to activity crashing in project management. INFORMS Journal on Computing 12 (2): 125–135.
Holland JH (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing 2 (2): 88–105.
Ismail Z (2008). Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm-tabu search. Journal of Mathematics and Statistics 4 (3): 161–167.
Jaillet P (1985). Probabilistic traveling salesman problems. PhD Thesis, Operations Research Center, MIT, Cambridge, MA.
Juan AA, Barrios BB, Vallada E, Riera D and Jorba J (2014a). SIM-ESP: A simheuristic algorithm for solving the permutation flow-shop problem with stochastic processing times. Simulation Modelling Practice and Theory 46: 101–117.
Juan AA, Faulin J, Grasman SE, Riera D, Marull J and Mendez C (2011). Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transportation Research Part C: Emerging Technologies 19 (5): 751–765.
Juan AA, Faulin J, Jorba J, Cáceres-Cruz J and Marques J (2013). Using parallel and distributed computing for solving real-time vehicle routing problems with stochastic demands. Annals of Operations Research 207 (1): 43–65.
Juan AA, Grasman SE, Caceres-Cruz J and Bektaş T (2014b). A simheuristic algorithm for the single-period stochastic inventory-routing problem with stock-outs. Simulation Modelling Practice and Theory 46: 40–52.
Juan AA, Lourenço HR, Mateo M, Luo R and Castella Q (2014c). Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues. International Transactions in Operational Research 21 (1): 103–126.
Kall P and Wallace SW (1994). Stochastic Programming. Wiley-Blackwell: Chichester, UK.
Kennedy J and Eberhart R (1995). Particle swarm optimization. In: Proceedings IEEE International Conference on Neural Networks. Perth, Australia, pp 1942–1948.
Kirkpatrick S, Gelatt CD and Vecchi MP (1983). Optimization by simulated annealing. Science 220 (4598): 671–680.
Kise H, Shiomi A, Uno M and Chao D (1982). An efficient algorithm for a chance-constrained scheduling problem. Journal of the Operations Research Society of Japan 25 (2): 193–203.
Kleinberg J, Rabani Y and Tardos É (2000). Allocating bandwidth for bursty connections. SIAM Journal on Computing 30 (1): 191–217.
Konak A and Kulturel-Konak S (2005). Simulation optimization using tabu search: An emperical study. In: Kuhl ME, Steiger NM, Armstrong FB and Joines JA (eds). Proceedings of the 2005 Winter Simulation Conference. IEEE Press: Orlando, FL, 4–7 December, pp 2686–2692.
Laporte G, Louveaux FV and Mercure H (1994). A priori optimization of the probabilistic traveling salesman problem. Operations Research 42 (3): 543–549.
Laroque C, Klaas A, Fischer J-H and Kuntze M (2012). Fast converging, automated experiment runs for material flow simulations using distributed computing and combined metaheuristics. In: Laroque C, Himmelspach J, Pasupathy R, Rose O and Uhrmacher AM (eds). Proceedings of the 2012 Winter Simulation Conference. IEEE Press: Berlin, Germany, 9–12 December, pp 102–111.
Legato P, Mazza RM and Trunfio R (2010). Simulation-based optimization for discharge/loading operations at a maritime container terminal. OR Spectrum 32 (3): 543–567.
Lei H, Laporte G and Guo B (2011). The capacitated vehicle routing problem with stochastic demands and time windows. Computers and Operations Research 38 (12): 1775–1783.
Lourenço HR, Martin OC and Stützle T (2003). Iterated local search. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer Academic Publishers: Norwell, MA, pp 321–353.
Lourenço HR, Martin OC and Stützle T (2010). Iterated local search: Framework and applications. In: Gendreau M and Potvin JY (eds). Handbook of Metaheuristics. Springer: New York, pp 363–397.
Makino T (1965). On a scheduling problem. Journal of the Operations Research Society Japan 8: 32–44.
Marinakis Y, Iordanidou G-R and Marinaki M (2013). Particle swarm optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing 13 (4): 1693–1704.
Moghaddam BF, Ruiz R and Sadjadi SJ (2012). Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Computers and Industrial Engineering 62 (1): 306–317.
Nawaz M, Enscore JEE and Ham I (1983). A heuristic algorithm for m-machine, n-job flow shop sequencing problem. International Journal of Management Science 11 (1): 91–95.
Nguyen V-P, Prins C and Prodhon C (2012). A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem. Engineering Applications of Artificial Intelligence 25 (1): 56–71.
Penna PHV, Subramanian A and Ochi LS (2011). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics 19 (2): 201–232.
Pinedo M (1984). Optimal policies in stochastic shop scheduling. Annals of Operations Research 1 (3): 305–329.
Ross KW and Tsang DHK (1989). The stochastic knapsack problem. IEEE Transactions on Communications 37 (7): 740–747.
Rothkopf MH (1966). Scheduling with random service times. Management Science 12 (9): 707–713.
Shanmugam G, Ganesan P and Vanathi PT (2011). Meta heuristic algorithms for vehicle routing problem with stochastic demands. Journal of Computer Science 7 (4): 533–542.
Shaw P (1998). Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M and Puget JF (eds). Principles and Practice of Constraint Programming—CP98. Springer-Verlag: Berlin/Heidelberg, pp 417–431.
Shen Z, Ordóñez F and Dessouky MM (2009). The stochastic vehicle routing problem for minimum unmet demand. In: Chaovalitwongse WA, Furman KC and Pardalos PM (eds). Optimization and Logistics Challenges in the Enterprise, Springer Optimization and Its Applications Springer: New York, pp 349–371.
Steinberg E and Parks MS (1979). A preference order dynamic program for a knapsack problem with stochastic rewards. Journal of the Operational Research Society 30 (2): 141–147.
Subramanian A and Battarra M (2012). An iterated local search algorithm for the travelling salesman problem with pickups and deliveries. Journal of the Operational Research Society 64 (3): 402–409.
Subramaniam G and Gosavi A (2007). Simulation-based optimisation for material dispatching in vendor-managed inventory systems. International Journal of Simulation and Process Modeling 3 (4): 238–245.
Subramanian A, Battarra M and Potts CN (2014). An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. International Journal of Production Research 52 (9): 2729–2742.
Tan KC, Cheong CY and Goh CK (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of Operational Research 177 (2): 813–839.
Teodorovic D and Pavkovic G (1992). A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand. Transportation Planning and Technology 16 (4): 261–273.
Tripathi M, Kuriger G and Wan H (2009). An ant based simulation optimization for vehicle routing problem with stochastic demands. In: Rossetti MD, Hill RR, Johansson B, Dunkin A and Ingalls RG (eds). Proceedings of the 2009 Winter Simulation Conference. IEEE Press: Austin, Texas, pp 2476–2487.
Vansteenwegen P and Mateo M (2014). An iterated local search algorithm for the single-vehicle cyclic inventory routing problem. European Journal of Operational Research 237 (3): 802–813.
Zhang T (2007). RLC_ACS: An improved ant colony algorithm for VRPSDP. In: Proceedings of 2007 International Conference on Machine Learning And Cybernetics. IEEE: Hong Kong, pp 978–983.
Zhang T, Chaovalitwongse WA and Zhang Y (2012). Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Computers and Operations Research 39 (10): 2277–2290.
Acknowledgements
This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P) and by the Ibero-American Programme for Science, Technology and Development (CYTED2010-511RT0419).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grasas, A., Juan, A. & Lourenço, H. SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization. J Simulation 10, 69–77 (2016). https://doi.org/10.1057/jos.2014.25
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jos.2014.25