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

Time Window Discretization and BATA Heuristics for Solving the VRPBTW Problems

本研究應用時窗離散（Time Window Discretization）策略與可回溯式門檻接受（BATA）法求解具時窗限制之回程取貨車輛路線問題（VRPBTW）。研究方法分為兩階段進行：第一階段採取時間窗離散化的方法，將VRPBTW問題中的時間窗限制消除，轉換成無時間窗的VRPB問題，並設計問題規模精簡策略，縮小問題規模；第二階段求解轉換後的VRPB問題，應用可回溯式門檻接受法作為巨集啟發式解法架構。在求解績效評估方面，本研究以Gelinas et al.（1995）的國際標竿題庫進行測試。結果發現與目前已知最佳結果在車輛數上的平均誤差為0.87輛，且有5題找到文獻已知最佳結果；旅行成本的平均誤差為5.32％。本研究亦發現，對時窗離散所提出的精簡策略可有效地簡化轉換後無時窗的VRPB問題規模。此外，不同題型之測試結果則顯示，本研究提出的結合時窗離散策略與可回溯式門檻接受法的求解架構，對於原作業點時間窗寬度較小且均勻的問題效果較佳。

Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. In this paper, we proposed a two-phase approach to solve the VRPBTW. First, using a time window discretization approach, we removed the time window constraints from the original VRPBTW and transformed it to an approximate VRPB. The second phase was focused on solving the transformed VRPB using a BATA meta-heuristic approach. We also proposed some discretization strategies which can effectively reduce the problem size of the transformed VRPB. The 15 benchmark instances defined by Gelinas et al. (1995) were selected for the evaluation of our proposed meta-heuristics. Results showed that 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 benchmark instances. In addition, our results imply that our proposed time window discretization approach is most effective for those problems which have uniform and relatively small time windows.