包容性深廣度搜尋法在週期性車輛路線問題之應用

Applications of the Gids Metaheuristic to the Periodic Vehicle Routing Problem

韓復華(Anthony Fu-Wha Han) ； 卓裕仁(Yuh-Jen Cho)

《運輸計劃季刊》 31卷1期 (2002/03) Pp. 1-35

https://doi.org/10.6402/TPJ.200203.0001

摘要

週期性車輛路線問題(periodic vehicle routing problem, PVRP)考慮顧客在多日配送中有不同頻率之需求，其問題複雜度更甚於傳統的車輛路線問題(vehicle routing problem, VRP)。本文先以服務日期型態(delivery-day pattern, DDP)說明PVRP的複雜性質，再應用一個新的巨集啟發式解法「包容性深廣度搜尋法(generic intensification and diversification Search, GIDS)」來求解PVRP，並報導其解題績效。GIDS法整合運用門檻接受法(threshold accepting, TA)與大洪水法(great deluge algorithm, GDA)等新近發展的包容性搜尋法，以及深度與廣度搜尋的巨集策略以達到更具智慧化之搜尋。GIDS法共包含多起始解構建(multiple initialization constructor, MIC)、深度化包容搜尋(generic search for intensification, GSI)及廣度化擾動搜尋(perturbation search for diversification, PSD)三個功能組件，並設計有五個執行模組；在模組的設計當中，本文也分別提出了多項新的求解方法與修正。本研究使用國際題庫之32個PVRP標竿例題做為測試各種GIDS執行模組與參數之基礎，並以UNIXC語言撰寫電腦程式，於SUN SPARC 10工作站上執行測試。結果顯示本研究測試題庫32個例題之最佳結果與文獻最佳已知結果比較，平均誤差僅為0.26%，且有6個例題找到突破目前文獻最佳已知解之結果，驗證了GIDS在PVRP之應用潛力。

關鍵字

巨集啟發式解法 ； 包容性深廣度搜尋法 ； 週期性車輛路線問題

並列摘要

The periodic vehicle routing problem (PVRP), a different from the conventional vehicle routing problem (VRP), considers the different delivery frequencies that customers may require during a dispatch period of time. This paper presents a new metaheuristic approach, i.e. the generic intensification and diversification search (GIDS), to solve the PVRP. The GIDS integrates the use of some recently developed generic search methods such as threshold accepting (TA) and great deluge algorithm (GDA), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: multiple initialization constructor (MIC), generic search for intensification (GSI), and perturbation search for diversification (PSD). We designed five modules and proposed several modified algorithms for the implementation of the GIDS to PVRP. A bank of thirty-two PVRP benchmark instances was tested by several different implementations of GIDS. All programs were coded in UNIX C and ran on a SUN SPARC 10 workstation. Computational results are very encouraging. We found that the average deviation from the thirty-two best-known solutions is merely 0.26%. Moreover using GIDS we have updated the best-known solutions for six of the thirty-two benchmark instances.

並列關鍵字

Metaheuristic ； Generic intensification and diversification search GIDS ； Periodic vehicle routing problem PVRP

參考文獻

(1997).Local Search in Combinatorial Optimization.New York:John Wiley and Sons.

(1996).Modern Heuristic Search Methods.New York:John Wiley and Sons.

(1993).Modern Heuristics Techniques for Combinatorial Problems.New York:John Wiley and Sons.

Ball, M.(1988).Vehicle Routing: Methods and Studies.Amsterdam:North-Holland.

Battiti, R.Tecchiolli, G.(1994).The Reactive Tabu Search.ORSA Journal on Computation.6