應用蟻群最佳化演算法求解越庫作業系統的車輛途程與卡車排序問題

如今全球貿易蓬勃發展，各大企業在成本的考量下，不少業者委外第三方物流倉儲及運送，在這繁複的貿易網路圖中，物流中心即為其中繼點，負責轉運、倉儲、資訊交流等重要功能。傳統的物流中心有四大主要功能：接收、倉儲、訂單揀貨和運輸，其中倉儲與員工揀貨是成本最高的。越庫作業系統 (Cross-Docking, CD) 為一種供應鏈管理中物流中心策略處理貨物的方法，貨品由物流中心接收後經由訂單資訊的整合，直接將貨物整合並送往出貨，目的在減少倉儲與人工揀貨之成本。本研究考量物流中心之成本，應用越庫作業系統，整合車輛途程問題 (Vehicle Routing Problem, VRP) 與卡車排序問題 (Truck Sequencing)，目標為物流中心營運時間與總運輸時間最小化。首先建構混合整數規劃數學模型，由於此問題屬於NP-Hard問題，因此使用蟻群最佳化演算法 (Ant Colony Optimization, ACO) ，分別使用兩方法求解：方法一、使用兩階段求解，先找出最佳車輛途程後將車內貨品數量給予第二階段求解最佳卡車排序，方法二、應用同步處理的方式，每次迭代產生之菁英VRPCD螞蟻就建立一較優虛擬卡車序列螞蟻，並以此加強費洛蒙濃度，以兩問題總成本更新費洛蒙。使用Gurobi最佳化軟體驗證本研究之數學模型，得到之最佳解可以測試ACO之誤差；由於此兩問題合併在過去尚未有學者探討，故本研究參考文獻例題產生方式，產生30題測試例題。本研究應用兩種ACO程序，得到之結果顯示30題測試例題總平均而言ACO2得到較好的最小成本為9682.3確實改善了ACO1的結果，而30題中有25題得到的結果是優於ACO1的，並且經過敏感度分析，將ACO1的卡車排序部分使用Gurobi測試最佳解，結果證實本研究卡車排序部分皆找到最佳解，並且於ACO2中由於VRPCD部分影響較深，故測試了VRPCD多次的處理情形，結果顯示VRPCD處理10次後得到的結果相較原始的處理1次來的降低許多，故未來將持續探討如何將VRPCD部分深入測試，預期未來能夠改善使得更接近最佳解。

關鍵字

越庫作業系統；車輛途程問題；卡車排序問題；蟻群最佳化演算法

並列摘要

Nowadays, the global trade booming, the freights are passed in and out the distribution centers and between companies frequently. For cost considerations, many companies outsource transportation and warehousing activities to the third-part logistics providers. In this complex logistics network, the cross-dock center is the point where the trucks are responsible for pickup and delivery and transfer between inbound and outbound traffic. The traditional warehouse has four major functions: receiving, warehousing, order picking and transport, which warehousing and staff picking are cost-intensive activities. Cross-docking is a logistics strategy in which freight is unloaded from inbound vehicles and (almost) directly loaded into outbound vehicles, with little or no storage in between. This strategy aims to reduce the cost of warehousing and order picking. This study considers a cross-docking system which combines the vehicle routing problem with cross-docking (VRPCD) for both inbound and outbound operations and truck sequencing problem (Truck Sequencing) at docks. The objective is to minimize the logistics center operation costs and transportation costs. Both VRP and sequencing problems are NP-hard problem. We first formulated the integrated problem with a mixed integer programming model. Since the integrated problem is a NP-hard problem, only small size instance can be solved with optimization software within reasonable computational time. We propose two ant colony optimization (ACO) algorithms to solve the problem. The first algorithm (ACO1) solves the VRP and sequencing problem by two independent ant colonies sequentially, in which the sequencing problem solved based on the results of the VRP. The second algorithm (ACO2) solves both problems simultaneously and iteratively by sharing the information between two ant colonies. In this study, the Gurobi optimization software is used to validate the mathematical model and tested for small size instances. Since there are no test instances for this integrated problem, we generate 30 test problems. The results show that ACO2 can obtain the optimal solutions in small size instances. ACO2 can provide better solutions in 25 out of the 30 test problems than ACO1. Through sensitivity analysis, we also found that the truck sequencing problem is easier to get the optimal solution than the VRPCD. We believe the proposed ACO algorithms can be used for practical use for the cross-docking system. In the future, we could consider multiple dock operations at the cross-dock for a more complex system.

並列關鍵字

Cross-Docking ； Vehicle Routing Problem ； Truck Sequencing ； Ant Colony Optimization

參考文獻

3. 羅敏華，「蟻群最佳化演算法於載重限制之車輛途程問題的研究」，元智大學工業工程與管理學系碩士學位論文，2003。

7. Arabani, A. R. B., Ghomi, S. M. T. F. and Zandieh, M. “A multi-criteria cross-docking Sequencing with just-in-time approach”, The International Journal of Advanced Manufacturing Technology, Vol. 49, No. 5-8, pp. 741-756, 2010.

4. Alpan, G., Ladier, A. L., Larbi, R. and Penz, B., “Heuristic solutions for transshipment problems in a multiple door cross docking warehouse”, Computers & Industrial Engineering, Vol. 61, No. 2, pp. 402-408, 2011.

5. Apte, U. M. and Viswanathan, S, “Effective cross docking for improving distribution efficiencies”, International Journal of Logistics, Vol. 3, No. 3, pp. 291-302, 2000.

8. Boloori Arabani, A. R., Fatemi Ghomi, S. M. T. and Zandieh, M., “Meta-heuristics implementation for Sequencing of trucks in a cross-docking system with temporary storage”, Expert Systems with Applications, Vol. 38, No. 3, pp. 1964-1979, 2011a.

國際替代計量

應用蟻群最佳化演算法求解越庫作業系統的車輛途程與卡車排序問題

全文下載

主題瀏覽