利用巨網機制結合回溯式門檻接受法求解中繼補貨站車輛路線問題之研究

Using Giant Tour Construction and BATA Metaheuristics to Solve Vehicle Routing Problem with Intermediate Replenishment Facilities

黃柏揚(Po-Yang Huang)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸與物流管理學系/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00299

摘要

中繼補貨站車輛路線問題 (Vehicle Routing Problem with Intermediate Replenishment Facilities, VRPIRF) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 之延伸。不同於VRP，VRPIRF考慮車輛在服務途中可利用中繼站進行補貨或是卸貨的作業，進而提高車輛之使用率。對於實務操作也更具其適用性。
本研究求解架構主要分成三階段：首先採用先排程後分群 (Route First-Cluster Second) 的方式構建起始路線；接以1-0、1-1、2-opt*、3-opt與Or-opt等鄰域搜尋交換法來改善起始解；最後，在進一步利用調整後之回溯式門檻接受法 (Backtracking Adaptive Threshold Accepting, BATA) 進行求解。本研究另針對問題特性，設計中繼補貨站重置機制 (RD Relocation)。搭配路線內鄰域搜尋改善法，RD Relocation能為求解結果找到最佳的中繼補貨站利用方式。
除了BATA求解架構之實驗測試之外，本研究進一步加入多重起始解策略 (Multi-Start)，測試多重起始解對VRPIRF求解績效之影響。本研究以66題國際標竿例題進行測試，求解結果共突破48題文獻已知最佳解，5題平手，平均誤差為-0.85%。

關鍵字

中繼補貨站車輛路線問題 ； 回溯式門檻接受法 ； 多重起始解

並列摘要

The Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is a variant of the traditional Vehicle Routing Problem (VRP). Compared with VRP, VRPIRF considers a numerous replenishment depots with unlimited capacity, capacity of vehicles and limitation of total duration. With these conditions, VRPIRF can be more conform to many distribution operations in the reality.
There are three modules in our proposed Metaheuristics to solve the VRPIRF. First, the Route First-Cluster Second method was adopted to construct the initial solution. Second, the Neighborhood Search (NS) module which includes 1-0, 1-1, 2-opt*, 3-opt and Or-opt. Finally, we applied a modified Backtracking Adaptive Threshold Accepting (BATA) process to further improve the solution. In addition, we developed RD-Relocation strategy combined with intra-route exchanges to find better locations of replenishment depots during the route improvement procedure. Moreover, we also conducted some multiple-start solution experiments with encouraging results.
In order to identify the feasibility of our proposed Metaheuristics, we compared our best solutions with VRPIRF benchmark instances. Results showed that our proposed methods have generated 48 new best known solutions (BKS) and 5 reaching BKS. The average deviation of all the tested instances is -0.85%.

並列關鍵字

Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) ； Backtracking Adaptive Threshold Accepting (BATA) ； Multi-Start

參考文獻

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

[15] 卓裕仁、朱佑旌 (2008)，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計劃季刊，第37卷第4期，頁405-430。

[16] 韓復華、陳仲豪 (2010)，「應用時窗離散策略與可回溯式門檻接受法求解VRPBTW 問題之研究」，運輸學刊，第22卷第3期，頁285-306。

[17] 韓復華、呂泓儒、朱佑旌 (2011)，「以改良型回溯門檻接受法求解回程取貨車輛路線問題之研究」，運輸學刊，第40卷第2期，頁23-232。

[2] Lin, S. (1965), “Computer Solutions of the Traveling Salesman Problem”, The Bell System Technical Journal, Vol. 44, pp. 2245-2269.