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

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

王志仁(Jr-Ren Wang)

指導教授 ： 胡黃德

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

摘要

宅配物流中心在商品流通的服務過程中，為滿足消費者的配送需求與追求運輸成本最小化的期望下，希望能迅速地做出最佳的配送路徑決策。此決策不但能增進獲利來達到企業營運所追求的目標，也能提升其本身的服務品質，藉此滿足消費者多變需求下的滿意度。因此，本研究將針對消費者對於產品種類的多樣化需求下，採用先以節省法為基礎，求得一組優良的初始解，再輔以禁忌搜法 (STS) 進行宅配物流中心移步交換與路徑規劃中的車輛途程間之改善，來滿足總配送成本最小化的目標。而在本研究之隨機模擬的測試例題中，所提出之 STS 演算法與最佳化軟體 (LINGO) 的相互比較下，可以發現到本研究所提之STS法可以有效率地求出一組優良的解。然而當問題規模較大時，STS 與 LINGO 的運算時間之差異程度更為顯著，而在求解的效果上，不會有太大的差異。

關鍵字

節省法 ； 禁忌搜尋法 ； 車輛途程問題 ； 宅配物流中心

並列摘要

For the home delivery service industry, the company has to find the shortest delivery path in order to satisfy the consumer’s needs with the minimum of transportation cost. Besides, it increases not only the profits of company but also raises the service qualities of this company to fit the customers’ various demands. In this research, we propose a heuristic method which was based on savings algorithm and tabu search (STS) with move methods and vehicle routing decisions to satisfy the objective of minimum transportation cost. In comparison with the solutions by STS and optimum solutions by LINGO with the simulation test problems, we found that STS had better performance in these test problems. When the problem size becomes larger, the between STS and LINGO solution time becomes significantly different. However, the solutions of the STS approach have no significant difference with that of the LINGO in all test problems.

並列關鍵字

Savings Algorithm ； Tabu Search ； Vehicle Routing Problem ； Home Delivery Depo

參考文獻

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

鄭啓忠，「配送中心場址規劃及選擇」，元智大學工業工程研究所，碩士論文， 1995。

徐明輝，「多部車一般性車輛途程解算法之研究」，元智大學工業工程研究所，碩士論文，1997。

許哲榮，「多產品配送中心場址規劃與選擇」，元智大學工業工程研究所，碩士論文，1998。

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