臺灣博碩士論文加值系統

近年來台灣觀光發展十分迅速，國內外的旅客在台灣旅遊之比例逐年上升，旅客通常會先決定要去哪些旅遊景點，然而許多人對當地位置不熟悉時，在未經行程規劃之前，直接前往並同時想下一個目的地，這會產生行程較長的問題，進而浪費不要必要之時間及金錢。為避免上述狀況發生，必須規劃出順暢不阻塞且耗時最短之行程路徑。在目前導航系統當中，會依據路況進行路徑導航，然而導航系統卻只能依賴旅客以人工方式自行規劃景點先後順序，來得到最短路徑，但條件因素過多，以致花費更多時間天數，才能找出最佳路徑規劃，如數天的行程、路徑距離、花費時間等等，則人工需大量耗時，且不一定能找出最短路徑行程。
本研究結合情境來模擬探討，利用基因演算法(Genetic Algorithm, GA)作為取代人工耗時問題，迅速規劃出路徑最佳化的排程問題為此題研究，並可參考GPS衛星導航中的路徑距離和路況結合路徑規劃。因此將路徑和路況參數列入適應值的評估條件，經基因演算中，將好的基因保留，不好的漸漸淘汰，經由複製來挑選出較高的適應函數值的染色體。此研究因沒有使用交配，所以在突變階段增加幾種不同的方式來改變路徑規劃，因此將路徑規劃達到最佳化。實驗結果得知加入基因演算法後，可快速運算且找出最佳行程規劃，改善人工尋找最短行程規劃的問題，且在短時間內找出旅遊行程規劃的最佳化。

In recent years, tourism in Taiwan has developed rapidly, and the proportion of tourists from all over the world who come to Taiwan has increased year by year. Passengers usually decide which tourist attractions to go first. However, when many people are unfamiliar with the local location, they will go directly to the next destination without planning the trip, which will cause long travel problems. Then waste unnecessary time and money. In order to avoid this, it is necessary to plan a smooth, non-blocking and shortest travel path. In the current navigation system, the path navigation is performed according to the road condition. However, the navigation system can only rely on the passenger to manually plan the order of the attractions to obtain the shortest path. However, if you consider the following factors: the number of days of travel, path distance, time spent, etc., if the conditional factors are too much, it will take more time to find the best path planning. Manual labor takes a lot of time and may not find the shortest path.
This study combines the situation to simulate the discussion, using the genetic algorithm as a substitute for the artificial time-consuming problem, and quickly planning the scheduling problem of the path optimization. And can refer to path distance and road conditions in GPS satellite navigation combined with path planning. Therefore, the path and road condition parameters are included in the evaluation conditions of the fitness value. In the genetic calculation, the good genes are retained, the bad genes are gradually eliminated, and the chromosomes with higher adaptation function values are selected through replication. This study did not use mating, so several different ways to change the path planning during the mutation phase to optimize the path planning. The experimental results show that after adding the gene algorithm, the algorithm can be quickly calculated and the optimal trip planning can be found, the problem of manually finding the shortest trip planning can be improved, and the optimization of the travel itinerary can be found in a short time.

摘要.............................................i
Abstract........................................ii
誌謝............................................iv
目錄.............................................v
表目錄..........................................vi
圖目錄.........................................vii
第一章 緒論......................................1
1.1 研究背景.....................................1
1.2 研究動機.....................................3
1.3 論文架構.................................... 5
第二章 基因演算法及其應用.........................6
2.1基因演算法....................................6
2.2 旅行商問題..................................15
2.3 GPS導航系統.................................17
第三章 基於基因演算法之旅遊行程規劃................18
第四章 實驗結果與討論...........................23
4.1 情境模擬....................................23
4.2 實驗情境....................................27
4.3 實驗結果與討論...............................28
第五章 結論與未來研究方向.......................36
參考文獻........................................37
Extended Abstract..............................40
Abstract.......................................40

