Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Solving multi-point traversal problem for pickup and delivery with distance limitation using genetic algorithm
Year (A.D.)
2023
Document Type
Thesis
First Advisor
ธีรพล ศิลาวรรณ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Electrical Engineering (ภาควิชาวิศวกรรมไฟฟ้า)
Degree Name
วิศวกรรมศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมไฟฟ้า
DOI
10.58837/CHULA.THE.2023.316
Abstract
ปัจจุบันธุรกิจการขนส่งอาหารและพัสดุมีการเติบโตสูงขึ้นอย่างมาก ต้นทุนในธุรกิจนี้แปรผันตามปัจจัยต่าง ๆ หนึ่งในนั้นคือปัจจัยด้านระยะทาง ซึ่งจะส่งผลต่อต้นทุนเชื้อเพลิงที่ใช้ในการขนส่ง การพัฒนาระบบการจัดการเส้นทางที่มีประสิทธิภาพจะช่วยเลือกเส้นทางที่ใช้ต้นทุนในการขนส่งอย่างเหมาะสม และช่วยเพิ่มความพร้อมในการตอบสนองความต้องการของผู้บริโภคได้อย่างมีประสิทธิภาพ งานวิจัยนี้ต้องการเพิ่มประสิทธิภาพให้กับเส้นทางของผู้ขนส่งโดยการเพิ่มจำนวนผู้ใช้บริการที่ผู้ขนส่งสามารถให้บริการได้ในการเดินทางแต่ละครั้ง รวมถึงให้อิสระในการกำหนดระยะทางที่ต้องการเดินทางในแต่ละครั้งตามความสะดวกของผู้ขนส่งด้วย ดังนั้นเส้นทางที่มีประสิทธิภาพสูงสุดจึงหมายถึงเส้นทางที่สามารถให้บริการผู้รับส่งสินค้าเป็นจำนวนมากที่สุดภายใต้เงื่อนไขระยะทางสูงสุดที่ถูกกำหนดโดยผู้ขนส่ง การค้นหาเส้นทางที่สอดคล้องกับวัตถุประสงค์ดังกล่าวเป็นปัญหามีความซับซ้อนทางเวลาสูง ดังนั้นจึงต้องเลือกใช้ขั้นตอนวิธีที่เหมาะสมในการแก้ปัญหา ซึ่งงานวิจัยนี้เล็งเห็นว่าขั้นตอนวิธีเชิงพันธุกรรมที่ประยุกต์ขั้นตอนวิธีแบบฮิวริสติกอื่น ๆ ในการหาคำตอบร่วมกันสามารถลดระยะเวลาในการหาคำตอบของปัญหานี้ได้ โดยคำตอบนั้นมีคุณภาพสูงใกล้เคียงกับขั้นตอนวิธีแบบเอาแต่แรงเมื่อจำนวนจุดให้บริการไม่เกิน 7 คู่ เพื่อให้ครอบคลุมตามจุดประสงค์ของผู้ใช้งานทั้งด้านคุณภาพและระยะเวลาในการหาคำตอบ ขั้นตอนวิธีเชิงพันธุกรรมที่งานวิจัยนี้นำเสนอมีรูปแบบที่แตกต่างกัน 2 รูปแบบ โดยทั้ง 2 จะมีจุดเด่นที่แตกต่างกันคือ รูปแบบที่มีจุดเด่นด้านคุณภาพของคำตอบ และรูปแบบที่มีจุดเด่นด้านระยะเวลาการหาคำตอบ
Other Abstract (Other language abstract of ETD)
Delivery service is popular nowadays. Costs in this business vary according to various factors including distance. It affects the fuel cost for delivery. Developing efficient route management can optimize delivery costs and increase readiness to serve customers. This research aims to increase the efficiency of the route by increasing the number of customers on a route. Including the freedom to determine the distance of the route according to the convenience of the messenger. Therefore, the most efficient route is defined as the route that can serve the greatest number of sender-receiver pairs of customers according to the distance set by the messenger. Finding a path corresponding to the objectives is a problem with high time complexity. This research found that the genetic algorithm with applying other heuristic algorithms can reduce the time to find the answer to this problem. The quality of the answer is approximate to the answer from the brute force algorithm when the number of service points is less or equal to 7 pairs. This research presents 2 types of genetic algorithms, one has an advantage in terms of the quality of the answers and the other has an advantage in terms of the computational time to find answers.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
เพ็งสุวรรณ์, พีรายุ, "การแก้ปัญหาการแวะผ่านหลายจุดสำหรับการรับส่งที่มีการจำกัดด้านระยะทางด้วยขั้นตอนวิธีเชิงพันธุกรรม" (2023). Chulalongkorn University Theses and Dissertations (Chula ETD). 10264.
https://digital.car.chula.ac.th/chulaetd/10264