螞蟻最佳化演算法(Ant Colony Optimization)是仿效螞蟻族群的覓食行為所發展而成的群體智慧演算法，屬於NP-hard組合最佳化問題，運用Hadoop的MapReduce框架運算，平行處理螞蟻最佳化演算法，增加執行效率來加速演化過程，應用於時窗化車輛途程問題(Vehicle Routing Problem with Time Windows, VRPTW)，在客戶硬時窗限制、車輛載重限制下計算最短路徑的派車途程規劃。
本研究應用MapReduce螞蟻最佳化演算法(MapReduce Ant Colony Optimization)求解時窗限制車輛途程問題，採用MapReduce架構的平行運算技術縮短執行時間，其中螞蟻最佳化演算法加入禁忌搜尋( Tabu Search )短期記憶和長期記憶概念，短期記憶使用禁忌列表( Tabu List )避免搜索過程中出現重複的移動，長期記憶使用頻率懲罰跳脫區域最佳解，增加搜尋空間多樣性。本研究求解Solomon學者VRPTW測試例題，在MapReduce框架下之績效和執行效率進行比較。

Ant colony optimization algorithm is a intelligence algorithm evolved on the foraging behavior of ants ethnic groups and belongs to NP-hard combinatorial optimization problems. Using Hadoop MapReduce framework to deal with parallel processing ant colony optimization algorithm that increase the efficiency to accelerate the evolution and is applied in Vehicle routing problems with time window problem to minimize the total distance of the routes under time window and vehicle capacity constraints.
This study applies MapReduce Ant Colony Optimization algorithm (MRACO) for solving vehicle routing problems with time window. We use Hadoop MapReduce parallel computing architecture technology to shorten the execution time and include the use of Tabu Search's short-term memory and long term memory concept. Short-term memory contains tabu list to avoid duplication move during the search process. In order to increase the search space diversity, long-term memory use frequently punishment to escape local optimum. This study computes Solomon's VRPTW test examples and compares with efficiency and performance under the MapReduce framework.

誌謝 I
摘要 II
ABSTRACT III
目錄 IV
圖目錄 VII
表目錄 IX
第一章 簡介 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 3
1.4 研究方法與流程 3
1.5 論文架構 4
第二章 文獻探討 5
2.1 時窗限制車輛途程問題 5
2.2 螞蟻最佳化演算法 6
2.3 TABU SEARCH 9
2.4 HADOOP 10
2.5 MAPREDUCE 13
第三章 螞蟻最佳化演算法 19
3.1 數學模型 19
3.2 演算法設計 21
3.2.1 演算法流程 21
3.2.2 途程解字串與限制 26
3.2.3 演算法加入VRPTW 限制 27
3.2.4 區域搜尋法 27
3.2.5 禁忌搜尋長期記憶 29
3.2.6 費洛蒙更新法則 30
第四章 MAPREDUCE 螞蟻最佳化演算法 31
4.1 MAPREDUCE 螞蟻最佳化演算法流程 31
4.2 實作MAPREDUCE 螞蟻最佳化演算法 36
第五章 實驗及比較 45
5.1 建置環境 45
5.2 參數設定 48
5.3 實驗結果 50
5.4 文獻比較 53
第六章 結論 54
參考文獻 55

