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

交通运输、生产制造等应用场景中，高效的求解方法有助于减小操作成本、提升服务效率。基于跪，文中建立了描述该 问题的整数线性规划模型，设计了相应的动态规划精确算法。相关的数值实验表明，该算法可以高效地求出不同规模

的问题的最优解。【关键词】旅行商问题;优先级约束;动态规划【中图分类号】F272

【文献标识码】B 【文章编号】1674 -4993(2019)12 -0086 -03Research on the Travelling Salesman Problem with Precedence Constraints□ ZHANG Si -long(Sino - US Global Logistics Institute,Shanghai Jiaotong University,Shanghai 200030,China)[Abstract] Travelling Salesman Problem (TSP) is a classic combinatorial optimization problem,which focuses on finding a shortest route which visits all the vertices in a graph exactly once. However, the route is often required to satisfy precedence constraints in practical applications. In this occasion, the problem is called Travelling Salesman Problem with Precedence

Constraints (TSP -PC). Since it is frequently found in some applications including logisitics,transportation and manufacturing,

an efficient methodology can contribute to the reduction of operation cost and the promotion of service. In order to achieve this

goal,this paper has described this problem by an integer linear programming model and designed an exact dynamic programming

algorithm. As is shown in the numerical experiments, different scales of TSP - PC can be solved to the optimality efficiently by the

algorithm.[Key words] travelling salesman problem；precedence constraints;dynamic programming旅行商问题（TSP）广泛存在于物流服务、交通运输、生产 制造等应用场景中，高效的求解方法有助于减小操作成本、提

1问题描述与数学模型1.1问题描述升服务效率。很多学者致力于研究这一问题的精确算法和近 似解法，在这方面的杰出贡献有Lawler等和Gutin等。如果实

在一个图g =（卩卫）中:点集卩={1,2,…,M是图中结点的集合，其中N是图中结点的数量;弧集旬是图中弧的集合，其中勺是从结点i指向结点j的弧，弧勺

际问题存在优先级约束,此时问题变为含优先级约束的旅行 商问题（TSP-PC）。TSP是TSP - PC的一种特殊情况，因此

TSP - PC 属于 NP - hard 问题。的长度用£表示。图中的一条路径（形如r= {%；2，e翻， e奶}）可以用一系列首尾相连的弧表示，路径的长度比=2

e严r

Mingozzi等在考虑含时间窗以及优先级约束的TSP时，提

碣等于各条弧的长度之和。TSP-PC的目标在于找到一条满足以下两个条件的最短

出了相应的动态规划算法，并采用定界函数去减小状态空间 的规模。Moon等采用遗传算法求解TSP - PC时,使用拓扑排

的路径:①该路径经过图中所有结点刚好一次;②优先级较高 的结点必须先于优先级较低的结点被访问，即访问优先级较

序以及一种新的交叉算子来增加解的多样性。Deinek。等和 Burkard等研究了某些关于TSP的变种。低的结点之前，必须保证优先级比它高的结点都已经被该路 径访问。虽然已经有不少学者获得了丰富的研究成果和经验，由 于问题的复杂性,求解大规模问题的精确解仍然有着不小的

需要注意的是,两个结点i和j之间的优先级关系有三

挑战。为了更好的解决该问题,本文先给出该问题的数学模

种:①i的优先级高于j,此时在访问j之前必须确保i已经被 访问;②i的优先级低于j,此时在访问i之前必须确保j已经

型，然后提出动态规划精确解法,最后进行相关的数值实验。【收稿日期】2019-09-18*基金项目：上海交通大学文理交叉基金（编号:17JCYA04）【作者简介】张思龙（1994—）,男,上海交通大学，中美物流研究院，硕士 （在读），研究方向:物流管理。第12期张思龙:含优先级约束的旅行商问题研究87被访问;③Z的优先级和j的优先级相等，此时不对i和j之间

的相对次序作出要求。为了进一步阐明问题，有必要使用算例做出形象解释。

表1是图中5个结点的之间的距离矩阵，表2是优先级关系 表,可以转化为图1所示的优先级拓扑图。路径｛ 屜闷｝ 没有访问到所有结点，路径｛ e13 ,e32畑,e42 ,劭!把结点2访问 T 2次，路径｛ %畑闷心｝违反了结点2和结点3之间的

优先级约束，所以它们都不是可行的路径。路径｛ e】3工32工朗，

虽然可行，但是它的长度为1\"显然过大。实际上，该算

例的最优解是路径｛刘屜屜i，长度为13 o表1距离矩阵表距离结点1结点2结点3结点4结点5结点104738结点240621结点376054

结点43250

3结点581430表2优先级关系表结点i

P,(优先级低于结点i的结点的集合)1 !2)2 03

｛2,4｝4

