แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา
The problem of excessive empty haul is a major problem in transportation planning. One of the solutions is to combine trips together to form a multi drop distribution. However, multi drop distribution planning is complicated and has to be efficiently managed. The objective of the vehicle routing wit...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | Theses and Dissertations |
| اللغة: | Thai |
| منشور في: |
จุฬาลงกรณ์มหาวิทยาลัย
2008
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://digiverse.chula.ac.th/Info/item/dc:44348 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| المؤسسة: | Chulalongkorn University |
| اللغة: | Thai |
| id |
44348 |
|---|---|
| record_format |
dspace |
| spelling |
443482024-03-18T09:16:25Z https://digiverse.chula.ac.th/Info/item/dc:44348 ©จุฬาลงกรณ์มหาวิทยาลัย Thesis 10.58837/CHULA.THE.2008.1344 tha กิตติโชติ ตันติภนา แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา Model and large scale neighbourhood search algorithms for vehicle routing problem with time-windows จุฬาลงกรณ์มหาวิทยาลัย 2008 2008 The problem of excessive empty haul is a major problem in transportation planning. One of the solutions is to combine trips together to form a multi drop distribution. However, multi drop distribution planning is complicated and has to be efficiently managed. The objective of the vehicle routing with time windows (VRPTW) is to determine a set of feasible routings for goods delivery to a set of customers within prescribed time windows while minimizing cost. The routes must also satisfy time windows, truck capacity, and other operational constraints. We present a column generation based exact algorithm and an improvement heuristics for the problem based on an extension of Large-scale Neighborhood Search (LNS) and probability theory. The proposed algorithm can find near-optimal solutions within reasonable amount of computation time. The analysis of the model results indicate that the model can reduce the percentages of empty haul distance by approximately 68 percent to 72 percent comparing the truckload operation without empty haul management. Moreover, using the algorithm can reduce transportation cost by approximately 42 percent. ปัญหาการเดินรถเที่ยวเปล่าจัดเป็นปัญหาที่สำคัญในการวางแผนขนส่ง ระยะการเดินรถเที่ยวเปล่านี้สามารถลดลงได้ด้วยการควบรวมการขนส่งเข้าด้วยกัน เพื่อให้เกิดการเดินรถขนส่งสินค้าแบบกระจายสินค้าหลายจุด (Multi Drop Distribution) อย่างไรก็ดีการวางแผนการขนส่งสินค้าแบบกระจายสินค้าหลายจุดนั้นจะต้องมีการวางแผนการจัดส่งสินค้าที่ดี กล่าวคือ มีวิธีในการแก้ปัญหาการจัดเส้นทางการเดินรถ (vehicle Routing Problem) ที่มีประสิทธิภาพ การจัดเส้นทางการเดินรถชนิดมีกรอบเวลา คือการหาเส้นทางการเดินรถในการขนส่งสินค้าไปยังกลุ่มลูกค้าทั้งหมดที่มีค่าใช้จ่ายต่ำที่สุดโดยลูกค้าแต่ละรายมีกรอบเวลาในการรับสินค้าที่ชัดเจน เส้นทางเดินรถขนส่งสินค้าจะต้องคำนึงถึงข้อจำกัดด้านกรอบเวลาและความจุของยานพาหนะ ยิ่งไปกว่านั้นความยากของการจัดเส้นทางการเดินรถอีกประการหนึ่งคือมีข้อจำกัดจำนวนมากที่เกิดขึ้นเนื่องจากสภาพการทำงานจริง ดังนั้นงานวิจัยนี้มีจุดประสงค์เพื่อพัฒนาการขนส่งสินค้าและสร้างโปรแกรมคอมพิวเตอร์ โดยนำเสนอวิธีกำเนิดสดมภ์ที่เป็นวิธีการหาผลเฉลยที่ดีที่สุดและวิธีการค้นหาเฉพาะแห่งขนาดใหญ่เชิงความน่าจะเป็นวิธีฮิวริสติคที่มีประสิทธิภาพในการแก้ปัญหาการจัดเส้นทางการเดินรถ สามารถหาผลเฉลยที่ดีได้ในระยะเวลาการประมวลที่เหมาะสม พิจารณาผลลัพธ์ที่ได้จากแบบจำลองพบว่า สามารถลดระยะทางการเดินรถเที่ยวเปล่าได้ประมาณร้อยละ 68 ถึง 72 ยิ่งไปกว่านั้นยังสามารถลดค่าใช้จ่ายลงได้ประมาณร้อยละ 42 เปรียบเทียบกับการขนส่งที่ไม่มีการจัดการการเดินเที่ยวเปล่า 139 pages ปัญหาการจัดเส้นทางเดินรถ การกระจายสินค้าจากผู้ผลิตสู่ผู้บริโภค การขนส่งสินค้า -- แบบจำลองทางคณิตศาสตร์ แบบจำลองทางคณิตศาสตร์ Vehicle routing problem Physical distribution of goods Commercial products -- Transportation -- Mathematical models Mathematical models มาโนช โลหเตปานนท์ https://digiverse.chula.ac.th/digital/file_upload/biblio/cover/44348.jpg |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| continent |
Asia |
| country |
Thailand Thailand |
| content_provider |
Chulalongkorn University Library |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
Thai |
| topic |
ปัญหาการจัดเส้นทางเดินรถ การกระจายสินค้าจากผู้ผลิตสู่ผู้บริโภค การขนส่งสินค้า -- แบบจำลองทางคณิตศาสตร์ แบบจำลองทางคณิตศาสตร์ Vehicle routing problem Physical distribution of goods Commercial products -- Transportation -- Mathematical models Mathematical models |
| spellingShingle |
ปัญหาการจัดเส้นทางเดินรถ การกระจายสินค้าจากผู้ผลิตสู่ผู้บริโภค การขนส่งสินค้า -- แบบจำลองทางคณิตศาสตร์ แบบจำลองทางคณิตศาสตร์ Vehicle routing problem Physical distribution of goods Commercial products -- Transportation -- Mathematical models Mathematical models กิตติโชติ ตันติภนา แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| description |
The problem of excessive empty haul is a major problem in transportation planning. One of the solutions is to combine trips together to form a multi drop distribution. However, multi drop distribution planning is complicated and has to be efficiently managed. The objective of the vehicle routing with time windows (VRPTW) is to determine a set of feasible routings for goods delivery to a set of customers within prescribed time windows while minimizing cost. The routes must also satisfy time windows, truck capacity, and other operational constraints. We present a column generation based exact algorithm and an improvement heuristics for the problem based on an extension of Large-scale Neighborhood Search (LNS) and probability theory. The proposed algorithm can find near-optimal solutions within reasonable amount of computation time. The analysis of the model results indicate that the model can reduce the percentages of empty haul distance by approximately 68 percent to 72 percent comparing the truckload operation without empty haul management. Moreover, using the algorithm can reduce transportation cost by approximately 42 percent. |
| author2 |
มาโนช โลหเตปานนท์ |
| author_facet |
มาโนช โลหเตปานนท์ กิตติโชติ ตันติภนา |
| format |
Theses and Dissertations |
| author |
กิตติโชติ ตันติภนา |
| author_sort |
กิตติโชติ ตันติภนา |
| title |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| title_short |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| title_full |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| title_fullStr |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| title_full_unstemmed |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| title_sort |
แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา |
| publisher |
จุฬาลงกรณ์มหาวิทยาลัย |
| publishDate |
2008 |
| url |
https://digiverse.chula.ac.th/Info/item/dc:44348 |
| _version_ |
1829266693934809088 |