การปรับปรุงประสิทธิภาพการหาคำตอบที่เหมาะสมโดยวิธีการแมลงวันผลไม้ สำหรับการเดินทางของพนักงานขาย
Article Sidebar
Main Article Content
บทคัดย่อ
การศึกษาการเพิ่มประสิทธิภาพในการหาคำตอบสำหรับการจัดเส้นทางปัญหาการเดินทางของพนักงานขาย (Traveling Salesman Problem : TSP) ด้วยวิธีการหาค่าที่เหมาะสมของแมลงวันผลไม้ (Fruit Fly Optimization Algorithm: FOA) การแก้ปัญหาการจัดเส้นทางด้วยเมต้าฮิวริสติก (Metaheuristic) ปรับปรุงการหาผลเฉลยเดิมของวิธีการแมลงวันผลไม้โดยการปรับค่าพารามิเตอร์ (parameter) เพิ่มไดเมนชั่น (dimension) ให้เป็น3มิติ (3D) และมิติที่สูงขึ้น (Hyper Dimensional) และการปรับเปลี่ยนแบบ Swap, Swop และ Insertion position แต่ละการปรับเปลี่ยนจะพิจารณาการสลับในสองตำแหน่ง (2-Opt) สามตำแหน่ง (3-Opt) และการสลับสองและสามตำแหน่ง (2-3 Opt) และการกำหนดค่าเริ่มต้นโดยใช้วิธีการ Saving โดยได้แบ่งผลการวิเคราะห์ปัญหาออกเป็น 3 ส่วน ดังนี้ 1. การพิจารณาหาตัวแปรที่เหมาะสมในการตั้งค่าพารามิเตอร์ 2. การพิจารณาที่เกิดจากการเรียนรู้ด้วยตัวเอง แบบวัตถุประสงค์เดียวโดยมีปัญหาเป็นแบบ TSP 3. ผลการพิจารณาข้อมูล TSP จำนวน 9 ชุดข้อมูล โดยมีตัวแบบปัญหาเป็นแบบวัตถุประสงค์เดียว และยังมีการเปรียบเทียบกับวิธีการอื่นๆ 10 วิธีการ
จากการวิจัยพบว่าแบบมีไดเมนชั่น 3มิติ โดยมีการปรับเปลี่ยนแบบการสลับแบบ 2-3 opt และมีการใช้ saving ในการกำหนดค่าประชากรเริ่มต้น เป็นอัลกอริทึมที่ดีที่สุด เกิดจากการปรับค่าพารามิเตอร์ให้มีไดเมนชั่นจากเดิมสองมิติ (2D) ให้เป็นสามมิติ (3D) ในพิกัด (X,Y,Z) จะเพิ่มประสิทธิภาพของ FOA โดยการเพิ่มไดเมนชั่น และมิติที่สูงขึ้น จากผลการทดสอบตัวแบบมาตรฐาน 9 ชุดข้อมูล ของปัญหา TSP โดยอัลกอริทึมที่ได้อันดับที่ 1 มีอยู่ด้วยกัน 2 อัลกอริทึม ได้แก่ 1) FOA3twothree17S ให้ผลลัพธ์ดีที่สุดของค่าที่ได้คำตอบใกล้เคียงค่า optimal solution จำนวน 4 ชุดข้อมูล ดังนี้ Dantzig42, att48, st70 และ Eil76 โดยมีเปอร์เซ็นต์คลาดเคลื่อนจากผลลัพธ์ดีที่สุดเป็น -2.780, 1.655, 3.659 และ 4.617 ตามลำดับ และ 2) FOA2twothree14S จำนวน 1 ชุดข้อมูล ได้แก่ berlin52 โดยมีเปอร์เซ็นต์คลาดเคลื่อนจากผลลัพธ์ดีที่สุดเป็น 3.437 ซึ่งเป็นไปตามวัตุประสงค์ เนื่องด้วยความสามารถในการเปลี่ยนแปลงค่าพารามิเตอร์มีตัวแปรที่สูงกว่าทำให้สามารถปรับตำแหน่งเพื่อเข้าหาค่าคำตอบของการแก้ไขปัญหา TSP ได้ดีกว่าแบบเดิม และทำการปรับเปลี่ยนแบบ 2-Opt, 3-Opt และ 2-3 Opt โดยการนำ Saving เข้ามาช่วยในกระบวนการหาคำตอบนั้น ทำให้คำตอบเข้าใกล้ค่า Optimal solution หรือมีคำตอบใกล้เคียงกับค่าคำตอบที่ดีที่สุด และการนำ Saving เข้ามาช่วยโดยการกำหนดค่าเริ่มต้นจะสามารถช่วยลดระยะเวลาในการหาคำตอบลงได้
Article Details
อนุญาตภายใต้เงื่อนไข Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
เอกสารอ้างอิง
Almufti, S., & Shaban, A. A. (2025). Comparative analysis of metaheuristic algorithms for solving the traveling salesman problems. International Journal of Scientific World, 7(1), 1–5.
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2007). The traveling salesman problem: A computational study. Princeton University Press.
Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1), 61–63.
Crişan, G. C., Pintea, C., & Pop, P. C. (2020). Studying heuristics adaptation to a specific degree of fuzziness. In 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE) (pp. 1–7). IEEE.
Crişan, P., Pintea, S., & Pop, F. (2020). Fruit fly optimization algorithm for traveling salesperson problem. International Journal of Computer Applications, 107(18), 1–6.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. BioSystems, 43(2), 73–81.
Gendreau, M., & Potvin, J. Y. (2010). Handbook of metaheuristics. Springer.
Han, X., Liu, Q., Wang, H., & Wang, L. (2018). Novel fruit fly optimization algorithm with trend search and co-evolution. Knowledge-Based Systems, 141, 1–17.
Holland, J. H. (1992). Adaptation in natural and artificial systems. MIT Press.
Huang, C., Li, X., & Wen, Y. (2021). An OTSU image segmentation based on fruitfly optimization algorithm. Alexandria Engineering Journal, 60(1), 183–188.
Huang, L., Wang, G. C., Bai, T., & Wang, Z. (2017). An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers of Information Technology & Electronic Engineering, 18(10), 1525–1533.
Huang, Y., & Su, T. (2017). Optimizing fruit fly algorithm to solve TSP problem. In 2017 International Conference on Computer Systems, Electronics and Control (ICCSEC) (pp. 1409–1411). IEEE.
Iscan, H., & Gunduz, M. (2017). An application of fruit fly optimization algorithm for traveling salesman problem. Procedia Computer Science, 111, 58–63.
Jiang, Z. B., & Yang, Q. (2016). A discrete fruit fly optimization algorithm for the traveling salesman problem. PLOS ONE, 11(11).
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 – International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE.
Laporte, G. (2010). Fifty years of vehicle routing. Transportation Science, 43(4), 408–416.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Wiley.
Li, H. Z., Guo, S., Li, C. J., & Sun, J. Q. (2013). A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm. Knowledge-Based Systems, 37, 378–387.
Li, X., Zhang, J., & Wang, Y. (2018). A modified fruit fly optimization algorithm for global optimization. Applied Intelligence, 48(7), 1851–1865.
Lin, S. M. (2013). Analysis of service satisfaction in web auction logistics service using a combination of fruit fly optimization algorithm and general regression neural network. Neural Computing and Applications, 22, 783–791.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516.
Liu, Y., Chen, X., & Dib, O. (2023). Application of hybrid metaheuristic algorithms including FOA and PSO to traveling salesman problem. In Intelligent Computing and Optimization Conference (pp. 3–18). Springer.
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61.
Mousavi, S. M., Sadeghi, J., Niaki, S. T. A., Alikar, N., Bahreininejad, A., & Metselaar, H. S. C. (2014). Two parameter-tuned meta-heuristics for a discounted inventory control problem in a fuzzy environment. Information Sciences, 276, 42–62.
Pan, Q. K., Sang, H. Y., Duan, J. H., & Gao, L. (2014). An improved fruit fly optimization algorithm for continuous function optimization problems. Knowledge-Based Systems, 62, 69–83.
Pan, W. T. (2012). A new fruit fly optimization algorithm: Taking the financial distress model as an example. Knowledge-Based Systems, 26, 69–74.
Pasandideh, S. H. R., Niaki, S. T. A., & Mousavi, S. M. (2013). Two metaheuristics to solve a multi-item multiperiod inventory control problem under storage constraint and discounts. The International Journal of Advanced Manufacturing Technology, 69(5), 1671–1684.
Ranjan, R. K., & Kumar, V. (2023). A systematic review on fruit fly optimization algorithm and its applications. Artificial Intelligence Review, 56, 13015–13069.
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384.
Reinelt, G. (1995). TSPLIB95: A library of sample instances for the TSP (and related problems). Universität Heidelberg.
Shan, D., Cao, G., & Dong, H. (2013). LGMS-FOA: An improved fruit fly optimization algorithm for solving optimization problems. Mathematical Problems in Engineering, 2013(1), 108768.
University of Heidelberg. (n.d.). TSPLIB95: Traveling Salesman Problem library. Institut für Informatik, Universität Heidelberg. Retrieved August 23, 2025.
Wang, G., Ma, L., & Chen, J. (2017). A bilevel improved fruit fly optimization algorithm for the nonlinear bilevel programming problem. Knowledge-Based Systems, 138, 113–123.
Wang, X., Li, H., & Yang, J. (2019). An improved fruit fly optimization algorithm for solving combinatorial optimization problems. Expert Systems with Applications, 127, 20–35.
Xu, H., & Chen, Y. (2020). A chaotic fruit fly optimization algorithm for solving the traveling salesman problem. Computers & Industrial Engineering, 142, 106372.
Zhang, L., Wang, S., & Liu, B. (2015). Fruit fly optimization algorithm for feature selection in classification. Knowledge-Based Systems, 89, 275–286.
Zhang, Y., Wang, H., & Li, J. (2023). Adaptive fruit fly optimization algorithm for solving discrete traveling salesman problems. Applied Soft Computing, 137, 110436.
Zheng, X. L., Wang, L., & Wang, S. Y. (2014). A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem. Knowledge-Based Systems, 57, 95–103.
