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

บทคัดย่อ

การขนส่งสินค้าปัจจุบันนี้มีความต้องการเพิ่มขึ้นเป็นอย่างมากเนื่องจากการมาของระบบการซื้อขายผ่านอินเตอร์เน็ตทำให้หลายบริษัทได้พัฒนาการขนส่งรูปแบบต่าง ๆ เพื่อตอบสนองตลาดและลดต้นทุน หนึ่งในนั้นคือการใช้โดรนไร้ผู้บังคับร่วมกับยานพาหนะอื่นเช่นรถบรรทุก โดยโดรนสามารถออกจากทั้งคลังสินค้าหรือจากรถบรรทุกเพื่อไปส่งสินค้าแล้วกลับมาที่ฐานพัก เพื่อรอรถบรรทุกมารับกลับหรือบินกลับคลังสินค้าเอง ปัญหาการจัดเส้นทางของยานพาหนะร่วมกับโดรน (Vehicle Routing Problem with Drone) ที่ศึกษาเป็นปัญหาการจัดเส้นทางการส่งสินค้าของรถบรรทุกและโดรนไปพร้อม ๆ กัน ซึ่งเป็นปัญหาที่มีขนาดใหญ่มากจึงไม่สามารถใช้วิธีการแก้ปัญหาแบบทั่วไปได้ งานวิจัยนี้ได้พัฒนาเทคนิคการผ่อนปรนปัญหาแบบลากรานจ์ (Lagrangian Relaxation) เพื่อนำมาใช้ควบคู่กับเทคนิค Brach-and-Price ในการคำนวนขอบเขตล่างของคำตอบในแต่ละขั้นของ Branch-and-Price ซึ่งขอบเขตล่างของลากรานจ์นั้นจะมีค่าใกล้คำตอบมากกว่าคำตอบจาก Column Generation ในขั้นนั้น ส่งผลให้เวลาที่ใช้ในการหาคำตอบลดลง