含优先级约束的旅行商问题研究*

□ 张思龙

(上海交通大学 中美物流研究院,上海 200030)

旅行商问题(TSP)广泛存在于物流服务、交通运输、生产制造等应用场景中，高效的求解方法有助于减小操作成本、提升服务效率。很多学者致力于研究这一问题的精确算法和近似解法，在这方面的杰出贡献有Lawler等和Gutin等。如果实际问题存在优先级约束，此时问题变为含优先级约束的旅行商问题(TSP-PC)。TSP是TSP-PC的一种特殊情况，因此TSP-PC属于NP-hard问题。

Mingozzi等在考虑含时间窗以及优先级约束的TSP时，提出了相应的动态规划算法，并采用定界函数去减小状态空间的规模。Moon等采用遗传算法求解TSP-PC时，使用拓扑排序以及一种新的交叉算子来增加解的多样性。Deineko等和Burkard等研究了某些关于TSP的变种。

虽然已经有不少学者获得了丰富的研究成果和经验，由于问题的复杂性，求解大规模问题的精确解仍然有着不小的挑战。为了更好的解决该问题，本文先给出该问题的数学模型，然后提出动态规划精确解法，最后进行相关的数值实验。

1 问题描述与数学模型

1.1 问题描述

TSP-PC的目标在于找到一条满足以下两个条件的最短的路径：①该路径经过图中所有结点刚好一次；②优先级较高的结点必须先于优先级较低的结点被访问，即访问优先级较低的结点之前，必须保证优先级比它高的结点都已经被该路径访问。

需要注意的是，两个结点i和j之间的优先级关系有三种：①i的优先级高于j，此时在访问j之前必须确保i已经被访问；②i的优先级低于j，此时在访问i之前必须确保j已经被访问；③i的优先级和j的优先级相等，此时不对i和j之间的相对次序作出要求。

为了进一步阐明问题，有必要使用算例做出形象解释。表1是图中5个结点的之间的距离矩阵，表2是优先级关系表，可以转化为图1所示的优先级拓扑图。路径{e13,e32,e24}没有访问到所有结点，路径{e13,e32,e24,e42,e25}把结点2访问了2次，路径{e12,e23,e34,e45}违反了结点2和结点3之间的优先级约束，所以它们都不是可行的路径。路径{e13,e32,e24,e45}虽然可行，但是它的长度为18，显然过大。实际上，该算例的最优解是路径{e34,e41,e12,e25}，长度为13。

表1 距离矩阵表

表2 优先级关系表

图1 优先级拓扑图

1.2 数学模型

建立数学模型可以使定义变得更加精准，描述变得更加清晰和严密。为此我们首先介绍它所涉及到的集合、参数、决策变量，然后建立一个整数线性规划模型。

1.2.1 下标和集合

0：虚拟的起始结点和虚拟的终止结点；

V：V={1,2,…,N}是图中结点的集合；

V0：包含虚拟起止点的结点的集合，V0=V=V∪{0}；

i,j：结点的下标；

Pi：优先级低于结点的结点的集合。

1.2.2 参数

N：图中结点的数量；

dij：弧eij的长度。

1.2.3 决策变量

xij：二元变量，当且仅当路径经过弧eij时取值为1，否则取值为0；

yi：整数变量，取值范围是{1,2,…,N}，代表结点i在路径中的次序。

1.2.4 整数线性规划模型

(1)

(2)

(3)

yj-yi>(xij-1)N,i∈V0,j∈V:i≠j

(4)

yi

(5)

y0=0

(6)

1≤yi≤N,integer,i∈V

(7)

xij∈{0,1},i∈V0,j∈V0:i≠j

(8)

式(1)是目标函数，表示最小化路径的长度。式(2)和式(3)是流平衡约束，要求每个结点的入度和出度均为1，以保证每个结点刚好被访问一次。式(4)是为了消除子回路。优先级约束体现在式(5)中，确保优先级较高的结点一定先被访问。式(6)-(8)表明决策变量的类型和取值范围。

2 求解算法

动态规划通过逐步递推最优子结构得到最终的最优解，而且能够消除冗余的中间状态，可以非常高效地求解TSP-PC问题。为了阐述求解该问题的动态规划算法，本节内容首先定义若干符号和算子，然后给出状态转移方程，最后描述算法流程。

2.1 符号和算子

应该注意到，如前述算例所示，输入的数据Pi只是包含了直接的优先级关系，间接的优先级关系并未被考虑。例如，由P3={2,4},P4={5}得知，结点3的优先级比结点5高。在纷繁复杂的大规模情况下，要想凭肉眼观察出全面的优先级关系并非易事，因此有必要使用如下的GET_PC算法来达到上述目的。

GET_PC算法

输入：优先级关系表Pi,i∈V

输出：后序集Ai,i∈V，先序集Bi,i∈V，无序集Ci,i∈V

