以禁忌搜尋法求解整合型揀貨與配送問題｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	張子浩 Tz-hau Chang
論文名稱：	以禁忌搜尋法求解整合型揀貨與配送問題 Using Tabu Search for Intergraded Picking and Distribution Problem
指導教授：	喻奉天 Vincent F. Yu
口試委員:	郭人介 Ren-jieh Kuo 林詩偉 Shin-wei Lin
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2011
畢業學年度：	99
語文別：	中文
論文頁數：	78
中文關鍵詞：	倉儲管理、揀貨作業、配送作業、禁忌搜尋法
外文關鍵詞：	Warehouse management, Order-picking, Distribution management, Tabu search
相關次數：	點閱：2872 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

本研究以新的觀點探討揀貨作業與配送作業對於整體物流作業成本的影響。過去學者在探討物流倉儲的揀貨問題時，都注重在揀貨作業本身的成本節省，而忽略了對於後續配送作業的影響。實務運作上，許多企業為了提升服務品質，已經捨棄一天出貨一次的作業模式，在此種運作情境內，揀貨作業與配送作業之間的整合將會非常重要。因此本研究以車輛途程問題(Vehicle Routing Problem; VRP)的概念建構整合揀貨作業與後續配送作業的最佳化物流作業成本問題之數學模型。由於最佳化軟體無法求解此類大型問題，故本研究以禁忌演算法為基礎，發展二階段的啟發式演算法，並針對此類問題發展特殊的移步方法，期望在合理的時間內，得到物流成本的改善。
實驗結果顯示，將後續的配送成本納入考量後，對整體物流成本將有顯著的改善。改善幅度約在4.90%~40.57%，帄均改善幅度為26.24%。根據實驗結果的統計分析可證明，訂單數的多寡與配送容量的大小對於演算法的改善幅度有顯著之影響。其中整體物流成本的最佳化與犧牲某階段作業效率的必要性之間並無明顯的關係。考量整體物流成本也可能使各階段的作業成本都獲得改善。

In this study, we take a new point of view on the impact of the picking and distribution operations on the overall logistics costs. Most previous researches on the picking operation focused on minimizing the costs of picking operation, but ignored its influence on the subsequent distribution operation. In practice, to improve the service quality, many logistics firms have stopped using the traditional one delivery per day distribution mode. In this case, the integration of the picking and the distribution operations become very important. Therefore, this research uses the concept of VRP (Vehicle Routing Problem) to construct a mathematical model for the optimal logistics operation cost problem, which considers both the picking operation and the subsequent distribution operation. Since large-scale problem instances cannot be solved to optimality by optimization software, we developed a two-stage meta-heuristic based on the tabu search method to solve the problem. Problem specific special moves are also developed so that the overall logistics costs can be reduced within a reasonable amount of computational time.
The results of computational study indicate that a significant improvement can be achieved after considering the distribution cost. The improvement ranges from 4.90% to 40.57%, and the average improvement is 26.24%. Statistic analysis of the experimental results shows that the number of orders and the distribution vehicle capacity have significant impact on the improvement obtained by the proposed heuristic. The results also indicate that it is possible to improve overall logistics costs without sacrificing the operational efficiency of some stages. In fact, optimizing the overall logistics costs may also improve the operational costs of all stages.

摘要 .................................................... I
Abstract ............................................... II
致謝 ................................................... III
目錄 .................................................... IV
表目錄 .................................................. VI
圖目錄 .................................................. VII
第一章 緒論 ............................................. 1
1.1 研究背景............................................. 1
1.2 研究動機............................................. 2
1.3 研究目的............................................. 3
1.4 研究假設............................................. 4
1.5 論文架構............................................. 7
第二章 文獻探討 ......................................... 9
2.1 物流中心作業......................................... 9
2.1.1 揀貨路徑問題....................................... 10
2.1.2 揀貨批次問題....................................... 11
2.2 VRP問題與求解方法 ................................... 13
2.2.1 VRP問題 ........................................... 13
2.2.2 VRPTW問題 ......................................... 13
2.2.3 求解方法........................................... 14
2.3 通用啟發式演算法..................................... 15
第三章 數學規劃模型 ..................................... 17
3.1 問題定義............................................. 17
3.1.1 揀貨批次路徑問題................................... 17
3.1.2 整合型揀貨與配送作業問題........................... 20
第四章 演算法設計 ....................................... 27
4.1 初始解建構........................................... 27
4.2 啟發式演算法......................................... 27
4.2.1 移步............................................... 27
4.2.3 禁忌搜尋........................................... 37
4.2.4 兩階段啟發式演算法................................. 39
4.2.5 演算法驗證......................................... 39
第五章 實驗設計與結果分析 ............................... 41
5.1 測詴範例建立......................................... 41
5.2 參數測詴............................................. 42
5.3 實驗設計............................................. 43
5.4 測詴結果............................................. 44
5.5 ANOVA統計檢定分析 ................................... 45
5.5.1 基本假設檢定....................................... 45
5.5.2 變異數分析......................................... 46
第六章 結論與建議 ....................................... 57
6.1 結論................................................. 57
6.2 研究貢獻............................................. 57
6.3 建議................................................. 58
參考文獻 ................................................ 59
附錄 .................................................... 62

                                

