Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การระบุคุณลักษณะที่ต้องการของผลเฉลยสำหรับปัญหาการจัดเส้นทางขนส่งแบบมีกรอบเวลาโดยใช้การเรียนรู้ของเครื่อง
Year (A.D.)
2024
Document Type
Thesis
First Advisor
Boonyarit Intiyot
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2024.921
Abstract
A vehicle routing problem with time windows (VRPTW) has been studied widely in the literature. Most effective methods to find a solution are still heuristics, which are constructed from the inventor’s ideas of how a good solution should be obtained, and their efficiency is quantified only by empirical data. However, these ideas may or may not yield a near-optimal solution. It would be better if we can identify some characteristics of a solution to VRPTW to help guide the heuristic in the right direction. Arnold and Sörensen had proposed a statistical learning model to determine a characteristic of a near-optimal solution for a vehicle routing problem (VRP). They used that knowledge to create a guided heuristic for a local search and the results were impressive. Therefore, we wish to extend this work to VRPTW by defining new solution metrics that involve time windows constraints and using a statistical tool to obtain characteristic(s) of a good solution to VRPTW. By applying a machine learning model, we examined 14,000 VRPTW instances to identify the key characteristics that differentiate high-quality solutions. Our experiment revealed that the average width per route is the most distinguishing characteristic, which also holds true for the standard VRP according to Arnold and Sorensen's findings. Moreover, the runner-up characteristics are the average compactness per route, measured by width, and the average total travel time and service time per route. These insights contribute to a deeper understanding of the VRPTW solution structures and offer a meaningful direction for the development of more effective heuristics.
Other Abstract (Other language abstract of ETD)
ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาได้รับการศึกษาอย่างแพร่หลาย วิธีการที่มีประสิทธิภาพมากที่สุดในการค้นหาผลเฉลยยังคงเป็นวิธีการในกลุ่มของฮิวริสติก ซึ่งสร้างขึ้นจากแนวคิดของผู้คิดค้นฮิวริสติกนั้น ๆ เองว่าผลเฉลยที่ดีควรจะหามาอย่างไร และประสิทธิภาพของฮิวริสติกจะถูกวัดจากข้อมูลจากการทดลองเท่านั้น อย่างไรก็ตามแนวคิดเหล่านี้อาจให้หรือไม่ให้ผลลัพธ์ที่ใกล้เคียงผลเฉลยที่เหมาะที่สุดก็ได้ มันจะดีกว่า หากเราสามารถระบุลักษณะเฉพาะบางประการของผลเฉลยสำหรับปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา ที่ช่วยชี้นำฮิวริสติกไปในทิศทางที่ถูกต้อง อาร์โนลด์และโซเรนเซนได้เสนอตัวแบบการเรียนรู้ทางสถิติ เพื่อหาลักษณะเฉพาะของผลเฉลยที่ใกล้เคียงผลเฉลยที่เหมาะที่สุดสำหรับปัญหาการจัดเส้นทางการขนส่ง พวกเขาใช้ความรู้ดังกล่าวในการสร้างฮิวริสติกที่มีการชี้นำสำหรับการค้นหาเฉพาะที่ และได้ผลลัพธ์ที่น่าประทับใจ ดังนั้นเราจึงต้องการขยายงานนี้ไปสู่ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา โดยการกำหนดเมทริกซ์ผลเฉลยใหม่ที่เกี่ยวข้องกับข้อจำกัดของกรอบเวลา และการใช้เครื่องมือทางสถิติเพื่อหาลักษณะเฉพาะของผลเฉลยที่ดีของปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา จากการประยุกต์ใช้โมเดลการเรียนรู้ของเครื่อง เราได้ตรวจสอบชุดข้อมูลปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา 14,000 ชุด เพื่อค้นหาลักษณะเฉพาะที่สำคัญที่สามารถแยกแยะผลเฉลยที่มีคุณภาพสูงออกมา การทดลองของเราแสดงให้เห็นว่า ความกว้างโดยเฉลี่ยต่อเส้นทางเป็นลักษณะเฉพาะที่โดดเด่นที่สุด ซึ่งเป็นลักษณะเฉพาะที่เด่นที่สุดสำหรับปัญหาการจัดเส้นทางการขนส่งมาตรฐานตามการค้นพบของอาร์โนลด์และโซเรนเซนเช่นกัน นอกจากนี้ลักษณะเฉพาะที่เด่นรองลงมาคือความกะทัดรัดเฉลี่ยต่อเส้นทางโดยวัดจากความกว้าง และเวลาเฉลี่ยในการเดินทางและเวลาการให้บริการโดยรวมต่อเส้นทาง ข้อมูลเชิงลึกดังกล่าวทำให้มีความเข้าใจที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับโครงสร้างของผลเฉลยของปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลา และสามารถใช้เป็นแนวทางที่มีความหมายในการพัฒนาฮิวริสติกที่มีประสิทธิภาพยิ่งขึ้น
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Chaochanglek, Teerapong, "Specifying the desired attributes of solutions to vehicle routing problems with time windows using machine learning" (2024). Chulalongkorn University Theses and Dissertations (Chula ETD). 74759.
https://digital.car.chula.ac.th/chulaetd/74759