臺灣博碩士論文加值系統

可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)是由Tarantilis et al. [38]於2001年提出，它是從門檻接受法演變而來的新型巨集啟發式解法。其主要差異在於門檻值變化並非單調遞減；當找不到可接受的交換時，可允許放鬆門檻值再重新搜尋。本研究以此方法作為基本架構，並與一般化插入/解繫法(GENIUS)和其他傳統鄰域搜尋法相結合，來求解VRP問題，以探討其求解績效。本研究之求解架構包含起始解模組、鄰域搜尋模組和可回溯式門檻接受模組三個部份。並以Christofides et al. [8]的14題國際標竿題庫作為績效評估的測試例題。
本研究首先以循序式的一般化插入法(GENI)產生起始解，再以鄰域搜尋模組改進，其方法共包括解繫法(US)、1-1、2-Opt和Or-Opt等數種。並且以巨網結構的方式建構路線，使其能同時考慮「路線內」與「路線間」的交換。同時，本研究設計了一個能夠擴大解繫法鄰域搜尋範圍機制(Expanded US)，以提高解繫法的搜尋績效。而本研究以C#語言撰寫程式，並在Pentium(R) 4，CPU為3.00GHz的個人電腦測試可回溯式門檻接受模組。結果顯示，傳統上BATA的設定，即門檻回溯比值b<1時，在起始門檻比率0.01、門檻下降比率0.9，以及門檻數列長度180的情況下，14題標竿題目的平均誤差可為1.2%。另外，本研究亦發現，若突破傳統BATA限制，而設定門檻回溯比值b>1時，在起始門檻比率0.02附近的範圍，門檻下降比率0.9以上附近的範圍，以及門檻數列長度180的情況下，可找到更佳的結果，其中最低的14題標竿題目平均誤差更降低至0.87%。表示此種更為放鬆的設計可能可以找到較佳的解。
最後，再與近年來國際期刊之文獻進行比較。本研究14題中共有7題可找到已知最佳解，而各題最佳結果之平均誤差僅為0.26%，且相比之下求解時間亦頗快速，顯示可回溯式門檻接受法可成為相當不錯的求解架構。

Backtracking Adaptive Threshold Accepting (BATA) was first introduced by Tarantilis et al. in 2001 for the distribution of perishable goods. This algorithm is similar to Threshold Accepting (TA) but the values of threshold are lowered or raised, depending on if an acceptable solution can be found in a fixed number of iterations. This research used a BATA structure embedded with GENIUS and other traditional exchange methods for solving the Vehicle Routing Problem (VRP). And the 14 classic instances described by Christofides et al. were selected for the evaluation of our method.
The first phase of our proposed metaheuristic is the following. A feasible initial solution was generated by a sequential GENI, and then improved by neighborhood search methods such as US, 1-1, 2-Opt, Or-Opt. Since we presented the solution as a giant tour, both the inter-route and intra-route improvements were considered simultaneously. We also proposed a mechanism named “Expanded US” to enhance the performance of US.
In the second phase, we applied BATA to further improve the giant-tour solution. We coded our metaheuristic method in C# and implemented all experiments on a Pentium 4, 3.00GHz personal computer. Results showed that the average deviation of 14 benchmark instances can be 1.2% using traditional BATA parameter b<1. We also tested the case of the threshold backtracking factor b>1 and found that this change could lead to even better results. The average of deviation of the 14 benchmark instances can be reduced to 0.87%. Overall, compared with the recent literatures, among the 14 instances, we found 7 best-known solutions and the average deviation is merely 0.26%. The average computer time is about 50 seconds which demonstrated the efficiency and potential applicability of our proposed method.

