Chulalongkorn University Theses and Dissertations (Chula ETD)

ฮิวริสติกสำหรับการหาเส้นทางการรับและส่งสินค้าให้ส่งทันภายในระยะเวลารับประกัน

Other Title (Parallel Title in Other Language of ETD)

Heuristic methodology to create pickup and delvery routes with guaranteed time constraint

Year (A.D.)

2006

Document Type

Thesis

First Advisor

วิภาวี ธรรมาภรณ์พิลาศ

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2006.1540

Abstract

งานวิจัยนี้พิจารณาการหาเส้นทางการรับและส่งสินค้าให้ส่งทันภายในระยะเวลารับประกัน โดยพิจารณาจากลักษณะการรับและส่งเวชระเบียนภายในโรงพยาบาล ขอบเขตของงานวิจัยนี้ศึกษาภายใต้ระบบที่มีความแน่นนอน โดยทราบข้อมูลทั้งหมดก่อนที่จะทำการจัดเส้นทางและข้อมูลเหล่านี้ไม่มีการเปลี่ยนแปลง การแก้ไขปัญหาได้พัฒนาเมตาฮิวริสติกเพื่อสร้างเส้นทางการขนส่งเวชระเบียนให้ส่งทันภายในระยะเวลารับประกัน โดยมีจุดประสงค์หลักเพื่อใช้จำนวนรถน้อยที่สุด และจุดประสงค์รองคือระยะเดินทางรวมน้อยที่สุด กระบวนการทำงานขอฮิวริสติกที่นำเสนอประกอบไปด้วย 3 ส่วนด้วยกัน ส่วนที่หนึ่งคือการสร้างเส้นทางเริ่มต้นโดยประยุกต์ใช้ฮิวริสติกการแทรกของโซโลมอน จากนั้นเข้าสู่ส่วนที่สองซึ่งจะทำการปรับปรุงคำตอบโดยใช้หลักการค้นหาคำตอบโดยวิธีตาบูเสริชและปรับปรุงเส้นทางโดยใช้ PD-Shift Operator PD-Exchange Operator และ Rearrange Operator ส่วนที่ 3 คือการสรุปผลสร้างเป็นเส้นทางการขนส่งพร้อมตารางเวลาการขนส่งสินค้า ผลการทดสอบของฮิวริสติกที่นำเสนอโดยเปรียบเทียบคำตอบกับแบบจำลองทางคณิตศาสตร์ พบว่าสำหรับปัญหาทดสอบที่มีจำนวนเวชระเบียนที่ต้องทำการขนส่ง 5 ชิ้น 6 ชิ้น 7 ชิ้น 8 ขิ้น 9 ชิ้น 10 ชิ้น และ 11 ชิ้นนั้น ฮิวริสติกที่นำเสนอสามารถหาค่าที่เหมาะสมที่สุดได้โดยมีเปอร์เซ็นต์ความผิดพลาดเฉลี่ยคิดเป็น 0.000% 0.0000% 0.373% 0.000% 0.533% 0.246% และ 0.000% ผลการทดสอบของฮิวริสติกที่นำเสนอโดยเปรียบเทียบคำตอบกับงานวิจัยปัญหา PDPTW ของ Li and Lim จำนวน 29 ปัญหา พบว่าฮิวริสติกที่นำเสนอสามารถหาคำตอบที่เท่ากันหรือดีกว่าคำตอบที่ดีที่สุดจำนวน 23 ปัญหา ให้คำตอบที่ใช้จำนวนรถเท่ากันแต่ระยะทางรวมยังไม่ดีเท่ากับคำตอบที่ดีที่สุดจำนวน 4 ปัญหา และให้คำตอบที่ต้องใช้รถมากกว่าคำตอบที่ดีที่สุด 1 คัน จำนวน 2 ปัญหา

Other Abstract (Other language abstract of ETD)

The research considers a methodology to create pickup and delivery routes with guaranteed time constraint. The case study of this research is the pickup and delivery patient records problem. All requests are known in advance. We develop a metaheuristic to create pickup and delivery routes with guaranteed time constraint. We consider objective functions prioritizing as follows: 1) to minimize the number of used vehicles and 2) to minimize the total distance. The proposed heuristic has 3 stages. The first stage generates the initial solution by adapting from Solomon’s insertion heuristic. Then tabu search approach including PD-Shift operator, PD-Exchange operator and Rearrange operator are used to improve the solution in the second stage. The final stage concludes completely pickup and delivery routes including schedule time of transportation. The experimental result comparing with the optimal solution from a mathematical model indicates that for 5-patient records, 6-patient records, 7-patient records, 8-patient records, 9-patient records, 10-patient records and 11-patient records test problems, the proposed heuristic yields an average error of only 0.000%, 0.000%, 0.373%, 0.000%, 0.533%, 0.246% and 0.000%. The experimental result comparing with the benchmarking problems of 29 PDPTW problem instances from Li and Lim indicates that there are 23 out of 29 problems that yield the equal or better solutions, 4 out of problems are not better in term of the total travel distance, but they obtain the same number of used vehicles. Others require exactly one more vehicle.

Link to Full Text

Share

COinS