Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/9186
| Title: | การกำหนดเส้นทางเดินรถแบบพลวัต |
| Other Titles: | Dynamic scheduling for vehicle routing problems |
| Authors: | กฤศณภัทร สวาสดิ์ |
| Advisors: | ปวีณา เชาวลิตวงศ์ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | paveena.c@chula.ac.th |
| Subjects: | การบริหารงานโลจิสติกส์ บริการจัดส่งสินค้า |
| Issue Date: | 2549 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | งานวิจัยนี้พิจารณาปัญหาการกำหนดเส้นทางเดินรถแบบพลวัต ที่มีข้อจำกัดด้านระยะเวลารับประกัน และความจุของรถขนส่ง โดยปัญหาในงานวิจัยนี้จะแตกต่างจากปัญหาการจัดเส้นทางเดินรถแบบดั้งเดิม เนื่องจากเป็นปัญหาในการกำหนดทั้งเวลาออกรถและเส้นทางในการจัดส่งสินค้าที่เหมาะสม โดยที่ข้อมูลของจุดรับสินค้าจะทยอยทราบหลังจากเริ่มขั้นตอนในการหาคำตอบ ทำให้ต้องมีการวางแผนจัดเส้นทางมากกว่าหนึ่งครั้ง ดังนั้นจึงจำเป็นต้องนำเอาการกำหนดเส้นทางเดินรถแบบพลวัตมาใช้เพื่อตอบสนองกับข้อมูลที่ทยอยเข้ามาในระบบ ฮิวริสติกที่นำเสนอจะทำงานในรูปแบบของการวนซ้ำหาคำตอบในสามขั้นตอน คือ กระบวนการจัดเตรียมข้อมูลกระบวนการจัดเส้นทาง และกระบวนการกำหนดเวลาออกรถ โดยในกระบวนการจัดเตรียมข้อมูลจะทำหน้าที่จัดเตรียมข้อมูลสำหรับอีกสองกระบวนการในขั้นถัดไป ในขั้นตอนถัดมาคือกระบวนการจัดเส้นทางจะทำหน้าที่สร้างเส้นทางที่เหมาะสมโดยใช้ insertion heuristic และ GRASP โดยในการสร้างเส้นทางนั้นมีสองแนวทางคือ แนวทางแรกพิจารณาจัดเส้นทางครั้งละหนึ่งเส้นทาง และแนวทางที่สองพิจารณาจัดเส้นทางครั้งละมากกว่าหนึ่งเส้นทาง และขั้นตอนสุดท้ายคือกระบวนการกำหนดเวลาออกรถจะทำหน้าที่กำหนดเวลาออกรถที่เหมาะสม การทดสอบความสามารถของฮิวริสติกที่นำเสนอ จะทดสอบกับปัญหาที่ดัดแปลงจากปัญหาของ Solomon ซึ่งผลจากการทดสอบพบว่าคำตอบที่ได้จากฮิวริสติกมีความแตกต่างจากขอบเขตล่างโดยเฉลี่ย 7.23% 11.54% และ 17.89% สำหรับปัญหาขนาด 25 จุดรับ 50 จุดรับ และ 100 จุดรับ ตามลำดับ |
| Other Abstract: | This research considers dynamic scheduling in a vehicle routing problem (VRP) with guaranteed service time and capacitated vehicle. Unlike the classic VRP, VRP with dynamic scheduling determines both dispatching time and an appropriate routing for each vehicle. When the information of all customer demand cannot be known at the same time, planning on vehicle routing must be done more than once. Therefore dynamic scheduling is needed in order to cope with continued information. The proposed heuristic works in three-step iterative manner: data preparation step, route establishing step, and vehicle dispatching step. The data preparation step arranges essential information to the next two steps. In route establishing step, an appropriate route is determined under insertion heuristic and GRASPS heuristic. Routes are established under two concepts: one route establishing at a time and more than one route establishing at a time. Finally, the dispatching time is determined in the third step. Solomon test problems are used in the computational experiment for heuristic testing. The results show that the heuristic yields 7.23%, 11.54% and 17.89% average gap from the lower bound for 25-cumtomer node, 50-customer node, and 100-customer node consecutively. |
| Description: | วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2549 |
| Degree Name: | วิศวกรรมศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิศวกรรมอุตสาหการ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/9186 |
| URI: | http://doi.org/10.14457/CU.the.2006.79 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2006.79 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Kritnapat.pdf | 1.96 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.