Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

A LAGRANGIAN RELAXATION AND GENETIC ALGORITHM FOR SOLVING INVENTORY ROUTING PROBLEM

Year (A.D.)

2014

Document Type

Thesis

First Advisor

มาโนช โลหเตปานนท์

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมโยธา

DOI

10.58837/CHULA.THE.2014.1211

Abstract

งานวิจัยชิ้นนี้เป็นการศึกษาเกี่ยวกับปัญหาการจัดเส้นทางและสินค้าคงคลังซึ่งเป็นปัญหาที่นำเอาการตัดสินใจในการเติมเต็มสินค้ามาวิเคราะห์ร่วมกับปัญหาการจัดเส้นทางการเดินรถ โดยมีวัตถุประสงค์เพื่อหาเส้นทางการเดินทาง เวลาในการขนส่ง และปริมาณสินค้าที่ขนส่ง ให้เพียงพอต่อความต้องการของลูกค้าและก่อให้เกิดต้นทุนรวมในการขนส่งสินค้าและจัดเก็บสินค้าที่ต่ำที่สุด โดยผู้วิจัยจะจำลองปัญหาให้อยู่ในรูปแบบกำหนดการเชิงเส้นจำนวนเต็มแบบผสม พร้อมทั้งเสนอวิธีการในการพัฒนาผลเฉลยปัญหาดังกล่าว โดยวิธีการในการพัฒนาผลเฉลยที่นำเสนอนั้น สามารถแบ่งการทำงานออกเป็นสองส่วน ส่วนแรกเสนอใช้วิธีผ่อนคลายแบบลากรางจ์ในการหาขอบเขตของปัญหา ส่วนที่สองจะประยุกต์ใช้วิธีทางพันธุกรรมเข้ามาช่วยในการพัฒนาผลเฉลยเบื้องต้น โดยที่แบบจำลองที่นำเสนอมานั้นจะถูกนำมาทดสอบกับชุดปัญหาตัวอย่างที่กำหนด สำหรับประสิทธิภาพของวิธีการในการหาผลเฉลยทั้งสองจะถูกนำมาเปรียบเทียบและวิเคราะห์กับวิธีการหาผลเฉลยแบบแม่นตรง (กำหนดระยะเวลาในการแก้ไขปัญหาคือหนึ่งชั่วโมง) ผลที่ได้พบว่าขอบเขตของปัญหาที่หาได้จากวิธีการผ่อนคลายแบบลากรางจ์มีความแตกต่างจากขอบเขตที่ดีที่สุดในหนึ่งชั่วโมงเฉลี่ยอยู่ที่ 24.32 เปอร์เซ็นต์ ส่วนการใช้วิธีทางพันธุกรรมเข้ามาช่วยในการพัฒนาผลเฉลยเบื้องต้นพบว่า วิธีการดังกล่าวสามารถพัฒนาคุณภาพผลเฉลยเบื้องต้นได้ในทุกปัญหา โดยเฉพาะอย่างยิ่งในปัญหาตัวอย่างที่มีขนาดใหญ่ที่สุดพบว่าประสิทธิภาพของวิธีการที่นำเสนอนั้นดีกว่าวิธีการหาผลเฉลยแบบแม่นตรงอย่างชัดเจน

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS