การวิเคราะห์เส้นทางรถโดยสารประจำทางในจังหวัดพระนครศรีอยุธยาด้วยขั้นตอนวิธีของไดก์สตรา

Abstract

ขั้นตอนวิธีของไดก์สตราถูกคิดค้นขึ้นเพื่อหาวิถีสั้นที่สุดจากจุดยอดหนึ่งไปจุดยอดใด ๆ ในกราฟถ่วงน้ำหนัก  งานวิจัยนี้มีวัตถุประสงค์เพื่อศึกษาเส้นทางของรถโดยสารประจำทางที่เดินทางระหว่างอำเภอในจังหวัดพระนครศรีอยุธยา เพื่อเป็นข้อมูลสำหรับการเดินทางที่ต้องการพิจารณาระยะเวลาที่ใช้และค่าใช้จ่ายในการเดินทาง โดยพิจารณาปัญหาในรูปกราฟถ่วงน้ำหนัก จุดในกราฟแทนจุดรับ–ส่งหลักในแต่ละอำเภอ ซึ่งจังหวัดพระนครศรีอยุธยามีทั้งหมด 16 อำเภอ โดยบางอำเภอมีจุดรับ–ส่งหลักมากกว่าหนึ่งจุด จะได้กราฟที่มีทั้งหมด 22 จุด โดยเส้นในกราฟแทนเส้นทางของรถโดยสารประจำทางที่เดินทางระหว่างอำเภอ และเมื่อนำกราฟที่ได้มาพิจารณาในรูปกราฟถ่วงน้ำหนักสองกราฟ คือ กราฟแรกน้ำหนักคือเวลาที่ใช้ในการเดินทางของแต่ละเส้นทาง ซึ่งนำมาจากแผนที่ของกูเกิล (Google map) และกราฟที่สองน้ำหนักคือค่าโดยสารของแต่ละเส้นทางซึ่งได้จากการสอบถามข้อมูลจากพนักงานขับรถและผู้โดยสาร จากนั้นสร้างกราฟทั้งสองให้เป็นกราฟเชิงเดี่ยว โดยเส้นทางที่มีทางเลือกในการเดินทางมากกว่าหนึ่งเส้นทางจะพิจารณาเลือกเส้นทางที่มีน้ำหนักน้อยที่สุดเพียงเส้นทางเดียว และประยุกต์ใช้ขั้นตอนวิธีของไดก์สตรากับกราฟทั้งสอง ผลลัพธ์ของกราฟแรกจะได้เส้นทางที่ใช้เวลาในการเดินทางน้อยที่สุดจากอำเภอพระนครศรีอยุธยาไปยังทุกจุดรับ–ส่งหลักของอำเภออื่น และผลลัพธ์ของกราฟที่สองจะได้เส้นทางที่มีค่าโดยสารที่น้อยที่สุดในการเดินทางจากอำเภอพระนครศรีอยุธยาไปยังทุกจุดรับ–ส่งหลักของอำเภออื่น