臺灣博碩士論文加值系統

在一般訂單批量問題的研究中，顧客訂單僅允許指派至單一張揀貨單中，若可將訂單內品項做合適的分割並合併成為多張揀貨單，可使在訂單合併時更具有彈性。且在單一樓層的物流中心倉儲揀貨系統中，揀貨時不僅需考量平面的行走路徑，還需考慮揀貨走道內的立體揀貨路徑。因此本研究目的為將多張顧客訂單中的品項做合適的合併成為多張揀貨單，同時規劃在揀貨走道內同時揀取多張揀貨單的揀貨路徑，降低揀貨行走時間，進而減少總系統的完工時間。
本研究提出一套啟發式演算法求解訂單批量問題，搭配模擬退火法求解各揀貨走道內的揀貨單揀取路徑。並探討在不同規模下的倉儲環境，啟發式演算法之求解效益。實驗結果發現，本研究之啟發式演算法在求解可分割假設下的訂單批量問題，可有效降低總系統揀貨完工時間。並由模擬退火法可成功規劃，各揀貨走道內同時揀取多張揀貨單的揀貨路徑，得到最佳的揀貨行走時間，驗證本啟發式演算法可有效降低物流中心倉儲揀貨作業時的總系統完工時間。

This research focuses on order batching problem which can split customer order, and design pick routing within aisles. A model is developed to minimize the system pick time which is represented by the longest time of picking orders. A heuristic algorithm is developed to solve the order batching and in-aisle routing problem. The solution algorithm is constructed by using simulated annealing algorithm specific focused on the in-aisle pick routing.
From the experiment results, this heuristic algorithm can solve several types of problems effectively. The results also indicate this algorithm can reduce system pick time and increase the system efficiency for the warehouse of operations.

摘 要 I
ABSTRACT II
圖目錄 V
表目錄 VII
一、緒論 1
1.1 研究背景與動機 2
1.2 研究目的 3
1.3 研究範圍與限制 4
1.4 研究方法與架構 6
二、文獻探討 7
2.1訂單批量問題 7
2.1.1 訂單批量問題的假設環境及求解目標 8
2.1.2 訂單批量問題的求解法與求解效率 9
2.2 揀貨路徑規劃問題 13
2.2.1 水平揀貨路徑規劃 15
2.2.2 垂直揀貨路徑規劃 18
2.2.3 旅行銷售員問題求解法 20
2.3啟發式演算法 22
2.3.1模擬退火法(Simulated Annealing, SA) 22
2.3.2 門檻接受法(Threshold Accepting, TA) 24
2.3.3 禁忌搜尋法(Tabu Search, TS) 26
2.4 田口式實驗設計 28
2.5小結 30
三、問題描述與模式建構 32
3.1 問題描述與假設 32
3.1.1 問題環境描述 32
3.1.2 研究問題假設 35
3.2 建構模式 36
3.2.1 變數定義 36
3.2.2 數學模式建立 39
3.2.3 數學模式驗證 41
3.3 揀貨單合併程序 42
3.4 揀貨走道內揀貨路徑規劃 47
3.4.1 模擬退火演算法 48
3.4.2 初始揀貨路徑建構程序 50
3.4.3 揀貨路徑改善程序 52
3.5 揀貨單改善程序 53
3.5.1 揀貨單改善程序 54
3.5.2 交換揀貨單及改善揀貨單選取規則 55
四、範例與例題驗證 60
4.1範例問題說明 60
4.2 田口參數實驗分析 62
4.2.1 田口參數實驗步驟說明 62
4.2.2 田口參數設計實例驗證分析 63
4.3 實驗求解品質驗證 68
4.3.1 啟發式求解法品質驗證 68
4.3.2 例題品質驗證 71
4.4 敏感度分析 81
4.4.1 揀貨走道內設備速率之實驗分析 82
4.4.2 不同揀貨設備容量之實驗與分析 84
4.5 小結 86
五、結論與未來研究方向 88
5.1 研究結論 88
5.2 未來研究方向 89
參考文獻 90
附錄一 LINGO求解程式碼及結果 94
附錄二 顧客訂單資料 96
附錄三 小型例題求解結果 100
附錄四 大型例題求解結果 103

