通过实例空间分析，揭示车辆路径问题中实例特征与算法表现的关系。
Instance space analysis of the capacitated vehicle routing problem
- 用降维和机器学习构建实例的二维投影空间
- 识别出23个影响算法性能的关键实例特征
- 提供可扩展的投影矩阵，便于新实例分析
本文旨在推进容量限制车辆路径问题（CVRP）研究，解决实例特性与元启发式算法（MH）性能之间复杂关系的理解难题。通过结合实例空间分析（ISA）方法与第12届DIMACS车辆路径挑战赛数据集，我们识别出23个相关实例特征。利用PRELIM、SIFTED和PILOT三个阶段，采用降维与机器学习技术，构建了实例空间的二维投影，揭示实例结构如何影响元启发式算法行为。本研究的关键贡献是提供了一个投影矩阵，使新实例可轻松融入该分析框架，为CVRP领域提供了新的实例分析方法。
原文摘要 · Abstract (English)
This paper seeks to advance CVRP research by addressing the challenge of understanding the nuanced relationships between instance characteristics and metaheuristic (MH) performance. We present Instance Space Analysis (ISA) as a valuable tool that allows for a new perspective on the field. By combining the ISA methodology with a dataset from the DIMACS 12th Implementation Challenge on Vehicle Routing, our research enabled the identification of 23 relevant instance characteristics. Our use of the PRELIM, SIFTED, and PILOT stages, which employ dimensionality reduction and machine learning methods, allowed us to create a two-dimensional projection of the instance space to understand how the structure of instances affect the behavior of MHs. A key contribution of our work is that we provide a projection matrix, which makes it straightforward to incorporate new instances into this analysis and allows for a new method for instance analysis in the CVRP field.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。