《Mathematical and Computational Applications》：Advanced Optimization Methods for the Knapsack, Traveling Salesman, and Close-Enough Traveling Salesman Problems: A Survey and Case Studies
组合优化问题（COPs），包括背包问题（KP）、旅行商问题（TSP）以及诸如足够接近旅行商问题（CETSP）的区域变体，构成了处理现代计算系统中复杂决策任务的基本模型。它们的计算难度促使了广泛的精确、启发式、元启发式、基于学习和混合优化方法的发展。本工作对这些方法进行了结构化综述和面向问题结构的比较分析，涵盖了遗传算法（GAs）、粒子群优化（PSO）、蚁群优化（ACO）、模拟退火（SA）、禁忌搜索（TS）、人工蜂群（ABC）、图神经网络（GNNs）和学习增强的混合方法。特别关注问题结构、公式化特征、可行性要求、计算成本和评估设置的差异如何影响不同优化范式的适用性。通过基于研究人员先前工作的两个案例研究讨论了这些方法的实际相关性：云计算中的虚拟机放置（VMP），通过简化的单资源0–1 KP抽象进行检查；以及无线传感器网络（WSNs）中数据收集的无人机轨迹优化，通过TSP、CETSP和基于邻域的路由模型进行检查。审查的证据表明，元启发式方法可以在计算困难的环境中提供灵活的搜索机制，而基于学习的模型可以在适当的训练数据和泛化条件可用时支持快速推理、预测、初始化或搜索指导。混合学习–优化框架在其组件解决潜在问题的互补限制时可能是有益的，尽管其有效性仍然依赖于问题结构、训练要求、计算预算、可行性处理和实现设计。在云环境中，基于背包的VMP公式为资源分配决策提供了有用的抽象，而在无人机辅助的WSNs中，诸如TSP和CETSP的路由模型提供了轨迹和数据收集决策的结构化表示。总体而言，本综述突出了现代优化范式的互补优势和局限性，并强调方法选择应由问题结构、操作要求、可行性考虑和计算约束指导。
论文主体内容总结如下：
Section 2: Literature Search and Selection Procedure
本文采用Scopus、Web of Science、IEEE Xplore和Google Scholar等数据库进行结构化文献检索，重点覆盖2024至2026年的最新研究，并补充经典文献。通过问题相关术语和方法学术语组合搜索，经过去重、标题摘要筛选和全文评估，最终纳入具有清晰方法贡献、数学公式或计算评估的研究。
Section 3: COPs Studied
3.1. Knapsack Problem
KP是经典的NP难问题，建模容量约束下的子集选择。对于0–1 KP，给定n个物品，每个物品有利润p
i和重量w
i，以及背包容量W，目标是最大化总利润且不超过容量。多维背包问题（MKP）引入多个资源约束。这些结构变化影响求解机制，如动态规划、数学规划和固定集元启发式等。
3.2. Traveling Salesman Problem
TSP要求寻找经过每个节点恰好一次并返回起点的最小成本哈密顿回路。与KP不同，TSP需要全局连通性，因此子环消除约束、有效不等式和分支割算法至关重要。
3.3. Close-Enough Traveling Salesman Problem
CETSP放宽了精确访问要求，每个目标仅需在服务区域内被访问，从而将离散排序与几何服务点选择耦合。文中给出了基于单元（cell）的混合整数抽象，并指出CETSP需要连续优化、离散化或交替优化。
3.4. Structural Comparison of KP, TSP, and CETSP
从决策结构、数学耦合、松弛与定界、分解机会、邻域设计、可行性管理和计算行为七个维度进行比较。KP以容量约束为特征，TSP强调全局连通，CETSP引入路由–几何交互。这些差异影响学习组件和混合策略的设计。
Section 4: Methods for Solving COPs
4.1. Exact Methods
4.1.1. Tree- and Cut-Based Methods
分支定界（B&B）通过递归划分和剪枝搜索；分支割（Branch-and-Cut）在搜索树中生成有效不等式。对于KP、TSP和CETSP，定界质量、预处理和问题特定不等式决定性能。
4.1.2. Dynamic Programming
动态规划（DP）利用最优子结构。0–1 KP的伪多项式复杂度为O(nW)；TSP的子集状态避免全排列枚举；CETSP的状态设计更为复杂。
4.1.3. Mathematical Programming
整数线性规划（ILP）和混合整数线性规划（MILP）提供通用框架。公式强度、预处理和求解器集成影响性能。对于TSP，连通性约束重要，CETSP还需处理几何变量。
4.1.4. Relaxation and Decomposition Methods
拉格朗日松弛、Dantzig–Wolfe分解、列生成和Benders分解利用可分离性。CETSP中路由顺序和几何服务点可自然分解。
4.1.5. Constraint Programming
约束规划（CP）强调传播和全局约束，可与数学规划结合。CETSP的连续几何决策对纯CP构成挑战。
4.2. Heuristic Methods
4.2.1. Constructive Heuristics
构造式启发式通过贪心决策生成初始可行解，例如KP中的利润重量比、TSP中的最近邻，CETSP需考虑服务区域几何。
4.2.2. Local Improvement Heuristics
局部改进从初始解出发搜索邻域，如TSP的2-opt、3-opt。KP中插入、移除、交换操作；CETSP中路由变化可能需要几何精炼。
4.2.3. Approximation and Repair Methods
近似算法提供质量保证，修复启发式恢复可行性，几何精炼处理连续服务点。
4.3. Metaheuristic Methods
4.3.1. Trajectory- and Neighborhood-Based Metaheuristics
包括模拟退火（SA）、禁忌搜索（TS）、变邻域搜索（VNS）、迭代局部搜索（ILS）、大邻域搜索（LNS）和自适应大邻域搜索（ALNS）。机制比标签更重要。
4.3.2. Population-Based Metaheuristics
遗传算法（GA）等种群方法通过选择、交叉、变异搜索。需要问题特定表示和修复机制。
4.3.3. Swarm Intelligence
蚁群优化（ACO）适合离散构造；粒子群优化（PSO）、人工蜂群（ABC）等需要离散映射。评估需注意预算和协议。
4.3.4. Multi-Start Metaheuristics
GRASP等多次启动，结合随机贪心构造和局部搜索。
4.4. Learning-Based Optimization Methods
4.4.1. Hopfield Neural Networks
Hopfield网络（HNN）通过能量函数编码优化问题，但稳定状态不保证全局最优。
4.4.2. Deep Learning Models
深度模型包括序列模型和图神经网络（GNN），可直接构造或辅助搜索。需要可行性掩码和局部优化。
4.4.3. Reinforcement Learning
强化学习（RL）将优化视为序列决策，可用于构造、搜索控制。但训练成本高，泛化受限。
4.4.4. Learning-Assisted Optimization
学习组件可预测变量、引导分支或加速子问题，与经典优化框架结合。
4.4.5. Evaluation, Generalization, and Comparison with OR Baselines
评估需区分训练/推理成本，测试分布偏移，并与强OR基线比较。
4.5. Hybrid Methods
4.5.1. Mathematical Programming-Based Heuristics
数学规划基启发式（matheuristics）利用受限MIP优化邻域，如局部分支。
4.5.2. Metaheuristic–Heuristic Hybrids
元启发式与问题特定启发式结合，如遗传搜索与动态规划分割。
4.5.3. Metaheuristic–Learning Hybrids
学习模型预测成本或选择算子，辅助元启发式。
4.5.4. Metaheuristic–Mathematical Programming Hybrids
元启发式主搜索，数学规划用于子问题精化。
4.5.5. Memetic Algorithms
模因算法结合种群搜索与局部改进。
4.5.6. Metaheuristic–Metaheuristic Hybrids
包括基于群体、进化、跨范式的混合，如PSO-ACO、GA-DE等，需验证组件互补性。
4.6. LLM-Assisted Optimization and Automated Heuristic Design
大语言模型（LLM）用于自动生成启发式、算法配置和搜索引导。自动化启发式设计（AHD）将LLM与进化搜索结合，但需考虑生成、验证、泛化和基准污染问题。
4.7. Computational Complexity and Evaluation Criteria
计算复杂度需与实证指标结合。评价应报告解质量、运行时间、预算、停止准则、多次运行、统计检验等。学习方法的离线成本需单独报告。
4.8. Problem-Structure-Aware Algorithm Selection
算法选择应根据问题结构而非算法名称。实例空间分析可用于选择合适方法。设计原则包括表示、邻域、可行性、分解、混合和评估。
Section 5: Applications and Case Studies
5.1. Metaheuristic and Neural Approaches for Virtual Machine Placement in Cloud Computing
VMP将虚拟机分配到物理机，实际是多服务器多资源问题。文中案例研究采用单资源0–1 KP抽象，比较了九种方法，神经方法表现有竞争力，但结论仅限于简化设置。
5.2. Optimization of UAV Flight Paths and Data Collection in Multi-UAV and WSN Environments
UAV数据收集可建模为TSP/CETSP。案例研究结合k-means聚类、ACO、SA、PSO、GA等，以及交叉点选择机制。不同研究中ACO和ABC表现不同，强调结果依赖实验设置。
5.3. Other Applications and Operational Challenges
其他应用包括覆盖问题、动态派送、医疗保健等。实际部署需考虑不确定性、多目标、可行性、计算延迟、人机交互和可解释性。
Section 6: Conclusions and Perspectives
综述不支持通用排序。未来研究应针对KP、TSP、CETSP的具体结构挑战，并强调可重复的、操作有意义的评估。
