超越大巡回：期望核心方法求解无限周期旅行商问题

《Journal of Mathematical Economics》：Beyond the grand tour: The aspiration core approach to the Infinite-Period Traveling Salesman Problem

　　

## 摘要

我们引入了无限周期旅行商问题（∞-TSP），这是经典TSP的一种推广，其中一个服务提供商需要反复访问同一组客户。我们的方法利用了期望核（aspiration core），这是合作博弈论中的一个概念，它将经典的核扩展到核可能为空的情况，同时允许形成适当的联盟。期望核提供了稳健的成本分配规则，并识别出应该在特定行程中一起访问的客户子集。当一次性旅行商博弈的核为空时，所建议的行程计划能够实现比重复单个大行程更低的每次访问平均成本。我们进一步利用期望核仁（aspiration nucleolus）——一个从期望核中选出的唯一成本分配——来完善我们的框架。

## 引言

经典旅行商问题（TSP）的典型动机如下。一组客户雇佣一个服务提供商，在其不同地点为其提供特定服务。提供商从公司的枢纽或母城出发，每个客户访问一次，然后返回枢纽。该问题有两个主要目标：找到最小化总成本的路径，以及将该成本在服务过的客户之间进行分配，使得没有任何客户子组有动力与另一个服务提供商单独谈判。这样的成本分配被称为处于相应合作博弈的核中，通常被称为"稳定"的分配，其依据是没有客户群体可以通过离开大联盟做得更好，因为没有任何群体被收取的费用超过其独立服务的成本。

我们探讨服务提供商/运营商频繁前往同一组地点时所面临的挑战。每个地点需要在任意长的时间范围内被反复访问，且访问不一定需要在严格或固定的时间范围内进行。相反，服务提供商必须设计一个行程计划，在访问频率和成本之间实现最佳平衡。我们将此问题称为无限周期旅行商问题，并简称为∞-TSP。

各行各业中有大量此类案例，例如医疗健康、公用事业、农业以及消费和订阅服务。例如，电力公司必须定期检查基础设施，但通常可以灵活安排人员路线；送货车、公交车或租赁车需要定期保养，但服务商可以灵活批量安排访问；农业专家需要在整个生长季节检查作物健康状况，但时间可以有一定灵活性；居家医疗保健提供商希望为患有慢性病的患者规划高效路线，但具体时间安排可以在一定窗口内浮动；许多商业或家用电器系统需要不定期检查和清洁，但不必在严格固定的日期进行。在所有这些情况下，提供商都必须反复访问一组客户/资产，但两次访问之间的具体时间有一定灵活性。提供商希望在持续滚动的时段内优化前往这些客户的旅行路线。

我们首先论证这个问题并不等同于经典TSP。以下例子说明了这一点。

**例1.1** 一个服务提供商必须无限多次访问九个不同的城市。这些城市根据彼得森图（参见Tamir, 1989和Petersen, 1898）通过道路连接，如图1所示。行程必须从标为0的母节点出发并结束于该节点。使用任何道路的代价均为1美元。

我们首先确定该图经典TSP的解。这对应于每个城市只需访问一次的情况。然而，由于该图不是完全图，提供商在同一行程中需要多次经过某些城市。在这种情况下，至少访问所有城市一次的最小成本为11美元。实现此成本的一条示例路线如图所示。

人们可能认为∞-TSP等同于经典TSP，因为处理无限周期场景的一种可能方法就是反复使用经典（一次性）TSP的最优路线。然而，这个解可能并非最优。事实上，对于这个例子，可以构建一个行程计划，使得每个城市被访问两次，总成本低于2×11=22美元。该计划由图2中描绘的三个（哈密顿）行程组成。

迭代此行程计划将每次访问的成本降至(8+8+5)/2=10.50美元<11美元。

当每个城市访问三次时，成本节约进一步增加。事实上，图3中描绘的四个行程计划将每次访问成本降至(9+9+8+5)/3=10?。

先前的例子引发了关于平均成本随访问次数无限增加时的渐近行为的问题。对于每种访问频率，每次访问的最小平均成本是在所有达到该频率的计划中总成本最低者的总成本除以该频率。对于前述访问频率，每次访问的最小平均成本随访问次数增加而下降。尽管这种关于访问次数的单调性并非一般性结论，我们将证明当访问次数增加时，平均成本最终会收敛。为了捕捉无限时间范围的概念，我们令访问次数趋于无穷，并研究每次访问最小平均成本的渐近行为。然后我们询问这一极限成本是否可以通过迭代的行程计划实现，并探讨它应如何在客户之间分配。

我们证明了∞-TSP可以通过利用与合作博弈论中一个解决方案概念——期望核——之间的新颖联系来解决。直观地说，期望核识别出在联盟理性范围内（即没有任何客户群体被收取的费用超过为其服务的成本）覆盖总成本最高的成本分配。因此，当核非空时，期望核与核一致。在这种情况下，大联盟是可持续的：可以找到一种方式将服务大联盟的总成本在其成员之间分享，使得没有客户子集有偏离的动力，因为任何服务他们的替代行程的成本至少与他们被分配的成本份额一样高。

然而，当核为空时，大联盟不再可持续。一种选择是通过ε-核方法放松联盟理性，迫使联盟承担更高的成本；或者，通过减少待分配的总成本。期望核采用后者。这样做时，它自然地导致适当联盟的形成：最有可能出现的联盟是那些在所选分配处联盟理性约束达到紧的联盟。从TSP的角度来看，这些对应于可以以恰好等于其分配成本一起服务的客户群体，使它们成为自我维持的子行程，没有偏离到其他安排的动机。

