用机器学习解决复杂路径规划问题，提升求解效率与质量
Learning for routing: A guided review of recent developments and future directions
- 将机器学习分为构建型和优化型两类方法，分类指导应用
- 融合传统运筹学与前沿模型，有效应对新型车辆路径问题
- 适合对智能算法优化感兴趣的科研人员与工程实践者
本文综述了机器学习（ML）在求解NP难组合优化问题中的最新进展，重点聚焦旅行商问题（TSP）与车辆路径问题（VRP）。由于这些问题固有的复杂性，精确算法常需过长计算时间才能获得最优解，而启发式方法仅能提供近似解且无法保证最优性。随着机器学习模型的快速发展，越来越多研究提出并实现多样化的ML技术以增强此类复杂路径问题的求解能力。本文提出一种分类体系，将基于机器学习的路由方法划分为构建型与改进型两类，突出其在不同问题特征下的适用性。本综述旨在整合传统运筹学方法与前沿机器学习技术，为未来研究提供结构化框架，并应对新兴的VRP变体挑战。
原文摘要 · Abstract (English)
This paper reviews the current progress in applying machine learning (ML) tools to solve NP-hard combinatorial optimization problems, with a focus on routing problems such as the traveling salesman problem (TSP) and the vehicle routing problem (VRP). Due to the inherent complexity of these problems, exact algorithms often require excessive computational time to find optimal solutions, while heuristics can only provide approximate solutions without guaranteeing optimality. With the recent success of machine learning models, there is a growing trend in proposing and implementing diverse ML techniques to enhance the resolution of these challenging routing problems. We propose a taxonomy categorizing ML-based routing methods into construction-based and improvement-based approaches, highlighting their applicability to various problem characteristics. This review aims to integrate traditional OR methods with state-of-the-art ML techniques, providing a structured framework to guide future research and address emerging VRP variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。