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

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

韓復華(Anthony F. Han) ； 方建皓(Chien-Hao Fang) ； 朱佑旌(Yu-Ching Chu)

《運輸學刊》 26卷3期 (2014/09) Pp. 411-433

https://doi.org/10.6383/JCIT.201409_26(3).0005

摘要

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

並列關鍵字

Heterogeneous Fixed Fleet Vehicle Routing Problem ； Restart threshold accepting ； Metaheuristics

參考文獻

廖昱傑、韓復華、卓裕仁()。

韓復華、吳宗勳()。

韓復華、楊智凱、卓裕仁(1997)。應用門檻接受法求解車輛路線問題之研究。運輸計劃季刊。26(2)，253-280。

Brandão, J.(2011).A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem.Computers and Operations Research.38(1),140-151.

Bräysy, O.,Berger, J.,Barkaoui, M.,Dullaert, W.(2003).A Threshold Accepting Metaheuristic for the Vehicle Routing Problem with Time Windows.Central European Journal of Operations Research.11(4),369-387.