Chulalongkorn University Theses and Dissertations (Chula ETD)

ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด

Other Title (Parallel Title in Other Language of ETD)

CAPACITATED DYNAMIC VEHICLE ROUTING PROBLEM WITH MULTIPLE DEPOTS

Year (A.D.)

2013

Document Type

Thesis

First Advisor

ปวีณา เชาวลิตวงศ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมอุตสาหการ

DOI

10.58837/CHULA.THE.2013.1349

Abstract

“ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด" เป็นปัญหาที่ลูกค้าเข้ามาในระบบแบบพลวัตทำให้ปัญหาจัดเส้นทางเดินรถเปลี่ยนไปตลอดเวลา อีกทั้งการมีระยะเวลารับประกันการขนส่งและจุดเริ่มต้นการขนส่งหลายจุดเป็นตัวเลือกในการจัดเส้นทาง ทำให้ต้องใช้ระยะเวลาที่รวดเร็วในการจัดเส้นทางเดินรถที่ดี งานวิจัยนี้ได้นำเสนอฮิวริสติกที่ประกอบการจัดลูกค้าเข้ากลุ่มเดียวกันและการเลือกจุดเริ่มต้นที่เหมาะสมพร้อมกับการจัดเส้นทางเดินรถไปในเวลาเดียวกัน โดยนำเสนอวิธีการนับจุดตัด (Square grid map) ในการรวมกลุ่มลูกค้าและจุดเริ่มต้นเข้าด้วยกันและทำการจัดเส้นทางเดินรถเบื้องต้นด้วยวิธีการ Sweep และ วิธีการ Reorder สุดท้ายทำการพัฒนาเส้นทางด้วยวิธีการ Insertion โดยผลที่ได้จากฮิวริสติกคือเส้นทางเดินรถและเวลาออกรถเพื่อเริ่มทำการขนส่ง ซึ่งได้ถูกนำมาวัดประสิทธิภาพด้วยการพิจารณาเปอร์เซ็นต์ความแตกต่างของระยะทางรวมโดยเปรียบเทียบกับคำตอบจากแบบจำลองคณิตศาสตร์ของปัญหาขนาดเล็กและทำการเปรียบเทียบคำตอบจากฮิวริสติกที่ปัญหาลักษณะต่างๆที่สร้างขึ้น ซึ่งฮิวริสติกใช้เวลาที่รวดเร็วในการจัดเส้นทางที่ไม่แตกต่างจากเส้นทางที่ดีที่สุดสำหรับปัญหาขนาดเล็ก และให้ผลที่น่าพอใจสำหรับปัญหาขนาดใหญ่ โดยการเลือกเส้นทางที่มีระยะทางที่สั้นที่สุด ณ เวลาใดๆ ให้ผลที่ดีกว่าการเลือกเส้นทางที่มีเวลาออกรถช้าที่สุด ซึ่งจากการวิเคราะห์ผลที่ได้จากการทดสอบฮิวริสติกพบว่า ฮิวริสติกให้คำตอบที่ดีสำหรับปัญหาที่มีความพลวัตสูง รถที่ขนสินค้าไปส่งผู้โดยสารมีความจุจำกัด และตำแหน่งของจุดเริ่มต้นมีจำนวนมากต่อหนึ่งปัญหา ซึ่งฮิวริสติกที่พัฒนาขึ้นมีความเหมาะสมในการแก้ปัญหาพลวัตเมื่อเทียบกับผลการจัดเส้นทางในปัญหาสถิต และวิธีการนับจุดตัดในการจัดกลุ่มลูกค้าเพื่อจัดเส้นทางเดินรถทำให้เกิดเส้นทางที่มีระยะสั้นกว่าการพิจารณาเฉพาะระยะทางกระจัดระหว่างลูกค้าที่ใช้ในการสร้างฮิวริสติกทั่วไป

Other Abstract (Other language abstract of ETD)

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.

Link to Full Text

Share

COinS