Two-Phase Heuristic Approach for Solving Capacitated Vehicle Routing Problem ฮิวริสติกสองเฟสสำหรับการแก้ปัญหาการจัดเส้นทางขนส่งของรถบรรทุกสินค้าที่มีข้อจำกัดความจุ

Abstract

การขนส่งสินค้ามีบทบาทสำคัญต่อการดำเนินธุรกิจอย่างมาก ปัญหาการจัดเส้นทางขนส่ง (VRP) ถือเป็นปัญหาที่ได้รับความสนใจเพื่อนำมาแก้ปัญหาการจัดเส้นทางการขนส่งที่ทำให้ได้ระยะทางสั้นที่สุด งานวิจัยนี้นำเสนอวิธีฮิวริสติก (Heuristic) สำหรับแก้ปัญหาการจัดการขนส่งที่มีข้อจำกัดด้านความจุของยานพาหนะ (CVRP) โดยประยุกต์ใช้การจัดเส้นทางด้วยวิธีจัดกลุ่มก่อนและจัดเส้นทางทีหลัง (CFRS) จากโจทย์ปัญหา (Instance) โดยมีขั้นตอนการหาผลลัพธ์ 2 เฟส โดยเฟสแรกคือ การจัดกลุ่ม (Clustering) จำนวน n กลุ่มย่อยเท่ากับจำนวนรถขนส่งที่ต้องใช้ขนส่ง ซึ่งแบ่งเป็น 3 วิธีได้แก่ 1) การจัดกลุ่มย่อยโดยใช้จุดศูนย์กลางแต่ละ กลุ่มย่อย (Seed Point) จากระยะทางที่ไกลสุดจากจุดกระจายสินค้า 2) การจัดกลุ่มย่อยโดยใช้จุดศูนย์กลางแต่ละกลุ่มย่อยจากระยะทางที่ใกล้สุดจากจุดกระจายสินค้า และ 3) การจัดกลุ่มย่อยโดยใช้จุดศูนย์กลางแต่ละกลุ่มย่อยจากจุดที่มีความต้องการสินค้ามากที่สุด ส่วนเฟสสองคือการหาลำดับการเดินรถโดยใช้วิธีในการหาผลลัพธ์ด้วยปัญหาการเดินทางของพนักงานขาย (TSP) งานวิจัยนี้ทำการเปรียบเทียบวิธีการจัดเส้นทางด้วยวิธีจัดกลุ่มก่อนและจัดเส้นทางทีหลังที่มีการดำเนินการเฟสแรกที่แตกต่างกันทั้งหมด 3 วิธี พบว่าการจัดเส้นทางการขนส่งที่มีข้อจำกัดความจุด้วยวิธีจัดกลุ่มก่อนและจัดเส้นทางทีหลัง โดยการใช้วิธีจัดกลุ่มจากจุดที่มีความต้องการสินค้ามากที่สุดในการจัดกลุ่มย่อยแต่ละกลุ่มย่อยแล้วจัดลำดับเส้นทางในการวิ่งรถทุกสินค้าด้วยวิธี TSP ให้ผลลัพธ์ที่ดีกว่าวิธีการจัดกลุ่มแบบอื่น คิดเป็นร้อยละ 60 จากโจทย์ที่ทดสอบทั้งหมด

The transportation of goods is essential to the operation of a business. The problem of planning transportation routes that accomplish the shortest distance is receiving attention, and the vehicle routing problem (VRP) is one of these subjects. This research presents a heuristic approach to using routing techniques to solve the capacitated vehicle routing problem (CVRP). Through applying routing techniques, two phases are involved in solving the instance, namely the cluster-first route-second (CFRS). The initial phase involves clustering n sub-groups according to the number of transport vehicles required. There are three methods for conducting this: 1) clustering based on the distance farthest from the depot to the center (seed point) of each sub-group, 2) seed point from the point of distribution nearest to the depot, and 3) seed point from the maximum demand. The second phase involves applying the travelling salesman problem (TSP) approach to find the route sequence. The results of the CVRP using the CFRS with the three different methods for the initial phase and the second phase, the routing for all goods using the TSP, are presented. Clustering using the seed point with the highest demand for each sub-group yielded better results than the other clustering methods, accounting for 60% of all benchmark instances.