車輛路線問題由於能廣泛應用於相關實務問題，因此有不少研究針對各種不同之車輛路線問題進行深入的探討。其中具時間窗車輛路線問題是所有車輛路線問題中，最基本也最重要的一個問題，國內外一直都有許多學者針對此問題研究求解方法，希冀能夠獲得不錯的成果。

本研究以Homberger and Gehring (2005)所提出之兩階段混合演化巨集啟發式解法為基礎，結合Solomon I1插入法構建多個起始解，(μ, λ)-演化策略進行第一階段以極小化車輛數為主要目標的改善，回溯式門檻接受法(Backtraking Adaptive Threshold Accepting, BATA)在第二階段以極小化旅行距離為主要目標進行最後之改善，來求解具時間窗車輛路線問題。並以Solomon(1983)所提出之56題國際標竿題庫進行測試，探討本研究提出之解題模組，其求解績效。

本研究在(μ, λ)-演化策略中提出交換模組之車輛節省接受法則，以增進在該階段極小化車輛數之績效，並在可回溯式門檻接受法中探討多種參數組合以及交換模組組合，進行解題績效之探討。經過測試之後，本研究56題測試題庫之最佳結果，車輛數為416輛，總旅行距離為58001.90，與文獻已知最佳解─車輛數為404輛、總旅行距離為56639.00之誤差皆在3%以內(車輛數為2.97%、總旅行距離為2.41%)。其中有十題與文獻已知最佳解結果相同。

Vehicle Routing Problem with Time Windows (VRPTW), an extension of the classical Vehicle Routing Problem (VRP), has been widely applied to logistics and home delivery. The VRPTW considers that customers request the carrier to serve them within a specific time interval, i.e. time window. Such a constraint makes the VRPTW harder to slove than the VRP. Therefore, most of the solution methods for VRPTW are heuristics or metaheuristics.

The objective function of the VRPTW considered combines the minimization of the number of vehicles (first priority) and the total travel distance (second priority). Our research is based on the two-phase hybrid metaheuristics introduced by Homberger and Gehring (2005). The aim of the first phase is the minimization of the number of vehicles by means of a (μ, λ)-evolution strategy, and in the second phase, the total distance is minimized using Backtracking Adaptive Threshold Accepting (BATA) proposed by Tarantilis et al. (2001). Solomon’s 56 benchmark VPRTW instances were utilized to evaluate the performance of this hybrid evolutionary metaheuristics.

In this thesis, we propose a vehicle saving acceptance rule to enhance the performance of (μ, λ)-evolution strategy. In BATA, we test several combinations of parameters and improvement methods. All the experiments of this metaheuristics are coded in C# and implemented on a computer with AMD Athlon(tm) 64 Processor 3000+.

As to all of the 56 instances tested, the total number of vehicles of the best solution found by our proposed hybrid evolutionary metaheuristics is 416, and the total travel distance is 58001.90. As compared to the best known solutions of the benchmark instances, the average deviation of required vehicles is 2.97%, and the average deviation of total distance is 2.41%. Among those 56 benchmark instances, we have found the best known solutions in 10 instances.

中文摘要..............................................i
英文摘要..............................................ii
目錄..................................................iii
表目錄................................................v
圖目錄................................................v
第一章 緒論...........................................1
1.1 研究背景與動機................................1
1.2 研究目的與範圍................................2
1.3 研究方法與流程................................3
第二章 具時間窗車輛問題文獻回顧.......................5
2.1 具時間窗車輛路線問題定義......................5
2.2 具時間窗車輛路線問題解法回顧..................6
2.2.1 時間可行性之檢驗..........................6
2.2.2 路線構建式啟發式解法......................7
2.2.3 路線改善法................................10
2.2.4 綜合型構建/改善法.........................14
2.2.5 巨集啟發式解法............................15
2.2.6 (μ,λ)演化策略.............................21
2.2.7 可回溯式門檻接受法........................21
第三章 混合演化巨集啟發式解法之模式構建...............23
3.1 混合演化巨集啟發式解法求解架構................23
3.2 起始解模組之建構..............................24
3.3 第一階段：(μ,λ)演化策略之建構.................26
3.4 第二階段：可回溯式門檻接受法之建構............27
第四章 混合巨集啟發式解法之測試與分析.................30
4.1 具時間窗車輛路線問題測試例題..................30
4.2 起始解模組測試與分析..........................30
4.3 第一階段：(μ,λ)演化策略之測試與分析...........31
4.4 第二階段：可回溯式門檻接受法之測試與分析......32
4.5 測試最佳結果..................................34
4.6 測試結果與文獻已知最佳解之比較................36
4.6.1 文獻已知最佳解............................36
4.6.2 測試結果與文獻已知最佳解比較分析..........38
第五章 結論與建議.....................................42
5.1 結論..........................................42
5.2 建議..........................................42
參考文獻..............................................44
附 錄 本研究最佳結果之成本及路線圖....................50

Backer, B., V. Fttrnon, P. Shaw, P. Kilby and P. Prosser (2000), “Solving vehicle routing problem using constraint prograntrning and metahearistics,” Journal of Heuristics, Vol. 6, pp. 501-523.

