以巨及啟發式解法求解時間窗車輛路線問題

Abstract

摘要 近年來車輛路線問題廣泛應用在相關實務問題上，因此有不少研究針對各種不同的車輛路線問題進行深入探討。其中時間窗車輛路線問題是所有車輛路線問題中，最基本也是最重要的一個問題，國內外亦有不少研究針對此問題進行求解。門檻接受法(Threshold Accepting, TA)與大洪水法(Great Deluge Algorithm, GDA)兩種巨集啟發式解法，在90年代便以提出、發展與應用，在求解相關問題上有不錯的表現。本研究以TA和GDA為搜尋架構，在交換模組中彈性加入車輛剩餘容量之權重值，以複合式交換成本進行交換改善，並對Solomon(1983)[29]之56題測試題庫進行穩定度測試與結果績效比較。 本研究解題架構包括起始解構建模組與包容性改善模組兩部份。起始解構建模組中又包含了最初起始解構建模組與鄰域搜尋模組。在最初起始解構建模組中，利用傳統的鄰近點法變化六種最初起始解構建模組；而在鄰域搜尋模組中包括一些採用複合式交換成本之傳統交換模組進行交換改善；包容性改善模組方面，本研究採用TA與GDA進行問題求解，其中有車輛剩餘容量權重值之組合。本研究測試環境為Windows XP作業系統、3G Hz處理器速度，以Visual C++ 6.0編譯軟體進行程式撰寫與測試。測試結果發現，執行效率上TA明顯優於GDA，而車輛數表現TA也略為優於GDA，但距離成本方面，TA表現則較GDA高出約2%。 針對56題測試例題，整理各種解題模組所得知最佳結果，有10題與文獻已知最佳結果相同，另外有11題車輛數多1輛，但距離成本優於已知文獻最佳解。本研究最佳結果，車輛數為418輛，距離成本為57515.52。與文獻已知最佳解比較，平均車輛數誤差為0.21輛；距離誤差為1.87%。整體來說，本研究在群聚類型的題型，表現最佳，而在隨機與混合類型的題型，則以車容量大類型的題型表現較好。

Abstract The Vehicle Routing Problem with Time Window (VRPTW), an extension of the classical Vehicle Routing Problems (VRP), is widely applied to logistics and home delivery. The VRPTW considers that customers request the carrier to serve them within a specific time interval, i.e. time window. Such a constraint makes the VRPTW harder to solve than the VRP. Therefore, most of the solution methods for VRPTW are heuristics or meta-heuristics. The Threshold Accepting (TA) and the Great Deluge Algorithm (GDA) are two meta-heuristics that have been developed in early 90’s. In this thesis, we developed two solution methods combining TA and GDA with traditional construction and neighborhood search algorithm, to solve the VRPTW. Furthermore, we proposed a compound cost function which simultaneously calculates the value of surplus capacity and travel time into a single and normalized function while evaluating the exchange cost of movement. We coded the computer programs in Visual C++, and tested on a 3G-Hz PC with Windows XP Operation System. A bank of Solomon’s 56 benchmark VRPTW instances was utilized to identify the performance of these TA and GDA methods. Results showed that the compound cost function is more effective than traditional cost function on solving VRPTW. As compared to the GDA-based method, the TA-based method implemented significantly more efficient and yielded results with slightly less number of vehicles required but about 2% more distance traveled. As to all of the 56 instances tested, the best solutions found by our proposed TA and GDA methods are respectively 418 vehicles and 57515.52 distance units. The average deviation of required vehicles is 0.21, and the average deviation of distance percentage is 1.87%. In sum, the performance of proposed TA and GDA methods is of competition to other meta-heuristics.