車輛途程問題（VRP）屬於NP-Hard問題，而此類型之問題在找尋最佳
解之情況下，必須花費十分冗長的運算時間；因此，為了要迅速得到與最
佳解差異不大的近似解，一般都會採用啟發法來求解。本研究將同時考慮
任務節點及任務網枝，並於車輛行走時有總時間之限制，而任務節點及任
務網枝有個別時窗之限制；如此之考慮條件，可使得本研究更加符合實際
車輛途程之應用。

本研究之啟發式解算，可分為兩個階段：初始解及尋優改善。初始解
以「最鄰近法」及「掃描法」求得，尋優改善以「塔布搜尋法」求得，如
此便可得到一個的近似解；在尋優改善時，並提出數種交換法（如：swap
、2-opt* exchange及insert），針對任務來進行交換改善之比較。最後
本研究之啟發解與「門檻值接受法」所求得之結果，並且以「幹枝界限法
」求得一個下限解做為基準相互比較，以瞭解本研究之實際成效。

The vehicle routing problem (VRP) is a kind of NP-Hard problem.It
takes a lot of operational time to find optimal solutions of VRP.
All known algorithms for solving these problems require a number
of computations which grow exponentially with the size of the
problem. Therefore most of the research into solving vehicle
routing problems has been concerned with finding heuristics that
provide good solutions to the VRP. In this paper we consider the
Multi-Vehicle Routing Problem with Time Windows (VRPTW) which is
a generalization of the VRP.

In this paper, the heuristic method is composed of two phases:
initial solution and improvement algorithm. The initial solution
can be obtained by "nearest neighbor procedure" and "scan algorithm".
The improvement algorithm is obtained by "Tabu research". Therefore,
we can obtain an approximate solution. Besides, we propose many
exchange methods (such as swap, 2-opt* exchange and insert) to deal
with different missions and compare their difference. We compare
with the results of "Threshold Accepting" and the heuristic solution
of this paper, and use "Branch and Bound" to obtain a lower bound
of the optimum value as a comparing basis. Therefore, we can realize
the effects of this paper.

目錄名稱 頁次
書名頁 ***************i
論文口試委員審定書 ***************ii
授權書 *************** iii
中文摘要 *************** iv
英文摘要 ***************v
誌謝****************************** vi
目錄******************************vii
表目錄******************************ix
圖目錄******************************x
第一章、緒論 **************1
1.1研究動機與目的**************1
1. 2研究範圍及假設**************2
1.3研究架構及流程**************3
第二章、文獻探討**************5
2. 1車輛途程問題之概論**************5
2.2車輛途程問題之求解法**************6
2. 3塔布搜尋法 **************7
2.3.1簡介**************7
2.3.2組成要素**************8
2.3.3演算步驟**************9
2.4交換法 **************11
2.5總結 ************** 14
第三章、研究問題描述**************15
第四章、研究方法**************18
4.1執行步驟 **************19
4.2初始解之建構**************21
4.2.1最鄰近法**************21
4.2.2掃瞄法**************22
4.3尋優改善 **************23
4.3.1串聯式塔布搜尋法******23
4.3.2鄰近解之定義******24
4.3.3塔布列表 *********** 29
第五章、實驗結果與分析 ***********32
5.1實驗環境 ***************32
5.2實驗方式 ***************32
5.3交換法之實驗 ***************33
5.4參數之實驗 ***************38
5.5成效評估之實驗 ***************57
第六章、結論與展望 ***************62
6.1結論 ***************62
6.2未來展望 ***************63
參考文獻 ***************64
程式附錄 ***************附-1

中文部份
1. 陳功欽，「一般性車輛途程之探討」，私立元智工學院，碩士論文，民國85年6月。
2. 徐明輝，「多部車一般性車輛途程解算法之研究」，私立元智工學院，碩士論文，民國86年6月。
3. 陳靜萍，「利用塔布搜尋法及隱價啟發式演算法求解生產計劃含裝設時間問題」，國立清華大學，碩士論文，民國86年6月。