Bent, R. and P. Van Hentenryck (2004), “A Two-stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 38, pp. 515-530.

Berger, J. and M. Barkaoui (2004), “A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 31, pp. 2037–2053.

Br�爨sy, O. (2003a), “Fast Local Searches for the Vehicle Routing Problem with Time Windows,” Inform. Systems Oper. Res, Vol. 41, pp. 179-194.

Br�爨sy, O. (2003b), “A Reactive Variable Neighborhood Search for the Vehicle Routing Problem with Time Windows,” INFORMS Journal on Computing,
Vol. 15, pp. 347-368.

Br�爨sy, O. and M. Gendreau (2005a), “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms,” Transportation Science, Vol. 39, No. 1, pp. 104-118.

Br�爨sy, O. and M. Gendreau (2005b), “Vehicle Routing Problem with Time Windows, Part II: Metaheuristics,” Transportation Science, Vol. 39, No. 1, pp. 119-139.

Clarke, G. and J. W. Wright (1964), “Scheduling of Vehicles form a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.

Campbell, A. M. and M. Savelsbergh (2004), “Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems,” Transportation Science, Vol. 38,
No. 3, pp. 369-378.

Chiang, W.C. and R.A. Russell (1996), “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, pp. 3-27.

Chiang, W. C. and R. A. Russell (1997), “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” INFORMS Journal of Computing, Vol. 9, No. 4, pp. 417-430.

Cordeau, J., G. Laporte and A. Mercier (2001), “A. Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 52, pp. 928-936.

Czech, Z.J. and P. Czarnas (2002), “Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows,” Distributed and Network-based Processing.

Darwin, C. (1859), On the Origin of Species by Means of Natural Selection or the Preservation of Favoured Races in the Struggle for Life, 1st edition, John Murray, London.

De Jong, K.A. (1975), “An Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph.D. thesis, University of Michigan, U.S.A.

Debudaj-Grabysz A. and Z. Czech (2004), “A Concurrent Implementation of Simulated Annealing and Its Application to the VRPTW Optimization Problem,” Distributed and Parallel Systems, Springer, Netherlands.

Desrochers, M., J. Desrosiers and M. M. Solomon (1992), “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows,” Operations Research, Vol. 40, No. 2, pp. 342-354.

Dorigo, M., D. Caro and L. M. Gambardella (1999), “Ant Algorithms for Discrete Optimization,” Artificial Life, Vol. 5, No. 2, pp. 137-172.

Dueck, G. and T. Scheuer (1990), “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175.

Dueck, G. (1993), “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol. 104,
pp. 86-92.

Fisher, M. L., K. O. Jornsten and O. B. G. Madsen (1997), “Vehicle Routing with Time Windows: Two Optimization Algorithms,” Operations Research, Vol. 45, No. 3, pp. 488-492.

Fisher M. L. (1995), “Vehicle Routing,” Chapter 1 in M. Ball, T. Magnanti, C. Monma & G. Nemhauser (eds.) Network Routing, Handbooks in Operations Research and Management Science, Vol. 8, pp. 1-33.

Gambardella, L. M., E. Tailard and G. Agazzi (1999), “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows,” in New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover(eds), McGraw-Hill, London, pp. 63-76.

Gendreau, M., A. Hertz and G. Laporte (1992), “New Insertion and Postoptimization Procedures for the Traveling Salesman Problem,” Operation Research, Vol. 40, pp. 1086-1094.

Gendreau, M. and G. Pesant (1999), “A Constraint Programming Framework for Local Search Methods,” Journal of Heuristics, Vol. 5, pp. 255-279.

Glover F. (1986), “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, Vol.13, pp. 533-549.

Goldberg, D., B. Korb and K. Deb. (1989), “Messy Genetic Algorithms: Motivation, Analysis and First Results,” Complex Systems, Vol. 3, pp. 493–530.

Holland, J.H. (1975), Adaptation in Natural and Artificial Systems, Ann Arbor: University of Michigan Press.

Homberger, J. and H. Gehring (1999), “Two Evolutionary Metsheuristics for the Vehicle Routing Problem with Time Windows,” INFOR, Vol. 37, pp. 297-318.

Homberger, J. and H. Gehring (2005), “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 162, pp. 220–238.

Ibaraki, T., S. Imahori, M. Kubo, T. Masuda, T. Uno and M. Yagiura (2002), “Effective Local Search Algorithms for Routing and Scheduling Problems with General Time Window Constraints,” Transportation Science, Vol. 39, No. 2,
pp. 206-232.

Ioannou, G., M. Kritikos and G. Prastacos (2001), “A Greedy Look-ahead Heuristic for the Vehicle Routing Problem with Time Windows,” Journal of the Operational Research Society, Vol. 52, pp. 523-537.

Kirkpatrick, S., C. Gelatt and M. Vecchi (1983), “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680.

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

Li, H. and A. Lim (2001), “A Metaheuristic for the Pickup and Delivery Problem with Time Windows,” In 13th IEEE international conference on tools with artificial intelligence (ICTAI), pp. 160-170.

