以改良型回溯門檻接受法求解回程取貨車輛路線問題之研究

A MODIFIED BATA APPROACH TO SOLVE VEHICLE ROUTING PROBLEM WITH BACKHAULS

本研究基於回溯門檻接受法（backtracking adaptive threshold accepting, BATA）提出一個新的求解回程取貨車輛路線問題（vehicle routing problem with backhaul）的巨集解法。回溯門檻接受法是由Tarantilis與Kiranoudis首先提出，對於門檻回溯比率值b僅考慮小於1的情形。廖昱傑等人提出b值可大於1之鬆弛回溯門檻接受法（relaxed BATA, RBATA）並用以成功求解VRP問題。本研究延用RBATA架構，再加入兩極跳躍法（flip-flop method, FF）的機制，提出改良型門檻回溯接受法（modified BATA）以求解VRPB問題。本研究以62題國際標竿例題進行測試。結果發現62題標竿例題中有37題找到文獻已知最佳解，平均誤差值僅約0.13%。

This study proposes a new meta-heuristic approach for solving the vehicle routing problem with backhauls (VRPB). The new approach is a modified backtracking adaptive threshold accepting (MBATA) solution scheme which combines the relaxed backtracking adaptive threshold accepting (RBATA) method and flip-flop heuristics (FF).The benchmark problems described by Goetschalckx and Jacobs-Blecha (1989) were selected for performance evaluation. Results showed that our proposed MBATA yielded 37 best-known solutions among 62 test instances, and the average deviation is merely 0.13%.