通过可解释AI分析VRP算法中的关键特征，提升启发式求解效率。
Study of Robust Features in Formulating Guidance for Heuristic Algorithms for Solving the Vehicle Routing Problem
- 用多分类模型分析VRP解的质量预测特征
- 发现部分特征在不同场景下始终是强预测因子
- 提出统一框架实现跨场景特征影响排序，适合算法设计者
车辆路径问题（VRP）是具有广泛实际应用的复杂组合优化问题，由于其属于$/mathcal{NP}$-Hard问题，通常采用元启发式算法求解。传统方法依赖人工设计的启发式规则，基于经验研究。近期研究表明，机器学习可捕捉组合优化解的结构特征，从而辅助设计更高效的算法，尤其适用于解决VRP。本文在此基础上，采用多种分类器模型进行敏感性分析，以预测VRP解的质量。通过可解释AI技术，深入理解模型决策机制。结果表明，尽管特征重要性随场景变化，但某些特征始终为强预测因子。为此，我们提出一个统一框架，用于在不同场景下对特征影响力进行排序。这些发现揭示了特征重要性分析在构建元启发式算法引导机制方面的潜力。
原文摘要 · Abstract (English)
The Vehicle Routing Problem (VRP) is a complex optimization problem with numerous real-world applications, mostly solved using metaheuristic algorithms due to its $\mathcal{NP}$-Hard nature. Traditionally, these metaheuristics rely on human-crafted designs developed through empirical studies. However, recent research shows that machine learning methods can be used the structural characteristics of solutions in combinatorial optimization, thereby aiding in designing more efficient algorithms, particularly for solving VRP. Building on this advancement, this study extends the previous research by conducting a sensitivity analysis using multiple classifier models that are capable of predicting the quality of VRP solutions. Hence, by leveraging explainable AI, this research is able to extend the understanding of how these models make decisions. Finally, our findings indicate that while feature importance varies, certain features consistently emerge as strong predictors. Furthermore, we propose a unified framework able of ranking feature impact across different scenarios to illustrate this finding. These insights highlight the potential of feature importance analysis as a foundation for developing a guidance mechanism of metaheuristic algorithms for solving the VRP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。