我们的定理5.2与命题3.2共同建立了：当且仅当相应的（一次性）旅行商博弈（TSG）的核为空时，每次访问成本可以被降低。鉴于每次访问成本有时会随访问次数增加，我们还探讨了当访问次数变大时成本节约的渐近行为。命题5.3找到了这些节约所收敛的极限。

我们的结果突出了期望核解决方案概念与∞-TSP之间的密切关系。特别是，我们证明了：

1. 每次访问最小成本的渐近值由期望核向量的汇总成本分配决定。
2. 实现渐近最小平均每次访问成本的最优行程计划可以借助期望核建议的联盟来构建。
3. 最优行程的成本可以分配给客户，使得没有任何联盟可以改善它。

由于期望核通常不是单值的，可能存在多个最优访问策略。挑战在于如何在它们之间进行选择。我们提出了一个从期望核中进行具体单值选择的概念，在文献中称为期望核仁（Bennett, 1983）。期望核仁——与Schmeidler（1969）定义的原始核仁相关但不同——继承了核仁的若干理想性质，包括非空性、唯一性和匿名性。这些性质中的每一个对于本文研究的问题都具有实际意义。

如果我们认为期望核分配是稳定的——因为每个联盟被收取的费用低于其独立成本，从而没有任何联盟有脱离的动力——那么期望核仁可以被描述为以在所有联盟中最大化"节约"的方式选择其中最稳定的分配，从最不利的一个开始。这里的"节约"指的是服务一个联盟所发生的成本与其分配成本之间的差额。该程序首先选择最大化最差联盟节约的分配。在通过这些步骤的分配中，它选择最大化第二不满足联盟节约的那些分配，依此类推。该过程继续以这种方式进行，逐步改善处境越来越好的联盟的位置，直到只剩下一个唯一的分配。这个分配就是期望核仁。因为期望核仁是一个不依赖于参与者名称的解决方案概念（因此它是匿名的），它保留了博弈的所有对称性。

本文的组织如下：第2节将本文置于经济学和运筹学文献中；第3节定义了问题并给出了相关（一次性）TSG的核为空的例子；第4节引入了期望核及其若干性质；第5节包含我们的主要结果，将期望核应用于相关的TSG并分析该合作解决方案概念所提出的替代解；第6节描述了期望核仁作为期望核的单值选择；第7节为结论。

## 文献

除了作为路由问题的角色外，经典旅行商问题（TSP）已从合作博弈的角度进行了广泛研究。在这种设定中，每个客户联盟被赋予服务其成员所需的最小成本，产生一个合作成本博弈，称为旅行商博弈（TSG），由Potters等人（1992）引入。主要目标是在客户之间分配服务大联盟的成本，同时满足某些理想性质。

## 形式化的∞-TSP问题

TSP可以通过加权、连通、不一定是完全图的有向图G=(V,A,l)在数学上表示，其中V、A和l定义如下。V?{0}∪N是一个有限节点集，其中0表示枢纽（或母城）的位置，每个i∈N是客户的位置。A?{(i,j)?V×V∣i≠j}是V中节点之间的弧集合。当上述包含关系以等号成立时，称图为完全图。函数l:A→R?为每条弧关联一个长度（或权重，或成本）l。

## 期望核

设(N,c)为一个合作成本博弈，其中N是一个有限集，c:2?→R?是一个特征（成本）函数，满足c(?)=0。(N,c)博弈的期望核，记为AC(c)，是那些覆盖最高总成本的联盟理性分配的子集。?因此，AC(c)=argmax{x(N)∣x(S)≤c(S),?S?N}。

## 将期望核应用于TSG

为明确概念，考虑以下例子。

**例5.1** 一个服务提供商必须无限多次访问6个不同的客户。客户的位置通过道路连接，如图4所示。?行程必须从服务提供商的枢纽出发并结束于该枢纽，该枢纽被标记为节点0。使用任何道路的代价均为1美元。

访问所有城市的最小成本为c(N)=8，如图所示。

## 选择唯一的成本分配

由于期望核通常不是单值的，我们接下来描述一种从期望核分配集合中选择一个单一成本分配向量的程序。我们的方法论使用了期望核仁的概念，该概念由Bennett（1981）引入。

激励核仁除了位于激励核之外，还具有若干其他优良性质，包括非空性、唯一性、平等对待同等项以及匿名性。

结论性评述

我们提出并分析了无限周期旅行商问题（∞-TSP），该问题是对经典旅行商问题（TSP）的扩展，考虑了在不确定的无限规划期内对客户地点的重复访问。我们的目标是在确保客户之间成本稳定分配的前提下，最小化长期（或渐近）的每次访问平均成本，这里的稳定是指没有任何联盟被收取超过为其成员提供服务的成本。

本文借鉴了合作博弈论中相对尚未充分探索的研究成果。

CRediT作者贡献声明

Camelia Bejan：撰写–审稿与编辑，撰写–初稿，项目管理，形式化分析，概念构思。

Juan Camilo Gómez：撰写–审稿与编辑，撰写–初稿，项目管理，形式化分析，概念构思。

利益冲突声明

作者声明不存在已知的、可能影响本文所报道工作的竞争性经济利益或个人关系。

致谢

Juan Camilo Gomez 衷心感谢华盛顿大学博塞尔分校商学院通过教职员工暑期研究薪资支持基金提供的资金支持。

Camelia Bejan | Juan Camilo Gómez