兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究

A TWO-PHASE BACKTRACKING THRESHOLD ACCEPTINGMETA-HEURISTIC FOR THE VEHICLE ROUTING PROBLEM WITH BACKHAULS AND TIME WINDOWS

時窗限制回程取貨車輛路線問題（vehicle routing problem with backhaul and time windows, VRPBTW）是車輛路線問題（vehicle routing problem, VRP）的延伸，屬於解題複雜度很高的NP-hard問題，其在物流配送實務上具有很高的應用價值。本研究結合門檻接受法（threshold accepting, TA）與傳統啟發式方法，設計一套可求解VRPBTW 之兩階段回溯式門檻接受法（two-phase backtracking threshold accepting, TBTA），並採用15題國際標竿例題進行測試，以分析此TBTA 巨集啟發式解法之解題績效。測試結果發現：車輛數之平均誤差百分比為3.52%，行駛時間之平均誤差百分比為2.81%，CPU之平均運算時間為33.69秒；此結果顯示TBTA法在求解VRPBTW上具有應用潛力。

The vehicle routing problem with backhauls and time windows (VRPBTW), which simultaneously considers the operations of delivery and pickup, is a variant of the classical vehicle routing problem (VRP). Successful application of the VRPBTW in real-world distribution will improve the performance of logistics. Due to the NP-hard complexity of VRPBTW, the most solution methods are heuristics and meta-heuristics. This paper aims to develop a two-phase backtracking threshold accepting (TBTA) meta-heuristic approach, which combines the threshold accepting (TA) meta-strategy and the traditional local search algorithms, to solve the VRPBTW. We adopted fifteen VRPBTW benchmark instances to test and analyze the performance of the proposed TBTA meta-heuristic. The average error percentages of TBTA are 3.52% for the objective of fleet size and 2.81% for the objective of traveling time. Moreover, the average value of CPU running time is merely 33.69 seconds. Computational results implied that the TBTA actually provides an efficient tool for VRPBTW applications.