Model And Optimization Algorithms Research On 0-1 Multiple Knapsack Problem With Knapsack Dependent Values

The knapsack problem(KP)not only has important theoretical research meanings,but also has important applications in practice.The values of items in the classic knapsack problems are independent of knapsack.However,for some practical problems,such as selecting the bus stations for different bus fleets in the public transportation system,the classic knapsack problem and its extended forms are not applicable.In this paper,inspired from some practical problems,0-1 multiple knapsack problem with knapsack dependent item values is proposed.In order to solve the model,a dynamic programming algorithm is designed.The dynamic programming algorithm can not solve large scale problems in an acceptable time,but heuristic algorithm can obtain a suboptimal solution in limited time and memory.So a greedy heuristic is also proposed to solve the model.For any scales,it can generate a feasible solution quickly and be a basis for further comparison.However,the quality of the solution needs to be improved.In order to improve the quality of the solution achieved by the greedy heuristic,the performance of the traditional AS algorithm and the traditional MMAS algorithm is studied.Through the analysis of the stagnation of the traditional algorithms,we believe that in solving large scale problems,the value of objective function is relatively large,and the pheromone trails are directly related to the value of the objective function.So that the effect of the pheromone trail on the selection probability as compared with the heuristic information is relatively small and the algorithm is close to greedy algorithm.In order to solve this problem,MMAS2 is developed with the newly proposed method by mapping the objective periodically for the purpose of adjusting the importance of the pheromone trails,in which the max-min pheromone limitation is also applied.And it has more chance to find better solutions.The experimental results on different randomly generated instances show that the proposed MMAS2 algorithm can effectively alleviate the stagnation phenomenon and get better optimization effect.The performance of the solution is significantly better than the MMAS algorithm and AS algorithm.