อัลกอริทึมระบบอาณานิคมมดสำหรับการจัดเส้นทางพาหนะขนส่ง โดยมีพาหนะขนส่งหลายขนาด ภายใต้การขนส่งที่มีกรอบเวลาจำกัด Ant Colony System (ACS) Algorithm for Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW)

Abstract

บทคัดย่อ

งานวิจัยนี้นำเสนอวิธีระบบอาณานิคมมดร่วมกับขั้นตอนการปรับคุณภาพคำตอบในการแก้ปัญหาการจัดเส้นทางพาหนะขนส่งโดยมีพาหนะขนส่งหลายขนาดและการขนส่งอยู่ภายใต้กรอบเวลาที่จำกัด โดยมีวัตถุประสงค์เพื่อ 1) หาจำนวนพาหนะขนส่งในการใช้งานที่เหมาะสมที่สุด และ 2) หาระยะทางเดินทางที่ใช้งานโดยรวมที่สั้นที่สุดภายใต้เงื่อนไขระยะเวลาการเดินทางที่สั้นที่สุดการแก้ปัญหาการจัดเส้นทางพาหนะขนส่งลักษณะนี้เป็นการวางแผนการใช้พาหนะขนส่งให้มีต้นทุนดำเนินการต่ำที่สุดจากพาหนะขนส่งที่มีหลายประเภทโดยในแต่ละประเภทมีการบรรทุกสินค้าที่จำกัดและให้การบริการลูกค้าอยู่ภายใต้กรอบเวลาที่จำกัดผู้วิจัยใช้ขั้นตอนการปรับปรุงคุณภาพคำตอบด้วยวิธีการ 2-Opt และ Move-Exchange มาร่วมในการปรับปรุงคำตอบเริ่มต้นที่ได้จากระบวนการของวิธีระบบอาณานิคมมด วิธีการที่ได้พัฒนาขึ้นมาผู้วิจัยนำมาสร้างเป็นชุดการคำนวณโดย Microsoft visual studio C++ เวอร์ชั่น 6.0 และใช้การประมวลผล 5 ครั้งต่อหนึ่งปัญหา โดยมีการกำหนดค่าพารามิเตอร์ที่เกี่ยวข้องดังนี้  = 1.60   = 0.1 และ = 0.1 ปัญหาในการทดสอบใช้ปัญหาของ Solomon จำนวน 15 ปัญหาคือ ปัญหากลุ่ม C1 R1 และ RC1 โดยกำหนดให้มีพาหนะขนส่ง 2 ประเภทคือ ประเภทที่ 1 (QA) มีความสามารถในการบรรทุกสินค้าได้สูงสุด 200 หน่วย และประเภทที่ 2 (QB) มีความสามารถในการบรรทุกสินค้าได้สูงสุด 100 หน่วยตามลำดับ ผลการวิจัยพบว่าวิธีระบบอาณานิคมมดร่วมกับขั้นตอนการปรับคุณภาพคำตอบนี้สามารถให้คุณภาพคำตอบที่ดีกว่าการวิธีใช้โปรแกรมลินโกที่ผู้วิจัยพัฒนาขึ้นมาและมีคุณภาพคำตอบที่ดีในภาพรวมสูงถึง 1.47 เปอร์เซ็นต์

Abstract

This study presented the Ant Colony System algorithm together with Local Search in solution of the fleet size and mix vehicle routing problem with time windows (FSMVRPTW). The purposes of this study were 1) to minimize the number of tours (or vehicles), and 2) to minimize the total travel distance where the objective of minimization of the number of tours takes precedence over the minimization of the total travel time. The FSMVRPTW is the planning of using various types of vehicles for the lowest cost of transportation which each type of vehicles have to load the limited goods and distribute them to the customers under the limited time. The researcher integrated the 2-Opt and Move-Exchange methods in the procedures to improve the initial solutions received from the Ant colony algorithm. The researchers employed the developed method to build up the algorithm through the use of Microsoft visual studio C++ version 6.0 with the 5 times of calculation for each problem data set. The parameter was set as = 1.60, = 0.1, and  = 0.1 respectively. The 15 Solomon problems including C1, R1, and RC1 sets were employed. The vehicles in this study were classified into two types namely 1) QA which has the maximum load for 200 units, and type QB having the maximum load for 100 units. The results revealed that the Ant Colony System algorithm together with Local Search gave the better solution that using the LINGO software developed by the researchers with the high quality of solution in general at the level of 1.47 percent.