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

Using Restart TA Metaheuristic Method to Solve Heterogeneous Fixed Fleet Vehicle Routing Problem

多車種固定車隊車輛路線問題（Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP）為傳統車輛路線問題（Vehicle Routing Problem, VRP）所發展出的相關問題。有別於VRP，HFFVRP考慮多種車種的車隊進行服務，車隊大小有固定限制，而不同車種間的變動使用成本亦有不同，較能符合供應鏈物流配送的實務情況。本研究求解流程共有三個步驟，首先，利用先排程後分群（route first-cluster second）之方法以GENIUS（GENeralized Insertion procedure, Unstring and String）建立巨網，接以考慮最經濟之車種進行車輛路線分割指派構建起始解；鄰域搜尋改善則採用cross exchange、2-opt、US（Unstring and String）、2-opt與Or-opt進行改善；最後使用重置門檻接受法（restart threshold accepting）加強求解時搜尋的廣度並跳脫局部最佳解之束縛。本研究所提出之方法論以HFFVRP國際標竿例題進行測試，18題例題中發現平手5題，整體平均誤差為0.75％。

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 metaheuristics. At first, we adopted the route-first cluster-second method considering average cost of used full loading vehicle types to construct the initial solution. And then used cross exchange, 2-opt, US, 2-opt and Or-opt to improve the initial solution. Finally, we applied restart threshold accepting to escape the constraint of local optimal solution. We compared our best results with Best Known Solutions (BKS) of HFFVRP benchmark instances. It showed that our proposed methods have generated 5 solutions reaching BKS. The average deviation of all the tested instances is 0.75%.