混合式演算法應用於同時收送貨之車輛途程問題

Applying Hybrid Algorithm to the Vehicle Routing Problem with Simultaneous Delivery and Pickup

鄭雁嬬(Yan-Ru Cheng)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

摘要

物流中心配送成本在物流業中佔很大的成本比例，而減少成本的主要因素，就是要在合理的時間、車輛和配送路徑將產品送達到顧客手中。同時收送貨車輛途程問題擺脫了傳統車輛途程問題，在需求點拜訪一次的限制下，可以進行同時收送貨的作業。本研究的目的主要在硬式時窗限制下，針對不同車容輛的種類與單一車容量的種類的適用時機為何。本研究採用節省法輔以路線內與路線間改善法求的較優良的解，再以粒子群演算法結合模擬退火法的降溫機制去進行途程中的路徑改善，以達到最小總配送成本的目標。而本研究所提出的混合式演算法與最佳化軟體 LINGO 的比較，發現本研究所提出的混合式演算法可以有效率地提出一組優良的解。且當問題規模擴大時，混合式演算法與 LINGO的運算時間之差異程度更為顯著，而在求解的效果上，不會有太大的差異。此結果與啟發式解法比較在總成本的差異上也有平均2 % 的改善，運算時間也無太大差異。而在多車種與單一車種的研究中發現，使用多車種可以有效的降低成本，但如果要使用單一車種，則是以車容量較少的車種比車容量較多的車種表現好。因此本研究所提出的混合式演算法可以有效的求解出較佳的解，也能有效的處理實務上的需求。

關鍵字

物流中心 ； 硬式時窗 ； 多車種 ； 節省法 ； 混合式演算法

並列摘要

Distribution cost accounts for the large percentage of total cost in logistics activities. The combination of fair time, right vehicles, and right routing can cut down the total cost and ensure the delivery to the customers. Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP) is a variation of classical Vehicle Routing Problems (VRP). Under the limit of visiting once for demand points, the VRPSDP can do delivery and pickup as the same time. The purpose of this study was to adopt the Savings Method and hybrid algorithm based on Particle Swarm Optimization (PSO) and Simulated Annealing (SA) to search for the objective of minimum transportation cost. In comparison with the optimum solutions by LINGO and hybrid algorithm with the test problems, we found that hybrid algorithm had better performance in these test problems. When the problem size becomes larger, the LINGO and hybrid algorithm solution time becomes significantly different. However, the solutions of the LINGO have no significant difference with that of the hybrid algorithm approach in all test problems. The heuristic algorithm has an average of 2% improvement on the total transportation cost, but the solution time is not significant different. This study found that various car types performed better than the unique car type.

並列關鍵字

Distribution Center ； Hard Window ； Various Car types ； Saving Method ； Hybrid Algorithm

參考文獻

張有恆，「現代物流管理」，華泰文化事業股份有限公司，2005。

曹餘偉，「應用禁忌搜尋法求解多車種多物流中心之區位途程問題」，元智大學工業工程研究所，碩士論文，2006。

邱仕銘，「同時收送貨車輛配送問題之研究」，長榮大學經營管理研究所碩士論文，2006。

陳坤賓，「模擬退火演算法應用於車輛途程問題之研究」，元智大學工業工程研究所，碩士論文，1998。

敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程研究所，碩士論文，1999。