การแก้ปัญหาการแวะผ่านหลายจุดสำหรับการรับส่งที่มีการจำกัดด้านระยะทางด้วยขั้นตอนวิธีเชิงพันธุกรรม

Abstract

ปัจจุบันธุรกิจการขนส่งอาหารและพัสดุมีการเติบโตสูงขึ้นอย่างมาก ต้นทุนในธุรกิจนี้แปรผันตามปัจจัยต่าง ๆ หนึ่งในนั้นคือปัจจัยด้านระยะทาง ซึ่งจะส่งผลต่อต้นทุนเชื้อเพลิงที่ใช้ในการขนส่ง การพัฒนาระบบการจัดการเส้นทางที่มีประสิทธิภาพจะช่วยเลือกเส้นทางที่ใช้ต้นทุนในการขนส่งอย่างเหมาะสม และช่วยเพิ่มความพร้อมในการตอบสนองความต้องการของผู้บริโภคได้อย่างมีประสิทธิภาพ

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

เพื่อให้ครอบคลุมตามจุดประสงค์ของผู้ใช้งานทั้งด้านคุณภาพและระยะเวลาในการหาคำตอบ ขั้นตอนวิธีเชิงพันธุกรรมที่งานวิจัยนี้นำเสนอมีรูปแบบที่แตกต่างกัน 2 รูปแบบ โดยทั้ง 2 จะมีจุดเด่นที่แตกต่างกันคือ รูปแบบที่มีจุดเด่นด้านคุณภาพของคำตอบ และรูปแบบที่มีจุดเด่นด้านระยะเวลาการหาคำตอบ