使用一個有效率的啟發式模擬退火法求解不確定需求下的庫存策略

An Efficient Approach for Simulated Annealing Heuristic to Optimize Inventory Policy under Uncertain Demand

鄭潮駿(Chao-Chun Cheng)

指導教授 ： 任恒毅

元智大學/工程學院/工業工程與管理學系/碩士(2011年)

https://doi.org/10.6838/YZU.2011.00124

摘要

啟發式演算法以其高效率的性能，受到許多領域的關注與應用，解決許多最佳化問題，然而每種演算法都必須要設定參數，它會影響求解的品質以及搜索最佳解花費的時間，因此如何設定最佳參數是一個很重要的議題。使用者往往會發現設定演算法的參數是一項艱鉅的工作，本研究將最佳計算資源配置(OCBA)幫助模擬退火法決定較佳參數，進而找到較佳解，並使用一些測試函數與不確定需求下的庫存問題，比較OCBA-SA與SA的求解品質，分析是否能減少設定參數造成的困擾。

關鍵字

最佳資源配置 ； 模擬退火法

並列摘要

With the advance of computing power, heuristic algorithms are gaining popularity since they mainly increase the efficiency in finding better solutions for hard problems, mostly combinatorial optimization one. However, heuristic algorithms often need setting parameter values in many situations, and the choices of parameter value set may affect solution quality and calculation time, as indicated in much literature. Naïve user of those heuristics sees parameter setting as a daunting task. Without sacrificing the value of heuristics, the parameter setting can be thought of as finding a best design; and the best design is the one that assist the heuristic in finding the best solution. In the study, Simulated Annealing (SA) heuristic algorithm with Optimal Computing Budgeting Allocation (OCBA) is suggested to determine better SA parameters and optimal solution. Standard testing examples were tested to compare the solution quality of OCBA-SA and SA only. OCBA-SA was also applied to a material inventory problem to find optimal inventory level under uncertain demands.

並列關鍵字

OCBA ； Simulated Annealing

參考文獻

1.Bechhofer, R. E. (1954). A single-sample multiple decision procedure for ranking means of normal populations with known variances. The Annals of Mathematical Statistics, 25(1), 16-39.

2.Chen, C.-H., He, D., Fu, M., & Lee, L. H. (2008). Efficient simulation budget allocation for selecting an optimal subset. INFORMS Journal on Computing, 20(4), 579-595.

4.Chen, C.-H., Yucesan, E., Dai, L., & Chen, H.-C. (2010). Optimal budget allocation for discrete-event simulation experiments. IIE Transactions, 42(1), 60-70.

5.Dai, L. (1996). Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems. Journal of Optimization Theory and Applications, 91(2), 363-388.

6.Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions on, 1(1), 53-66.