การปรับปรุงอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดโดยอัลกอริทึมทางพันธุกรรมสำหรับปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุ

Abstract

ปัญหาการกำหนดเส้นทางยานพาหนะที่มีความจุ (CVRP) คือปัญหาการขนส่งสินค้าจากโรงงานผลิตสินค้าไปยังลูกค้าแต่ละสถานที่ โดยรับบริการขนส่งสินค้าคนละ 1 ครั้งเท่านั้น และมีระยะทางและค่าขนส่งที่แตกต่างกัน ต้องการให้ค่าใช้จ่ายในการขนส่งน้อยที่สุด และสามารถส่งสินค้าถึงลูกค้าทุกคน โดยส่วนมากใช้อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด (NN) แก้ปัญหา CVRP เนื่องจากอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดนั้นสามารถใช้งานได้ง่ายและดำเนินการได้อย่างรวดเร็ว แต่คำตอบจากอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดนั้นค่อนข้างแย่ เพราะ อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดจะเลือกเส้นทางที่สั้นที่สุดในบริเวณข้างเคียง โดยไม่พิจารณาผลรวมของระยะทางในการเดินทางทั้งหมด เพื่อปรับปรุงคำตอบที่ได้จากการค้นหา งานวิจัยฉบับนี้ขอเสนออัลกอริทึมทางพันธุกรรม (GA) ที่ใช้กับอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด ปรับปรุงคำตอบ อัลกอริทึมที่เสนอนี้เรียกว่าการปรับปรุงอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดโดยใช้อัลกอริทึมทางพันธุกรรมสำหรับปัญหาการกำหนดเส้นทางรถที่มีความจุหรือ NNGA อัลกอริทึมที่เสนอได้รับการทดสอบใน 5 กรณีทดสอบที่เราสร้างขึ้นจาก Google Map ผลจากการทดลองแสดงให้เห็นว่าระยะทางของอัลกอริทึมที่เสนอสามารถลดลง 6.66% เมื่อเปรียบเทียบกับระยะทางของอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด