Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
ปัญหาการจัดเส้นทางยานพาหนะที่มีข้อจำกัดด้านเวลาจากจุดเริ่มต้นหลายจุดไปยังจุดหมายต่าง ๆ ซึ่งเลือกสรรได้โดยการใช้อัลกอริธึมทางพันธุกรรม
Year (A.D.)
2025
Document Type
Thesis
First Advisor
Chaodit Aswakul
Second Advisor
Chawit Sakulyuenyong
Third Advisor
Prachya Rungtweesuk
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Electrical Engineering (ภาควิชาวิศวกรรมไฟฟ้า)
Degree Name
Master of Engineering
Degree Level
Master's Degree
Degree Discipline
Electrical Engineering
DOI
10.58837/CHULA.THE.2025.169
Abstract
This thesis addresses the vehicle routing problem with time constraints from multiple origins to selective destinations by using a genetic algorithm for efficient path planning. The focus is on optimizing field collection and repossession activities in the financial industry to enhance operational efficiency and customer satisfaction. The proposed approach integrates two main components: a tailored genetic algorithm for multi-objective optimization and a graph neural network for precise travel time estimation. The genetic algorithm is designed to minimize total travel distance or travel time and balance the workload among field collectors, while the graph neural network provides travel time estimates to evaluate the practical applicability of the routing solutions. Extensive experiments have been conducted to evaluate the performance of the proposed method, with comparisons to dynamic programming and Google OR-tools. The results indicate that the genetic algorithm offers competitive solutions, with a linear increase in computational time relative to problem complexity, demonstrating its scalability for real-world applications. The graph neural network model significantly outperforms baseline methods in hourly travel time estimation, achieving superior results evaluated by root mean square error, mean absolute error, root mean squared percentage error, and mean absolute percentage error. The integration allows the genetic algorithm to manage the trade-off between travel distance and travel time efficiently, resulting in accurate and practically usable path planning. From the experiments, the genetic algorithm proves more efficient than Google OR-tools in terms of computational time and scalability when dealing with more than 300 customers, although its performance in terms of solution quality is 13.7 percents on average lower than single-objective GA and 22.4 percents on average lower than that of Google OR-tools. Given that the travel time estimation is calculated as a daily overview and does not include the hourly traffic conditions during the day, using estimated travel time has a 5.43% better effect on the overall path planning, compared to using travel distance, which can be directly obtained from map data. This result is useful in practice because it indicates that travel distance can be used to replace daily estimated travel time, which incurs high computational costs. The routing results remain similar in performance for applications where the solution must be calculated and routes assigned once per day in the morning. However, if there is a routing application that requires answers to change hourly during the day, the performance of the graph neural network model is expected to be useful in combination with genetic algorithms. This represents a future area of research.
Other Abstract (Other language abstract of ETD)
งานวิจัยนี้กล่าวถึงปัญหาการจัดเส้นทางยานพาหนะที่มีข้อจำกัดด้านเวลา โดยมีจุดเริ่มต้นหลายจุดและจุดหมายปลายทางที่เลือกสรรได้ โดยใช้อัลกอริธึมทางพันธุกรรมเพื่อให้ได้วิธีการจัดเส้นทางที่มีประสิทธิภาพ จุดเน้นของการวิจัยนี้คือการเพิ่มประสิทธิภาพในการเก็บหนี้และยึดทรัพย์ ในอุตสาหกรรมการเงินเพื่อเพิ่มประสิทธิภาพการดำเนินงานและความพึงพอใจของลูกค้า วิธีการที่เสนอประกอบด้วยสองส่วนหลัก: อัลกอริธึมทางพันธุกรรมที่ปรับแต่งเพื่อการหาค่าเหมาะที่สุดแบบวัตถุประสงค์หลายด้าน และ เครือข่ายหน่วยประสาทแบบกราฟเพื่อประเมินเวลาการเดินทางอย่างแม่นยำ อัลกอริธึมทางพันธุกรรมถูกออกแบบมาเพื่อลดระยะทางหรือระยะเวลาการเดินทางทั้งหมดและแบ่งภาระงานให้สมดุลระหว่างผู้เก็บภาคสนาม ในขณะที่เครือข่ายหน่วยประสาทแบบกราฟทำการประเมินเวลาการเดินทางเพื่อประเมินการใช้งานในทางปฏิบัติของผลลัพธ์จากการจัดเส้นทาง จากการทดลองที่ถูกดำเนินการเพื่อประเมินประสิทธิภาพของวิธีการที่นำเสนอ โดยเปรียบเทียบกับวิธีการกำหนดการพลวัต และ กูเกิ้ลโออาร์ทู ผลลัพธ์พบว่าอัลกอริธึมทางพันธุกรรมมีการเสนอวิธีการที่มีประสิทธิภาพ โดยมีการเพิ่มขึ้นของเวลาการคำนวณแบบเชิงเส้นสัมพันธ์กับความซับซ้อนของปัญหา ซึ่งแสดงให้เห็นถึงความสามารถในภาวะปรับค่าได้สำหรับการใช้งานในสถานการณ์จริง แบบจำลองเครือข่ายหน่วยประสาทแบบกราฟมีประสิทธิภาพสูงกว่าวิธีการแบบเส้นฐานในการประเมินเวลาการเดินทาง โดยได้ผลลัพธ์ที่เหนือกว่าโดยวัดจาก ค่ารากกำลังสองเฉลี่ยผิดพลาด ค่าผิดพลาดเฉลี่ยสมบูรณ์ ค่าเปอร์เซ็นรากกำลังสองเฉลี่ยผิดพลาด และค่าเปอร์เซ็นผิดพลาดเฉลี่ยสมบูรณ์ การผสมผสานนี้ทำให้อัลกอริธึมทางพันธุกรรมสามารถจัดการผลได้เสียจากการแลกเปลี่ยนระหว่างระยะทางและเวลาในการเดินทางได้อย่างมีประสิทธิภาพ ส่งผลให้ได้วิธีการจัดเส้นทางที่มีความแม่นยำและสามารถใช้งานได้จริง จากการวิจัยอัลกอริธึมทางพันธุกรรมที่นำเสนอมีประสิทธิภาพสูงกว่ากูเกิ้ลโออาร์ทูในด้านของระยะเวลาในการคำนวนที่เร็วกว่าและภาวะปรับค่าได้ที่สูงกว่า ในกรณีที่จำนวนลูกค้ามีมากกว่า 300 คนขึ้นไป แต่อัลกอริธึมทางพันธุกรรมที่มีหลายวัตถุประสงค์มีประสิทธิภาพในด้านคุณภาพของคำตอบต่ำกว่าอัลกอริธึมทางพันธุกรรมที่มีวัตถุประสงค์เดียว ร้อยละ 13.7 และต่ำกว่ากูเกิ้ลโออาร์ทู ร้อยละ 22.4 เนื่องจากการประมาณระยะเวลาในการเดินทางนั้นคำนวนภาพรวมเฉลี่ยในแต่ละวันโดยไม่ได้คำนวนสภาพการจราจรรายชั่วโมงระหว่างวัน การใช้ข้อมูลระยะเวลาการเดินทางประเมินจึงมีผลกระทบต่อภาพรวมการจัดลำดับเส้นทางการเดินทางโดยรวมดีกว่าร้อยละ 5.43 เมื่อเทียบกับการใช้ข้อมูลระยะทางที่สามารถนำมาใช้งานได้โดยตรงจากข้อมูลแผนที่ ผลลัพธ์นี้จึงเป็นประโยชน์ในทางปฏิบัติเพราะสามารถนำข้อมูลระยะทางมาใช้ทดแทนข้อมูลระยะเวลาเดินทางเฉลี่ยรายวันที่ใช้ต้นทุนในการคำนวนสูงกว่า โดยผลลัพธ์จากการจัดเส้นทางที่ได้ยังคงมีประสิทธิภาพใกล้เคียงกันสำหรับการประยุกต์ในปัญหานี้ซึ่งต้องคำนวนคำตอบและมอบหมายเส้นทางวันละหนึ่งครั้งในช่วงเช้า อย่างไรก็ตามหากมีการประยุกต์การจัดเส้นทางซึ่งต้องการคำตอบที่สามารถเปลี่ยนแปลงได้รายชั่วโมงในระหว่างวัน ประสิทธิภาพของแบบจำลองเครือข่ายหน่วยประสาทแบบกราฟคาดหวังว่าจะสามารถนำมาใช้ประกอบร่วมกับอัลกอริธึมทางพันธุกรรมซึ่งเป็นงานวิจัยต่อไปได้ในอนาคต
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Kruetet, Manocha, "Vehicle routing problem with time constraint from multiple origins to selective destinations by using genetic algorithm" (2025). Chulalongkorn University Theses and Dissertations (Chula ETD). 75078.
https://digital.car.chula.ac.th/chulaetd/75078