請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/94694完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 潘建興 | zh_TW |
| dc.contributor.advisor | Frederick Kin Hing Phoa | en |
| dc.contributor.author | 黃健滔 | zh_TW |
| dc.contributor.author | Kin To Wong | en |
| dc.date.accessioned | 2024-08-16T17:34:02Z | - |
| dc.date.available | 2024-08-17 | - |
| dc.date.copyright | 2024-08-16 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-08-05 | - |
| dc.identifier.citation | Abdel‐Basset, M., Abdel-Fatah, L., & Sangaiah, A. K. (2018). Metaheuristic Algorithms: A Comprehensive Review. In Elsevier eBooks (pp. 185–231). https://doi.org/10.1016/b978-0-12-813314-9.00010-4
Abdel‐Basset, M., Ding, W., & El-Shahat, D. (2020). A hybrid Harris Hawks optimization algorithm with simulated annealing for feature selection. Artificial Intelligence Review, 54(1), 593–637. https://doi.org/10.1007/s10462-020-098603 Bandaru, S., & Deb, K. (2016). Metaheuristic Techniques. https://www.egr.msu.edu/~kdeb/papers/c2016029.pdf Beheshti, Z. (2013). A review of population-based meta-heuristic algorithm. Soft Computing, 5(1), 1–35. http://home.ijasca.com/data/documents/IJASCA07_REVISED.pdf Bellman, R. (1962). Dynamic Programming treatment of the travelling salesman problem. Journal of the ACM, 9(1), 61–63. https://doi.org/10.1145/321105.321111 Bertsimas, D., & Tsitsiklis, J. N. (1993). Simulated annealing. Statistical Science, 8(1). https://doi.org/10.1214/ss/1177011077 Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308. https://doi.org/10.1145/937503.937505 Bonyadi, M. R., Azghadi, M. R., & Shah‐Hosseini, H. (2008). Population-Based optimization algorithms for solving the travelling salesman problem. In InTech eBooks. https://doi.org/10.5772/5586 Boysen, N., Fedtke, S., & Schwerdfeger, S. (2020). Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum, 43(1), 1–58. https://doi.org/10.1007/s00291-020-00607-8 De Smith, M. J., Goodchild, P. M. F., & Longley, P. P. A. (2018). Geospatial analysis: A Comprehensive Guide to Principles Techniques and Software Tools. The Winchelsea Press. Distance Matrix API request and response. (n.d.). Google for Developers. https://developers.google.com/maps/documentation/distance-matrix/distance-matrix Dorigo M (1992) Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy Eren, E., & Tuzkaya, U. R. (2021). Safe distance-based vehicle routing problem: Medical waste collection case study in COVID-19 pandemic. Computers & Industrial Engineering, 157, 107328. https://doi.org/10.1016/j.cie.2021.107328 Flood, M. M. (1956). The Traveling-Salesman Problem. Operations Research, 4(1), 61–75. https://www.jstor.org/stable/167517 Fraser, A. (1957). Simulation of genetic systems by Automatic Digital Computers. Australian Journal of Biological Sciences, 10(4), 484–491. https://doi.org/10.1071/bi9570484 Gad, A. G. (2022). Particle Swarm Optimization Algorithm and its Applications: A Systematic review. Archives of Computational Methods in Engineering, 29(5), 2531–2561. https://doi.org/10.1007/s11831-021-09694-4 Gaertner, D., & Clark, K. L. (2005). On optimal parameters for ant colony optimization algorithms. International Conference on Artificial Intelligence, 83–89. https://dblp.uni-trier.de/db/conf/icai/icai2005-1.html#GaertnerC05 Getting directions through the Directions API. (n.d.). Google for Developers. https://developers.google.com/maps/documentation/directions/get-directions Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549. https://doi.org/10.1016/0305-0548(86)90048-1 Glover, F. (1990). Tabu Search—Part II. ORSA Journal on Computing, 2(1), 4–32. https://doi.org/10.1287/ijoc.2.1.4 Gmira, M., Gendreau, M., Lodi, A., & Potvin, J. (2021). Tabu search for the time-dependent vehicle routing problem with time windows on a road network. European Journal of Operational Research, 288(1), 129–140. https://doi.org/10.1016/j.ejor.2020.05.041 Goldberg, D. E., & Lingle Jr, R. (1985, July). AllelesLociand the Traveling Salesman Problem. In Proceedings of the 1st International Conference on Genetic Algorithms (pp. 154-159). Grisales-Noreña, L. F., Montoya, O. D., & Ramos‐Paja, C. A. (2020). An energy management system for optimal operation of BSS in DC distributed generation environments based on a parallel PSO algorithm. Journal of Energy Storage (Print), 29, 101488. https://doi.org/10.1016/j.est.2020.101488 Guevara, C., & Peñas, M. S. (2020). Surveillance routing of COVID-19 infection spread using an intelligent infectious diseases algorithm. IEEE Access, 8, 201925–201936. https://doi.org/10.1109/access.2020.3036347 Gutin, G., & Punnen, A. P. (2007). The traveling salesman problem and its variations. In Combinatorial optimization. https://doi.org/10.1007/b101971 Halim, A., & Ismail, I. (2017). Combinatorial Optimization: Comparison of heuristic algorithms in travelling salesman Problem. Archives of Computational Methods in Engineering, 26(2), 367–380. https://doi.org/10.1007/s11831-017-9247-y Hoffman, K. L., Padberg, M., & Rinaldi, G. (2013). Traveling salesman problem. Encyclopedia of operations research and management science, 1, 1573-1578. Holland, J. H. (1975). Adaptation in natural and artificial systems. https://dl.acm.org/citation.cfm?id=129194 Hsu, T., & Phoa, F. K. H. (2018). A smart initialization on the swarm intelligence based method for efficient search of optimal minimum energy design. In Lecture Notes in Computer Science (pp. 78–87). https://doi.org/10.1007/978-3-319-93815-8_9 Huang, E. C., & Phoa, F. K. H. (2023a). Uniformly scattering neighboring nodes of an Ego-Centric network on a spherical surface for better network visualization. In Studies in computational intelligence (pp. 97–107). https://doi.org/10.1007/978-3-031-21131-7_8 Huang, E. C., & Phoa, F. K. H. (2023b). A UNIFORM PLACEMENT OF ALTERS ON SPHERICAL SURFACE (U-PASS) FOR EGO-CENTRIC NETWORKS WITH COMMUNITY STRUCTURE AND ALTER ATTRIBUTES. Advances in Complex Systems, 26(03). https://doi.org/10.1142/s0219525923400039 Hussain, A., Muhammad, Y. S., Sajid, M. N., Hussain, I., Shoukry, A. M., & Gani, S. (2017). Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational Intelligence and Neuroscience, 2017, 1–7. https://doi.org/10.1155/2017/7430125 Ilin, V., Simić, D., Simić, S. D., Simić, S., Saulić, N., & Calvo-Rolle, J. L. (2022). A hybrid genetic algorithm, list-based simulated annealing algorithm, and different heuristic algorithms for the travelling salesman problem. Logic Journal of the IGPL (Print), 31(4), 602–617. https://doi.org/10.1093/jigpal/jzac028 Jiang, C., Wan, Z., & Peng, Z. (2020). A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Systems With Applications, 139, 112867. https://doi.org/10.1016/j.eswa.2019.112867 Jiang, H., He, Z., Ye, G., & Zhang, H. (2020). Network intrusion detection based on PSO-XGBoost model. IEEE Access, 8, 58392–58401. https://doi.org/10.1109/access.2020.2982418 Katoch, S., Chauhan, S. S., & Kumar, V. (2020). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80(5), 8091–8126. https://doi.org/10.1007/s11042-020-10139-6 Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks (Vol. 4, pp. 1942-1948). IEEE. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671 Lin, F. P., & Phoa, F. K. H. (2017). An Efficient Construction of Confidence Regions via Swarm Intelligence and Its Application in Target Localization. IEEE Access, 6, 8610–8618. https://doi.org/10.1109/access.2017.2785789 Liu, H., Phoa, F. K. H., Chen-Burger, Y., & Lin, S. (2024). An efficient swarm intelligence approach to the optimization on high-dimensional solutions with cross-dimensional constraints, with applications in supply chain management. Frontiers in Computational Neuroscience, 18. https://doi.org/10.3389/fncom.2024.1283974 Miller, B. L., & Goldberg, D. E. (1995). Genetic algorithms, tournament selection, and the effects of noise. Complex systems, 9(3), 193-212. Miller, C., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326–329. https://doi.org/10.1145/321043.321046 Mirjalili, S. (2018). Evolutionary Algorithms and Neural Networks: Theory and applications.https://openlibrary.org/books/OL28177039M/Evolutionary_Algorithms_and_Neural_Networks Olson, R. S. (2015, March 8). Dr. Randal S. Olson | Computing the optimal road trip across the U.S. https://randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/ Osaba, E., Yang, X., & Del Ser, J. (2020). Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. In Elsevier eBooks (pp. 135–164). https://doi.org/10.1016/b978-0-12-819714-1.00020-8 Phoa, F. K. H. (2017). A Swarm Intelligence Based (SIB) method for optimization in designs of experiments. Natural Computing, 16(4), 597–605. https://doi.org/10.1007/s11047-016-9555-4 Phoa, F. K. H., Chen, C., Wang, W., & Wong, W. K. (2016). Optimizing Two-Level supersaturated designs using swarm intelligence techniques. Technometrics, 58(1), 43–49. https://doi.org/10.1080/00401706.2014.981346 Phoa, F. K. H., & Tsai, T. (2020). A Two-Step approach to the search of minimum energy designs via swarm intelligence. In Lecture Notes in Computer Science (pp. 37–45). https://doi.org/10.1007/978-3-030-53956-6_4 Phoa, F. K. H., Liu, H., Chen-Burger, Y., & Lin, S. (2021). Metaheuristic optimization on Tensor-Type solution via Swarm Intelligence and its application in the profit optimization in designing selling scheme. In Lecture Notes in Computer Science (pp. 72–82). https://doi.org/10.1007/978-3-030-78743-1_7 Razali, N. M., & Geraghty, J. (2011, July). Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering (Vol. 2, No. 1, pp. 1-6). Hong Kong, China: International Association of Engineers. Reinelt, G. (1991). TSPLIB—A Traveling Salesman problem Library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376 Rego, C., Gamboa, D., Glover, F., & Osterman, C. (2011). Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211(3), 427–441. https://doi.org/10.1016/j.ejor.2010.09.010 Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3), 563–581. https://doi.org/10.1137/0206041 Shi, X., Liang, Y., Lee, H. P., Lu, C., & Wang, Q. X. (2007). Particle swarm optimization-based algorithms for TSP and generalized TSP. Information Processing Letters, 103(5), 169–176. https://doi.org/10.1016/j.ipl.2007.03.010 Shi, Y., & Eberhart, R. C. (1999, July). Empirical study of particle swarm optimization. In Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406) (Vol. 3, pp. 1945-1950). IEEE. Singh, K., Lin, S. P., Phoa, F. K. H., & Chen-Burger, Y. H. J. (2021). Swarm Intelligence optimisation algorithms and their applications in a complex Layer-Egg supply chain. In Smart innovation, systems and technologies (pp. 39–51). https://doi.org/10.1007/978-981-16-2994-5_4 Singh, K., Liu, H., Phoa, F. K. H., Lin, S., & Chen-Burger, Y. (2022). Decentralized supply chain optimization via Swarm Intelligence. In Lecture Notes in Computer Science (pp. 432–441). https://doi.org/10.1007/978-3-031-09677-8_36 Sörensen, K., & Glover, F. (2013). Metaheuristics. In Springer eBooks (pp. 960–970). https://doi.org/10.1007/978-1-4419-1153-7_1167 Sun, W., & Phoa, F. K. H. (2022). Network community detection via an improved swarm intelligence approach. In Lecture Notes in Computer Science (pp. 419–431). https://doi.org/10.1007/978-3-031-09677-8_35 Sutrisno, H., & Phoa, F. K. H. (2023). Anomalous variable-length subsequence detection in time series: mathematical formulation and a novel evolutionary algorithm based on clustering and swarm intelligence. Applied Intelligence, 53(24), 29585–29603. https://doi.org/10.1007/s10489-023-05066-6 Szu, H. (1987). Fast simulated annealing. Physics Letters A, 122(3–4), 157–162. https://doi.org/10.1016/0375-9601(87)90796-1 Talbi, E. (2009). Metaheuristics: from design to implementation. In HAL (Le Centre pour la Communication Scientifique Directe). https://hal.inria.fr/hal-00750681 Wang, K., Li, X., Gao, L., Li, P., & Gupta, S. M. (2021). A genetic simulated annealing algorithm for parallel partial disassembly line balancing problem. Applied Soft Computing, 107, 107404. https://doi.org/10.1016/j.asoc.2021.107404 Wei, X. (2014). Parameters analysis for basic Ant Colony Optimization Algorithm in TSP. International Journal of U- and E-service, Science and Technology, 7(4), 159–170. https://doi.org/10.14257/ijunesst.2014.7.4.16 Yen, P., & Phoa, F. K. H. (2021). Traveling salesman problem via swarm Intelligence. In Lecture Notes in Computer Science (pp. 106–115). https://doi.org/10.1007/978-3-030-78743-1_10 Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2016). An effective rank based ANT system algorithm for solving the balanced vehicle routing problem. International Journal of Industrial Engineering-theory Applications and Practice, 23(1). https://journals.sfu.ca/ijietap/index.php/ijie/article/view/1119/0 Yu, S., Ding, C., & Zhu, K. (2011). A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems With Applications, 38(8), 10568–10573. https://doi.org/10.1016/j.eswa.2011.02.108 Zhang, G., Wang, H., Zhao, W., Guan, Z., & Li, P. (2021). Application of improved Multi-Objective AnT Colony Optimization Algorithm in ship weather routing. Journal of Ocean University of China, 20(1), 45–55. https://doi.org/10.1007/s11802-021-4436-6 Zheng, Y., Lv, X., Qian, L., & Liu, X. (2022). An optimal BP neural network track prediction method based on a GA–ACO hybrid algorithm. Journal of Marine Science and Engineering, 10(10), 1399. https://doi.org/10.3390/jmse10101399 | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/94694 | - |
| dc.description.abstract | 旅行推銷員問題（TSP）一直都是個具挑戰性的最佳化問題，促使人們發展各種方法去有效率地解決這個問題。本研究提出了一個改良基於群體智慧的最佳化演算法（Swarm Intelligence-based method）框架的最佳化演算法，並將這改良後的方法論與一些常規的最佳化演算法：基因演算法和蟻群演算法的最佳解和計算時間作比較。在有47 和50 個目的地的非對稱TSP 中，我們提出的方法在最佳解和計算時間方面表現均為最佳。為貼近實際應用，本研究利用了Google Maps API獲取路徑資料，並把結果視覺化，呈現在OpenStreetMap 的地圖上以供參考。 | zh_TW |
| dc.description.abstract | The Travelling Salesman Problem (TSP) has long been a challenging optimization puzzle, prompting the development of various methodologies to seek for efficient solutions. In this paper, we propose an improved optimization algorithm with the implementation of the Swarm Intelligence-based method (SIB). This improved method is compared to conventional optimization techniques, the Genetic Algorithm (GA) and the Ant Colony Optimization (ACO), in terms of solution quality and computational time. In asymmetric TSPs with 47 and 50 destinations, our proposed method has the best performance in terms of solution quality and computational time. To incorporate real world applications, route data are retrieved by using Google Maps API and the results are visualized on OpenStreetMap for reference. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-08-16T17:34:02Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-08-16T17:34:02Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgments i
摘要 ii Abstract iii Table of Contents iv List of Figures vi List of Tables vii 1. Introduction 1 1.1 Travelling Salesman Problem (TSP) 1 1.2 Development of TSP and Optimization Techniques 3 1.3 Challenges in Logistics 5 2. Literature Review 7 2.1 Metaheuristics of Solving the TSP 7 2.1.1 Simulated Annealing (SA) 8 2.1.2 Tabu Search (TS) 10 2.1.3 Genetic Algorithm (GA) 11 2.1.4 Ant Colony Optimization (ACO) 14 2.1.5 Particle Swarm Optimization (PSO) 16 2.2 Swarm Intelligence-Based Method 18 2.3 Datasets 22 3. Methodology 29 3.1 Google Maps API 29 3.2 Improved Swarm Intelligence Based Method 30 3.2.1 Initialization 31 3.2.2 Iteration 32 4. Experimental Setup and Result 36 4.1 Programming language and hardware 36 4.2 Experiment 36 4.3 Result for 50 landmarks 36 4.4 Result for 47 cities 44 4.4 Parameter setup of algorithms 48 5. Discussion and Conclusion 52 Reference 55 Appendix 68 | - |
| dc.language.iso | en | - |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 旅行推銷員問題 | zh_TW |
| dc.subject | 萬用啟發式演算法 | zh_TW |
| dc.subject | 群體智慧 | zh_TW |
| dc.subject | 地圖視覺化 | zh_TW |
| dc.subject | Metaheuristics | en |
| dc.subject | Swarm Intelligence | en |
| dc.subject | Optimization | en |
| dc.subject | Travelling Salesman Problem | en |
| dc.subject | Map Visualization | en |
| dc.title | 利用基於群體智慧的最佳化演算法解決旅行推銷員問題， 以進行有效率的路徑規劃 | zh_TW |
| dc.title | Solving the Travelling Salesman Problem for Efficient Route Planning through Swarm Intelligence-Based Optimization | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.coadvisor | 孫紹華 | zh_TW |
| dc.contributor.coadvisor | Shao-Hua Sun | en |
| dc.contributor.oralexamcommittee | 張漢利;尹邦嚴 | zh_TW |
| dc.contributor.oralexamcommittee | Hendri Sutrisno;Peng-Yeng Yin | en |
| dc.subject.keyword | 旅行推銷員問題,最佳化,群體智慧,萬用啟發式演算法,地圖視覺化, | zh_TW |
| dc.subject.keyword | Travelling Salesman Problem,Optimization,Swarm Intelligence,Metaheuristics,Map Visualization, | en |
| dc.relation.page | 83 | - |
| dc.identifier.doi | 10.6342/NTU202403317 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2024-08-07 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 資料科學學位學程 | - |
| 顯示於系所單位： | 資料科學學位學程 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 2.08 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。