Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

APPLICATION OF GENETIC ALGORITHM FOR VEHICLE ROUTING PROBLEM OF CHICKEN RENDERING PLANTS

Year (A.D.)

2013

Document Type

Thesis

First Advisor

สุทัศน์ รัตนเกื้อกังวาน

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมอุตสาหการ

DOI

10.58837/CHULA.THE.2013.1337

Abstract

การส่งออกเนื้อไก่สดมีการถูกกีดกันโดยข้ออ้างเรื่องการจัดการซากไก่ที่ไม่ถูกสุขลักษณะ ทำให้ทางภาครัฐมีดำริที่จะสร้างโรงกำจัดซากไก่ ซึ่งมีตำแหน่งที่ตั้งให้เลือกอยู่ 2 แห่ง ระหว่าง 1) บริเวณตำบลลำพญากลาง จังหวัดลพบุรี หรือ 2) ตำบลทับกวาง จังหวัดสระบุรี เพื่อรองรับปริมาณซากไก่จากพื้นที่โดยรอบ สำหรับงานวิจัยนี้จะพิจารณาเส้นทางการขนส่งซากไก่และเศษซากไก่ จากศูนย์รวมซากไก่ต่างๆทั้ง 22 จุด โดยมีวัตถุประสงค์เพื่อให้มีค่าใช้จ่ายรวมในการขนส่งให้ต่ำที่สุด ในการขนส่งจะเป็นการจ้างเหมารถบรรทุกซึ่งคิดค่าขนส่งเป็นอัตราเหมาจ่ายแบบขั้นบันไดตามระยะทาง (Stepwise Linear) โดยลักษณะปัญหานี้เป็นรูปแบบพิเศษของปัญหาการจัดเส้นทางเดินรถที่มีเงื่อนไขเวลาและความจุของรถ (Capacitated Vehicle Routing Problem with Time Window) เนื่องจากปัญหาดังกล่าวมีความซับซ้อนแบบ NP-Hard จึงได้เสนอวิธีการหาคำตอบด้วยวิธีทางฮิวริสติก โดยแบ่งขั้นตอนเป็น 2 ช่วง ช่วงแรก คือ การสร้างคำตอบตั้งต้นด้วย Saving Algorithm และพัฒนาเพื่อหาคำตอบที่ดีขึ้นด้วย Genetic Algorithm ผลลัพธ์ที่ได้เมื่อเปรียบเทียบกับ Saving Algorithm พบว่า ในกรณีโรงกำจัดซากไก่ตั้งที่ ตำบลลำพญากลาง สามารถลดค่าใช้จ่ายในการขนส่งแบบเหมาจ่ายรวมได้ 960,000 บาทต่อปี หรือ ร้อยละ 1.74 และในกรณีโรงกำจัดซากไก่ตั้งที่ ตำบลทับกวาง สามารถลดค่าใช้จ่ายในการขนส่งแบบเหมาจ่ายรวมได้ 1,860,000 บาทต่อปี หรือ ร้อยละ 3.39 และหากคิดเฉพาะค่าใช้จ่ายในการขนส่งเป็นหลัก การตั้งโรงกำจัดซากไก่ที่ตำบลทับกวาง จะประหยัดกว่าการตั้งโรงกำจัดซากไก่ที่ตำบลลำพญากลาง ปีละ 1,194,000 บาท หรือ ร้อยละ 2.2 โดยผลการวิจัยนี้สามารถแก้ปัญหาที่มีความซับซ้อนได้อย่างรวดเร็ว และได้คำตอบที่ค่อนข้างดีซึ่งสามารถนำเครื่องมือที่ได้ไปปรับใช้เพื่อหาคำตอบได้ง่ายและรวดเร็ว

Other Abstract (Other language abstract of ETD)

One of the non-tariff barriers for chicken export is the hygienic disposal of chicken carcasses. This has lead to the planned construction of a public chicken rendering plant between in Lamphayaklang, Lopburi or in Tubkwang, Saraburi to accommodate 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 in 2 phases; initialization with a saving algorithm and improvement with a genetic algorithm. The saving algorithm was chosen due 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 result of Genetic Algorithm compared to the Saving Algorithm found in Lamphayaklang, Lopburi will be able to save 960,000 baht per year or 1.74% and Tubkwang, Saraburi will be able to save 1,860,000 baht per year or 3.39%. And if we consider only the cost of transportation in Tubkwang, Saraburi cheaper than Lamphayaklang, Lopburi about 1,194,000 baht per year or 2.2%. 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.

Link to Full Text

Share

COinS