Hybrid metaheuristic development for packing problems

การพัฒนาไฮบริดเมตาฮิวริสติก สำหรับปัญหาการบรรจุ

Name: Kanokwatt Shiangjen

ThaSH: Hybrid metaheuristic -- Design

Classification :.DDC: 658.781

ThaSH: Production planning

ThaSH: Materials handling

ThaSH: Production engineering

ThaSH: Lifting and carrying

Abstract: The packing problem is NP-hard optimization problem related to geometric algorithms for finding a good arrangement of multiple small items into a larger container. Many optimization algorithm have been proposed such as exact algorithm, heuristic and metaheuristic algorithm. The exact algorithm is guaranteed to find the optimal solution but it is a time-consuming process. Since the exact algorithm becomes inefficient for the large scale of the problem. The heuristic algorithm has been applied to find the approximate solutions within a reasonable of computational time but it is not guaranteed to be optimal and usually got stuck in a local minimum. Therefore, metaheuristic algorithm, a general class of stochastic optimization has been introduced by employing some degree of randomness to find an optimal solution and many of the best results in practical optimization were found by using hybrid algorithm between heuristic and metaheuristic algorithm. This dissertation focuses on the generality designation of the hybridization among heuristic, metaheuristic and acceptance criteria for solving 2D rectangular packing problems with the case study of knapsack packing of the fixed orientation rectangular items subtype with non-guillotine cutting (2D-KPPOF). Two heuristic algorithms consist of the enhancing heuristic placement (EHP) and the bidirectional heuristic placement (BHP) is developed. The former heuristic is the preliminary study in design the packing rules which consider the positive influence of the placement position from the left and right side of the wall of the current residual space by increasing the possibility of packing more suitable width of the rectangle into a container. While the latter heuristic is designed by preserving the advantage of EHP and considers the positive influence of placement position from the top to bottom side of the current residual space. The efficiency of exploitation task in a search space is improved by hybrid the proposed heuristics with many metaheuristics consist of local search (LS), simulated annealing (SA), a hybrid between LS and SA (HSA) and iterated local search (ILS). The exploration task in the search space is generated using two techniques that are a multistart strategy and a shift strategy. The former strategy is a basic technique for restart the initial solution by changing the ordering criteria of the rectangles whereas the latter strategy enhances a former strategy by including the acceptance criteria and randomization. The decision to restart the initial solution of the latter strategy will depend on the quality of solutions. The hybrid metaheuristics are tested with many scales of the problems. The experimental results show that the hybridization among the proposed heuristic, ILS and a shift strategy can produce high-quality solutions for most of the benchmark datasets within a reasonable of computational time.

Chiang Mai University Library

Address: Chiang Mai

Email: cmulibref@cmu.ac.th

Name: Somchai Prasitjutrakul

Role: Chairman

Name: Jakrapop Wonglakorn

Role: Member

Name: Jeerayut Chaijaruwanich

Role: Member

Name: Samerkae Somhom

Role: Member

Name: Wijak Srisujjalertwaja

Role: Member

Created: 2017

Modified: 2018-10-18

Issued: 2018-10-18

วิทยานิพนธ์/Thesis

application/pdf

CallNumber: Th 658.781 K16H

eng

DegreeName: Doctor of Philosophy

Level: Doctoral Degree

Descipline: Computer Science

Grantor: Chiang Mai University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	comp70417ksj_full.pdf	5.39 MB	6	2021-02-02 15:59:40

ใช้เวลา

0.043134 วินาที