Font Size: a A A

Study On Heuristics For The Quadratic Multiple Knapsack Problem And Its Variant Problem

Posted on:2018-01-12Degree:DoctorType:Dissertation
Country:ChinaCandidate:J QinFull Text:PDF
GTID:1318330515483402Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
The quadratic multiple knapsack problem(QMKP)is an extension of the well-known combinatorial optimization problem 0-1 knapsack problem.QMKP has many important practical applications in different contexts,including the assignment of workmen to different tasks when their ability to cooperate may affect the results,the determination of the locations of the earth stations f-or communication satellites with a budget constraint,and the determination of the sites of railway stations,freight handling terminals,and airports.Another problem named the problem of composing medical crews(CMC)is arising at the operation center of the Emergency Medical Service of Milano,which shares the common structure of QMKP and can be viewed as an variant problem of QMKP.In addition to their important practical applications,thess two problems are also notable tor the theoretical significance as combinatorial optimization problems.The practical applications and computational challenge of QMKP and CMC have motivated a variety of solution approaches,most of which are approximation algorithms and meta-heuristic methods.However,these methods still need to be further improved because of their drawbacks.Based on those methods already existed in the literiture,this dissertation tries to propose more effective heuristics to solve QMKP and CMC,hoping to provide new improved results and also more choices for solving these problems.Firstly,this dissertation proposes a highly effective tabu search(TS)method that incorporates a hybridization scheme combining both feasible and infeasible local searches to effectively explore the search space of QMKP.The proposed TS integrate infeasible local searches can permit searches through the infeasible search space to bring more freedom to the search.Then,we conduct experimental tests on a set of QMKP instances to evaluate the performance of our proposed TS algorithm and analyze the effect of sevral components of TS in boosting the performance of the proposed TS algorithm.Secondly,based on the grouping property of QMKP,this dissertation design a memetic algorithm for QMKP.The proposed MA using a backbone based crossover operator which tries to preserve the assignment of objects respect to a number of parent individuals,leading to solution of high quality.We compare the computational results of our MA with sevral best algorithms from literature under different time limit.The comparison results emphasize the superiority of our algorithm.The conclusion is given at last.Thirdly,this dissertation study a variant problem of QMKP,named the problem of composing medical crews(CMC).We proposed a two phases tabu search algorithm,which integrate problem-specific knowledge within its search process.The two phases local search process integrated in the TS can make a balance between the objective function and the diversity constraint during the search and avoid the algorithm prematurely trapping in a local optimum.To further evaluate the relative effectiveness and efficiency of our proposed algorithm,we compare our TS algorithm with two currently best-performing heuristic algorithms for CMC.Further,wo conduct additional experiments to show the important role of the two phases local search structure and give the final conclusion.Fourthly,this dissertation proposes a memetic algorithm for CMC according to the MA framework used in QMKP.We introduce a dedicated backbone based crossover operator to generate promising new offspring and employ a quality-and-distance replacement strategy for population updates to maintain the polulation diversity.We also conduct experiments to compare the performance of MA and other methods proposed in the literiture and then investigate sevral important components of the proposed MA algorithm that contribute to its effectiveness.
Keywords/Search Tags:Quadratic Multiple Knapsack Problem, Tabu Search, Composing Medical Crews, Memetic Algorithm, Infeasible Solution
PDF Full Text Request
Related items