การประยุกต์ตัวแบบปัญหาการเดินทางของเซลล์แมน กรณีศึกษาการจัดเส้นทางรถรางนำเที่ยวของเทศบาลนครเชียงราย

Abstract

งานวิจัยนี้เป็นการศึกษาปัญหาการหาเส้นทางที่สั้นที่สุด โดยการประยุกต์ใช้ตัวแบบปัญหา การเดินทางของเซลล์แมน โดยมีรถรางนำเที่ยวของเทศบาลนครเชียงราย เป็นกรณีศึกษา โดยข้อมูล ระยะทางและเส้นทางทั้งหมดหามาจาก Google Earth และการออกสำรวจ ซึ่งในขั้นตอนแรกจะเป็น การนำเอาตัวแบบปัญหาวิถีสั้นสุด เข้ามาหาระยะทางระหว่างจุดท่องเที่ยวแต่ละแห่ง โดยใช้โปรแกรม เชิงเส้นหาคำตอบ จากนั้นนำเอาตัวแบบปัญหาการเดินทางของเซลล์แมนเข้ามาหาเส้นทางที่สั้นที่สุด สำหรับรถรางนำเที่ยว โดยจะใช้โปรแกรมเชิงเส้น มาหาคำตอบของตัวแบบ และทำการนำเอาการจัด เส้นทางโดยใช้ค่าประมาณเข้ามาหาคำตอบอีก โดยใช้วิธีการเปรียบเทียบการประหยัด เพื่อเป็นการ เปรียบเทียบวิธีการที่เหมาะสม

ผลการศึกษาวิจัย พบว่าวิธีการที่ใช้โปรแกรมเชิงเส้น ได้คำตอบของระยะทางรวมที่ 5,510 เมตร ส่วนการใช้วิธีการเปรียบเทียบการประหยัด ได้คำตอบของระยะทางรวมที่ 5,850 เมตร ซึ่งวิธีการใช้โปรแกรมเชิงเส้น ในการหาคำตอบ สามารถให้คำตอบที่ดีกว่า ซึ่งจะมีระยะทางรวมที่สั้น กว่า 550 เมตร หรือคิดเป็นร้อยละ 9.075 และเมื่อเปรียบเทียบระยะทางรวมของเส้นทางเดิม ที่รถรางใช้วิ่งในปัจจุบันคือ 6,060 เมตร ซึ่งจะได้คำตอบของเส้นทางที่สั้นกว่าเส้นทางเดิมโดยที่ผ่าน จุดท่องเที่ยวครบทุกจุดเหมือนเดิม

An Application of the Travelling Salesman Problem Case Study: Routing for Streetcar Tour of the Chiang Rai

The research aims to find the shortest route for an electric car tour in Chiangrai through an application of the travelling salesman problem (TSP). Data on the distances and directions were obtained from Google Earth and from surveying. The shortest path problem was initially used to find the distance between tourist locations by means of linear programming. The traveling salesman problem was then used to find the shortest route for an electric car tour. Linear programming was used to create a model and the routes were mapped and compared with those from the savings algorithm.

The result showed that linear programming produced the shortest distance of 5,510 meters while the savings algorithm arrived at a distance of 5,850 meters. This is a difference of 550 meters, or 9.075%, and so the use of linear programming resulted in a shorter route. The current route of the electric car tour runs to a total of 6,060 meters, so the findings show that a shorter route that runs through all the tourist locations is possible.