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

Abstract

多車種固定車隊車輛路線問題(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%.