Skip to main content
SpringerLink
Log in

SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

  • Article
  • Published:
Journal of Simulation

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4

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.

    Article  Google Scholar 

  • Baker KR and Altheimer D (2012). Heuristic solution methods for the stochastic flow shop problem. European Journal of Operational Research 216 (1): 172–177.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Beraldi P and Ruszczyński A (2002). The probabilistic set-covering problem. Operations Research 50 (6): 956–967.

    Article  Google Scholar 

  • Bertsimas DJ (1992). A vehicle routing problem with stochastic demand. Operations Research 40 (3): 574–585.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Bianchi L, Dorigo M, Gambardella LM and Gutjahr WJ (2009). A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing 8 (2): 239–287.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Gendreau M, Laporte G and Séguin R (1996b). Stochastic vehicle routing. European Journal of Operational Research 88 (1): 3–12.

    Article  Google Scholar 

  • Glover F (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences 8 (1): 156–166.

    Article  Google Scholar 

  • Glover F (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13 (5): 533–549.

    Article  Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Holland JH (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing 2 (2): 88–105.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Kall P and Wallace SW (1994). Stochastic Programming. Wiley-Blackwell: Chichester, UK.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Kleinberg J, Rabani Y and Tardos É (2000). Allocating bandwidth for bursty connections. SIAM Journal on Computing 30 (1): 191–217.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • Makino T (1965). On a scheduling problem. Journal of the Operations Research Society Japan 8: 32–44.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Pinedo M (1984). Optimal policies in stochastic shop scheduling. Annals of Operations Research 1 (3): 305–329.

    Article  Google Scholar 

  • Ross KW and Tsang DHK (1989). The stochastic knapsack problem. IEEE Transactions on Communications 37 (7): 740–747.

    Article  Google Scholar 

  • Rothkopf MH (1966). Scheduling with random service times. Management Science 12 (9): 707–713.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

Download references

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

  1. EADA Business School, Barcelona, Spain

    Alex Grasas

  2. IN3—Open University of Catalonia, Barcelona, Spain

    Angel A Juan

  3. Universitat Pompeu Fabra, Barcelona, Spain

    Helena R Lourenço

Authors
  1. Alex Grasas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Angel A Juan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Helena R Lourenço
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alex Grasas.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jos.2014.25

Keywords

Search

Navigation