英文部份
4. Araque, J. R., G. Kudva, T. L. Morin and J. F. Pekny, "A Branch-and-cut Algorithm for vehicle routing Problems," Annals of Operations Research, Vol. 50, pp.37-60, 1994.
5. Ball, M. and M. Magazine, "The Design and Analysis of Heuristics," Networks, Vol.11., 1981, pp. 215-219.
6. Bowerman, R. L., P. H. Calamai and G. B. Hall, "The Spacefilling Curve with Optimal Partitioning Heuristic for the Vehicle Routing Problem," European Journal of Operational Research, Vol. 76., 1994, pp.128-142.
7. Chiang, W. C. and R. A. Russell, "Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows," Annals of Operations Research, Vol. 63, pp.3-27, 1996.
8. Cordeau, J. F., M. Gendreau and G. Laporte, "A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems," Networks, Vol. 30, September, pp.105-119, 1997.
9. Desrochers, M., J. Desrodiers and M. Solomon, "A new Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, Vol. 40, No 2, March-April, pp.342-354, 1992.
10. Dror, M. and L. Levy, "A vehicle routing Improvement Algorithm Comparison of a Greedy and a Matching Implementation for Inventory Routing," Computers Operations Research, Vol. 13, No 1. pp. 33-45, 1986.
11. Duhamel, C., J. Y. Potvin and J. M. Rousseau, "A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows," Transportation Science, Vol. 31, No. 1, February, pp.49-59, 1997.
12. Fischetti, M., P. Toth and D. Vigo, "A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs," Operations Research, Vol. 42, No 5, September-October, pp.846-859, 1994.
13. Fisher, M. L., K. O. Jornsten and O. B. G. Madsen, "Vehicle Routing with Time Windows: two Optimization Algorithms," Operations Research, Vol. 45, No 3, May-June, pp.488-492, 1997.
14. Foisy, C. and J. Y. Potvin "Implementing an Insertion Heuristic for Vehicle Routing on Parallel Hardware," Computers Operations Research, Vol. 20, No 7. pp. 737-745, 1993.
15. Garcia, B. L., J. Y. Potvin and J. M. Rousseau, "A parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problem with Time Window Constraints," Computers Operations Research, Vol. 21, No 9. pp. 1025-1033, 1994.
16. Gendreau, M., A. Hertz and G. Laporte, "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, Vol. 40, No 10,October, pp.1276-1290, 1994.
17. Gendreau, M., G. Laporte and R. Seguin, "A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers," Operations Research, Vol. 44, No 3, May-June, pp.469-477, 1996.
18. Glover, F. and M. Laguna "Modern Heuristic Techniques for Combinatorial Problems," John Wiley & Sons, Inc., pp.70-150 1993.
19. Kohl, N. and O. B. G. Madsen, "An Optimization Algorithm for The Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation," Operations Research, Vol. 45, No 3, May-June, pp.395-406, 1997.
20. Laporte, G. and I. H. Osman, "Routing problems: A Bibliography," Annals of Operations Research, Vol. 61, pp.227-262, 1995.
21. Lenstra, J. and A. R. Kan, "Complexity of Vehicle Routing and Scheduling Problems," Networks, Vol. 11, pp. 221-228, 1981.
22. Nambiar, J. M., L. F. Gelders and L. N. V. Wassenhove, "Plant Location and Vehicle Routing in the Malaysian Rubber Smallholder Sector: A Case Study," European Journal of Operational Research, Vol. 38., 1989, pp.14-26.
23. Neloson, M. D., K. E. Nygard, J. H. Griffin and W. E. Shreve, "Implementation Techniques for the Vehicle Routing Problem," Computers Operations Research, Vol. 12, No 3. pp. 273-283, 1985.
24. Pooley, J., "Integrated Production and Distribution Facility Planning at Ault Foods," Interfaces, Vol. 24, No 4, July-August, pp.113-121, 1994.
25. Potvin, J. Y., T. Kervahut, B. L. Garcla and J. M. Rousseau, "The Vehicle Routing Problem with Time Windows Part I：Tabu Search," INFORMS Journal on Computing, Vol. 8, No. 2, Spring, pp.158-164, 1996.
26. Potvin, J. Y., "Genetic Algorithm for the Traveling Salesman Problem," Annals of Operations Research, Vol. 63, pp.339-370, 1996.
27. Renaud, J., G. Laporte and F. F. Boctor, "A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem," Computers Operations Research, Vol. 23, No 3. pp. 229-235, 1996.
28. Taillard, E., P. Badeau, M. Gendreau, F. Guertin and J. Y. Potvin, "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, Vol. 31, No. 2, May, pp.170-186, 1997.
29. Dueck, G. and T. Scheuer, "Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing," Journal of Computational Physics, Vol. 90, pp. 161-175, 1990.
30. Osman, I. H., "Meta-strategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem," Annals of Operations Research, Vol. 41, pp. 421-451, 1993.
31. Grederickson, G. N., "Approximation Algorithms for some Routing Problems," SIAM journal on computing, Vol. 7., 1978, pp.178-193.
32. Frizzell, P. W. and J. W. Giffin, "The Split Delivery Vehicle Scheduling Problem with Time Windows and Grid Network Distances," Computers Operations Research, Vol. 22, No 6. pp. 655-667, 1995.
33. Benton, W. C. and M. D. Rossetti, "The Vehicle Scheduling Problem with Intermittent Customer Demands," Computers Operations Research, Vol. 19, No 6. pp. 521-531, 1992.
34. Bertsimas, D. J., "A Vehicle Routing Problem with Stochastic Demand," Operations Research, Vol. 40, No 3, May-June, pp.574-585, 1992.