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

A Modified Bata Approach to Solve Vehicle Routing Problem with Backhauls

韓復華(Anthony F. Han) ； 呂泓儒(Hong-Ru Lu) ； 朱佑旌(Herman Y. Chu)

《運輸計劃季刊》 40卷2期 (2011/06) Pp. 213-232

https://doi.org/10.6402/TPJ.201106.0213

摘要

本研究基於回溯門檻接受法(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 (MBA TA) 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 MBA TA yielded 37 best-known solutions among 62 test instances, and the average deviation is merely 0.13%.

並列關鍵字

Vehicle routing problem with backhauls VRPB ； Backtracking adaptive threshold accepting BA TA ； Flip-flop method FF

參考文獻

Golden, B. L.(Ed.),Assad, A. A.(Ed.)(1988).Vehicle Routing: Methods and Studies.Amsterdam:Elsevier Science.

Tarantilis, C. D.,Kiranoudis, C. T.(2001).A Meta-heuristic Algorithm for the Efficient Distribution of Perishable Foods.Journal of Food Engineering.50(1),1-9.

廖昱傑、韓復華、卓裕仁()。

Goetschalckx, M.,Jacobs-Blecha, C.(1989).The Vehicle Routing Problem with Backhauls.European Journal of Operational Research.42(1),39-51.

Toth, P.,Vigo, D.(1996).A Heuristic Algorithm for the Vehicle Routing Problems with Backhauls.Advanced Methods in Transportation Analysis.(Advanced Methods in Transportation Analysis).: