Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/43057
Title: ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด
Other Titles: CAPACITATED DYNAMIC VEHICLE ROUTING PROBLEM WITH MULTIPLE DEPOTS
Authors: ขวัญแก้ว มีทรัพย์ทวีกูล
Advisors: ปวีณา เชาวลิตวงศ์
Other author: จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email: paveena.c@chula.ac.th
Subjects: ปัญหาการจัดเส้นทางเดินรถ
แบบจำลองทางคณิตศาสตร์
ฮิวริสติกอัลกอริทึม
Vehicle routing problem
Mathematical models
Heuristic algorithms
Issue Date: 2556
Publisher: จุฬาลงกรณ์มหาวิทยาลัย
Abstract: “ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด” เป็นปัญหาที่ลูกค้าเข้ามาในระบบแบบพลวัตทำให้ปัญหาจัดเส้นทางเดินรถเปลี่ยนไปตลอดเวลา อีกทั้งการมีระยะเวลารับประกันการขนส่งและจุดเริ่มต้นการขนส่งหลายจุดเป็นตัวเลือกในการจัดเส้นทาง ทำให้ต้องใช้ระยะเวลาที่รวดเร็วในการจัดเส้นทางเดินรถที่ดี งานวิจัยนี้ได้นำเสนอฮิวริสติกที่ประกอบการจัดลูกค้าเข้ากลุ่มเดียวกันและการเลือกจุดเริ่มต้นที่เหมาะสมพร้อมกับการจัดเส้นทางเดินรถไปในเวลาเดียวกัน โดยนำเสนอวิธีการนับจุดตัด (Square grid map) ในการรวมกลุ่มลูกค้าและจุดเริ่มต้นเข้าด้วยกันและทำการจัดเส้นทางเดินรถเบื้องต้นด้วยวิธีการ Sweep และ วิธีการ Reorder สุดท้ายทำการพัฒนาเส้นทางด้วยวิธีการ Insertion โดยผลที่ได้จากฮิวริสติกคือเส้นทางเดินรถและเวลาออกรถเพื่อเริ่มทำการขนส่ง ซึ่งได้ถูกนำมาวัดประสิทธิภาพด้วยการพิจารณาเปอร์เซ็นต์ความแตกต่างของระยะทางรวมโดยเปรียบเทียบกับคำตอบจากแบบจำลองคณิตศาสตร์ของปัญหาขนาดเล็กและทำการเปรียบเทียบคำตอบจากฮิวริสติกที่ปัญหาลักษณะต่างๆที่สร้างขึ้น ซึ่งฮิวริสติกใช้เวลาที่รวดเร็วในการจัดเส้นทางที่ไม่แตกต่างจากเส้นทางที่ดีที่สุดสำหรับปัญหาขนาดเล็ก และให้ผลที่น่าพอใจสำหรับปัญหาขนาดใหญ่ โดยการเลือกเส้นทางที่มีระยะทางที่สั้นที่สุด ณ เวลาใดๆ ให้ผลที่ดีกว่าการเลือกเส้นทางที่มีเวลาออกรถช้าที่สุด ซึ่งจากการวิเคราะห์ผลที่ได้จากการทดสอบฮิวริสติกพบว่า ฮิวริสติกให้คำตอบที่ดีสำหรับปัญหาที่มีความพลวัตสูง รถที่ขนสินค้าไปส่งผู้โดยสารมีความจุจำกัด และตำแหน่งของจุดเริ่มต้นมีจำนวนมากต่อหนึ่งปัญหา ซึ่งฮิวริสติกที่พัฒนาขึ้นมีความเหมาะสมในการแก้ปัญหาพลวัตเมื่อเทียบกับผลการจัดเส้นทางในปัญหาสถิต และวิธีการนับจุดตัดในการจัดกลุ่มลูกค้าเพื่อจัดเส้นทางเดินรถทำให้เกิดเส้นทางที่มีระยะสั้นกว่าการพิจารณาเฉพาะระยะทางกระจัดระหว่างลูกค้าที่ใช้ในการสร้างฮิวริสติกทั่วไป
Other Abstract: Capacitated 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.
Description: วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2556
Degree Name: วิศวกรรมศาสตรมหาบัณฑิต
Degree Level: ปริญญาโท
Degree Discipline: วิศวกรรมอุตสาหการ
URI: http://cuir.car.chula.ac.th/handle/123456789/43057
URI: http://doi.org/10.14457/CU.the.2013.524
metadata.dc.identifier.DOI: 10.14457/CU.the.2013.524
Type: Thesis
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.