Development of Vehicle Routing Problem by 2-Phase Heuristics Algorithm

Abstract

Transportation costs are considered the main costs of the logistics system. Inefficient transportation management therefore affects total logistics costs. This research therefore investigates solutions for solving efficient vehicle routing problems. This guideline helps entrepreneurs reduce transportation costs by applying Visual Basic programming. This research aims to find the shortest distance route under the specified number of vehicles and create a program that helps plan transportation routes by applying two-phase heuristics based on the Cluster First-Route Second (CFRS). The data analysis of the case study company, a medical equipment distribution company, found customers scattered in 5 regions. Therefore, the coordinates of all customers were collected. Then use the CFRS to cluster customer groups by K-Means, sequence the customer routes in each group with Greedy Algorithm, and compare the results with the method where the Hill climbing Algorithm (HCA) improved the results. The result of the study found that using the CFRS with the HCA has a better distance than the original routing. The total distance decreased by 58.43 percent. In addition, there was an experiment to analyze finding the K value that was appropriate for the problem by making assumptions in 2 cases. Case 1 found that when there was 1 distribution center, the distance results increased according to the K value. Case 2 found that without considering the distribution center, the best distance result was at a K value of 9. In conclusion, K value analysis will give good or bad results, it depends on the selection of the appropriate one for the type of problem and can be used as a decision-making tool for distribution centers. Finally, the program developed from such a theory can be applied in actual transportation planning, and the program developed from the above theory can be practically applied to vehicle routing problems.

ต้นทุนการขนส่งถือว่าเป็นต้นทุนหลักของระบบโลจิสติกส์ การจัดการด้านการขนส่งที่ไม่มีประสิทธิภาพจึงส่งผลกระทบต่อต้นทุนรวมทางด้านโลจิสติกส์ บทความนี้จึงศึกษาแนวทางแก้ปัญหาการจัดเส้นทางการขนส่งให้มีประสิทธิภาพ ซึ่งเป็นแนวทางที่ช่วยให้ผู้ประกอบการลดต้นทุนการขนส่ง โดยประยุกต์ใช้การเขียนโปรแกรม Visual Basic บทความนี้มีวัตถุประสงค์เพื่อหาเส้นทางการขนส่งที่มีระยะทางต่ำที่สุดภายใต้จำนวนคันรถที่กำหนด และเพื่อสร้างโปรแกรมที่ช่วยวางแผนการจัดเส้นทางการขนส่งโดยประยุกต์ใช้วิธีฮิวริสติกส์แบบสองขั้น หรือหลักการ Cluster First-Route Second (CFRS) จากการวิเคราะห์ข้อมูลของบริษัทกรณีศึกษาซึ่งเป็นบริษัทจำหน่ายเครื่องมือแพทย์ พบว่ามีลูกค้ากระจายตัวอยู่ 5 ภูมิภาค จึงได้นำข้อมูลตำแหน่งพิกัดของลูกค้ามาใช้วิธี CFRS โดยทำการจัดกลุ่มลูกค้าด้วยค่าเฉลี่ยของเค และจัดลำดับเส้นทางของลูกค้าแต่ละกลุ่มด้วยขั้นตอนวิธีแบบละโมบ จากนั้นทำการเปรียบเทียบผลลัพธ์กับวิธีที่มีการปรับปรุงผลลัพธ์ด้วยขั้นตอนวิธีการปีนเขา ผลการศึกษาพบว่า การใช้วิธี CFRS ร่วมกับการปรับปรุงผลลัพธ์ด้วยขั้นตอนวิธีการปีนเขา มีระยะทางการขนส่งที่ดีว่าวิธีการจัดเส้นทางแบบเดิมโดยมีระยะทางรวมลดลงคิดเป็นร้อยละ 58.43 อีกทั้งมีการทดลองวิเคราะห์การหาค่า K ที่เหมาะสมกับปัญหาโดยตั้งสมมติฐานขึ้น 2 กรณี กรณีที่ 1 พบว่าเมื่อมีศูนย์กระจายสินค้า 1 แห่ง ผลลัพธ์ด้านระยะทางนั้นเพิ่มขึ้นตามค่า K กรณีที่ 2 พบว่าเมื่อไม่มีการพิจารณาถึงศูนย์กระจายสินค้ามีผลลัพธ์ด้านระยะทางที่ดีที่สุดอยู่ที่ค่า K เท่ากับ 9 สรุปได้ว่าการวิเคราะห์ค่า K จะให้ผลลัพธ์ที่ดีหรือไม่ดีนั้นขึ้นอยู่กับการเลือกประยุกต์ใช้ให้เข้ากับรูปแบบของปัญหาสามารถนำไปเป็นเครื่องมือช่วยในการตัดสินใจเพื่อศูนย์กระจายสินค้าได้ และโปรแกรมที่พัฒนาขึ้นจากทฤษฎีดังกล่าวสามารถนำไปประยุกต์ใช้ในการวางแผนจัดเส้นทางการเดินรถได้จริง