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

Time Window Discretization and BATA Heuristics for Solving the VRPBTW Problems

韓復華(Anthony F. Han) ； 陳仲豪(Chung-Hao Chen)

《運輸學刊》 22卷3期 (2010/09) Pp. 285-306

https://doi.org/10.6383/JCIT.201009.0285

摘要

本研究應用時窗離散(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.

並列關鍵字

Time window discretization ； Threshold accepting TA ； Backtrack adaptive threshold accepting BATA ； Vehicle routing problem with backhauls VRPB ； Vehicle routing problem with backhauls and time windows VRPBTW

參考文獻

李泰琳、張靖(2008)。應用時窗分割與整數化策略簡化時窗收卸貨問題之研究。運輸學刊。20(3)，313-350。

卓裕仁、朱佑旌(2008)。兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究。運輸計劃季刊。37(4)，405-429。

廖昱傑(2007)。應用可回溯式門檻接受法結合GENIUS求解VRP問題之研究(碩士論文)。交通大學運輸科技與管理學系。

Appelgren, L. H.(1969).A Column Generation Algorithm for a Ship Scheduling Problem.Transportation Science.3(1),53-68.

Appelgren, L. H.(1971).Integer Programming Methods for a Vessel Scheduling Problem.Transportation Science.5(1),62-74.