步骤1：初始化Ai←Bi←Ci←Ø，i∈V,初始化矩阵M：若j∈Pi，则Mij←1；否则Mij←+∞

步骤2：对矩阵M运行弗洛伊德(Floyd)算法

步骤3：对于i∈V，j∈V,i≠j，执行：若Mij

步骤4：输出Ai，Bi,Ci,i∈V算法结束

运行GET_PC算法产生的三种集合的含义分别如下：对于∀j∈Ai,i∈V而言，结点的优先级(直接或者间接)高于结点j，在访问结点j之前必须确保结点i已经被访问；对于∀j∈Bi,i∈V而言，结点的优先级低于结点j，在结点j被访问之后才允许访问结点i；对于∀j∈Ci,i∈V而言，结点i和结点j的优先级相等，先访问哪一个都可以。此外，这三个集合互斥，而且它们的并集等于V{i}，即有|Ai|+|Bi|+|Ci|=N-1和Ai∪Bi∪Ci∪{i}=V。

下面进一步定义一些符号：

H：H是一个结点的集合，且其中所有结点的优先级相等，即对于∀i,j∈H，有j∈Ci；

s：s={H,i},i∈H是一个状态，它对应着一类路径，该类路径访问过的结点集合是W(H)，且最后访问的结点是i；

Q(s)：Q(s)={j:j∈VW(H),∀j2∈VW(H),j2∉Bj}是结点集合，它们尚未被s所对应的路径访问，且在剩下的结点当中，没有任何一个结点的优先级高于它们；

R(s)：表示状态s所对应的最短路径；

St：St={{H,i}:|W(H)|=t,i∈V},t∈{1,2,…，N}是一类状态的集合，这类状态所对应的路径访问过的结点数量为t；

F(s)：目标函数，表示状态s所对应最短路径的长度；若{H,i}∉St，t=|W(H)|,则F({H,i})=+∞。

2.2 状态转移方程

有了上述定义之后，现在给出状态转移条件：

j∈Q({H,i}),H′=H∪{j}Bj,F({H,i})+dij

(9)

上式对结点j做了明确要求，且指出了H′的形式：它等于原有集合H并入结点j之后，再减去所有优先级比j高的结点。另外，只允许发生让路径的长度变得更短的状态转移。在式(9)被满足的情况下，状态转移如下进行：

F({H′,j})=F({H,i})+dij,R({H′,j})=R({H,i})∪{eij}

(10)

动态规划算法的另一关键部分是边界条件：

F(Ø)=0,R(Ø)=Ø

(11)

2.3 算法流程

具备以上铺垫之后，现在介绍求解TSP-PC的动态规划精确算法。

DP_TSP_PC算法

输入：各结点之间的距离dij，i∈V,j∈V,i≠j，优先级关系表Pi,i∈V

输出：TSP-PC问题的最优解(长度d以及路径r)

步骤1：运行GET_PC算法，得到Ai,Bi,Ci,i∈V

步骤2：初始化：t←1,S0←{Ø},S1←S2←…←SN←Ø

步骤3：对于∀{H,i}∈St-1，∀j∈Q({H,i})，若状态转移条件式(9)被满足，则按照式(10)进行状态转移，且St←St∪{{H′,j}}

步骤4：若t=N，转到步骤5；否则t←t+1，转到步骤3

3 数值实验

介绍数值实验的内容之前，需要再引入一个符号K，它代表着H中所包含结点的数量的上限|H|max。实际上，K的值由优先级关系中的Ci,i∈V唯一确定。这是因为H中各个结点的优先级相等，即∀j1,j2∈H,j1≠j2，一定有j1∈Cj2(j2∈Cj1也会自然成立)。

本文实验使用C++语言编写的程序，在酷睿四核I7-7700HQ(2.80GHz)和16GB内存的计算机上，求解15个不同规模的随机算例来验证算法的效率。如表3所示，值、值越大，算例越复杂。

K值较小的时候求解速度很快，程序能在数秒内给出最优解。即使N=100,K=15的时候，最优解也能在6分钟以内求得。另外，可以看出当N值不变时，K值的增长导致求解时间增长的幅度特别大，远比当K值不变时单纯增大N值带来的影响强烈，这说明当K值不是特别大的时候，K值对复杂度的影响比网络中结点总数N值的影响要大。

表3 不同规模算例所耗费的时间 (单位：秒)

4 总结

本文研究了含优先级约束的旅行商问题(TSP-PC)的模型和算法，并对算法做了相关分析和数值实验。在此过程中，建立了整数线性规划模型，但是由于该问题属于NP-hard问题，所以直接使用求解器求解模型是不够高效的，为此本文提出了相应的状态表示方法及动态规划算法。通过数值实验证明了该算法的高效性，多达100个结点的TSP-PC问题的最优解能被很快地求出来。在后续的研究中，可以着手考虑寻找比较好的上界和下界，使动态规划过程中出现的状态数量减少，从而加快求解速度。