[1] 林志剛( 2013 )，改良螞蟻最佳化演算法求解VRPTW 問題，大同大學資訊經營研究所碩士論文。
[2] 柯景文( 1999 )，禁制搜尋法於動態車輛巡迴路線問題之研究，逢甲大學交通工程與管理學系碩士班。
[3] 林建佑( 2011 )，車輛途程與時窗問題之改善，東吳大學資訊管理研究所碩士論文。
[4] 陳家和、丁慶榮( 2005 )，應用螞蟻演算法於時窗限制車輛途程問題之研究，運輸學刊vol. 17 pp. 261-280。
[5] 李相勇、田澎( 2008 )，開放式車輛路徑問題的蟻群優化演算法，中國系統工程理論與實踐Vol. 28(6)，pp 81-93。
[6] 李泰琳、張靖( 2010 )，調適型導引螞蟻演算法求解時窗收卸貨問題之研究，運輸學刊，第39 卷，第1 期，頁99-132。
[7] 黃金智( 1999 )，隨機型車輛途程問題解法之研究，大葉大學工業工程研究所碩士論文。
[8] 何俊德( 2012 )，同時收送貨存貨途程配銷模式之研究─以混合免疫禁忌演算法求解，龍華科技大學資訊管理系碩士班。
[9] 陸嘉恒( 2014 )，徹底研究Hadoop 實戰分析，上奇資訊股份有限公司。
[10] 廖丞宇( 2013 )，植基於Hadoop 雲端運算架構之平行基因演算法與粒子群演算法的應用，崑山科技大學資訊管理研究所碩士論文。
[11] 王會穎、倪志偉、吳昊( 2013 )，求解多維背包問題的MapReduce 蟻群優化演算法，中國計算機工程Vol. 39 Issue (4)，pp 248-253。
[12] 賈瑞玉、李亞龍( 2013 )，基於MapReduce 的量子蟻群演算法，電腦工程與應用49(19): 246-249。
[13] Dorigo, M., and Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions on, vol. 1, pp. 53-66, 1997.
[14] Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, vol. 1, pp. 190-206.
[15] Ghemawat, S., Gobioff, H., and Leung, S. T. (2003). Web search for a planet:the google cluster architecture. Google Inc.
[16] Dean, J. and Ghemawat, S. (2004). MapReduce: Simplied Data Processing on Large Clusters. Google Inc.
[17] Solomon, M. (2005). VRPTW BENCHMARK PROBLEMS. http://web.cba.neu.edu/~msolomon/problems.htm.
[18] Dantzig, G. B., and Ramser, J. H. (1959). The truck dispatching problem. Management science, vol. 6, pp. 80-91.
[19] Bulleneimer, B., Hartl, R. F., and Strauss, C. (1997). Strauss. applying the ant system to the vehicle routing problem. In: Proc. of the Second Internat. Conf. on Metaheuristics, pp 1-12.
[20] Stutzle, T., and Hoos, H. H. (1997). The MAX–MIN ant system and local search for the traveling salesman problem. Proceedings of the IEEE International Conference on Evolutionary Computation, IEEE Press, Piscataway, USA, pp 309–314.
[21] Reimann, M., Stummer, M., and Doerner, K. (2002). A Savings Based Ant System For The Vehicle Routing Problem. GECCO,pp 1317-1326.
[22] Catay, B. (2006). An Ant Colony Optimization Approach for the Capacitated Vehicle familylRouting Problem with Simultaneous Delivery and Pick-up. Proceedings of the EWGT Joint Conferences,pp 275-282.
[23] Chen, C. H., and Ting, C. J. (2005). A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows. Journal of the Eastern Asia Society for Transportation Studies, Vol. 6, pp. 2822-2836.
[24] Wang, Y. P. (2012). A Hybrid Approach Based on Ant Colony System for the VRPTW. Advanced Technology in Teaching-Proceedings of the 3rd International Conference on Teaching and Computational Science , pp. 327-333.
[25] Wang, H. L., He, Y., and Zheng, G. (2010). Application and research on Vehicle Routing Problem with Time Window based on dynamic adaptive ant colony algorithm. Computer Application and System Modeling (ICCASM), International Conference on, pp. V7-8-V7-12.
[26] Cruz, J. J. (2011). A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products. Journal of Heuristics.
[27] Yu, B., Yang, Z. Z., and Yao, B. Z. (2011). A hybrid algorithm for vehicle routing problem with time windows. Expert Systems with Applications, vol. 38, pp.435-441.
[28] Ding, Q., Hu, X., Sun, L., and Wang, Y. (2012). An improved ant colony optimization and its application to vehicle routing problem with time windows. Neurocomputing, vol. 98, pp. 101-107.
[29] Gendreau, M., Hertz, A., and Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, Vol. 40,No. 10, pp.1276-1290.
[30] Barbarosoglu, G., and Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computer & Operations Research, 26, pp.255-270.
[31] Lau, H. C., Sim, M., and Teo, K. M. (2003). Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research 148 559–569.
[32] Ho, S. C., and Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, vol. 31, pp. 1947-1964.
[33] Chang, F., Dean, J., and Ghemawat S. (2006). Bigtable: A Distributed Storage System for Structured Data. Google Inc.
[34] Doug, C. (2012). YARN/MRv2. http://dongxicheng.org/mapreduce-nextgen/client-codes/.
[35] Bu, Y. Y., Howe, B., Balazinska, M., and Ernst, M. D. (2010). HaLoop Efficient Iterative Data Processing On Large Scale Clusters. Department of Computer Science and Engineering.
[36] Doug, C. (2008). Apache Hadoop. http://hadoop.apache.org/.
[37] Cheng, X. G., Xiao, N. F. (2013). Parallel Implementation of Dynamic Positive and Negative Feedback ACO with Iterative MapReduce Model. JICS ,pp 2359- 2370.
[38] Tan, Q., He, Q., and Shi, Z. Z. (2012). Parallel Max-Min Ant System Using MapReduce. Lecture Notes in Computer Science Volume 7331, pp 182-189.
[39] Mohan, A., and G, R. (2014). Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework. International Journal of Computer Applications Volume88 ,p8.
[40] Bhavani, R. (2011). A novel parallel hybrid K-means-DE-ACO clustering approach for genomic clustering using MapReduce. Proceedings of World Congress on Information and Communication Technologies (WICT-2011), pp. 132–137.
[41] Sudha, S. G., and Selvaraj, D. (2010). A Novel Parallel Hybrid PSO-GA using MapReduce to Schedule Jobs in Hadoop Data Grids. 2010 Second World Congress on Nature and Biologically Inspired Computing Dec. 15-17 in Kitakyushu, Fukuoka,Japan.
[42] Ilhan, O. (1976). Traveling salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Ph. D Dissertation,Northwestern University, Evanston, IL.
[43] Xing, G. H. and Yu, S. L. (2007). Dynamic stage ant colony algorithm and its convergence. Control and Decision, vol. 22, p. 685.
[44] Melian-Batista, B., Santiago, A., Bello, F. (2014). A bi-objective vehicle routing problem with time windows: a real case in Tenerife. Applied Soft Computing, vol.17, pp. 140–152.
[45] Gong, Y. J. (2012). Optimizing the Vehicle Routing Problem With Time Windows A Discrete Particle Swarm. Systems, Man, and Cybernetics, Volume:42 Issue:2.
[46] Nazif, H., and Lee, L. S. (2010). Optimized crossover genetic algorithm for vehicle routing problem with time windows. American journal of applied sciences, vol. 7, p.95.