การประยุกต์ใช้วิธีการเชิงพันธุกรรม สำหรับปัญหาเส้นทางการขนส่งของโรงกำจัดซากไก่

Abstract

บทคัดย่อ

การส่งออกเนื้อไก่สดมีการถูกกีดกันโดยข้ออ้างเรื่องการจัดการซากไก่ที่ไม่ถูกสุขลักษณะ ทำให้ภาครัฐมีแนวคิดที่จะสร้างโรงกำจัดซากไก่ที่ตำบลทับกวางจังหวัดสระบุรี เพื่อรองรับปริมาณซากไก่จากพื้นที่โดยรอบสำหรับงานวิจัยนี้จะพิจารณาเส้นทางการขนส่งซากไก่และเศษซากไก่จากศูนย์รวมซากไก่ต่างๆ ทั้ง 22 จุด งานวิจัยนี้มีวัตถุประสงค์เพื่อให้มีค่าใช้จ่ายรวมในการขนส่งให้ต่ำที่สุด โดยในการขนส่งจะเป็นการจ้างเหมารถบรรทุกซึ่งคิดค่าขนส่งเป็นอัตราเหมาจ่ายแบบขั้นบันไดตามระยะทาง และลักษณะปัญหานี้เป็นรูปแบบพิเศษของปัญหาการจัดเส้นทางเดินรถที่มีเงื่อนไขเวลาและความจุของรถ เนื่องจากปัญหาดังกล่าวมีความซับซ้อนแบบ NP-Hard จึงได้เสนอวิธีการหาคำตอบด้วยวิธีทางฮิวริสติก โดยแบ่งขั้นตอนเป็น 2 ช่วง ช่วงแรกคือ การสร้างคำตอบตั้งต้นด้วยวิธีการแบบประหยัด (Saving Algorithm) และพัฒนาเพื่อหาคำตอบที่ดีขึ้นด้วยวิธีการเชิงพันธุกรรม (Genetic Algorithm) ผลลัพธ์ที่ได้จากการไปรับซากไก่และเศษซากไก่จากศูนย์รวมซากไก่ต่างๆ ทั้ง 22 จุด พบว่าใช้รถขนส่งทั้งหมด 13 รอบ โดยใช้ค่าใช้จ่ายรวม 100,350 บาทต่อวัน ระยะทางรวม 3,996.90 กม.ต่อวัน และใช้เวลาประมวลผลประมาณ 1.78 วินาที ดังนั้นการวิจัยโดยวิธีนี้ไม่เพียงแต่สามารถแก้ปัญหาที่มีความซับซ้อนได้อย่างรวดเร็ว และได้คำตอบที่ค่อนข้างดีแล้วยังสามารถนำไปปรับใช้เพื่อหาคำตอบได้ง่ายและรวดเร็ว หากต้องการเปลี่ยนสถานที่ตั้งโรงกำจัดซากเป็นที่อื่น

คำสำคัญ: ปัญหาการจัดเส้นทาง วิธีการเชิงพันธุกรรม โรงกำจัดซากไก่

Abstract

One of the non-tariff barriers for chicken export is the hygienic disposal of the chicken carcasses. This leads to a construction of a public chicken rendering plant in Tubkwang, Saraburi to accommodate the large quantity of chicken carcasses from 22 nodes nearby. This is a Capacitated Vehicle Routing Problem with Time Window, which is one of the classical combinatorial problems with NP-Hard complexity. Furthermore, the stepwise linear objective function makes this problem more challenging. The authors proposed a method to tackle this problem with 2 phases; initialization with a saving algorithm and improvement with a genetic algorithm. The saving algorithm was chosen because it delivers good solutions for the linear objective function problems while the genetic algorithm was chosen because of its efficiency in finding a good solution having a good starting point. The combination of the two meta-heuristic yields a solution of 13 routes for the 22 pickup nodes with the total transportation cost of 100,350 baht per day and total distance of 3,996.90 km. per day within a few seconds of computation. This approach will not only deliver a good solution for this problem quickly, but it also can be applied to solve for another solution in a timely manner when considering a new plant location.

Keywords: Vehicle Routing Problem, Genetic Algorithm, Chicken Rendering Plants