Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/43057
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorปวีณา เชาวลิตวงศ์en_US
dc.contributor.authorขวัญแก้ว มีทรัพย์ทวีกูลen_US
dc.contributor.otherจุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์en_US
dc.date.accessioned2015-06-24T06:23:44Z
dc.date.available2015-06-24T06:23:44Z
dc.date.issued2556en_US
dc.identifier.urihttp://cuir.car.chula.ac.th/handle/123456789/43057
dc.descriptionวิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2556en_US
dc.description.abstract“ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด” เป็นปัญหาที่ลูกค้าเข้ามาในระบบแบบพลวัตทำให้ปัญหาจัดเส้นทางเดินรถเปลี่ยนไปตลอดเวลา อีกทั้งการมีระยะเวลารับประกันการขนส่งและจุดเริ่มต้นการขนส่งหลายจุดเป็นตัวเลือกในการจัดเส้นทาง ทำให้ต้องใช้ระยะเวลาที่รวดเร็วในการจัดเส้นทางเดินรถที่ดี งานวิจัยนี้ได้นำเสนอฮิวริสติกที่ประกอบการจัดลูกค้าเข้ากลุ่มเดียวกันและการเลือกจุดเริ่มต้นที่เหมาะสมพร้อมกับการจัดเส้นทางเดินรถไปในเวลาเดียวกัน โดยนำเสนอวิธีการนับจุดตัด (Square grid map) ในการรวมกลุ่มลูกค้าและจุดเริ่มต้นเข้าด้วยกันและทำการจัดเส้นทางเดินรถเบื้องต้นด้วยวิธีการ Sweep และ วิธีการ Reorder สุดท้ายทำการพัฒนาเส้นทางด้วยวิธีการ Insertion โดยผลที่ได้จากฮิวริสติกคือเส้นทางเดินรถและเวลาออกรถเพื่อเริ่มทำการขนส่ง ซึ่งได้ถูกนำมาวัดประสิทธิภาพด้วยการพิจารณาเปอร์เซ็นต์ความแตกต่างของระยะทางรวมโดยเปรียบเทียบกับคำตอบจากแบบจำลองคณิตศาสตร์ของปัญหาขนาดเล็กและทำการเปรียบเทียบคำตอบจากฮิวริสติกที่ปัญหาลักษณะต่างๆที่สร้างขึ้น ซึ่งฮิวริสติกใช้เวลาที่รวดเร็วในการจัดเส้นทางที่ไม่แตกต่างจากเส้นทางที่ดีที่สุดสำหรับปัญหาขนาดเล็ก และให้ผลที่น่าพอใจสำหรับปัญหาขนาดใหญ่ โดยการเลือกเส้นทางที่มีระยะทางที่สั้นที่สุด ณ เวลาใดๆ ให้ผลที่ดีกว่าการเลือกเส้นทางที่มีเวลาออกรถช้าที่สุด ซึ่งจากการวิเคราะห์ผลที่ได้จากการทดสอบฮิวริสติกพบว่า ฮิวริสติกให้คำตอบที่ดีสำหรับปัญหาที่มีความพลวัตสูง รถที่ขนสินค้าไปส่งผู้โดยสารมีความจุจำกัด และตำแหน่งของจุดเริ่มต้นมีจำนวนมากต่อหนึ่งปัญหา ซึ่งฮิวริสติกที่พัฒนาขึ้นมีความเหมาะสมในการแก้ปัญหาพลวัตเมื่อเทียบกับผลการจัดเส้นทางในปัญหาสถิต และวิธีการนับจุดตัดในการจัดกลุ่มลูกค้าเพื่อจัดเส้นทางเดินรถทำให้เกิดเส้นทางที่มีระยะสั้นกว่าการพิจารณาเฉพาะระยะทางกระจัดระหว่างลูกค้าที่ใช้ในการสร้างฮิวริสติกทั่วไปen_US
dc.description.abstractalternativeCapacitated Dynamic Vehicle Routing Problem with Multiple Depots is the problem that demands from customer enter dynamically to the system in several of time. The objective is to generate routes for dispatching orders by minimizing distances. The feasible route should transport demands within the guarantee time and the total demand for each route cannot be over the vehicle capacity. Thus, there are two decisions to be considered: a proper depot and a proper group of customer nodes. This research developed the heuristic which counts square grids map under all feasible Manhattan distance to cluster customers to the same group, then applies sweep and reorder method to generate the initial feasible routing. To finish the routing process, insertion procedure has been applied to improve routing and all routes will be processed to determine dispatching time. Efficiency of developed heuristics is determined by testing with standard problems and generated problems. Heuristics performed well on small problems comparing with the optimal solution from CPLEX by consuming short time. For large problems, heuristic provided good routes in a very short of time. Choosing a shortest routing instead of a maximum dispatching time routing always provide a better routes if testing with generated problem. The overall results shown that the developed heuristics appropriate to solve a high dynamic of customers, capacitated vehicles and multiple depots problems and provide better solutions if the problems are dynamic comparing with static problems. Lastly, the results from testing the counting grids heuristic are better than results from heuristic using general Euclidian distance as criteria for clustering customers in every problem.en_US
dc.language.isothen_US
dc.publisherจุฬาลงกรณ์มหาวิทยาลัยen_US
dc.relation.urihttp://doi.org/10.14457/CU.the.2013.524-
dc.rightsจุฬาลงกรณ์มหาวิทยาลัยen_US
dc.subjectปัญหาการจัดเส้นทางเดินรถ
dc.subjectแบบจำลองทางคณิตศาสตร์
dc.subjectฮิวริสติกอัลกอริทึม
dc.subjectVehicle routing problem
dc.subjectMathematical models
dc.subjectHeuristic algorithms
dc.titleปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุดen_US
dc.title.alternativeCAPACITATED DYNAMIC VEHICLE ROUTING PROBLEM WITH MULTIPLE DEPOTSen_US
dc.typeThesisen_US
dc.degree.nameวิศวกรรมศาสตรมหาบัณฑิตen_US
dc.degree.levelปริญญาโทen_US
dc.degree.disciplineวิศวกรรมอุตสาหการen_US
dc.degree.grantorจุฬาลงกรณ์มหาวิทยาลัยen_US
dc.email.advisorpaveena.c@chula.ac.then_US
dc.identifier.DOI10.14457/CU.the.2013.524-
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
5570537021.pdf2.65 MBAdobe PDFView/Open


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