Li, H. and A. Lim (2003), “Local Search with Annealing-like Restarts to Solve the VRPTW,” European Journal of Operational Research, Vol. 150, pp. 155-127.

Mester, D., O. Br�爨sy and W. Dullaert (2007), “A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems,” Expert Systems with Applications, Vol. 32, pp. 508-517.

Or, I. (1976), Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, Ph.D. Dissertation, Northwestern University.

Osman, I. H. (1993), “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, pp. 421-451.

Potvin, J. Y. and J. M. Rousseau (1993), “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows,” European Journal of Operational Research, Vol. 66, pp. 331-341.

Potvin, J.Y., T. Kervahut, B.L. Garcia and J.M. Rousseau (1996), “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,”�}Informs Journal on Computing, Vol. 8, No. 2, pp. 158-164.

Potvin, J.Y. and S. Bengio (1996), “The Vehicle Routing Problem with Time Windows Part II: Genetic Search,” INFORMS Journal on Computing, Vol. 8,
No. 2, pp.165-172.

Rochat, Y., and E. Taillard (1995), “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” J. Heuristics, Vol. 1, pp. 147-167.

Russell, R. A. (1995), “Hybrid Heuristics for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 29, No. 2, pp. 156-166.

Rousseau, L., M. Gendreau and G. Pesant (2002), “Using Constraint-based Operators to Solve the Vehicle Routing Problem with Time Windows,” Journal of Heuriatics, Vol. 8, pp. 43-58.

Salhi, S. and G.K. Rand (1993), “Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem,” European Journal of Operational Research, Vol. 66, pp. 313-330.

Schrimpf, G., J. Schneider, H. Stamm-Wilbrandt and G. Dueck (2000), “Record Breaking Optimization Results Using the Ruin and Recreate Principle,” Journal of Computational Physics, Vol. 159, pp. 139-171.

Schwefel, H.P. (1981), Numerical Optimization of Computer Models, John Wiley & Sons, Chichester.

Solomon, M. M. (1983), “Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms,” Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.

Solomon, M. M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operation Research, Vol. 35,
pp. 254-265.

Solomon LAB: http://web.cba.neu.edu/~msolomon/ (2007/08/21)

Tarantilis ,C.D and. Kiranoudis, C.T. (2001), “A Meta-heuristic Algorithm for the Efficient Distribution of Perishable Food,” Journal of Food Engineering, Vol. 50, pp.1-9.

Thangiah, S. R., K. E. Nygard and P. L. Juell (1991), “GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows,” Proc. 7th IEEE Conf. Artificial Intelligence Appl., IEEE Computer Society Press, Los Alamitos, pp. 322-328.

Thangiah, S. R., I. H. Osman and T. Sun (1994), “Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Touting Problems with Time Windows,” Technical Report UKC/OR94/4, Institute of Mathematics & Statistics, University of Kent, Canterbury, UK.
Taillard, E., P. Badeau, M. Gendreau, F. Guertin and J.Y.

Potvin (1997), “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, ” Transportation Science, Vol. 31, No. 2, pp. 170-186.

丁慶榮、陳家和(2005)，「應用螞蟻演算法於時窗限制車輛途程問題之研究」，運輸學刊，第十七卷第三期，pp. 261-280。

王生德(2003)，「以巨集啟發式方法求解時窗限制回程取貨車輛路線問題(VRPBTW)之研究」，私立中華大學科技管理研究所碩士論文。

林修竹(1999)，「包容性啟發式解法在VRPTW問題上之應用」，國立交通大學運輸工程與管理學系碩士論文。

朱佑旌(2005)，「巨集啟發式解法應用於時窗限制多車種回程取貨車輛路線問題之研究」，中華大學科技管理研究所碩士論文。

何昆諭(2005)，「以巨集啟發式解法求解時間窗車輛路線問題」，國立交通大學運輸科技與管理學系碩士論文。

卓裕仁(2001)，「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」，國立交通大學運輸工程與管理學系所博士論文。

陳國清(1998)，「GDA與RRT啟發式解法在VRP問題上之應用」，國立交通大學交通運輸研究所碩士論文。

楊智凱(1995)，「以門檻接受法改善TSP與VRP路網成本之研究」，國立交通大學土木研究所運工管組碩士論文。

廖昱傑(2007)，「應用可回溯式門檻接受法結合GENIUS求解VRP問題之研究」，國立交通大學運輸科技與管理學系碩士論文。

韓復華、卓裕仁(1996)，「路線與排程問題研究：結合交換型解法與AI演算法之應用」，國立交通大學運輸工程與管理學系，八十六年度國科會專題研究計畫成果報告(NSC-86-2621-E-009-001)。

韓復華、卓裕仁(1998)，「混合型啟發式解法在多車種車輛路線問題之應用」，國立交通大學運輸工程與管理學系，八十七年度國科會專題研究計畫成果報告(NSC-87-2211-E-009-024)。

韓復華、張靖(1996)，「車輛路線問題研究：SA、TA、NM、SSS與交換型啟發式解法之綜合應用分析」，國立交通大學運輸工程與管理學系，八十五年度國科會專題研究計畫成果報告(NSC-85-2211-E-009-023)。