中文摘要 i
英文摘要 ii
誌 謝 iii
目 錄 iv
表 目 錄 vi
圖 目 錄 vii
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究內容與範圍 1
1.3 研究方法與流程 2
第二章 文獻回顧 4
2.1 車輛路線問題 4
2.2 啟發式解法回顧 5
2.2.1 傳統的啟發式解法 6
2.2.2 一般化插入法與解繫法(GENIUS) 9
2.2.3 巨集啟發式解法 13
2.3 可回溯式門檻接受法 16
2.4 小結 17
第三章 起始解與鄰域搜尋法構建 18
3.1 起始解產生：一般化插入法(GENI) 18
3.2 鄰域搜尋模組之設計 18
3.2.1 於巨網結構下(Giant Tour)下執行鄰域搜尋 18
3.2.2 擴大解繫法(US)鄰域搜尋範圍之設計 20
第四章 BATA應用於VRP之設計與測試 21
4.1 BATA與GENIUS結合之設計 21
4.1.1 門檻值回溯幅度之探討 21
4.1.2 執行架構說明 22
4.2 測試例題說明 24
4.3 測試結果之整理與分析 25
4.3.1 實驗設計 25
4.3.2 起始解測試 25
4.3.3 鄰域搜尋模組測試 26
4.3.4 可回溯式門檻接受模組測試 29
4.4 演算法績效比較與分析 35
第五章 結論與建議 37
5.1 結論 37
5.2 建議 37
參考文獻 38
附 錄 最佳個案結果與路線圖 42

