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

Applications of the Gids Metaheuristic to the Periodic Vehicle Routing Problem

10.6402/TPJ.200203.0001

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

巨集啟發式解法 ； 包容性深廣度搜尋法 ； 週期性車輛路線問題 ； Metaheuristic ； Generic intensification and diversification search GIDS ； Periodic vehicle routing problem PVRP

運輸計劃季刊

31卷1期（2002 / 03 / 30）

1 - 35

繁體中文

週期性車輛路線問題(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.

1. (1996).Modern Heuristic Search Methods.New York:John Wiley and Sons.
2. (1997).Local Search in Combinatorial Optimization.New York:John Wiley and Sons.
3. (1993).Modern Heuristics Techniques for Combinatorial Problems.New York:John Wiley and Sons.
4. Ball, M.(1988).Vehicle Routing: Methods and Studies.Amsterdam:North-Holland.
5. Battiti, R.Tecchiolli, G.(1994).The Reactive Tabu Search.ORSA Journal on Computation,6
6. Beltrami, E.Bodin, L.(1974).Networks and Vehicle Routing for Municipal Waste Collection.Networks,4
7. Charon, I.Hudry, O.(1993).The Noising Method: A New Method for Combinatorial Optimization.Operations Research Letters,14(3)
8. Christofides, N.Beasley, J.(1984).The Period Routing Problem.Networks,14
9. Christofides, N.Eilon, S.(1969).An Algorithm for the Vehicle Dispatching Problem.Operation Research Quarterly,20(3)
10. Clarke, G.Wright, J. W.(1964).Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.Operations Research,12(4)
11. Cordeau, J.Gendreau, M.Laporte, G.(1997).A Tabu Search Heuristic for Periodic and Multi-depot Vehicle Routing Problems.Networks,30
12. Dror, M.Ball, M.(1987).Inventory/ Routing: Reduction from an Annual to a Short-period Problem.Naval Research Logistics Quarterly,34
13. Dueck, G.(1993).New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-record Travel.Journal of Computational Physics,104
14. Dueck, G.Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.Journal of Computational Physics,90
15. Fisher, M.(1995).Handbooks in Operations Research and Management Science 8: Network Routing.Amsterdam:North-Holland.
16. Gaudioso, M.Paletta, G.(1992).A Heuristic for the Periodic Vehicle Routing Problem.Transportation Science,26
17. Glover, F.(1986).Future paths for integer programming and links to artificial intelligence.Computers and Operation Research,13
18. Glover, F.Laguna, M.(1997).Tabu Search.Massachusetts:Kluwer Academic Publishers.
19. Golden, B.Wasil, E.(1987).Computerized Vehicle Routing in the Soft Drink Industry.Operations Research,35
20. Kirkpatrick, S.Gelatt, Jr. C. D.Vecchi, M. P.(1983).Optimization by Simulated Annealing.Science,220
21. Lenstra, J. K.Rinnooy, K. A.(1981).Complexity of Vehicle Routing and Scheduling Problem.Networks,11
22. Lin, S.(1965).Computer solutions of the traveling salesman problem.Bell System Technology Journal,44
23. Mladenovic, N.Hansen, P.(1997).Variable Neighborhood Search.Computers ＆ Operations Research,24
24. Or, I.(1976).Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking.IL:Northwestern University.
25. Osman, I.Kelly, J.(1996).Metaheuristics: Theory and Applications.Massachusetts:Kluwer Academic Publishers.
26. Rosenkrantz, D. J.Stearns, R. E.Lewis, II, P. M.(1977).An Analysis of several heuristics for the Traveling Salesman Problem.SIAM Journal on Computing,6
27. Russell, R.Gribbin, D.(1991).A Multiphase Approach to the Period Routing Problem.Networks,21
28. Russell, R.Igo, W.(1979).An Assignment Routing Problem.Networks,9
29. Tan, C.Beasley, J.(1984).A Heuristic Algorithm for the Period Vehicle Routing Problem.OMEGA,12
30. Tsubakitani, S.Evans, J.(1998).An Empirical Study of a New Metaheuristics for the Traveling Salesman Problem.European Journal of Operation Research,104
31. 曹以明 Chao, I-MingGolden, B. L.Wasil, E.(1995).An Improved Heuristic for the Period Vehicle Routing Problem.Networks,26(1)
32. 陳國清(1998)。GDA與RRT啟發式解法在VRP問題上之應用。國立交通大學交通運輸研究所。
33. 韓復華 Han, Fu-Hwa(1999)。混合型AI啟發式方法在週期性車輛路線問題（PVRP）之應用。行政院國家科學委員會。
34. 韓復華 Han, Fu-Hwa卓裕仁 Cho, Yuh-Jen(2000)。中華民國第五屆運輸網路研討會論文集。逢甲大學。
35. 韓復華 Han, Fu-Hwa卓裕仁 Cho, Yuh-Jen(2001).Essays and Surveys in Metaheuristics.Massachusetts:Kluwer Academic Publishers.
36. 韓復華 Han, Fu-Hwa卓裕仁 Cho, Yuh-Jen(1999).A New Meta-heuristic Approach to the Fleet Size and Mix Vehicle Routing Problem.Journal of the Eastern Asia Society for Transportation Studies,3
37. 韓復華 Han, Fu-Hwa卓裕仁 Cho, Yuh-Jen(1999).Proceedings of the Third Metaheuristics International Conference (MIC '99).Angra dos Reis, Rio de Janeiro, Brazil:
38. 韓復華 Han, Fu-Hwa張靖 Chang, Ching(1996)。車輛路線問題研究：SA、TA、NM、SSS與交換型啟發式方法之綜合應用分析。國立交通大學運輸工程與管理學系／行政院國家科學委員會。
39. 韓復華 Han, Fu-Hwa張靖 Chang, Ching(1997)。路線與排程問題研究：結合交換型解法與AI演算法之應用。國立交通大學運輸工程與管理學系／行政院國家科學委員會。
40. 韓復華 Han, Fu-Hwa陳國清(1996)。成本擾動法（NM）與兩極跳躍法（FF）在TSP問題應用之研究。國立交通大學運輸工程與管理學系。