1-Equity-Transformer：求解NP-Hard Min-Max路由问题的顺序生成算法（AAAI-24)(完)（code）

Abstract

最小最大路由问题旨在通过智能体合作完成任务来最小化多个智能体中最长行程的长度。这些问题包括对现实世界有重大影响的应用场景，但已知属于NP-hard问题。现有方法在大规模问题上面临挑战，尤其是在需要协调大量智能体以覆盖数千个城市的情况下。本文提出了Equity-Transformer来解决大规模最小最大路由问题。首先，我们采用顺序规划方法来处理最小最大路由问题，使我们能够利用强大的序列生成器（例如,Transformer）。其次，我们提出了关键的归纳偏差，以确保智能体之间的公平工作量分配。通过在两个代表性的最小最大路由任务中展示其优越性能：最小最大多智能体旅行商问题（min-max mTSP）和最小最大多智能体取货和送货问题（min-max mPDP），证明了Equity-Transformer的有效性。值得注意的是，我们的方法在100个智能体和1000个城市的mTSP案例中，与竞争性启发式方法（LKH3）相比，实现了大约335倍的运行时间减少和约53%的成本值降低。我们提供了可复现的源代码：https://github.com/kaist-silab/equity-transfor