Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
วิธีการผ่อนปรนปัญหาแบบลากรานจ์สำหรับแบบจำลองการจัดเส้นทางยานพาหนะร่วมกับโดรน
Year (A.D.)
2020
Document Type
Thesis
First Advisor
Manoj Lohatepanont
Second Advisor
Shin-ei Takano
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Civil Engineering (ภาควิชาวิศวกรรมโยธา)
Degree Name
Master of Engineering
Degree Level
Master's Degree
Degree Discipline
Civil Engineering
DOI
10.58837/CHULA.THE.2020.112
Abstract
Nowadays, e-commerce increases parcel transportation demand year by year. Many companies are seeking the way to improve performance of delivery service and cost-efficiency. One among many solutions is using a drone attached with a truck for the last mile delivery. A drone can be launched from either depot or truck and returned to the depot or wait for the truck to take them back from the docking station around the delivery area. The vehicle routing problem with drones considers truck- and drone-route simultaneously. It is an enormous problem that cannot be solved by a normal linear programming method. This research proposes the Lagrangian relaxation technique, in conjunction with the Branch-and-Price technique, to estimate the lower bound of the solution in each iteration of the Branch-and-Price. The lower bound from the Lagrangian relaxation is tighter than the solution from the Column generation which can improve the total solution time. The bound use in Branch-and-Price as a fathom condition, these help the search tree not to explore unnecessary nodes. The computational experiment includes randomly generated instances and real-world instances. Moreover, the operation cost of truck-based and truck-drone-based are compared to point out the benefit of using drones.
Other Abstract (Other language abstract of ETD)
การขนส่งสินค้าปัจจุบันนี้มีความต้องการเพิ่มขึ้นเป็นอย่างมากเนื่องจากการมาของระบบการซื้อขายผ่านอินเตอร์เน็ตทำให้หลายบริษัทได้พัฒนาการขนส่งรูปแบบต่าง ๆ เพื่อตอบสนองตลาดและลดต้นทุน หนึ่งในนั้นคือการใช้โดรนไร้ผู้บังคับร่วมกับยานพาหนะอื่นเช่นรถบรรทุก โดยโดรนสามารถออกจากทั้งคลังสินค้าหรือจากรถบรรทุกเพื่อไปส่งสินค้าแล้วกลับมาที่ฐานพัก เพื่อรอรถบรรทุกมารับกลับหรือบินกลับคลังสินค้าเอง ปัญหาการจัดเส้นทางของยานพาหนะร่วมกับโดรน (Vehicle Routing Problem with Drone) ที่ศึกษาเป็นปัญหาการจัดเส้นทางการส่งสินค้าของรถบรรทุกและโดรนไปพร้อม ๆ กัน ซึ่งเป็นปัญหาที่มีความซับซ้อนมากจึงไม่สามารถใช้วิธีการแก้ปัญหาแบบทั่วไปได้ งานวิจัยนี้ได้พัฒนาเทคนิคการผ่อนปรนปัญหาแบบลากรานจ์ (Lagrangian Relaxation) เพื่อนำมาใช้ควบคู่กับเทคนิค Branch-and-Price ในการคำนวนขอบเขตล่างของคำตอบในแต่ละขั้นของ Branch-and-Price ซึ่งขอบเขตล่างของลากรานจ์นั้นจะมีค่าใกล้คำตอบมากกว่าคำตอบจาก Column Generation ในขั้นนั้น ส่งผลให้เวลาที่ใช้ในการหาคำตอบลดลงจากการนำมาใช้เป็นเงื่อนไขในการหยุด Branch-and-Price ช่วยให้ไม่สำรวจ Node ที่ไม่จำเป็น ในการทดลองนั้นจะดำเนินการโดยใช้ตัวอย่างที่สร้างขึ้นมาแบบสุ่มและตัวอย่างจากแผนที่จริง นอกจากนี้ได้เปรียบเทียบต้นทุนของการใช้เพียงรถบรรทุกและการใช้รถบรรทุกร่วมกับโดรนเพื่อให้เห็นถึงประโยชน์ของการใช้โดรนได้ชัดเจนยิ่งขึ้น
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Charoenwut, Perawit, "Lagrangian relaxation method for integrated vehicles and drones routing model" (2020). Chulalongkorn University Theses and Dissertations (Chula ETD). 164.
https://digital.car.chula.ac.th/chulaetd/164