ฮิวริสติกสำหรับการจัดเส้นทางเดินรถแบบเปิดเพื่อลดต้นทุนการขนส่ง

Abstract

การจัดเส้นทางเดินรถแบบเปิดเป็นแนวทางหนึ่งในการลดต้นทุนขนส่งของลักษณะการขนส่งจากหลายแห่งไปยังจุดรับส่งสินค้าต่างๆ ที่ตั้งกระจายเป็นระยะทางไกล งานวิจัยนี้มีจุดประสงค์เพื่อพัฒนาฮิวริสติกสำหรับปัญหาการจัดเส้นทางเดินรถแบบเปิดเพื่อลดต้นทุนการขนส่ง โดยเส้นทางขนส่งในงานวิจัยนี้เป็นการเดินรถขนส่งอย่างต่อเนื่องที่รถขนส่งไม่จำเป็นจะต้องกลับมายังจุดตั้งต้นของแต่ละรอบ อีกทั้งมีการรับและส่งสินค้าบนเส้นทาง ภายใต้ข้อจำกัดความจุในการบรรทุกและกรอบเวลากำหนดส่งมอบ ฮิวริสติกที่นำเสนอพัฒนามาจากวิธีการ Insertion heuristic ซึ่งเป็นวิธีการหาคำตอบที่ง่ายและเหมาะสำหรับการจัดเส้นทางที่คำนวณแทรกงานขนส่งใหม่ลงเส้นทางเดิมได้อย่างรวดเร็ว การทดสอบฮิวริสติกด้วยปัญหาตัวอย่างเมื่อเปรียบเทียบต้นทุนการขนส่งที่ได้จากวิธี insertion กับวิธีการ Nearest neighbor ซึ่งเป็นวิธีที่นิยมใช้แก้ปัญหาการจัดเส้นทาง พบว่า การจัดเส้นทางเดินรถแบบเปิดด้วยวิธีInsertion heuristic ให้คำตอบที่ดีกว่าเฉลี่ยลดลงเท่ากับ 6.11% โดยผลลัพธ์ที่ได้ให้ค่าต้นทุนที่ต่ำกว่าทุกลักษณะของตัวอย่างการขนส่งที่สร้างขึ้นจากความต้องการขนส่งจริง ส่งผลให้ฮิวริสติกที่พัฒนาขึ้นมีประสิทธิภาพสำหรับการลดต้นทุนการขนส่งของปัญหาการจัดเส้นทางเดินรถแบบเปิด

The open vehicle routing is another way of reducing transportation cost for the transportation which is characterized by transporting from many sites to various loading spots distributed in the remote areas. This research aims to develop a heuristic for solving the open vehicle routing problem in order to reduce transportation cost. The routes used in this research are continuous ones where the vehicle is not required to return to the depot after servicing the last customer on a route. Also, there is a service of pickup and delivery on the route under loading capacity and time window constraints. The proposed heuristic is developed from the Insertion heuristic which is a method to find the simple and properly for the route is calculated to insert new transportation requirements on the old route quickly. According to the heuristic test by sample problems compared to the transportation cost obtained from insertion and nearest neighbor method, which is popular in solving routing problem, the experimental results show that the open vehicle routing by insertion heuristic method provides less number of better solutions by average for 6.11 %. The result obtained yields lower cost in all characteristics of sample of transportation created from real transportation needs, leading the developed heuristic to have efficiency in reducing transportation cost of the open vehicle routing.