Chulalongkorn University Theses and Dissertations (Chula ETD)

ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ

Other Title (Parallel Title in Other Language of ETD)

Genetic algorithm with local search for three dimensional bin packing problem

Year (A.D.)

2003

Document Type

Thesis

First Advisor

ประภาส จงสถิตย์วัฒนา

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2003.1365

Abstract

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

Other Abstract (Other language abstract of ETD)

This thesis proposes a genetic algorithm for three dimensional bin packing problem. The proposed method incorporates genetic algorithm with local search procedures. Three local search procedures are proposed : 1) randomly swap two items, 2) distribute the least filled container to other containers and 3) remove the largest item from a container and put it in a new container. These local search procedures are used during the fitness evaluation of a solution. The original solution will be replaced by the new solution found from the local search procedure if the new solution is better. The experiments are carried out to compare genetic algorithms, genetic algorithms with local search and heuristic. The evaluation is based on three aspects : the number of instances solved, the time used to find solution and the throughput of the methods. The results show that the use of local search procedures improves the number of instances solved. Genetic algorithm with local search procedures find solutions faster than the heuristic method when the size of problem is larger than 30. Considering the throughput, genetic algorithm with local search procedures is much better than the heuristic method.

Link to Full Text

Share

COinS