應用螞蟻演算法求解儲位重整問題

Ant algorithm for the Storage Recombination Problem

朱正成(Cheng-Cheng Chu)

指導教授 ： 張淳智 ； 楊志文

國立臺中科技大學/商管學群/事業經營研究所/碩士(2008年)

摘要

存貨管理對企業而言是一門重要的課題，良好的存貨管理可以降低企業額外所付出之成本，而「儲位重整」則是輔助企業，將已經造成混亂情況之成品環境，迅速且花費最少成本，達到恢復原始成品分類或改變成品分類之目的。前述儲位重整問題目前尚未有相關文獻加以探討，因此，本研究乃先針對問題進行定義，再建立問題數學模式並加以求解。本研究期望找出「儲位重整問題」之最小成本，由於本研究所提出之問題是屬於組合最佳化問題，因此本研究採取近年來發展迅速之螞蟻演算法進行求解，同時為了求解的正確性及周延性，本研究自行設計出各種類型之問題，並依照各類型問題，分別尋找用於螞蟻演算法求解之適合參數設定。為了瞭解使用螞蟻演算法之求解品質，本研究另外採取「貪婪法」來進行求解，並做為比較之基礎，最後再將兩個方法的求解結果進行比較。結果顯示，螞蟻演算法與貪婪法求解結果相比，其求解誤差率皆低於4.02%，但使用求解時間相比，在求解問題規模數為500之問題，使用貪婪法求解之運算時間為2879分鐘，使用螞蟻演算法之運算時間則僅需10.5分鐘，因此在求解實務大型問題時相當具有應用價值。

關鍵字

螞蟻演算法 ； 儲位重整問題 ； 整櫃問題

並列摘要

Inventory management is a critical topic when it comes down to business. With good storage management, one may be able to decrease the total cost in extra spending; and along with “Storage Recombination”, it becomes an asset to the business itself. “Storage Recombination” takes the chaotic conditions of inventory environment in to account, it is fast, efficient and low cost, help restoring the original inventory classification or the goal for production labeling. However there has not been any related article on the topic of “Storage Recombination”. Therefore this research first defines the definition for the problem, creating a mathematical formula for the problem then solving it. Hoping to find the lowest cost for the “Storage Recombination Problem”, due to the fact that the problem itself is a kind of the combination optimization, Therefore, this paper is done through the modern method of Ant Algorithm to obtain the solution. At the mean time, to make sure that the solutions is valid and expandable, we have created many problem sets, and through indifferent categorize using the method of Ant Algorithm to obtain the valid parameters. Also to understand the quality of the solution given by the method of Ant Algorithm, we use another method of Greedy Method to obtain the solution simultaneously, so at the end we may compare both results. The results show contrast between Ant Algorithm and Greedy Method, their error rates are lower than 4.02%. But the study compares with the computing time that problem size is 500, the computing time which use greedy method is 2879 minutes and the computing time which use ant algorithm is 10.5 minutes. That means our solver base on Ant Algorithm is valuable in practice use.

並列關鍵字

Ant Algorithm ； Storage Recombination Problem ； pre-marshalling problem

參考文獻

Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18, 41-48.

Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved Ant System algorithm for the Vehicle Routing Problem. Annals of Operations Research, 89, 319-328.

Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344, 243-278.

Dorigo, M., & Caro, G. D. (1999). Ant Colony Optimization: A New Meta-Heuristic. IEEE, 1470-1477.

Dorigo, M., & Gambardella, L. M. (1997a). Ant colonies for the travelling salesman problem. BioSystems, 43, 73-81.