Chulalongkorn University Theses and Dissertations (Chula ETD)

วิธีฮิวริสติกเพื่อการแก้ปัญหาแบบพลวัตในการกำหนดตำแหน่งที่ตั้งศูนย์กระจายสินค้าโดยมีข้อจำกัดด้านขนาดและต้นทุนคงที่

Other Title (Parallel Title in Other Language of ETD)

Heuristic for solving dynamic problems of capacitated and fixed-charge distribution center locations

Year (A.D.)

2009

Document Type

Thesis

First Advisor

สีรง ปรีชานนท์

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2009.1616

Abstract

ปัญหาตำแหน่งที่ตั้งศูนย์กระจายสินค้าแบบพลวัตที่มีข้อจำกัดด้านขนาดนั้น จัดเป็นปัญหา ประเภทหนึ่งของปัญหาในกลุ่ม NP-hard combinatorial optimization ของการออกแบบ ระบบโลจิสติกส์และระบบการกระจายสินค้า ซึ่งปัญหาดังกล่าวมีวัตถุประสงค์เพื่อทำให้ค่าใช้จ่าย รวมของการสนองตอบต่อความต้องการของลูกค้าตลอดช่วงเวลาของการวางแผนมีค่าน้อยที่สุด โดยการเลือกเปิดศูนย์กระจายสินค้าที่เหมาะสมจากตำแหน่งของศูนย์กระจายที่มีศักยภาพ โดย ในส่วนของความต้องการของลูกค้านั้น ในงานวิจัยนี้จะพิจารณาความต้องการของลูกค้าว่ามี ลักษณะเปลี่ยนแปลงไปตามเวลาหรือเป็นความต้องการที่เป็นฟังก์ชันของเวลา อีกทั้งเพื่อที่จะ สามารถนำไปใช้ในการปฏิบัติงานจริง ลูกค้าแต่ละรายจะสามารถรับบริการจากศูนย์กระจายสินค้า ได้เพียงแห่งเดียวเท่านั้น โดยในวิทยานิพนธ์ฉบับนี้ได้นำเสนอขั้นตอนวิธีการแก้ปัญหาโดยอยู่บน พื้นฐานของวิธีฮิวริสติกการค้นหาแบบทาบู โดยใช้วิธีการประเมินเซตข้างเคียงแบบการประมาณ แทนวิธีการหาคำตอบที่ดีที่สุดซึ่งมีข้อดี คือ สามารถลดระยะเวลาในการหาคำตอบเมื่อปัญหามี ขนาดใหญ่ได้เป็นอย่างดี นอกจากนั้นในงานวิจัยนี้ยังได้กำหนดให้ศูนย์กระจายสินค้าแห่งใดที่เปิด ให้บริการแล้วไม่สามารถที่จะย้ายตำแหน่งหรือปิดลงภายหลังได้ซึ่งมีเหตุผลมาจากต้นทุนค่า ก่อสร้างศูนย์กระจายสินค้าแต่ละแห่งนั้นต้องใช้เงินลงทุนจำนวนมากและระยะเวลาในการก่อสร้าง ใช้เวลานานจึงไม่เหมาะสมที่จะย้ายตำแหน่งบ่อยๆ โดยงานวิจัยนี้ได้เสนอขั้นตอนวิธีในการ แก้ปัญหาซึ่งอยู่บนพื้นฐานของวิธีการค้นหาแบบทาบู และจากผลการทดสอบประสิทธิภาพของฮิว ริสติกที่สร้างขึ้นเปรียบเทียบกับขั้นตอนวิธีพันธุกรรมซึ่งเป็นฮิวริสติกเปรียบเทียบพบว่ามีขั้นตอน วิธีที่พัฒนาขึ้นมีประสิทธิภาพที่ดี โดยผลเฉลยส่วนใหญ่จะเป็นคำตอบที่ดีที่สุดหรือใกล้เคียง คำตอบที่ดีที่สุดและใช้ระยะเวลาการคำนวณน้อยกว่าขั้นตอนวิธีพันธุกรรมมาก

Other Abstract (Other language abstract of ETD)

Dynamic capacitated facility location is one of the NP-hard combinatorial optimization problems in logistics and distribution system design. The objective of this problem is to minimize the total cost for satisfying customer demands over the whole planning horizon by choosing service facilities among all possible locations subject to limited capacity constraint. The demands in this paper are considered to be changing over time or time-dependent demand, moreover, for practical setting each customer demand can be supplied from only one service facility. In this paper, a heuristic-based algorithm, Tabu Search, is proposed by using approximate neighborhood evaluation since it is an effective way to reduce computational time when the size of problem is large. In addition, since building a new facility requires a large amount of capital and is time consuming, the relocation of any opened facilities is not allowed over the planning horizon. Computational results of Tabu Search heuristic are compared with Genetic Algorithms. The results show that the algorithm is very efficient, the solutions in most cases are optimal or near-optimal with reasonable computational time compared to GA.

Link to Full Text

Share

COinS