Albareda-Sambola, M., Alonso-Ayuso, A., Molina, E., & De Blas, C. S. (2009). Variable neighborhood search for order batching in a warehouse. Asia-Pacific Journal of Operational Research, 26(5), 655-683.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers and Operations Research, 30(5), 787-800.
Baker, E. K. (1983). An exact algorithm for the time-constrained traveling salesman problem. Operations Research, 31(5), 938-945.
Bartholdi, J., & Hackman, S. (2011). Warehouse & distribution science. Available from http://www2.isye.gatech.edu/~jjb/wh/book/editions/wh-sci-0.94.pdf
Beasley, J. E. (1983). Route first--cluster second methods for vehicle routing. Omega, 11(4), 403-408.
Bodin, L., Golden, B., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research, 10(2), 63-211.
Bozer, Y., & Kile, J. (2008). Order batching in walk-and-pick order picking systems. International Journal of Production Research, 46(7), 1887-1909.
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant System algorithm for thevehicle Routing Problem. Annals of Operations Research, 89, 319-328.
Chang, Y. H. (1998). Logistical Management: Hwa Tai Publishing.
Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53(5), 512-522.
De Koster, M., Van Der Poort, E., & Wolters, M. (1999). Efficient orderbatching methods in warehouses. International Journal of Production Research, 37(7), 1479-1504.
De Koster, R., Le-Duc, T., & Roodbergen, K. (2007). Design and control of warehouse order picking: A literature review. European Journal of Operational Research, 182(2), 481-501.
De Koster, R., & Van Der Poort, E. (1998). Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions. IIE transactions, 30(5), 469-480.
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3), 243-278.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gademann, A. J. R. M., Van Den Berg, J. P., & Van Der Hoff, H. H. (2001). An order batching algorithm for wave picking in a parallel-aisle warehouse. IIE Transactions, 33(5), 385-398.
Gademann, N., & Van De Velde, S. (2005). Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions, 37(1), 63-75.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340-349.
Glover, F., & Taillard, E. (1993). A user's guide to tabu search. Annals of Operations Research, 41(1), 1-28.
Goetschalckx, M., & Ratliff, H. (1988). Order picking in an aisle. IIE transactions, 20(1), 53-62.
Gu, J., Goetschalckx, M., & McGinnis, L. (2007). Research on warehouse operation: A comprehensive review. European Journal of Operational Research, 177(1), 1-21.
Hall, R. (1993). Distance approximations for routing manual pickers in a warehouse. IIE transactions, 25(4), 76-87.
Hsu, C., Chen, K., & Chen, M. (2005). Batching orders in warehouses by minimizing travel distance with genetic algorithms. Computers in Industry, 56(2), 169-178.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Laporte, G., Gendreau, M., Potvin, J.-Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5), 285-300.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for thetraveling-salesman problem. Operations Research, 21(2), 498-516.
Or, I. (1976). Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Northwestern University.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451.
Petersen, C., & Aase, G. (2004). A comparison of picking, storage, and routing policies in manual order picking. International Journal of Production Economics, 92(1), 11-19.
Petersen, C., Aase, G., & Heiser, D. (2004). Improving order-picking performance through the implementation of class-based storage. International Journal of Physical Distribution & Logistics Management, 34(7), 534-544.
Petersen II, C. (2000). An evaluation of order picking policies for mail order companies. Production and Operations Management, 9(4), 319-335.
Petersen II, C., & Schmenner, R. (1999). An evaluation of routing and volume-based storage policies in an order picking operation. Decision Sciences, 30(2), 481-501.
Ratliff, H., & Rosenthal, A. (1983). Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Operations Research, 31(3), 507-521.
Semet, F., & Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41(4), 469-488.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.
Taillard, E., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2), 170-186.
Tan, K. C., Lee, L. H., Zhu, Q. L., & Ou, K. (2001). Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering, 15(3), 281-295.
Tompkins, J., White, J., & Bozer, Y. (2010). Facilities planning: Wiley.
Toth, P., & Vigo, D. (2002). The vehicle routing problem: Society for Industrial Mathematics.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116(1), 87-99.
Van Breedam, A. (1995). Improvement heuristics for the Vehicle Routing Problem based on simulated annealing. European Journal of Operational Research, 86(3), 480-490.
Yu, B., Yang, Z.-Z., & Yao, B. (2009). An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 196(1), 171-176.

簡易檢索 / 詳目顯示

相關論文