以重置門檻接受法求解多車種固定車隊車輛路線問題之研究

Abstract

多車種固定車隊車輛路線問題 (Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 所發展出的相關問題。有別於VRP，HFFVRP考慮多種車種的車隊進行服務，車隊大小有固定限制，而不同車種間的變動使用成本亦有不同，較能符合供應鏈物流配送的實務情況。 本研究求解流程共有三個步驟：首先，利用先排程後分群 (Route First-Cluster Second) 之方法以GENIUS建立一巨網，接以考慮最經濟之車種進行車輛路線分割指派構建起始解；鄰域搜尋改善則採用Cross exchange、2-Opt*、US、2-Opt與Or-Opt進行改善；最後使用重置門檻接受法 (Restart Threshold Accepting) 加強求解時搜尋的廣度並跳脫局部最佳解之束縛。此外，本研究還額外進行多重起始解進行Restart TA的求解的測試。 本研究所提出之方法論以HFFVRP國際標竿例題進行測試，18題例中發現突破2題文獻已知最佳解，平手5題，整體平均誤差為1.12%。

The Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP) is a variant of the conventional Vehicle Routing Problem (VRP). Compared with VRP, HFFVRP considers a fixed size of fleet with different types and variable costs of vehicles. There are three steps in our proposed Meta-heuristics. At first, we adopted the Route First-Cluster Second method with considering average cost of used full loading vehicle types to construct the initial solution. And then use Cross exchange, 2-Opt*, US, 2-Opt and Or-Opt to improve the initial solution. Finally, we applied Restart Threshold Accepting to escape the local optimal solution. Moreover, we also conducted some multiple-start solution experiments to solve HFFVRP. We compared our best results with best known solutions (BKS) of HFFVRP benchmark instances. It showed that our proposed methods have generated 2 breakthrough solutions and 5 reaching BKS. The average deviation of all the tested instances is 1.10%.