Cuckoo search and enhanced artificial bee colony heuristic methods for vehicle routing problem with backhaul and time window constraints - Tanawat Worawattawechai (Chulalongkorn University, 2017)
ปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลามีจุดประสงค์เพื่อหาเส้นทางเดินรถที่เป็นไปได้ที่ทำให้ระยะทางในการเดินทางโดยรวมมีค่าน้อยที่สุด โดยมีข้อจำกัดในด้านความจุของรถ รถเที่ยวกลับ และ หน้าต่างเวลา ในดุษฎีนิพนธ์นี้ ได้นำเสนอตัวแบบทางคณิตศาสตร์ของปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลา เพื่อใช้ในการหาผลเฉลยที่เหมาะที่สุด นอกจากนี้ ยังได้นำเสนอวิธีฮิวริสติกผู้แข่งขันที่เร่งด่วนและใกล้ที่สุด (nearest urgent candidate หรือ NUC) ซึ่งใช้เทคนิคในการจัดลำดับความเร่งด่วนและการเลือกผู้แข่งขัน และวิธีฮิวริสติกการเลือกเพื่อนบ้านใกล้ที่สุดด้วยวงล้อรูเล็ตต์ (nearest neighbor with roulette wheel selection หรือ NNRW) ซึ่งเป็นการผสมผสานวิธีการเลือกด้วยวงล้อรูเล็ตต์กับการเลือกเพื่อนบ้านที่ใกล้ที่สุดที่ปรับปรุงแล้ว เพื่อนำมาใช้แก้ปัญหานี้ นอกจากนี้ ยังได้นำเสนอวิธีเมตาฮิวริสติกสองวิธี เพื่อหาผลเฉลยที่เหมาะที่สุดหรือใกล้จะเหมาะที่สุด วิธีแรกคือขั้นตอนวิธีค้นแบบนกกาเหว่า (cuckoo search หรือ CS) ซึ่งได้ถูกนำมาใช้กับปัญหานี้เป็นครั้งแรก วิธีที่สองคือขั้นตอนวิธีอาณาจักรผึ้งเทียมแบบเพิ่มประสิทธิภาพ (enhanced artificial bee colony หรือ EABC) ซึ่งใช้เทคนิครายชื่อต้องห้าม การค้นหาอย่างเป็นลำดับของผึ้งเฝ้ารัง และการผสมผสานของเทคนิคต่าง ๆ ในการค้นคำตอบใกล้เคียง ผลการวิจัยเชิงคำนวณชี้ให้เห็นว่า ขั้นตอนวิธีที่ถูกนำเสนอมาทั้งหมดนั้นมีสมรรถภาพที่ดีในเชิงคุณภาพโดยเฉพาะขั้นตอนวิธีอาณาจักรผึ้งเทียมแบบเพิ่มประสิทธิภาพ ซึ่งได้ 33 ผลเฉลยที่เทียบเท่าหรือผลเฉลยที่ดีที่สุดอันใหม่จาก 45 ปัญหาโดยเปรียบเทียบกับผลเฉลยที่ดีที่สุดที่รวบรวมมาจากงานวิจัยต่างๆ ดังนั้นขั้นตอนวิธีที่นำเสนอข้างต้นจึงเป็นวิธีที่มีประสิทธิภาพในการแก้ปัญหาการจัดเส้นทางเดินรถซึ่งมีข้อจำกัดด้านรถเที่ยวกลับและหน้าต่างเวลา