提出新混合整数锥规划模型，显著提升多智能体动态目标旅行商问题求解效率
A Mixed-Integer Conic Program for the Multi-Agent Moving-Target Traveling Salesman Problem
- 将现有模型重构成非凸混合整数非线性规划，再创新转化为混合整数锥规划
- 计算结果表明，运行时间降低达两个数量级，最优性间隙改善超90%
- 适合需高效求解复杂动态路径规划的多智能体系统研究者
移动目标旅行商问题（MT-TSP）旨在为从静止起点出发的单个代理设计最短路径，使其在各自的时间窗口内恰好访问一组移动目标并返回起点。本文针对多智能体移动目标旅行商问题（MA-MT-TSP）——MT-TSP的扩展版本，提出一种新的混合整数锥规划（MICP）公式。方法首先将当前最先进的MICP公式重述为非凸混合整数非线性规划（MINLP），随后通过创新重构得到新的MICP。计算结果表明，该公式相比现有最优方法，运行时间最多降低两个数量级，最优性间隙改善超过90%。
原文摘要 · Abstract (English)
The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a shortest path for an agent that starts at a stationary depot, visits a set of moving targets exactly once, each within one of their respective time windows, and returns to the depot. In this paper, we introduce a new Mixed-Integer Conic Program (MICP) formulation for the Multi-Agent Moving-Target Traveling Salesman Problem (MA-MT-TSP), a generalization of the MT-TSP involving multiple agents. Our approach begins by restating the current state-of-the-art MICP formulation for MA-MT-TSP as a Nonconvex Mixed-Integer Nonlinear Program (MINLP), followed by a novel reformulation into a new MICP. We present computational results demonstrating that our formulation outperforms the state-of-the-art, achieving up to two orders of magnitude reduction in runtime, and over 90% improvement in optimality gap.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。