應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研究

Abstract

具時窗限制之回程取貨車輛路線問題(Vehicle Routing Problem with Backhauls and Time Windows, VRPBTW)為傳統車輛路線問題所發展出的相關問題，其假設車輛必須先服務完所有送貨點顧客，然後才能開始服務取貨點顧客，且所有顧客皆有時間窗之限制，求解複雜度相當高，屬於NP-Hard問題。 本研究應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題，研究方法分為兩階段進行。第一階段採取時間窗離散化(Time Window Discretization)的方法，將VRPBTW問題中的時間窗限制消除，轉換成無時間窗的VRPB問題，並根據VRPBTW問題特性設計問題規模精簡策略，縮小問題規模。第二階段求解轉換後的VRPB問題，首先以最近鄰點法構建起始解，採用Reduction、1-0、1-1、S-S及Or-opt等鄰域搜尋法進行改善，並且應用可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)做為求解VRPB問題之巨集啟發式解法架構。 本研究以Gelinas et al. (1995)的15題國際標竿例題做為測試例題，利用C#語言撰寫程式，在Intel(R)雙核心，CPU為2.00GHz的個人電腦進行測試。結果發現，本研究第一階段所採用之五項問題規模精簡策略可有效地簡化轉換後無時窗的VRPB問題規模。15題標竿例題中，節點總數平均減少15.3%，節線總數平均減少97.3%。在第二階段本研究設計之BATA模組測試中，15題標竿例題之最佳結果，車輛數平均誤差為0.87輛，且有5題找到文獻已知最佳結果；旅行成本平均誤差為5.32%。本研究亦發現，在標竿題庫BHR101題組中，車輛數均能找到已知最佳結果，顯示結合時窗離散策略與可回溯式門檻接受法進行求解，對於原作業點時間窗寬度較小且均勻的問題，求解效果較佳。

Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. The VRPBTW assumes that all linehaul customers should be visited before any backhaul customer, and all customers need to be visited within a specific time window. In this thesis, we proposed a two-phase approach to solve the VRPBTW problems. In the first phase, we transformed the VRPBTW problems to approximate VRPB problems, removing the time window constraints from the original problems. We also proposed Problem Scale Simplification Strategy to reduce the size of the transformed VRPB problems. The second phase is focused on solving the transformed VRPB problems using a meta-heuristic approach. A feasible initial solution was first generated by Nearest Neighbor algorithm, and improved by neighborhood search methods such as Reduction, 1-0, 1-1, S-S, Or-opt. We then applied Backtracking Adaptive Threshold Accepting (BATA) to further improve the solutions. The 15 benchmark problems described by Gelinas et al. (1995) were selected for the evaluation of our meta-heuristics. Our proposed heuristics were coded in Visual C# and tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. We found that our proposed Problem Scale Simplification Strategy can effectively reduce the number of nodes and arcs by 15.3% and 97.3% respectively on average. Results showed that for the 15 benchmark problems, the average deviation from the best known solutions are 0.87 in fleet size, and 5.32% in total distance respectively. We also found five best known solutions of the 15 VRPBTW benchmarks. The results of our study implied that our proposed time window discretization approach is most effective for solving VRPBTW problems with uniform and relatively small time windows.