iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning
<|reference_start|>iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning: This paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP), where the goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. Though MTSP has been widely studied, obtaining near-optimal solutions for large-scale problems is still challenging due to its NP-hardness. Recent efforts in data-driven methods face challenges of the need for hard-to-obtain supervision and issues with high variance in gradient estimations, leading to slow convergence and highly suboptimal solutions. We address these issues by reformulating MTSP as a bilevel optimization problem, using the concept of imperative learning (IL). This involves introducing an allocation network that decomposes the MTSP into multiple single-agent traveling salesman problems (TSPs). The longest tour from these TSP solutions is then used to self-supervise the allocation network, resulting in a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP). Additionally, to tackle the high-variance gradient issues during the optimization, we introduce a control variate-based gradient estimation algorithm. Our experiments showed that these innovative designs enable our gradient estimator to converge 20% faster than the advanced reinforcement learning baseline and find up to 80% shorter tour length compared with Google OR-Tools MTSP solver, especially in large-scale problems (e.g. 1000 cities and 15 agents).<|reference_end|>
@article{guo2024imtsp:,
    title={iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with
  Imperative Learning},
    author={Yifan Guo, Zhongqiang Ren, and Chen Wang},
    journal={arXiv preprint arXiv:2405.00285},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.00285},
    primaryClass={cs.AI cs.LG cs.RO}
}