Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
วิธีฮิวริสติกค้นแบบนกกาเหว่าและอาณาจักรผึ้งเทียมแบบเพิ่มประสิทธิภาพสำหรับปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลา
Year (A.D.)
2017
Document Type
Thesis
First Advisor
Boonyarit Intiyot
Second Advisor
Chawalit Jeenanunta
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2017.11
Abstract
The vehicle routing problem with backhauls and time windows (VRPBTW) aims to find a feasible vehicle route that minimizes the total traveling distance while imposing capacity, backhaul, and time-window constraints. In this dissertation, a mathematical model of VRPBTW is introduced to obtain an optimal solution. The heuristics, namely the nearest urgent candidate (NUC), which applies the urgency priority and candidate techniques, and the nearest neighbor with roulette wheel selection (NNRW) which is a combination of a roulette wheel selection method and the improved nearest neighbor heuristic, are also presented to solve this problem. Moreover, two metaheuristic methods are presented to obtain the optimal or near optimal solutions. The first is a cuckoo search (CS) algorithm, which is applied to this problem for the first time. The second is the enhanced artificial bee colony (EABC) algorithm which uses a forbidden list, the sequential search for onlookers, and the combination of neighborhood search techniques. The computational results indicate that proposed algorithms yield good performance in terms of solution quality, especially EABC. It obtained 33 ties or new best known solutions out of 45 instances comparing with the best known solutions found in the literature. Hence, the proposed algorithms are the effective ways to solve the VRPBTW.
Other Abstract (Other language abstract of ETD)
ปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลามีจุดประสงค์เพื่อหาเส้นทางเดินรถที่เป็นไปได้ที่ทำให้ระยะทางในการเดินทางโดยรวมมีค่าน้อยที่สุด โดยมีข้อจำกัดในด้านความจุของรถ รถเที่ยวกลับ และ หน้าต่างเวลา ในดุษฎีนิพนธ์นี้ ได้นำเสนอตัวแบบทางคณิตศาสตร์ของปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลา เพื่อใช้ในการหาผลเฉลยที่เหมาะที่สุด นอกจากนี้ ยังได้นำเสนอวิธีฮิวริสติกผู้แข่งขันที่เร่งด่วนและใกล้ที่สุด (nearest urgent candidate หรือ NUC) ซึ่งใช้เทคนิคในการจัดลำดับความเร่งด่วนและการเลือกผู้แข่งขัน และวิธีฮิวริสติกการเลือกเพื่อนบ้านใกล้ที่สุดด้วยวงล้อรูเล็ตต์ (nearest neighbor with roulette wheel selection หรือ NNRW) ซึ่งเป็นการผสมผสานวิธีการเลือกด้วยวงล้อรูเล็ตต์กับการเลือกเพื่อนบ้านที่ใกล้ที่สุดที่ปรับปรุงแล้ว เพื่อนำมาใช้แก้ปัญหานี้ นอกจากนี้ ยังได้นำเสนอวิธีเมตาฮิวริสติกสองวิธี เพื่อหาผลเฉลยที่เหมาะที่สุดหรือใกล้จะเหมาะที่สุด วิธีแรกคือขั้นตอนวิธีค้นแบบนกกาเหว่า (cuckoo search หรือ CS) ซึ่งได้ถูกนำมาใช้กับปัญหานี้เป็นครั้งแรก วิธีที่สองคือขั้นตอนวิธีอาณาจักรผึ้งเทียมแบบเพิ่มประสิทธิภาพ (enhanced artificial bee colony หรือ EABC) ซึ่งใช้เทคนิครายชื่อต้องห้าม การค้นหาอย่างเป็นลำดับของผึ้งเฝ้ารัง และการผสมผสานของเทคนิคต่าง ๆ ในการค้นคำตอบใกล้เคียง ผลการวิจัยเชิงคำนวณชี้ให้เห็นว่า ขั้นตอนวิธีที่ถูกนำเสนอมาทั้งหมดนั้นมีสมรรถภาพที่ดีในเชิงคุณภาพโดยเฉพาะขั้นตอนวิธีอาณาจักรผึ้งเทียมแบบเพิ่มประสิทธิภาพ ซึ่งได้ 33 ผลเฉลยที่เทียบเท่าหรือผลเฉลยที่ดีที่สุดอันใหม่จาก 45 ปัญหาโดยเปรียบเทียบกับผลเฉลยที่ดีที่สุดที่รวบรวมมาจากงานวิจัยต่างๆ ดังนั้นขั้นตอนวิธีที่นำเสนอข้างต้นจึงเป็นวิธีที่มีประสิทธิภาพในการแก้ปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลา
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Worawattawechai, Tanawat, "Cuckoo search and enhanced artificial bee colony heuristic methods for vehicle routing problem with backhaul and time window constraints" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 501.
https://digital.car.chula.ac.th/chulaetd/501