多車種固定車隊車輛路線問題之啟發式解法研究

Using Heuristics to Solve Heterogeneous Fixed Fleet Vehicle Routing Problem

吳宗勳(Tsung-Hsun Wu)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸科技與管理學系/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00558

摘要

多車種固定車隊車輛路線問題(Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP)是傳統車輛路線問題(Vehicle Routing Problem, VRP)之延伸。不同於VRP僅考慮單一車種，HFFVRP考慮不同容量與成本的固定車隊，較能符合供應鏈物流配送的條件。
本研究以平行式可換車種依路線重心之最省插入法為起始解構建方法，鄰域搜尋改善運用1-1、2-Opt*、Or-Opt*、2-Opt與Or-Opt*交換法，並依問題特性設計了車種改善機制。車種改善機制於鄰域搜尋改善時，可依路線的車輛乘載量尋找最適合之車種，以便在交換改善的過程中，能夠讓各路線可以靈活地運用不同車種，使車輛的使用上能達到更好的配置。本研究應用回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)為巨集啟發式解法求解HFFVRP，其中門檻回溯比率可大於一。
本研究以Taillard所發表的8題例題、Li et al.所發表的5題例題以及Brandao所發表的5題題庫，共18題國際標竿例題進行測試，發現其中有1題突破文獻已知最佳解，平均誤差為3.04%。

關鍵字

車輛路線問題 ； 多車種固定車隊車輛路線問題 ； 門檻接受法 ； 回溯式門檻接受法

並列摘要

The Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) is a variant of vehicle routing problem (VRP). Unlike classical VRP, the HFFVRP considers a fixed size of fleet with different types and variable costs of vehicles.
In this paper, we apply Backtracking Adaptive Threshold Accepting (BATA) for solving HFFVRP. According to characteristic of the problem, we developed a vehicle type improvement mechanism which can find a neighborhood solution with a better vehicle type combination.
Our proposed meta-heuristic is tested on a set of 18 benchmark instances including 8 instances from Taillard, 5 instances from Li et al. and 5 instances from Brandao. Results showed that our proposed methods have generated 1 best know solution (BKS). The average deviation of all the tested instances is 3.04%.

並列關鍵字

Vehicle Routing Problem (VRP) ； Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) ； Threshold Accepting (TA) ； Backtracking Adaptive Threshold Accepting (BATA)

參考文獻

[23] 呂泓儒，「以改良型可回溯式門檻接受法求解回程取貨車輛路線問題之研究」，碩士論文，國立交通大學，民國98年。

[25] 卓裕仁、朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計畫季刊，第三十七卷，頁405-430，民國97年。

[1] Brandao, J., "A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem," Computers & Operations Research, vol. 38, pp. 140-151, 2011.

[2] Christofides, N., Mingozzi, A., and Toth, P., "The vehicle routing problem," Combinatorial optimization, vol. 11, pp. 315-338, 1979.

[3] Clarke, G. and Wright, J. W., "Scheduling of vehicles form a central depot to a number of delivery points," Operations Research, vol. 12, pp. 568-581, 1964.