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

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%.