1.曾國男，魏乃捷，2002，現代物流中心，初版，復文書局，台南市。
2.吳復強，2005，產品穩健設計：田口方法之原理與應用，初版，全威圖書有限公司，臺北縣。
3.張福榮，2000，物流管理，初版，五南圖書出版有限公司，台北市。
4.邱婉婷，2007，在有交叉走道的倉儲環境之下探討訂單批次問題，國立雲林科技大學，碩士論文。
5.陳建緯，2001，大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用，國立交通大學，碩士論文。
6.陳隆熙，2002，一個解決TSP問題最佳解的穩定方法-以TA演算法為例，大葉大學，碩士論文。
7.黃小芬，2005，考慮有限巡行距離下之混合收、送貨車輛途程問題，國立雲林科技大學，碩士論文。
8.羅中育，2001，田口品質工程應用於模擬退火法參數組合之研究-以旅行推銷員問題(TSP)為例，國立雲林科技大學，碩士論文。
9.Heragu, S.,1997, Facilities Design, PWS, Boston.
10.Tompkins, J.A., White, J.A., Bozer, Y.A. and Tanchoco, J.M.A., 2003, Facilities Planning, 3rd edition, John Wiley & Sons, Inc., Hoboken, NJ.
11.Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., 1995, The Traveling Salesman Problem, Wiley, Chichester.
12.Aase, G., Petersen and C.G., 2004, “A comparison of picking, storage, and routing policies in manual order picking”, International Journal of Production Economics, vol. 92, pp.11-19.
13.Bektas, T., 2006, “The multiple traveling salesman problem: an overview of formulations and solution procedures”, Omega International Journal of Management Science, vol. 34, pp.209-219.
14.Calvo, R.W. and Cordone, R., 2003, “A heuristic approach to the overnight security service problem”, Computers & Operations Research, vol. 30, pp.1269-1287.
15.Chen, M.C. and Wu, H.P., 2005, “An association-based clustering approach to order batching considering customer demand patterns”, Omega International Journal of Management Science, vol. 33, pp. 333-243.
16.Chen, M.C., Huang, C.L., Chen, K. Y. and Wu, H.P., 2005, “Aggregation of orders in distribution centers using data mining”, Expert Systems with Applications, vol. 28, pp.453-460.
17.De Koster, R., Le-Duc, T. and Roodbergen, K.J., 2007, “Design and control of warehouse order picking: A literature review”, European Journal of Operational Research, vol. 182, pp. 481-501.
18.Elsayed, E.A. and Stern, R.G., 1983, “Computerized algorithms for order processing in automated warehousing systems”, International Journal of Production Research, vol. 21, no.4, pp.579-586.
19.Elsayed, E.A. and Unal, O.I., 1989, “Order batching algorithms and travel-time estimation for automated storage/retrieval systems”, International Journal of Production Research, vol. 27, no. 7, pp.1097-1114.
20.Gademann, N. and van de Velde, S., 2005, “Order batching to minimize total travel time in a parallel-aisle warehouse”, IIE Transactions, vol. 37, pp.63-75.
21.Gademann, N., van den Berg, J. and van der Hoff, H., 2001, “An order batching algorithm for wave picking in a parallel-aisle warehouse”, IIE Transactions, vol 33, pp.385-398.
22.Gademann, N. and Velde, S.V., 2005, “Order batching to minimize total travel time in a parallel-aisle warehouse”, IIE Transactions, vol. 37, pp.63-75.
23.Gavish, B., 1976, “A note on the formulation of the m-salesman traveling salesman problem”, Management Science, vol. 22, no. 6, pp.704-705.
24.Gibson, D.R. and Sharp, G.P., 1992, “Order batching procedures”, European Journal of Operational Research, vol. 58, pp.57-67.
25.Glove, F., 1977, “Heuristucs for Integer Programming Using Surrogate Constraints”, Decision Sciences, vol. 8, pp.156-166.
26.Gu, J., Goetschalckx, M. and McGinnis, L.F., 2007, “Research on warehouse operation: A comprehensive review”, European Journal of Operational Research, vol. 177, pp. 1-21.
27.Hall, R.W., 1993, “Distance approximation for routing manual pickers in a warehouse”, IIE Transactions, vol. 25, pp.77-87.
28.Hsu, C.M., Chen, M.C. and Chen, K.Y., 2005, “Batching orders in warehouse by minimizing travel distance with genetic algorithms”, Computers in Industry, vol. 56, pp.169-178.
29.Kim, B.I., Heragu, S.S., Graves, R.J. and Onge, A.S., 2003, “Clustering-based order picking sequence algorithm for an automated warehouse”, International Journal of Production Research, vol. 41, no. 15, pp.3445-3460.
30.Kirkpatrick, S., C. D. Gelatt and M. P. Vecchi, 1983, “Optimization by simulated annealing”, Science, 200(4956), pp.671-680.
31.Laporte, G., 1992, “The Traveling Salesman Problem : An Overview of exact and approximate algorithms” European Journal of Operational Research, Vol. 59, pp. 231-247
32.Lin, S., 1965, “Computer solutions of the traveling salesman problem”, The Bell System Technical Journal, Vol. 44, pp. 2245-2269.
33.Makris, P.A. and Giakoumakis, I.G., 2003, “k-Interchange heuristic as an optimization procedure for material handling applications”, Applied Mathematical Modelling, vol. 27, pp.345-358.
34.Norback, J. P. and Love, R. F., 1979, “Heuristic for the Hamiltonian path problem in Euclidean two space”, Journal of Operations Research Society, Vol. 30, pp. 363-368.
35.Or. I., 1976, Traveling salesman-type Combinatorial Problems and Their Relation on the Logistics of regional Blood Banking, Northwestern University, Ph. D. Dissertation.
36.Pan, C.H. and Liu, S.Y., 1995, “A comparative study of order batching algorithms”, Omega International Journal of Management Science, vol. 23, no.6, pp. 691-700.
37.Petersen, C.G. and Aase, G., 2004, “A comparison of picking, storage, and routing policies in manual order picking”, International Journal of Production Economics, vol. 92, pp.11-19.
38.Roodbergen, K.J., 2001, Layout and routing methods for warehouses, RSM Erasmus University, the Netherlands, Ph.D. thesis.
39.Roodbergen, K.J. and De Koster, R., 2001a, “Routing methods for warehouses with multiple cross aisles”, International Journal of Production Research, vol. 39, no, 9, pp.1865-1883.
40.Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. N., 1977, “An analysis of Several Heuristics for the Traveling Salesman Problem”, SLAM Journal on Computing, Vol. 6, pp. 563-581, 1977.
41.Rosenwein, M.B., 1996, “A comparison of heuristics for the problem of batching orders for warehouse selection”, International Journal of Production Research, vol. 34, no.3, pp.657-664.