⑸1.2数学模型建立数学模型可以使定义变得更加精准,描述变得更加 清晰和严密。为此我们首先介绍它所涉及到的集合、参数、决 策变量，然后建立一个整数线性规划模型。1.2.1下标和集合0：虚拟的起始结点和虚拟的终止结点；V：V二｛1,2,…,M是图中结点的集合；% :包含虚拟起止点的结点的集合,％二V二VU ｛0｝；

结点的下标；E:优先级低于结点的结点的集合。1.2.2参数M图中结点的数量；S：弧夠的长度。1.2.3决策变量叫:二元变量，当且仅当路径经过弧夠时取值为1,否则取

值为0；兀:整数变量，取值范围是代表结点》在路

径中的次序。1.2.4整数线性规划模型min . v^v.dijXij(1)s. t.

ioEX x--可 = 1,/ e V(2)jwVoX： i#j XyJ V⑶为一兀 >(% —l)N，淀 VoJeVJHj(4)Ji (3)是流平衡约束，要求每个结点的入度和出度均为1,以保

证每个结点刚好被访问一次。式(4)是为了消除子回路。优 先级约束体现在式(5)中,确保优先级较高的结点一定先被访

问。式(6)-(8)表明决策变量的类型和取值范围。2求解算法动态规划通过逐步递推最优子结构得到最终的最优解，

而且能够消除冗余的中间状态,可以非常高效地求解TSP- PC问题。为了阐述求解该问题的动态规划算法，本节内容首

先定义若干符号和算子，然后给出状态转移方程,最后描述算

法流程。2.1符号和算子应该注意到，如前述算例所示，输入的数据P,只是包含 了直接的优先级关系，间接的优先级关系并未被考虑。例如, 由厶二｛2,4｝,匕二｛5｝得知，结点3的优先级比结点5高。

在纷繁复杂的大规模情况下，要想凭肉眼观察出全面的优先 级关系并非易事，因此有必要使用如下的GET_PC算法来达 到上述目的。GET_PC算法输入:优先级关系表PJwV输出:后序集4,淀v,先序集5,淀v,无序集G u步骤1:初始化ArBHiw v,初始化矩阵m：若j

丘4，则叫—1;否则M帀- + OO步骤2:对矩阵M运行弗洛伊德(Floyd)算法步骤3 ：对于淀V,j e V, i列,执行:若MjjCN,则人U ｛；!；若叫 ；否则｛/步骤4 ：输出4, ,5, C,,淀V算法结束运行GET_PC算法产生的三种集合的含义分别如下:对 于VjeA,Ze V而言,结点的优先级(直接或者间接)高于结 点在访问结点j之前必须确保结点i已经被访问;对于Vje BJwV而言，结点的优先级低于结点j,在结点j被访问之后

才允许访问结点：;对于WeCJeV而言,结点i和结点j的

优先级相等，先访问哪一个都可以。此外，这三个集合互斥， 而且它们的并集等于八⑴，即有1人1 +IBJ + ICJ二N-1和

4U5UGUM =yo下面进一步定义一些符号：88物流工程与管理第41卷H：H是一个结点的集合，且其中所有结点的优先级相等, 即对于有jwC；;W(H):W(H) = {j:j£UB!UH}包含H中所有的结点以 及叭H中所有比H中某结,養的优先级更高的结点；s：s=\\H,i\\ ,iwH是一个状态，它对应着一类路径，该类

路径访问过的结点集合是叭H),且最后访问的结点是i;Q(s) :Q(s) = \\j-.j e V\\W(H)，町2 e V\\W(H) ,j2 g 鸟}是

结点集合，它们尚未被s所对应的路径访问，且在剩下的结点 当中，没有任何一个结点的优先级高于它们；R(s):表示状态s所对应的最短路径；S,：S, = I =t,i£V} ,te\\l,2,-,N}是一类状态的集合，这类状态所对应的路径访问过的结点数量

为t；F(s):目标函数，表示状态s所对应最短路径的长度;若

{H,i\\ 则 F({H,讣)=+8。2.2状态转移方程有了上述定义之后，现在给出状态转移条件：iff.il) ,H' =HU\\j\\

) + 如 (9)上式对结点j做了明确要求，且指出了 H'的形式:它等于 原有集合H并入结点j之后,再减去所有优先级比j高的结

点。另外,只允许发生让路径的长度变得更短的状态转移。 在式(9)被满足的情况下,状态转移如下进行：

