ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด

Abstract

“ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด” เป็นปัญหาที่ลูกค้าเข้ามาในระบบแบบพลวัตทำให้ปัญหาจัดเส้นทางเดินรถเปลี่ยนไปตลอดเวลา อีกทั้งการมีระยะเวลารับประกันการขนส่งและจุดเริ่มต้นการขนส่งหลายจุดเป็นตัวเลือกในการจัดเส้นทาง ทำให้ต้องใช้ระยะเวลาที่รวดเร็วในการจัดเส้นทางเดินรถที่ดี งานวิจัยนี้ได้นำเสนอฮิวริสติกที่ประกอบการจัดลูกค้าเข้ากลุ่มเดียวกันและการเลือกจุดเริ่มต้นที่เหมาะสมพร้อมกับการจัดเส้นทางเดินรถไปในเวลาเดียวกัน โดยนำเสนอวิธีการนับจุดตัด (Square grid map) ในการรวมกลุ่มลูกค้าและจุดเริ่มต้นเข้าด้วยกันและทำการจัดเส้นทางเดินรถเบื้องต้นด้วยวิธีการ Sweep และ วิธีการ Reorder สุดท้ายทำการพัฒนาเส้นทางด้วยวิธีการ Insertion โดยผลที่ได้จากฮิวริสติกคือเส้นทางเดินรถและเวลาออกรถเพื่อเริ่มทำการขนส่ง ซึ่งได้ถูกนำมาวัดประสิทธิภาพด้วยการพิจารณาเปอร์เซ็นต์ความแตกต่างของระยะทางรวมโดยเปรียบเทียบกับคำตอบจากแบบจำลองคณิตศาสตร์ของปัญหาขนาดเล็กและทำการเปรียบเทียบคำตอบจากฮิวริสติกที่ปัญหาลักษณะต่างๆที่สร้างขึ้น ซึ่งฮิวริสติกใช้เวลาที่รวดเร็วในการจัดเส้นทางที่ไม่แตกต่างจากเส้นทางที่ดีที่สุดสำหรับปัญหาขนาดเล็ก และให้ผลที่น่าพอใจสำหรับปัญหาขนาดใหญ่ โดยการเลือกเส้นทางที่มีระยะทางที่สั้นที่สุด ณ เวลาใดๆ ให้ผลที่ดีกว่าการเลือกเส้นทางที่มีเวลาออกรถช้าที่สุด ซึ่งจากการวิเคราะห์ผลที่ได้จากการทดสอบฮิวริสติกพบว่า ฮิวริสติกให้คำตอบที่ดีสำหรับปัญหาที่มีความพลวัตสูง รถที่ขนสินค้าไปส่งผู้โดยสารมีความจุจำกัด และตำแหน่งของจุดเริ่มต้นมีจำนวนมากต่อหนึ่งปัญหา ซึ่งฮิวริสติกที่พัฒนาขึ้นมีความเหมาะสมในการแก้ปัญหาพลวัตเมื่อเทียบกับผลการจัดเส้นทางในปัญหาสถิต และวิธีการนับจุดตัดในการจัดกลุ่มลูกค้าเพื่อจัดเส้นทางเดินรถทำให้เกิดเส้นทางที่มีระยะสั้นกว่าการพิจารณาเฉพาะระยะทางกระจัดระหว่างลูกค้าที่ใช้ในการสร้างฮิวริสติกทั่วไป