Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/77162
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorManoj Lohatepanont-
dc.contributor.advisorShin-ei Takano-
dc.contributor.authorPerawit Charoenwut-
dc.contributor.otherChulalongkorn University. Faculty of Engineering-
dc.date.accessioned2021-09-22T23:32:21Z-
dc.date.available2021-09-22T23:32:21Z-
dc.date.issued2020-
dc.identifier.urihttp://cuir.car.chula.ac.th/handle/123456789/77162-
dc.descriptionThesis (M.Eng.)--Chulalongkorn University, 2020-
dc.description.abstractNowadays, 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.-
dc.description.abstractalternativeการขนส่งสินค้าปัจจุบันนี้มีความต้องการเพิ่มขึ้นเป็นอย่างมากเนื่องจากการมาของระบบการซื้อขายผ่านอินเตอร์เน็ตทำให้หลายบริษัทได้พัฒนาการขนส่งรูปแบบต่าง ๆ เพื่อตอบสนองตลาดและลดต้นทุน หนึ่งในนั้นคือการใช้โดรนไร้ผู้บังคับร่วมกับยานพาหนะอื่นเช่นรถบรรทุก โดยโดรนสามารถออกจากทั้งคลังสินค้าหรือจากรถบรรทุกเพื่อไปส่งสินค้าแล้วกลับมาที่ฐานพัก เพื่อรอรถบรรทุกมารับกลับหรือบินกลับคลังสินค้าเอง ปัญหาการจัดเส้นทางของยานพาหนะร่วมกับโดรน (Vehicle Routing Problem with Drone) ที่ศึกษาเป็นปัญหาการจัดเส้นทางการส่งสินค้าของรถบรรทุกและโดรนไปพร้อม ๆ กัน ซึ่งเป็นปัญหาที่มีความซับซ้อนมากจึงไม่สามารถใช้วิธีการแก้ปัญหาแบบทั่วไปได้ งานวิจัยนี้ได้พัฒนาเทคนิคการผ่อนปรนปัญหาแบบลากรานจ์ (Lagrangian Relaxation) เพื่อนำมาใช้ควบคู่กับเทคนิค Branch-and-Price ในการคำนวนขอบเขตล่างของคำตอบในแต่ละขั้นของ Branch-and-Price ซึ่งขอบเขตล่างของลากรานจ์นั้นจะมีค่าใกล้คำตอบมากกว่าคำตอบจาก Column Generation ในขั้นนั้น ส่งผลให้เวลาที่ใช้ในการหาคำตอบลดลงจากการนำมาใช้เป็นเงื่อนไขในการหยุด Branch-and-Price ช่วยให้ไม่สำรวจ Node ที่ไม่จำเป็น ในการทดลองนั้นจะดำเนินการโดยใช้ตัวอย่างที่สร้างขึ้นมาแบบสุ่มและตัวอย่างจากแผนที่จริง นอกจากนี้ได้เปรียบเทียบต้นทุนของการใช้เพียงรถบรรทุกและการใช้รถบรรทุกร่วมกับโดรนเพื่อให้เห็นถึงประโยชน์ของการใช้โดรนได้ชัดเจนยิ่งขึ้น-
dc.language.isoen-
dc.publisherChulalongkorn University-
dc.relation.urihttp://doi.org/10.58837/CHULA.THE.2020.112-
dc.rightsChulalongkorn University-
dc.subjectDrone aircraft-
dc.subjectShipment of goods-
dc.subjectอากาศยานไร้นักบิน-
dc.subjectการขนส่งสินค้า-
dc.subject.classificationMathematics-
dc.subject.classificationEngineering-
dc.titleLagrangian relaxation method for integrated vehicles and drones routing model-
dc.title.alternativeวิธีการผ่อนปรนปัญหาแบบลากรานจ์สำหรับแบบจำลองการจัดเส้นทางยานพาหนะร่วมกับโดรน-
dc.typeThesis-
dc.degree.nameMaster of Engineering-
dc.degree.levelMaster's Degree-
dc.degree.disciplineCivil Engineering-
dc.degree.grantorChulalongkorn University-
dc.identifier.DOI10.58837/CHULA.THE.2020.112-
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
6170231921.pdf3.05 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.