Equitable Routing - Rethinking the Multiple Traveling Salesman Problem

多旅行商问题（MTSP）是著名的旅行商问题（TSP）的一种推广形式，它涉及到一个额外的参数，即旅行商的数量。在MTSP中，几个在集散地的旅行商需要访问一组相互连接的目标，以使每个目标最多被一个旅行商访问一次，同时最小化他们的旅程总长度。MTSP同样重要的变体是最小最大MTSP，它旨在通过要求所有旅行商中最长的旅程尽可能短来分配工作量（各自旅程的长度），即最小化所有旅行商中最大旅程的长度。最小最大MTSP在现实生活中的应用中非常重要，以确保旅行商的工作负载平衡。文献中已知最小最大MTSP非常难以通过其线性松弛提供良好的下界来最优解。在本文中，我们提出了两种新的参数化MTSP变体，称为“公平-MTSP”。一种变体被制定为混合整数二次锥规划（MISOCP），另一种变体被制定为混合整数线性规划（MILP）。两种变体都着重于强制销售人员的工作负载公平，即销售人员的旅程长度分布公平，同时最小化他们旅程的总成本。我们提出了算法来解决公平-MTSP的两种变体，达到全局最优解，并在基准和实际测试实例上提供计算结果，这为公平-MTSP作为最小最大MTSP的可行替代方案提供了支持。

论文解决的问题是什么是如何设计两个新的参数化MTSP变体，即公平-MTSP，以解决销售员工作负载不平衡的问题。

论文的关键思路是通过将公平约束引入MTSP中，将其转化为MISOCP和MILP问题，以实现销售员工作负载的公平分配。

论文的实验结果表明，公平-MTSP是解决销售员工作负载不平衡问题的有效方法。论文还提供了开源代码和测试数据集，以便其他研究人员进一步研究和应用。

最近的相关研究包括MTSP和min-max MTSP的求解方法，以及其他基于公平分配的优化问题的研究。