Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/45672
Title: การใช้วิธีผ่อนคลายแบบลากรางจ์ร่วมกับวิธีทางพันธุกรรมในการแก้ไขปัญหาการจัดเส้นทางและสินค้าคงคลัง
Other Titles: A LAGRANGIAN RELAXATION AND GENETIC ALGORITHM FOR SOLVING INVENTORY ROUTING PROBLEM
Authors: ศรัณย์ พิพัฒนพงศ์โสภณ
Advisors: มาโนช โลหเตปานนท์
Other author: จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email: Manoj.L@chula.ac.th,lmanoj@gmail.com
Subjects: จีเนติกอัลกอริทึม
การโปรแกรมเชิงจำนวนเต็ม
ปัญหาการจัดเส้นทางเดินรถ
การควบคุมสินค้าคงคลัง
Genetic algorithms
Integer programming
Vehicle routing problem
Inventory control
Issue Date: 2557
Publisher: จุฬาลงกรณ์มหาวิทยาลัย
Abstract: งานวิจัยชิ้นนี้เป็นการศึกษาเกี่ยวกับปัญหาการจัดเส้นทางและสินค้าคงคลังซึ่งเป็นปัญหาที่นำเอาการตัดสินใจในการเติมเต็มสินค้ามาวิเคราะห์ร่วมกับปัญหาการจัดเส้นทางการเดินรถ โดยมีวัตถุประสงค์เพื่อหาเส้นทางการเดินทาง เวลาในการขนส่ง และปริมาณสินค้าที่ขนส่ง ให้เพียงพอต่อความต้องการของลูกค้าและก่อให้เกิดต้นทุนรวมในการขนส่งสินค้าและจัดเก็บสินค้าที่ต่ำที่สุด โดยผู้วิจัยจะจำลองปัญหาให้อยู่ในรูปแบบกำหนดการเชิงเส้นจำนวนเต็มแบบผสม พร้อมทั้งเสนอวิธีการในการพัฒนาผลเฉลยปัญหาดังกล่าว โดยวิธีการในการพัฒนาผลเฉลยที่นำเสนอนั้น สามารถแบ่งการทำงานออกเป็นสองส่วน ส่วนแรกเสนอใช้วิธีผ่อนคลายแบบลากรางจ์ในการหาขอบเขตของปัญหา ส่วนที่สองจะประยุกต์ใช้วิธีทางพันธุกรรมเข้ามาช่วยในการพัฒนาผลเฉลยเบื้องต้น โดยที่แบบจำลองที่นำเสนอมานั้นจะถูกนำมาทดสอบกับชุดปัญหาตัวอย่างที่กำหนด สำหรับประสิทธิภาพของวิธีการในการหาผลเฉลยทั้งสองจะถูกนำมาเปรียบเทียบและวิเคราะห์กับวิธีการหาผลเฉลยแบบแม่นตรง (กำหนดระยะเวลาในการแก้ไขปัญหาคือหนึ่งชั่วโมง) ผลที่ได้พบว่าขอบเขตของปัญหาที่หาได้จากวิธีการผ่อนคลายแบบลากรางจ์มีความแตกต่างจากขอบเขตที่ดีที่สุดในหนึ่งชั่วโมงเฉลี่ยอยู่ที่ 24.32 เปอร์เซ็นต์ ส่วนการใช้วิธีทางพันธุกรรมเข้ามาช่วยในการพัฒนาผลเฉลยเบื้องต้นพบว่า วิธีการดังกล่าวสามารถพัฒนาคุณภาพผลเฉลยเบื้องต้นได้ในทุกปัญหา โดยเฉพาะอย่างยิ่งในปัญหาตัวอย่างที่มีขนาดใหญ่ที่สุดพบว่าประสิทธิภาพของวิธีการที่นำเสนอนั้นดีกว่าวิธีการหาผลเฉลยแบบแม่นตรงอย่างชัดเจน
Other Abstract: In this research, we study about Inventory Routing Problem (IRP). IRP is a problem that integrated the inventory replenishment decision to analyze with Vehicle Routing Problem (VRP). The objective is to find the routes, dates and quantities of deliveries, in order to meet the demand of customers which causes the lowest transportation and inventory holding cost. By using Mixed Integer Programming (MIP), this paper presents two approaches for solving the Inventory Routing Problem. First, we present a Lagrangian Relaxation to find a lower bound of the problem. Second, we use a Genetic Algorithm to develop an incumbent solution from Branch and Bound. The proposed approaches were tested with the given examples and the efficiency of proposed approaches were compared and analyzed with exact solution approach. Results show that the average difference of the Lagrangian Relaxation bound from the best bound is 24.34 percent. On the other hand, results also show that Genetic Algorithm can be used to improve the quality of incumbent solutions in every example. Moreover, from the biggest example, it was observed that Genetic Algorithm clearly performs better than exact solution approach
Description: วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2557
Degree Name: วิศวกรรมศาสตรมหาบัณฑิต
Degree Level: ปริญญาโท
Degree Discipline: วิศวกรรมโยธา
URI: http://cuir.car.chula.ac.th/handle/123456789/45672
URI: http://doi.org/10.14457/CU.the.2014.1047
metadata.dc.identifier.DOI: 10.14457/CU.the.2014.1047
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
5670392421.pdf1.83 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.