1. 朱佑旌，「巨集啟發式解法應用於時窗限制多車種回程取貨車輛路線問題之研究」，中華大學，碩士論文，民國95年。
2. 卓裕仁，「以巨集啟發式解法求解多車種與週期性車輛路線問題之研究」，國立交通大學，博士論文，民國89年。
3. 陳國清，「GDA與RRT啟發式解法在VRP問題上之應用」，國立交通大學，碩士論文，民國87年。
4. 楊智凱，「以門檻接受法改善TSP及VRP路網成本」，國立交通大學，碩士論文，民國84年。
5. Blasum, U. and Hochst�鱸tler, W., "Application of the Branch and Cut Method to the Vehicle Routing Problem," Technical Report ZPR2000-386, Zentrum fur Angewandte Informatik K�匜n, 2000.
6. Bodin, L., Golden, B., Assad, A. and Ball, M., “Routing and scheduling of vehicle and crew: the state of art,” Special Issue of Computers and Operations Research, Vol.10, No.2, 1983, pp. 63-211.
7. Christofides, N., Eilon, S., “An algorithm for the vehicle-dispatching problem,” Operational Research Quarterly, Vol. 20, No. 3, 1969, pp. 309-318.
8. Christofides, N., Mingozzi, A., Toth, P. and Sandi, C., Combinatorial Optimization, John Wiley & Sons, Inc., 1979.
9. Clarke, G. and Wright, J., “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, 1964, pp.568-589.
10. Cordeau, J-F., Gendreau, M., Laporte, G., “A tabu search heuristic for periodic and multi-depot vehicle routing problems,’ Networks, Vol. 30, N0.2, 1997, pp.105-119.
11. Cordeau, J-F., Gendreau, M., Laporte, G., Potvin, J-Y. and Semet, F., “A guide to vehicle routing heuristics,” Journal of the Operational Research Society, Vol. 53, 2002, pp.512-522.
12. Cordeau, J-F., Laporte, G. and Mercier, A., “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, Vol. 52, 2001, pp.928–936.
13. Cordeau, J-F., Laporte, G., Savelsbergh, M.W.P. and Vigo, D., “Vehicle routing,” in: C. Barnhart and Laporte, G. (eds), Handbooks in Operations Research and Management Science: Transportation, Vol.14, Elsevier B.V., 2005.
14. Dantzig, G. B. and Ramser, R.H., “The truck dispatching problem,” Management Science, Vol. 6, 1959, pp.80–91.
15. Dueck, G., “New optimization heuristics: the great deluge algorithm and the record-to-record travel,” Journal of Computational Physics, Vol. 104, 1993, pp. 86-92.
16. Dueck, G. and Scheuer, T., “Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing,” Journal of Computational Physics, Vol. 90, 1990, pp.161-175.
17. Ergun, ��., Orlin, J.B. and Steele-Feldman, A., “Creating very large scale neighborhoods out of smaller ones by compounding moves, “Journal of Heuristics, Vol. 12, 2006, pp. 115-140.
18. Franceschi1, R.D., Fischetti1, M. and Toth, P., “A new ILP-based refinement heuristic for Vehicle Routing Problems,” Mathematical Programming, Vol. 105, 2006, pp. 471-499.
19. Fukasawa, R., Longo, H., Lysgaard, J., Arag�姛, M.P.D., Reis, M., Uchoa, E., and Werneck, R.F., “Robust branch-and-cut-and-price for the capacitated vehicle routing problem”, Mathematical Programming, Vol. 106, No. 3, 2006, pp.491-511.
20. Funke, B., Gr�刡ert, T. and Irnich, S., “Local search for vehicle routing and scheduling problems: review and conceptual integration,” Journal of Heuristics, Vol. 11, 2005, pp.267–306.
21. Gendreau, M., Hertz, A.. and Laporte, G., “New insertion and postoptimization procedures for the Traveling Salesman Problem.,” Operations Research, Vol. 40, 1992, pp.1086-1094.
22. Gendreau, M., Hertz, A. and Laporte, G., “A tabu search heuristic for the vehicle routing problem,” Management Science, Vol. 40, No. 10, 1994, pp.1276-1290.
23. Gendreau, M., Hertz, A., Laporte, G. and Stan, M., “A generalized insertion heuristic for the traveling salesman problem with time windows,” Operations Research, Vol. 43, No.3, 1998, pp.330-335.
24. Golden, B.L. and Assad, A.A., Vehicle Routing: Methods and Studies, Elsevier Science Publishers B.V., 1988.
25. Ho, S.C. and Gendreau, M., “Path relinking for the vehicle routing problem,” Journal of Heuristics, Vol.12, 2006, pp. 55-72.
26. Kirkpatrick, S., Gelatt, C., and Vecchi, M., “Optimization by Simulated Annealing,” Science, Vol.220, 1983, pp. 671-680.
27. Lawler, E., Lenstra, J., Rinnooy Kan, A. and Shmoys, D., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, Inc., 1985.
28. Lin, S., “Computer solutions of the traveling salesman problem,” The Bell System Technical Journal, 1965, pp.2245-2269.
29. Mester, D. and Br�爨sy, O., “Active guided evolution strategies for large-scale vehicle routing problems with time windows,” Computers & Operations Research, Vol. 32, 2005, 1593–1614.
30. Mester, D. and Br�爨sy, O., “Active guided evolution strategies for large-scale capacitated vehicle routing problems,” Computers & Operations Research, Vol. 34, 2007, 2964–2975.
31. Network Lab: http://140.113.119.114/network/, 07/27/2007.
32. Or, I., Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, PhD. Dissertation, Northwestern University, 1996.
33. Osman, I.H., “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, Vol. 41, 1993, pp.421-451.
34. Rochat, Y. and Taillard, ��.D., “Probabilistic diversification and intensification in local search for vehicle routing,” Journal of heuristics, Vol. 1, No. 1, 1995, pp. 147-167.
35. Rosenkrantz, D., Sterns, R. and Lewis, P., “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal of Computing, Vol. 6, 1977, pp.563-581.
36. Taillard, ��.D., “Parallel Iterative Search Methods for Vehicle Routing Problems,” Networks, Vol.23, No.8, 1993, pp.661-673.
37. Tarantilis, C.D., “Solving the vehicle routing problem with adaptive memory programming methodology,“ Computers & Operations Research , Vol. 32, 2005, pp.2309–2327.
38. Tarantilis, C.D. and Kiranoudis, C.T.. “A meta-heuristic algorithm for the efficient distribution of perishable foods,” Journal of Food Engineering , Vol. 50, 2001, pp. 1-9.
39. Tarantilis, C.D., Kiranoudis, C.T. and Vassiliadis, V.S., “A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem.” Journal of the Operational Research Society, Vol. 54, 2003, pp. 65-71.
40. Tarantilis, C.D., Kiranoudis, C.T. and Vassiliadis, V.S., “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem.,” European Journal of Operational Research, Vol. 152, 2004, pp.148-158.
41. Universit�� di Bologna-D.E.I.S.- Operations Research, http://www.or.deis.unibo.it/, 07/27/2007.
42. Xu, J. and Kelly, J.P., “A network flow-based tabu search heuristic for the vehicle routing problem,” Transportation Science, Vol. 30, No.4, 1996, pp. 379-393.
43. VRP Web: http://neo.lcc.uma.es/radi-aeb/WebVRP/, 07/27/2007.