Does Complex Metaheuristic Out-Perform Simple Hill-Climbing for Optimization Problems? A Simulation Evaluation

Abstract:

In this paper we compare the performance of metaheuristic methods, namely simulated annealing and Tabu Search, against simple hill climbing heuristic on a supply chain optimization problem. The benchmark problem we consider is the retailer replenishment optimization problem for a retailer selling multiple products. Computation and simulation results demonstrate that simulated annealing and Tabu search improve solution quality. However, the performance improvement is less in simulations with random noise. Lastly, simulated annealing appears to be more robust than Tabu search, and the results justify its extra implementation effort and computation time when compared against hill climbing.

• Periodical: Advanced Materials Research (Volume 748)
• Pages: 666-669
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.748.666
• Online since: August 2013
• Authors: Xing Wen Zhang
• Keywords: Heuristic, Hill Climbing, Meta-Heuristic, Optimization, Retailer Replenishment, Simulated Annealing (SA), Simulation, Tabu Search

References

[1] E. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines: A Stochastic Ap- proach to Combinatorial Optimization and Neural Computing. Wiley, Chichester, 1989.

DOI: 10.1080/09540098908915652

[2] R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.

[3] L. Chen and H. Lee. Information Sharing and Order Variability Control Under a Generalized[1]Demand Model. Management Science, 55(5):781–797, 2009.

DOI: 10.1287/mnsc.1080.0983

[4] J.-F. Cordeau, G. Laporte, and A. Mercier. A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Journal of the Operational Research Society, 52:928–936, 2001.

DOI: 10.1057/palgrave.jors.2601163

[5] M. Gendreau, A. Hertz, and G. Laporte. A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, 40:1276–1290, 1994.

DOI: 10.1287/mnsc.40.10.1276

[6] P. Glasserman. Monte Carlo Methods in Financial Engineering. Springer-Verlag, New York, 2004.

[7] F. Glover and T. Laguna. Tabu Search. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1997.

[8] J. Kahn. Inventories and the Volatility of Production. American Economic Review, 77:667– 679, 1987.

[9] S. Kirkpatrick and C. Gelatt amnd M. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671–680, 1983.

DOI: 10.1126/science.220.4598.671

[10] P. J. M. Laarhoven and E. Aarts. Simulated Annealing: Theory and Applications. Reidel, Dordrecht, 1987.

[11] H. Lee, V. Padmanabhan, and S. Whang. Information Distortion in a Supply Chain: The Bullwhip Effect. Management Science, 43(4):546–558, 1997.

DOI: 10.1287/mnsc.43.4.546

[12] S. Martello. Knapsack Problems: Algorithms and Computer Implementations. John Wiley& Sons, Inc., New York, NY, 1990.

[13] D. Pisinger. The Quadratic Knapsack Problem-a Survey. Discrete Applied Mathematics, 155(5): 623–648, 2007.

DOI: 10.1016/j.dam.2006.08.007