|
ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด |
|---|---|
| รหัสดีโอไอ | |
| Title | ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด |
| Creator | ขวัญแก้ว มีทรัพย์ทวีกูล |
| Contributor | ปวีณา เชาวลิตวงศ์ |
| Publisher | จุฬาลงกรณ์มหาวิทยาลัย |
| Publication Year | 2556 |
| Keyword | ปัญหาการจัดเส้นทางเดินรถ, แบบจำลองทางคณิตศาสตร์, ฮิวริสติกอัลกอริทึม, Vehicle routing problem, Mathematical models, Heuristic algorithms |
| Abstract | “ปัญหาการจัดเส้นทางเดินรถที่มีความจุจำกัดแบบพลวัตโดยมีจุดเริ่มต้นหลายจุด” เป็นปัญหาที่ลูกค้าเข้ามาในระบบแบบพลวัตทำให้ปัญหาจัดเส้นทางเดินรถเปลี่ยนไปตลอดเวลา อีกทั้งการมีระยะเวลารับประกันการขนส่งและจุดเริ่มต้นการขนส่งหลายจุดเป็นตัวเลือกในการจัดเส้นทาง ทำให้ต้องใช้ระยะเวลาที่รวดเร็วในการจัดเส้นทางเดินรถที่ดี งานวิจัยนี้ได้นำเสนอฮิวริสติกที่ประกอบการจัดลูกค้าเข้ากลุ่มเดียวกันและการเลือกจุดเริ่มต้นที่เหมาะสมพร้อมกับการจัดเส้นทางเดินรถไปในเวลาเดียวกัน โดยนำเสนอวิธีการนับจุดตัด (Square grid map) ในการรวมกลุ่มลูกค้าและจุดเริ่มต้นเข้าด้วยกันและทำการจัดเส้นทางเดินรถเบื้องต้นด้วยวิธีการ Sweep และ วิธีการ Reorder สุดท้ายทำการพัฒนาเส้นทางด้วยวิธีการ Insertion โดยผลที่ได้จากฮิวริสติกคือเส้นทางเดินรถและเวลาออกรถเพื่อเริ่มทำการขนส่ง ซึ่งได้ถูกนำมาวัดประสิทธิภาพด้วยการพิจารณาเปอร์เซ็นต์ความแตกต่างของระยะทางรวมโดยเปรียบเทียบกับคำตอบจากแบบจำลองคณิตศาสตร์ของปัญหาขนาดเล็กและทำการเปรียบเทียบคำตอบจากฮิวริสติกที่ปัญหาลักษณะต่างๆที่สร้างขึ้น ซึ่งฮิวริสติกใช้เวลาที่รวดเร็วในการจัดเส้นทางที่ไม่แตกต่างจากเส้นทางที่ดีที่สุดสำหรับปัญหาขนาดเล็ก และให้ผลที่น่าพอใจสำหรับปัญหาขนาดใหญ่ โดยการเลือกเส้นทางที่มีระยะทางที่สั้นที่สุด ณ เวลาใดๆ ให้ผลที่ดีกว่าการเลือกเส้นทางที่มีเวลาออกรถช้าที่สุด ซึ่งจากการวิเคราะห์ผลที่ได้จากการทดสอบฮิวริสติกพบว่า ฮิวริสติกให้คำตอบที่ดีสำหรับปัญหาที่มีความพลวัตสูง รถที่ขนสินค้าไปส่งผู้โดยสารมีความจุจำกัด และตำแหน่งของจุดเริ่มต้นมีจำนวนมากต่อหนึ่งปัญหา ซึ่งฮิวริสติกที่พัฒนาขึ้นมีความเหมาะสมในการแก้ปัญหาพลวัตเมื่อเทียบกับผลการจัดเส้นทางในปัญหาสถิต และวิธีการนับจุดตัดในการจัดกลุ่มลูกค้าเพื่อจัดเส้นทางเดินรถทำให้เกิดเส้นทางที่มีระยะสั้นกว่าการพิจารณาเฉพาะระยะทางกระจัดระหว่างลูกค้าที่ใช้ในการสร้างฮิวริสติกทั่วไป |
| URL Website | cuir.car.chula.ac.th |