F({H\") =F({H,讣)+£,R({HJ) =R({H,i})U {唧(10)动态规划算法的另一关键部分是边界条件:F(0) =O,R(0) =0

(11)2.3算法流程具备以上铺垫之后,现在介绍求解TSP-PC的动态规划

精确算法。DP_TSP_PC 算法输入:各结点之间的距离d^,is V,jwV,详j,优先级关系 表 Pt,i^V输出:TSP - PC问题的最优解(长度d以及路径r)步骤1:运行GET_PC算法，得到步骤2：初始化詁•<—1 ,S()<—{ 0} ,S1^—S2<----•<—S”<—0步骤3：对于若状态转移 条件式(9)被满足，则按照式(10)进行状态转移，且S,—S, U

{{刃川步骤4 ：若t = N,转到步骤5 ；否则t—t + 1，转到步骤3步骤 5 : d = minF(s)seSjy ,r=7?(s)：F(s) = d,s e SN,输出 d 和r,算法结束3数值实验介绍数值实验的内容之前,需要再引入一个符号K,它代

表着H中所包含结点的数量的上限实际上,K的值由 优先级关系中的 U唯一确定。这是因为H中各个结点

的优先级相等,即Vj； ,j2 e H,j\\列2，—定有Ji e C”匕e Cfl也

会自然成立)。本文实验使用C+ +语言编写的程序，在酷睿四核17-

7700HQ(2. 80GHz)和16GB内存的计算机上，求解15个不同

规模的随机算例来验证算法的效率。如表3所示，值、值越 大,算例越复杂。K值较小的时候求解速度很快，程序能在数秒内给出最

优解。即使N = 100 ,K = 15的时候,最优解也能在6分钟以内 求得。另外，可以看出当N值不变时,K值的增长导致求解时

间增长的幅度特别大，远比当K值不变时单纯增大N值带来

的影响强烈，这说明当K值不是特别大的时候,K值对复杂度 的影响比网络中结点总数N值的影响要大。表3不同规模算例所耗费的时间(单位:秒)K值N值K = 3K = 6K = 9K = 12K = 15TV = 250. 0010. 0030. 0150.1862. 048N = 500. 0020. 0200. 1751.0785. 7087V = 750. 0020. 0410. 2612. 34617.6817V = 1000.0030.0290.30437.857342.8244总结本文研究了含优先级约束的旅行商问题(TSP-PC)的模 型和算法，并对算法做了相关分析和数值实验。在此过程中，

建立了整数线性规划模型,但是由于该问题属于NP-hard问 题，所以直接使用求解器求解模型是不够高效的,为此本文提

出了相应的状态表示方法及动态规划算法。通过数值实验证 明了该算法的高效性，多达100个结点的TSP- PC问题的最 优解能被很快地求出来。在后续的研究中，可以着手考虑寻 找比较好的上界和下界,使动态规划过程中出现的状态数量 减少,从而加快求解速度。[参考文献][1 ] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B.Shmoys. The traveling salesman problem - a guided tour of

combinational optimization [ DB/OL ] . Wiley, Chichester,

1985：87-143.[2] G. Gutin, A. P. Punnen. Dynamic programming strategies for

the traveling salesman problem with time window and preced­

ence constraints [ DB/OL ]. Kluwer, Dordrecht, 1997.[3] A. Mingozzi, L. Binaco, S. Ricciardelli. Dynamic program -

ming strategies for the traveling salesman problem with time window and precedence constraints [ J ]. Operations

Research, 1997,45(3) ：365 -377.[4] C. Moon, J. Kim, G. Choi, Y. Seo. An efficient genetic

algorithm for the traveling salesman problem with precedence constraints [ J ]. European Journal of Opertional Research,

2002,140(3):606-617.[5] V. G. Deineko,G. J. Woeginger. The convex - hull 一 and - k

-line travelling salesman problem [ J ]. Information Processing Letters, 1996,59(6) ：295 -301.(下转第121页)第12期钱 琦等:农产品销售020模式分析121的食材处理存有安全隐患质疑，所以绝大多数情况下倾向于自 己烹饪处理。更重要的是,他们对于电子支付技术或者其他信

到线下门店换取相应奖品,从而吸引线上的人群到线下体验。 线下则不定期给予较大优惠，像限量T元换购”，“满多少减

息技术的不熟悉，是他们尝试020模式的最大障碍。4 020模式未来的发展战略多少”，利用人们的“实惠”心理以及蜂鸣效应间接进行品牌 的传播和扩散。在门店也可以推行扫码关注公众号首单减免 活动,吸引一部分线下群体到线上平台，同时也可以通过在线

4.1明确规定农产晶采购标准,进一步扩大晶牌经营生鲜电商可以将资金和技术应用于生产基地，咨询农户 上平台发布一些优惠信息使线下群体知悉。尤其针对对于电 子技术不是很熟悉，或是对产品安全和健康存有质疑的老年

意见建立农产品种植标准体系;以市场需求为导向，严格把控 源头产品质量，实施标准化生产，扩大农户参与型的品牌化

人,可以在门店提供试吃,并赠送一些小礼物，像扇子,纸盒纸

经营。4.1.1实现标准化种植巾等，在上面印有线上线下商城的二维码和优惠信息，告知他

们可以让子女通过扫描二维码在线上商城下单然后配送到 户，从而避免老人频繁的远途运输。标准化种植就是将一定的科学标准应用于农产品的种

植，使农产品的产量和质量都出现一定程度的提高，从而使农

产品产值也逐渐向最大化靠拢。4.1.2建立农产品“溯源”机制[参考文献][1] 章胜勇，时润哲，于爱芝.农业供给侧改革背景下农产晶

建立农产品“溯源”机制。可以通过动态跟踪农产品生长 批发市场的功能优化分析[J].北京工商大学学报(社会 科学版),2016(6).[2] 郭承龙.农村电子商务模式探析一基于淘宝村的调研

[J].经济体制改革,2015(5) ：110-115,信息，将农产品所有种植信息存入到外包装上唯一对应的二 维码中，这样消费者就可以通过直接扫描商品二维码,获取到

该农产品从生产到检验到采摘等一系列的相关信息〔回O

4.1.3标准化和“个性化”共存[3] 张旭梅，梁晓云，但斌.考虑消费者便利性的“互联网+”

千篇一律的产品销售不可能始用于所有消费者,针对那 生鲜农产品供应链020商业模式[J].当代经济管理，

2018(1) ：21 -27.些追求个性、与众不同的消费者，可以实施定制化的方案来提

升客户满意度。4.2完善物流配送体系[4] 郑红明，叶新仪,陈洁,et al.特色农产品020销售模式研

究[J].商场现代化,2018,870(09) ：9-11,[5] 王纪录.农产話020模式基本框架构建及其运行机制

[J].商业经济研究,2017(8) ： 150-152.① 政府相关部门加大对物流基础设施的投入，制定与完 善法规政策,对物流配送体系进行规范化整治。② 加快和完善先进物流信息技术的应用，如GPS、ITS、 EDI 等。[6] 张建奇.020模式应用于农产品流通现代化的探讨[J].

物流科技,201&[7] 刘壮.特色农产品的020模式问题与对策研究——以山

③ 在农村构建完善的配送中心。形成具有仓储、流通加 工、包装、分拣等功能,并能与采购配送环节相对接的新农产 品配送链;另外，可以利用第三方物流平台已经较为成熟的配

西省古县为例[J].经济师,2017(9).[8] 周娴,郁志芳，杜传来,et al.几种林果低温贮藏的冷害及

送业务，来进一步加强农产品物流网络的辐射范围。其调控研究进展[J].南京林业大学学报：自然科学版，

2004(3) ： 105 -110.④ 培养物流高素质人才。一方面，强化高等院校的物流 教学，提供更多合作实习平台。另一方面，利用农村剩余劳动

[9] 乔丰娟，孙桂娥.基于“互联网+”的020模式生鲜农产

力发展人才队伍，根据能力的不同层次,提供从基层到管理等 岗位差异化的培训⑴)。4.3

品供应链研究——以消费者感知体验为视角[J].江苏农 业科学,2018(1) ：348 -352.[10] 郭承龙.重塑网络消费者初始信任——网誉认证理论探

提高农产晶020模式的关注度，增加用户信任来鼓励用

户参与线上结合线下进行同步宣传。线上可以设计为消费者需

讨[J].图书情报工作,2012,56(10):124-130.[11] 胡以一.供应链模式下020生鲜农产晶采购路径优化研

要通过分享活动链接给好友积累成功邀请数,最后通过积分 究[J].现代商业,2018,No.500( 19) ：19-20.(上接第88页)[6] R. E. Burkard,V. G. Deineko,G. J. Woeginger. The travelling

salesman problem on permuted monge matrices [ J] . Journal

the TSPTW[J], INFORMS Journal on Computing,2002,14

(4) ：403 - 417.[9] T. D. Fry, R. D. Armstrong, J. H. Blackstone. Minimizing

of combinatorial optimization, 1998,2(4) ：333 -350.[7] R. E. Burkard, V. G. Deineko, R. V. Dal, J. A. A. Van Der

Weighted Absolute Deviation in Single Machine Scheduling

[J]. HE Transactions ,1987 ：445 - 450.Veen,G. J. Woeginger. Well - solvable special cases of the

traveling salesman problem: a survey [ J ]. ISAM Review,

[10] A. Sanjeev. Polynomial time approximation schemes for

Euclidean TSP and other geometric problems [ J ].

1998,14(4) ：496-546.[8] F. Focacci, A. Lodi, M. Milano. A hybrid exact algorithm for

Proceedings on 37th Annual Symposium on Foundations of

Computer Science,1996 ：2 -11.