Application of ant colony algorithm for tourism routing arrangement of Nonthaburi
Article Sidebar
Published:
Sep 17, 2021
Keywords:
Ant colony algorithm traveling salesman problem route planning; metaheuristics route planning metaheuristics benchmark problems
Main Article Content
Abstract
The research presented the Ant Colony Algorithm together with Local search including Swap, 2-opt and Insert Point to plan the route arrangement of Nonthaburi tourist attractions. The purpose of this research was to find the shortest paths for route to travel in Nonthaburi. The results showed that the best parameters for the algorithm used in the research included the pheromone evaporation equal to 0.9, the relative influence of the pheromone and the heuristic information equal to 5 and ant population equal to 10. The algorithm which was presented could calculate the optimal path which were equal to 76.5 kilometers using 1.003 seconds of average processing time. In addition, the research also tested algorithm with 15 Benchmark Problems. It appeared that the algorithm which was presented could search solutions all Benchmark Problems. The kroA150 Problem had the highest error deviation equal to 1.79 percent. The research compared the optimal solutions with Traditional Ant colony algorithm, Evolutionary and Nearest Neighbor algorithm. It showed that the algorithm which was presented. outperformed Traditional Ant Colony algorithm, Evolutionary algorithm and Nearest Neighbor algorithm
Article Details
Section
บทความวิจัย (Research Article)
References
[1] นพดล อ่ำดี, ธนภัทร มะณีแสง และหทัยนุช จันทร์ ชัยภูมิ. การประยุกต์ใช้วิธีอาณานิคมมดเพื่อจัด เส้นทางการท่องเที่ยวในอำเภอเขาค้อ. การประชุม วิชาการเครือข่ายวิศวกรรมไฟฟ้ามหาวิทยาลัย เทคโนโลยีราชมงคล ครั้งที่ 8. 25 – 27 พฤษภาคม 2559:501 – 504.
[2] ชิดชนก อัจฉริยนิติ, บุสริน ศรสวรรค์,สุรัสวดี มณีวงศ์ และนันทิยา ดิษประธูป. การประยุกต์ใช้ปัญหาการเดินทางของพนักงานขายในการหาเส้นทางการท่องเที่ยวจังหวัดนครนายก. การประชุมสัมมนาเชิงวิชาการด้านการจัดการ โลจิสติกส์และโซ่อุปทาน ครั้งที่ 18. 8 – 9 พฤศจิกายน 2561:1 – 8.
[3] เสริมศิริ นิลดำ, กษิดิศ ใจผาวัง, จิราพร ขุนศรี, เบญจวรรณ เบญจกรณ์, ศิริพรรณ จีนะบุญเรือง, นิเวศ จีนะบุญเรือง และคณะ. การพัฒนาเส้นทางการ ท่องเที่ยวตามรอยชาติพันธุ์ในจังหวัดเชียงราย. วารสารวิจัยราชภัฎพระนคร สาขามนุษยศาสตร์และสังคมศาสตร์ ครั้งที่ 12 :26 – 37.
[4] พัชรินทร์ เสริมการดี และธีระ สุภเพียร. เส้นทางการท่องเที่ยวชุมชน: สินค้าหนึ่งตำบลหนึ่งผลิตภัณฑ์ (OTOP) ในอำเภอปากพะยูน จังหวัดพัทลุง. การประชุมหาดใหญ่วิชาการระดับชาติ ครั้งที่ 6. 26 มิถุนายน 2558:1042 – 1052.
[5] ระพีพันธ์ ปิตาคะโส. วิธีการวิวัฒนาการโดยใช้ผลต่างสำหรับแก้ปัญหาการขนส่งโลจิสติกส์. พิมพ์ครั้ง ที่ 1:ภาควิชาวิศวกรรมอุตสาหการมหาวิทยาลัย อุบลราชธานี.
[6] เสกสรรค์ วินยางค์กูล, นิเวศน์ จีนะบุญเรือง, ประเวช อนันเอื้อ, นคร ไชยวงศ์ศักดา, พรวิไล กันทะวงค์, ณัฐพล หมวกเครือ และคณะ. การประยุกต์ตัวแบบปัญหาการเดินทางของเซลล์แมน กรณีศึกษาการจัดเส้นทางรถรางนำเที่ยวของเทศบาลนครเชียงราย. วารสารวิชาการคณะเทคโนโลยีอุตสาหกรรม มหาวิทยาลัยราชภัฏลำปาง ครั้งที่ 7:85 – 97.
[7] พัชรลักษณ์ รักธรรมจิรสุข. การศึกษารูปแบบการจัดเส้นทางเพื่อทำการวางแผนการเดินทางของพนักงานขาย. การประชุมวิชาการครุศาสตร์อุตสาหกรรมระดับชาติ ครั้งที่ 7. 6 พฤศจิกายน 2557:185 – 192.
[8] ทัศนวรรณ กังฮา, ศิวิสา จงรักษ์ และพัชราภรณ์ เนียมมณี. การจัดเส้นทางการเดินรถของรถรับ-ส่งนักเรียนโดยการใช้อัลกอริทึมเชิงพันธุกรรม. การประชุมวิชาการ การวิจัยดำเนินงาน ประจำปี 2548 :49 – 58.
[9] Mohammad Ahmadvand, Narges Mahmoodi Darani and Majid Yousefikhoshbakht. Solving the Travelling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm. Journal of Advances in Computer Research Vol.3. Islamic Azad University. August 2012 :75 – 84.
[10] Yingying Yu, Yan Chen and Taoying Li. A New Design of Genetic Algorithm for Solving TSP. 2011 Fouth International Joint Conference on Computational Sciences and Optimization. Yunnan. China. 15 – 19 April 2011:309 – 313.
[11] Yongsheng Pan and Yong Xia. Solving TSP by Dismantling Cross Paths. 2014International Conference on Orange Technologies. China. 20 – 23 September 2014:121 – 124.
[12] Wang Xueyuan. Research on Solution of TSP Based on Improved Genetic Algorithm. 2018 International Conference on Engineering Simulation and Intelligent Control. Hunan China. 10 – 11 August 2018:78 – 82.
[13] Marco Dorigo and Gianni A. Di Caro. Ant colony optimization: A new meta- heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99. USA. 6 – 9 July 1999:1470 – 1477.
[14] ระพีพันธ์ ปิตาคะโส. 2554. วิธีการเมตาฮิวริสติกเพื่อแก้ไขปัญหาการวางแผนการผลิตและการจัดการ โลจิสติกส์. พิมพ์ครั้งที่ 1:สมาคมส่งเสริมเทคโนโลยี (ไทย-ญี่ปุ่น).
[15] สุพรรณ สุดสนธิ์, อดิศักดิ์ สิงห์สั่งถ้ำ, ชราวุฒิ น้อยทะรงค์ และยงยุทธ จันรอง. อัลกอริทึม ระบบอาณานิคมมด สำหรับการจัดเส้นทาง พาหนะขนส่งโดยมีพาหนะขนส่งหลายขนาด ภายใต้การขนส่งที่มีกรอบเวลาจำกัด. วารสารวิชาการ เทคโนโลยีอุตสาหกรรม ครั้งที่ 11:53 – 68.
[16] ฐิตินนท์ ศรีสุวรรณดี และระพีพันธ์ ปิตาคะโส. การแก้ปัญหาการจัดเส้นทางการขนส่งยานพาหนะด้วยวิธีการ 5 อาณานิคมมด กรณีศึกษาบริษัทเจียรนัย น้ำดื่ม จำกัด. วารสารวิจัยมหาวิทยาลัยขอนแก่น ครั้งที่ 17:706 – 714.
[17] กิตติโรจน์ สันติฐายี และอุดม จันทร์จรัสสุข. ขั้นตอนวิธีอาณานิคมมดสำหรับปปัญหาการจัดเส้นทางการเดินรถที่มีความต้องการแบบสโทแคสติก. วารสารวิจัยและพัฒนา มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ครั้งที่ 41:387 – 400.
[18] Xiaojiang Li, Jiapin Liao and Min Cai. Ant Colony Algorithm for Large Scale TSP. 2011 International Conference on Electrical and Control Engineering. China. 16 – 18 September 2011:573 – 576.
[19] Pragya, Pratyush and Maitreyee Dutta. TSP Solution Using Dimensional Ant Colony Optimization. 2015 Fifth International Conference on Advanced Computing & Communication Technologies. India. 21 – 22 February 2015:506 – 512.
[20] Bai Yan-qi, Sun Xiao and Cao Zhi-yi. TSP Optimization by the Cellular Ant Algorithm. 2011 International Conference on Instrumentation Communication and Control. China. 21 – 23 October 2011:274 – 276.
[21] Lin Yuanyuan and Zhang Jing. An Application of Ant Colony Optimization Algorithm in TSP. 2012 Fifth International Conference on Intelligent Networks and Intelligent Systems. China. 1 – 3 November 2012:61 – 64.
[22] Ivan Brezina Jr. and Zuzana Cickova. Solving the Travelling Salesman Problem Using the Ant Colony Optimization. Journal of Management Information system Vol.6. September 2011:10 – 14.
[23] Naixue Xiong, Wenliang Wu and Chunxue Wu. An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. An Improved Routing Optimization Algorithm Based on Traveling Salesman Problem for Social Networks. Molecular Diversity Preservation International Sustainability Report 2017. 8 June 2017:1 – 15.
[24]Departmet of Scientific Computing at Florida State University. Florida State University. Available from: https://people.sc.fsu.edu/~burkardt/datasets/tsp/tsp.html.
[25] Gerhard Reinelt. TSPLIB – A Traveling Salesman Problem Library. ORSA Journal on Computing:376 – 384.
[2] ชิดชนก อัจฉริยนิติ, บุสริน ศรสวรรค์,สุรัสวดี มณีวงศ์ และนันทิยา ดิษประธูป. การประยุกต์ใช้ปัญหาการเดินทางของพนักงานขายในการหาเส้นทางการท่องเที่ยวจังหวัดนครนายก. การประชุมสัมมนาเชิงวิชาการด้านการจัดการ โลจิสติกส์และโซ่อุปทาน ครั้งที่ 18. 8 – 9 พฤศจิกายน 2561:1 – 8.
[3] เสริมศิริ นิลดำ, กษิดิศ ใจผาวัง, จิราพร ขุนศรี, เบญจวรรณ เบญจกรณ์, ศิริพรรณ จีนะบุญเรือง, นิเวศ จีนะบุญเรือง และคณะ. การพัฒนาเส้นทางการ ท่องเที่ยวตามรอยชาติพันธุ์ในจังหวัดเชียงราย. วารสารวิจัยราชภัฎพระนคร สาขามนุษยศาสตร์และสังคมศาสตร์ ครั้งที่ 12 :26 – 37.
[4] พัชรินทร์ เสริมการดี และธีระ สุภเพียร. เส้นทางการท่องเที่ยวชุมชน: สินค้าหนึ่งตำบลหนึ่งผลิตภัณฑ์ (OTOP) ในอำเภอปากพะยูน จังหวัดพัทลุง. การประชุมหาดใหญ่วิชาการระดับชาติ ครั้งที่ 6. 26 มิถุนายน 2558:1042 – 1052.
[5] ระพีพันธ์ ปิตาคะโส. วิธีการวิวัฒนาการโดยใช้ผลต่างสำหรับแก้ปัญหาการขนส่งโลจิสติกส์. พิมพ์ครั้ง ที่ 1:ภาควิชาวิศวกรรมอุตสาหการมหาวิทยาลัย อุบลราชธานี.
[6] เสกสรรค์ วินยางค์กูล, นิเวศน์ จีนะบุญเรือง, ประเวช อนันเอื้อ, นคร ไชยวงศ์ศักดา, พรวิไล กันทะวงค์, ณัฐพล หมวกเครือ และคณะ. การประยุกต์ตัวแบบปัญหาการเดินทางของเซลล์แมน กรณีศึกษาการจัดเส้นทางรถรางนำเที่ยวของเทศบาลนครเชียงราย. วารสารวิชาการคณะเทคโนโลยีอุตสาหกรรม มหาวิทยาลัยราชภัฏลำปาง ครั้งที่ 7:85 – 97.
[7] พัชรลักษณ์ รักธรรมจิรสุข. การศึกษารูปแบบการจัดเส้นทางเพื่อทำการวางแผนการเดินทางของพนักงานขาย. การประชุมวิชาการครุศาสตร์อุตสาหกรรมระดับชาติ ครั้งที่ 7. 6 พฤศจิกายน 2557:185 – 192.
[8] ทัศนวรรณ กังฮา, ศิวิสา จงรักษ์ และพัชราภรณ์ เนียมมณี. การจัดเส้นทางการเดินรถของรถรับ-ส่งนักเรียนโดยการใช้อัลกอริทึมเชิงพันธุกรรม. การประชุมวิชาการ การวิจัยดำเนินงาน ประจำปี 2548 :49 – 58.
[9] Mohammad Ahmadvand, Narges Mahmoodi Darani and Majid Yousefikhoshbakht. Solving the Travelling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm. Journal of Advances in Computer Research Vol.3. Islamic Azad University. August 2012 :75 – 84.
[10] Yingying Yu, Yan Chen and Taoying Li. A New Design of Genetic Algorithm for Solving TSP. 2011 Fouth International Joint Conference on Computational Sciences and Optimization. Yunnan. China. 15 – 19 April 2011:309 – 313.
[11] Yongsheng Pan and Yong Xia. Solving TSP by Dismantling Cross Paths. 2014International Conference on Orange Technologies. China. 20 – 23 September 2014:121 – 124.
[12] Wang Xueyuan. Research on Solution of TSP Based on Improved Genetic Algorithm. 2018 International Conference on Engineering Simulation and Intelligent Control. Hunan China. 10 – 11 August 2018:78 – 82.
[13] Marco Dorigo and Gianni A. Di Caro. Ant colony optimization: A new meta- heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99. USA. 6 – 9 July 1999:1470 – 1477.
[14] ระพีพันธ์ ปิตาคะโส. 2554. วิธีการเมตาฮิวริสติกเพื่อแก้ไขปัญหาการวางแผนการผลิตและการจัดการ โลจิสติกส์. พิมพ์ครั้งที่ 1:สมาคมส่งเสริมเทคโนโลยี (ไทย-ญี่ปุ่น).
[15] สุพรรณ สุดสนธิ์, อดิศักดิ์ สิงห์สั่งถ้ำ, ชราวุฒิ น้อยทะรงค์ และยงยุทธ จันรอง. อัลกอริทึม ระบบอาณานิคมมด สำหรับการจัดเส้นทาง พาหนะขนส่งโดยมีพาหนะขนส่งหลายขนาด ภายใต้การขนส่งที่มีกรอบเวลาจำกัด. วารสารวิชาการ เทคโนโลยีอุตสาหกรรม ครั้งที่ 11:53 – 68.
[16] ฐิตินนท์ ศรีสุวรรณดี และระพีพันธ์ ปิตาคะโส. การแก้ปัญหาการจัดเส้นทางการขนส่งยานพาหนะด้วยวิธีการ 5 อาณานิคมมด กรณีศึกษาบริษัทเจียรนัย น้ำดื่ม จำกัด. วารสารวิจัยมหาวิทยาลัยขอนแก่น ครั้งที่ 17:706 – 714.
[17] กิตติโรจน์ สันติฐายี และอุดม จันทร์จรัสสุข. ขั้นตอนวิธีอาณานิคมมดสำหรับปปัญหาการจัดเส้นทางการเดินรถที่มีความต้องการแบบสโทแคสติก. วารสารวิจัยและพัฒนา มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ครั้งที่ 41:387 – 400.
[18] Xiaojiang Li, Jiapin Liao and Min Cai. Ant Colony Algorithm for Large Scale TSP. 2011 International Conference on Electrical and Control Engineering. China. 16 – 18 September 2011:573 – 576.
[19] Pragya, Pratyush and Maitreyee Dutta. TSP Solution Using Dimensional Ant Colony Optimization. 2015 Fifth International Conference on Advanced Computing & Communication Technologies. India. 21 – 22 February 2015:506 – 512.
[20] Bai Yan-qi, Sun Xiao and Cao Zhi-yi. TSP Optimization by the Cellular Ant Algorithm. 2011 International Conference on Instrumentation Communication and Control. China. 21 – 23 October 2011:274 – 276.
[21] Lin Yuanyuan and Zhang Jing. An Application of Ant Colony Optimization Algorithm in TSP. 2012 Fifth International Conference on Intelligent Networks and Intelligent Systems. China. 1 – 3 November 2012:61 – 64.
[22] Ivan Brezina Jr. and Zuzana Cickova. Solving the Travelling Salesman Problem Using the Ant Colony Optimization. Journal of Management Information system Vol.6. September 2011:10 – 14.
[23] Naixue Xiong, Wenliang Wu and Chunxue Wu. An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. An Improved Routing Optimization Algorithm Based on Traveling Salesman Problem for Social Networks. Molecular Diversity Preservation International Sustainability Report 2017. 8 June 2017:1 – 15.
[24]Departmet of Scientific Computing at Florida State University. Florida State University. Available from: https://people.sc.fsu.edu/~burkardt/datasets/tsp/tsp.html.
[25] Gerhard Reinelt. TSPLIB – A Traveling Salesman Problem Library. ORSA Journal on Computing:376 – 384.