Equitable Routing -- Rethinking the Multiple Traveling Salesman Problem

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

论文旨在解决多个旅行推销员问题（MTSP）中的公平性问题，即如何在最小化总成本的同时，公平地分配推销员的工作量，使得他们的旅行长度分配合理。

论文提出了两种公平-MTSP的新变体，一种是混合整数二次锥规划（MISOCP），另一种是混合整数线性规划（MILP），旨在保证推销员的工作量公平，并在最小化总成本的同时最小化最长旅行长度。

论文提出的算法能够全局最优地解决公平-MTSP问题，并在基准和实际测试实例上进行了计算结果。值得注意的是，公平-MTSP是解决推销员工作负载均衡的一个可行选择，而且论文提供的算法也是可行的。论文还提供了数据集和开源代码。

在最近的研究中，也有一些关于MTSP的公平性问题的研究，如“Fair Multi-Depot Vehicle Routing Problem with Multiple Trips”。