建構具演化能力之蟻群演算法－儲位重整問題之求解

Constructing an New ACS with Evolutional Capability for the Storage Recombination Problem

王爾謙(Erh-Chien Wang)

指導教授 ： 張淳智

國立臺中科技大學/資訊與流通學院/流通管理系碩士班/碩士(2012年)

摘要

本研究探討之「儲位重整問題」是發生在企業有過多的存貨，而導致倉儲空間的不足，迫使將成品放置於其它類型成品之儲存空間，使得倉庫之存貨呈現一個混亂的情況。本研究係為輔助企業在此種情況下，透過取下棧板來整理存貨，將存貨分類恢復至原先擬定之分佈狀態，進一步提升整體作業流程之效率。
由於儲位重整問題屬於組合最佳化問題，過去研究皆採用螞蟻演算法求解，但該方法於參數設定上為主觀設定或採用窮舉方式尋找最適參數，使過程需耗費相當多的時間。對此本研究提出一個「具演化能力之蟻群演算法」，融合了基因演算法之概念，尋找各種問題之最適參數來增加效益，來節省其窮舉所耗費之時間。測試結果發現，具演化能力之蟻群演算法於問題規模30、50、100時，有部分解可得到改善，而問題規模200時，可完全改善過去研究之演算法。在求解時間部分，本研究節省了窮舉時間，其節省之時間成本約為過去研究之100倍，證明本研究之演算法是有其效益的。

關鍵字

螞蟻演算法 ； 基因演算法 ； 儲位重整

並列摘要

The Storage Recombination Problem is a problem occurring when an enterprise faces the excessive stock and result in chaotic condition of inventory. This research aims to develop an efficient algorithm to restore the disordered stock layout.
Because Storage Recombination Problem is a kind of combination optimization problem, the ant algorithm was adopted to solve this type of problem in the past. However, it took a great deal of time in finding the best parameters since the early researches often take a trial and error or an exhaustive attack approach to search them. To improve the efficiency, this research proposes a new ACS with evolutional capability (ACSE), which combines ACS with the concept of genetic algorithm so as to search for the best parameters of ACS and the solution of Storage Recombination Problem simultaneously. The results show that ACSE can improve the results for Storage Recombination Problem especially in large scale cases. In the part of CPU time, ACSE spends only one hundredth amount of time than the traditional ant algorithm.

並列關鍵字

Ant colony optimization ； Genetic algorithm ； Storage recombination Problem

參考文獻

張雲豪（民98）。虛擬網路蟻群最佳化於儲位重整問題之研究（未出版之碩士論文）。國立臺中技術學院，臺中市。

陳春益、趙時樑（2004）。貨櫃碼頭出口儲區門型起重機小車取櫃問題之研究。運輸計劃季刊，3，449-469。

Beckers, R., Deneubourg, J. L., & Goss, S. (1992). Trails and U-turns in the selection of the shortest path by the ant Lasius niger. Journal of Theoretical Biology, 159(4), 397-415.

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.

Chen, S. M., & Chien, C. Y. (2011). Parallelized genetic ant colony systems for solving the traveling salesman problem. Expert Systems with Applications, 38(4), 3873-3883.