基于多目标优化的动态背包问题

Dynamic Knapsack Problem Based on Multi-Objective Optimization

摘要: 优化问题和背包问题一直是科学研究领域的难点和热点问题。实际中很多优化问题都可以转化为背包问题，根据优化目标的非单一性，又可以提升复杂度，构造多目标背包问题。随着社会发展的复杂化趋势，使得这些问题迫切满足动态性，多约束等需求，因此动态背包问题逐渐成为新型研究主题的热点。本文通过结合多目标优化、动态背包问题的特点，提出了一个满足成本预算最低目标，客户满意度和车辆装载率最大目标的数学模型。并且对粒子群算法的特点进行了分析研究，然后利用多目标粒子群优化算法，对该动态背包问题进行了优化。为了验证模型的有效性和算法的效果与性能，利用随机产生的测试序列作为案例进行求解。

Abstract: Optimization problems and knapsack problems have always been difficult and hot issues in the field of scientific research. In practice, many optimization problems can be transformed into knapsack problems. According to the non-singularity of the optimization objective, the complexity can be improved and a multi-objective knapsack problem can be constructed. With the complex trend of social development, these problems urgently meet the needs of dynamics and multiple constraints, so the dynamic knapsack problem is gradually becoming a hot topic of new research topics. By combining the characteristics of multi-objective optimization and dynamic knapsack problem, this paper proposes a mathematical model that satisfies the objective of minimum cost budget, maximum customer satisfaction and vehicle loading rate. The characteristics of particle swarm optimization are analyzed and studied, and the dynamic knapsack problem is optimized by using multi-objective particle swarm optimization algorithm. In order to verify the validity of the model and the effect and performance of the algorithm, the randomly generated test sequence is used as a case to solve.