Genetically Modified Genetic Algorithm for Capacitated Vehicle Routing Problem

Abstract

Genetic algorithm (GA) is one of artificial intelligence that has its roots in Charles Darwin’s theory. The GA process of finding solutions is parallel searched, which the solutions obtained through the search in one generation will lead to the transmission of the fit characteristics of the solutions discovered in the current generation to the next. Therefore, selecting populations with the fit characteristics is important to optimal solution of GA. This research aims to develop genetic algorithm based on evolutionary virology concepts for the capacitated vehicle routing problem, called GM-GA method. The GM-GA mimics the principle of developing the strength of the virus to survive and spread, known as Gain-of-Function. The GM-GA is a specific selection with three criteria: 1) Build routes beginning with the farthest stop from the depot 2) Load trucks with stop volumes that are in closest proximity to each other, and 3) The stop sequence on a route should form a teardrop pattern. This is based on practical guidelines for good routing and scheduling. After that, experiments were then carried out on an instance problem from OR Library in the A series of capacitated vehicle routing problem including small, medium, and large problem. In experiments, it was found that the GM-GA method has a convergence rate than the GA method, but the GA method still finds optimal solutions than the GM-GA method. When the GA method’s results were compared to those of the GM-GA method, it was found that in large problem, the GM-GA method had the closest solution to the GA method and they have convergence rate of optimal solution as well as small problem. It was determined that the GM-GA method is appropriate for application in large industries with sizable customer bases.

ขั้นตอนวิธีเชิงพันธุกรรมเป็นปัญญาประดิษฐ์ชนิดหนึ่งที่มีรากฐานมาจากทฤษฎีวิวัฒนาการของชาร์ล ดาร์วินตามแนวคิดการอยู่รอดของผู้ที่แข็งแกร่งที่สุด กระบวนการค้นหาคำตอบของขั้นตอนวิธีเชิงพันธุกรรมมีลักษณะแบบคู่ขนาน ซึ่งคำตอบที่ได้จากการค้นหาในหนึ่งรุ่นจะนำไปสู่การถ่ายทอดคุณลักษณะที่ดีของคำตอบที่ค้นพบในรุ่นปัจจุบันไปยังรุ่นถัดไป ดังนั้นการคัดเลือกประชากรที่มีลักษณะดีที่สุดจึงเป็นสิ่งสำคัญที่ช่วยเพิ่มประสิทธิภาพคำตอบของขั้นตอนวิธีเชิงพันธุกรรม งานวิจัยนี้มีวัตถุประสงค์เพื่อพัฒนาขั้นตอนวิธีเชิงพันธุกรรมด้วยหลักการเชิงวิวัฒนาการด้านไวรัสวิทยาสำหรับปัญหาการจัดเส้นทางเดินรถแบบมีข้อจำกัดเรื่องความจุของยานพาหนะ ซึ่งเรียกวิธีใหม่นี้ว่า GM-GA ในการพัฒนาวิธี GM-GA จะอาศัยการเลียนแบบหลักการพัฒนาความแข็งแกร่งของเชื้อไวรัสให้สามารถอยู่รอดและแพร่ระบาดได้ หรือที่เรียกว่า Gain-of-Function ซึ่งแตกต่างจากขั้นตอนวิธีเชิงพันธุกรรมดั้งเดิมที่กลไกการคัดเลือกของวิธี GM-GA เป็นการคัดเลือกอย่างเฉพาะเจาะจงด้วยเงื่อนไข 3 ประการ ได้แก่ 1) ในการสร้างเส้นทางแต่ละครั้งควรพิจารณาสร้างเส้นทางจากจุดของลูกค้าที่มีระยะทางไกลจากศูนย์กระจายสินค้ามากที่สุดก่อน 2) ในแต่ละเส้นทางที่ถูกสร้างขึ้น ลูกค้าควรตั้งอยู่ใกล้ ๆ กัน และ 3) เส้นทางที่ถูกสร้างขึ้นควรมีลักษณะเป็นรูปหยดน้ำ ซึ่งอ้างอิงตามหลักการกำหนดเส้นทางและการจัดตารางเวลาที่ดี จากนั้นจึงนำทั้งสองวิธีไปทดสอบกับปัญหาตัวอย่างจาก OR Library ในกลุ่มปัญหาการจัดเส้นทางเดินรถแบบมีข้อจำกัดเรื่องความจุของยานพาหนะ ชุด A ได้แก่ปัญหาขนาดเล็ก ปัญหาขนาดกลาง และปัญหาขนาดใหญ่ เพื่อเปรียบเทียบประสิทธิภาพการค้นหาคำตอบ จากการทดสอบพบว่าวิธี GM-GA มีพฤติกรรมการลู่เข้าสู่คำตอบที่ไวกว่าวิธี GA แต่วิธี GA ยังคงค้นหาคำตอบได้ดีกว่าวิธี GM-GA จากการเปรียบเทียบพบว่าในปัญหาขนาดใหญ่จะให้คำตอบที่ค้นหาด้วยวิธี GM-GA ใกล้เคียงกับวิธี GA มากที่สุด รวมทั้งมีพฤติกรรมการลู่เข้าสู่คำตอบได้ไวไม่ต่างกับปัญหาขนาดเล็ก จึงสรุปได้ว่าวิธี GM-GA เหมาะสำหรับนำไปประยุกต์ใช้ในอุตสาหกรรมขนาดใหญ่ที่มีกลุ่มลูกค้าจำนวนมาก