應用禁忌搜尋法求解多車種多產品宅配中心之車輛途程問題

Applying Tabu Search to the Vehicle Routing Problem with Multi-Product and Heterogeneous Fleet Home Delivery Depot

蔡 佩 紋(Pei-Wen Tsai)

指導教授 ： 胡 黃 德

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

摘要

企業為了提高利率，以及滿足消費者的配送需求和降低物流成本，因此企業必須快速地決定最佳配送路線，來提升本身服務品質，以增加企業競爭力。以往在規劃物流配送系統時，只考慮到區位的影響因素，進而求出最小運送成本，然而在消費者需求越來越多樣化的今日，必須同時將這些會造成影響的因素考慮進去，來計算出總運送成本，並符合實際之狀況。本研究之目的為針對車輛種類以及消費者在產品種類多樣化的需求下，首先採用節省法為基礎，求得一優良的初始解，接著再以禁忌搜尋法來進行移步交換的車輛配送路徑規劃之改善，目標為最小化總配送成本。在本研究的結果中發現，多車種所求得之成本優於單一車種。此外也顯示，在提出來之 STS 演算法與最佳化軟體 LINGO 的比較下， STS 演算法能夠有效地求出優良的解。當問題規模越大時， STS 演算法與 LINGO 的運算時間之差異程度更大，但是在求解的效果上，差異並不會太大。所以 STS 演算法不僅能有效地求出優越的解，在規模較大的問題下也能夠有效地處理，以達到實務上之需求。

關鍵字

宅配物流中心 ； 多產品 ； 多車種 ； 節省法 ； 禁忌搜尋法

並列摘要

The Vehicle Routing Problem is one of basic logistics operation problems that appear in home delivery real-world problems. To increase the profit rate as the target of the business operation, the company has to find the shortest delivery path in order to satisfy the consumer’s needs with the minimum of transportation cost. Also, the considerations of transportation cost and various customers’ needs have raised the problem to be more important than before. The purpose of this study was to develop a heuristic method which was based on savings method and tabu search (STS), with move methods and vehicle routing decisions to satisfy the objective of minimum transportation cost. The results show that the total cost by combing various car size are less than the unique car size. In comparison with the optimum solutions by LINGO and STS with the test problems, we found that STS had better performance in these test problems. When the problem size becomes larger, the LINGO and STS solution time becomes significantly different. However, the solutions of the LINGO have no significant difference with that of the STS approach in all test problems.

並列關鍵字

Home Delivery Depot ； Multi - product ； Heterogeneous Fleets ； Savings Algorithm ； Tabu Search

參考文獻

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

葉仁吉，「以類免疫演算法應用於船席指派問題之研究」，淡江大學運輸科學研究所，碩士論文，2006。

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

俞錫強，「零場站之車輛途程模式」，元智大學資訊管理研究所，碩士論文，2006。

馬凱賢，「結合區域搜尋之遺傳演算法求解多車種之車輛途程問題」，國立暨南國際大學土木工程研究所，碩士論文，2007。