[1]林信宏，2013，”應用蟻群演算法於旅程規劃之研究”，國立虎尾科技大學資訊工程系研究所，碩士論文。
[2]王騰毅，2010，”整合即時路況之導航系統研究”，國立虎尾科技大學機械與機電工程系研究所，碩士論文。
[3]劉俊宏，2010，”應用粒子群演算法求解雙機流程工廠群組排成問題”，國立虎尾科技大學經營管理研究所，碩士論文。
[4]林信宏，2013，”應用蟻群演算法於旅程規劃之研究”，國立虎尾科技大學資訊工程系研究所，碩士論文。
[5]廖雅陵，2015，”人工智慧方法應用於校車路徑規劃問題”，國立虎尾科技大學經營管理研究所，碩士論文。
[6]涂榮城，2017，”應用人工智慧言算法於多選擇性及固定參觀時間之博物館路徑問題”，工業管理系工業工程與管理碩士班。
[7]夏新海，2004，”物流配送車輛度優化研究”，武漢理工大學交通运输规划与管理，碩士論文
[8]劉建宏，2005，”含時窗限制式卡車與拖車途程問題之研究”，國立中央大學土木工程研究所，碩士論文
[9]林昇甫、徐永吉，2009，遺傳演算法及其應用，五南圖書出版股份有限公司，台北市。
[10]魏維勉，2007，”建構整合型基因演算法最佳化主動運補路線”，國防大學中正理工學院，兵器系統工程研究所，碩士論文。
[11]陳仲星，2017，”國民中學排課問題最佳化研究—使用基因演算法”，樹德科技大學，資訊管理系碩士班，碩士論文。
[12]周鵬程，2007，遺傳演算法原理與應用－活用 Matlab(附程式光碟片)(修訂四版)，台灣：全華圖書股份有限公司，台北市。
[13]蘇木春、張孝德，2004，機器學習：類神經網路、模糊系統以及基因演 算法則(修訂二版)，台灣：全華圖書股份有限公司，台北市。
[14]王進德，2006，類神經網路與模糊控制理論入門與應用，全華圖書股份有限公司，臺北市。
[15]沈志忠譯，2016，MATLAB程式設計及應用/Stephen J. Chapman著，新加坡商聖智學習，台北市。
[16]張睿穎，2017，”應用多目標基因演算法於物流規劃問題”，國立台北科技大學，工業工程與管理碩士班，碩士論文。
[17]中華民國交通部觀光局http://admin.taiwan.net.tw/public/public.aspx?no=315
[18]Holland, J. H.,1992 , Adaptation in Natural and Artificial Systems, MI: The University of Michigan Press, Ann Arbor.
[19]Holland, J. H.,1992 , “Genetic Algorithms”, Sci. Am., pp.66-72,July.
[20]Melanie Mitchell, 1996 , An introduction to genetic algorithms, Mass. :MIT Press Cambridge.
[21]Biethahn, J., Nissen, V., Evolutionary Algorithms in Management Applications, 1995, Springer-Verlag, Berlin.
[22]J. Hartigan (1975), Clustering Algorithms, John Wiley & Sons, New York.
[23]Louis, S. J. and Rawlins, G. J., 1991, “Designer genetic algorithm in structure design”, in Proc. 4th Int. Conf. Genetic Algorithms, pp.53-60.
[24]Syswerda, G. ,1989 , “Uniform crossover in genetic algorithms”, in Proc. 3rd Int. Conf. Genetic Algorithms, pp.2-9.
[25]Eshelman, L. J. , Caruanu, R. A. and Schaffer, J. D. , 1989, “Biases in the crossover landscape＂, in Proc. 3rd Int. Conf. Genetic Algorithms, pp.10-19.
[26]Goldberg, D, E., 1989, Genetic Algorithm in Search, Optimization, and Machine Learning , Addison-Wesley , New York.
[27]Baker, J. E.,1985 , “Reducing bias and inefficiency in the selection algorithm＂, in Proc. 2nd Int. Conf. Genetic Algorithm, pp.14-21.
[28]https:// zh.wikipedia.org/wiki/旅行推銷員問題
[29]https:// zh.wikipedia.org/wiki/全球定位系统
[30]P.C.Chang, J. C. Hsieh, and C. H. Hsiao, 2002 “Application of genetic algorithm to the unrelated parallel machine problem scheduling”, J. Chin. Inst. Eng., vol. 19, no. 2, pp. 79-95.
[31]J. B. Jensen and M. Nielsen, 1992 “A simple genetic algorithm applied to discontinuous regularization”, Proc. of the IEEE-SP Workshop Neural Networks for Signal Processing, pp. 69-78.
[32]G. R. Harik, F. G. Lobo and D. E. Goldberg, 1999 “The compact genetic algorithm”, IEEE T. Evolut. Comput., vol. 3, no. 4, pp. 287-297.
[33]H. Braun, 2006 , On solving travelling salesman problems by genetic algorithms, Springer-Verlag, Berlin.
[34]J. Arabas, Z. Michalewicz, and J. Mulawka, 1994 “GAVaPS-A genetic algorithm with varying population size”, Proc. IEEE Int. Conf. Evolutionary Computation, pp. 73-78.
[35]K. Y. Lee and P. S. Mohamed, 2002“A real-coded genetic algorithm involving a hybrid crossover method for power plant control system design”, Proc. IEEE Int. Conf. Evolutionary Computation, pp. 1069-1074.
[36]D. Beasley, D. R. Bull, and R. R. Martin, 1993, “An overview of genetic algorithms: Part 1 ,Fundamentals ”, University Computing, vol. 15, no. 2, pp. 58-69.
[37]R. Kowalczyk, 1997, “Constrained genetic operators preserving feasibility of solutions in genetic algorithms”, Proc. Int. Cont Genetic Algoriühms in Engineering Systems: Innovations and Applications, pp. 191-196.
[38]P. C. Chang, J. C. Hsieh, and C. H. Hsiao,2002, “Application of genetic algorithm to the unrelated parallel machine problem scheduling”, J. Chin. Inst. Eng., vol. 19, no. 2, pp. 79-95.
[39]盧濟安，2009，含住宿及興趣景點考量之旅遊規劃系統，淡江大學資訊管理學系碩士班，碩士論文。
[40]陳雅雯，2007，蟻群最佳化演算法於生態旅遊路線規劃之研究，立德管理學院資源環境研究所，碩士論文。
[41]Chen, Y.-H., Sun, W.-J., & Chiang, T.-C. , 2015, “Multiobjective Orienteering Problem with Time Windows: An Ant Colony Optimization Algorithm”, Proceedings of the Technologies and Applications of Artificial Intelligence, pp. 128-135, Tainan, Taiwan.
[42]Dantzig, G. and Ramser, J. , 1959, “The Truck Dispatching Problem”, Management Science, Vol. 6,No 1, pp. 80-91, Oct 1959.
[43]L. A. Zadeh, 1965, “Fuzzy sets”, Information and Control , vol. 8, no. 3, pp. 338-353, June 1965.
[44]M. Dorigo, V. Maniezzo, and A. Colorni, 1996, “The ant system: Optimization by a colony of cooperating agents”, IEEE Trans. Syst, Man, Cybern. B, vol. 26, no. 2, pp. 29-41, Feb 1996.
[45]Kennedy, J., and Eberhart, R., 1995, "Particle swarm optimization," Proc. Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, pp. 1942-1948, August 2007.