ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ
วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2546
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | Thai |
| Published: |
จุฬาลงกรณ์มหาวิทยาลัย
2009
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/9725 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chulalongkorn University |
| Language: | Thai |
| id |
th-cuir.9725 |
|---|---|
| record_format |
dspace |
| spelling |
th-cuir.97252009-08-06T04:54:54Z ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ Genetic algorithm with local search for three dimensional bin packing problem จิระเดช พลสวัสดิ์ ประภาส จงสถิตย์วัฒนา จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ การบรรจุหีบห่อ จีเนติกอัลกอริทึม วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2546 วิทยานิพนธ์ฉบับนี้เสนอการใช้ขั้นตอนวิธีเชิงพันธุกรรมสำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ โดยเพิ่มการค้นเฉพาะที่ในขั้นตอนวิธีเชิงพันธุกรรม ได้เสนอการค้นเฉพาะที่ทั้งหมด 3 แบบ ได้แก่ 1) การสุ่มสลับลำดับ 2) การกระจายผลิตภัณฑ์ในตู้สินค้าที่บรรจุได้น้อยที่สุดไปตู้สินค้าอื่นๆ 3) การเลือกชิ้นใหญ่ที่สุดออกไปบรรจุในตู้สินค้าใหม่ การค้นเฉพาะที่เหล่านี้ถูกใช้ในระหว่างการวัดคุณภาพของคำตอบ ถ้าพบคำตอบที่ดีกว่าจึงจะแทนที่คำตอบเดิมด้วยคำตอบที่ได้จากการค้นเฉพาะที่ ทำการทดลองเพื่อเปรียบเทียบผลระหว่างขั้นตอนวิธีเชิงพันธุกรรม, ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่และขั้นตอนวิธีแบบศึกษาสำนึก เกณฑ์การเปรียบเทียบมี 3 อย่างได้แก่จำนวนปัญหาที่หาคำตอบได้, เวลาในการหาคำตอบและปริมาณงานต่อหน่วยเวลา ผลการทดลองแสดงให้เห็นว่าการใช้การค้นเฉพาะที่ทำให้สามารถหาคำตอบได้มากขึ้น ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่หาคำตอบได้เร็วกว่าขั้นตอนวิธีแบบศึกษาสำนึกเมื่อขนาดของปัญหามากกว่า 30 ชิ้น และเมื่อพิจารณาในแง่ปริมาณงานต่อหน่วยเวลาพบว่าขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่ให้ปริมาณงานต่อหน่วยเวลามากกว่าขั้นตอนวิธีแบบศึกษาสำนึก 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. 2009-08-06T04:54:53Z 2009-08-06T04:54:53Z 2546 Thesis 9741741669 http://cuir.car.chula.ac.th/handle/123456789/9725 th จุฬาลงกรณ์มหาวิทยาลัย 815256 bytes application/pdf application/pdf จุฬาลงกรณ์มหาวิทยาลัย |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| country |
Thailand |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
Thai |
| topic |
การบรรจุหีบห่อ จีเนติกอัลกอริทึม |
| spellingShingle |
การบรรจุหีบห่อ จีเนติกอัลกอริทึม จิระเดช พลสวัสดิ์ ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| description |
วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2546 |
| author2 |
ประภาส จงสถิตย์วัฒนา |
| author_facet |
ประภาส จงสถิตย์วัฒนา จิระเดช พลสวัสดิ์ |
| format |
Theses and Dissertations |
| author |
จิระเดช พลสวัสดิ์ |
| author_sort |
จิระเดช พลสวัสดิ์ |
| title |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| title_short |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| title_full |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| title_fullStr |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| title_full_unstemmed |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| title_sort |
ขั้นตอนวิธีเชิงพันธุกรรมร่วมกับการค้นเฉพาะที่สำหรับปัญหาการบรรจุผลิตภัณฑ์ในสามมิติ |
| publisher |
จุฬาลงกรณ์มหาวิทยาลัย |
| publishDate |
2009 |
| url |
http://cuir.car.chula.ac.th/handle/123456789/9725 |
| _version_ |
1681413593370722304 |