基于LINGO的旅行商问题的建模方法*

王继强

(山东财经大学数学与数量经济学院，山东 济南 250014)

基于LINGO的旅行商问题的建模方法*

王继强

(山东财经大学数学与数量经济学院，山东 济南 250014)

旅行商问题是图论中一类经典的最优化问题，其研究对于其他图优化问题的解决具有重要的理论意义和实际价值。针对旅行商问题建模中的困难之处——如何避免“分割”现象，提供了三种不同的解决方法，并给出了基于当今最流行的优化计算软件LINGO的实证分析。

旅行商问题；模型；整数规划；LINGO

1 引言

在图论中，图是由顶点和边两个要素构成的拓扑结构，其中顶点表示对象，边表示对象之间的关系。任何两相异顶点之间恰好存在唯一一条边的图称为完全图；在图中，顶点和边交错出现的一个序列称为链，边不重复出现的一个封闭序列称为圈，遍历所有顶点的圈称为哈密尔顿圈。

旅行商问题又称旅行售货员问题或货郎担问题，是一个经典的图的优化问题[1～3]，其内容是：一个商人要从自己所在的城市出发去若干个城市销售商品，经过其余各城市恰好一次后，再回到出发地。若任意两个城市之间的距离已知，问：他应如何选择旅行路线，才能使总旅程最短？

从图的角度看，旅行商问题是要从一个边赋权的完全图中找出一个边权之和最小的哈密尔顿圈---最优哈密尔顿圈。遗憾的是，旅行商问题是著名的NP-困难问题之一，即它不可能存在多项式时间精确算法，除非P=NP；然而，随着计算机科学与技术的迅猛发展，特别是LINGO、LINDO[4～6]等高性能计算软件的成功研发与广泛应用，即便在图的规模相当大时，人们也仍然能够迅速地求得其最优解。

为便于建立旅行商问题的数学模型，不妨假设：旅行商从城市1出发，遍访城市2、…、n各一次后，再回到城市1；城市i和j之间的距离为dij，其中dii=+∞，这一假设将使得最优旅行路线中不可能存在从城市i到i的环。在实际计算中，+∞可用一个充分大的正数来代替。

2 模型建立

首先引入决策变量：

则目标函数为：

约束条件为：

此外，xij=0,1；i,j=1,…,n。

不难知道，满足以上约束条件的变量xij(i,j=1,…,n)不一定构成一条可行的旅行路线。如在n=6的旅行商问题中，令x12=x23=x31=1，x45=x56=x64=1，其余xij=0，则不难验证它们对应问题的一个可行解，但却构成如图1所示的多回路“分割”现象。

Figure 1 Phenomenon of separation图1 “分割”现象

因此，应在模型中添加约束条件，以避免“分割”现象的发生。

下面重点介绍三种避免“分割”现象的方法。

2.1 方法一

2.2 方法二

对于上述两种方法，注意到城市集合{1,2,…,n}的非空真子集共有2n-2个，当然上述约束条件也有2n-2个，这要求在实际计算中需有一定的编程技巧。

2.3 方法三

为避免出现上述多回路“分割”现象，还需特别增加下列约束条件[6]：

其中，ui≥0(i=1,…,n)是为了构造上述约束条件而特别针对每一顶点引入的辅助变量，没有实际意义。

证明

(1)任一存在多回路“分割”现象的旅行路线都不满足上述约束条件(无论ui、uj如何取值)。

事实上，若某一旅行路线存在多回路“分割”现象，则它至少有两个回路，从而至少有一个回路不含城市v1，如图1中回路v4→v5→v6→v4，即x45=x56=x64=1,但变量u4、u5、u6及x45、x56、x64一起并不满足下列约束条件：

这是因为上述三个不等式左、右分别相加后将得出矛盾的结果：18≤15。

(2)任一可行的旅行路线都满足上述约束条件(只要ui、uj适当取值)。

事实上，设v1→vs→vt→…→vi→vj→…→vk→v1是一条可行的旅行路线(即TSP的一个可行解为x1s=xst=…=xij=…=xk1=1，其余xij=0)，则令ui=i-1，uj=i。于是，对xij=1，上述约束条件变为(i-1)-i+n≤n-1，显然成立；对xij=0，上述约束条件变为(i-1)-i+0≤n-1，显然成立。

□

综上所述，可建立如下混合整数规划模型：

3 实证分析

算例六个城市，距离矩阵如表1所示。

Table 1 Distance matrix

下面以方法三提供的模型为例编写如下LINGO程序：

model:

sets:

city/1..6/:u;

link(city,city):dist,x;

endsets

data:

dist= 99999,702,454,842,2396,1196,

702,99999,324,1093,2136,764,

454,324,99999,1137,2180,798,

842,1093,1137,99999,1616,1857,

2396,2136,2180,1616,99999,2900,

1196,764,798,1857,2900,99999;

enddata

n=@size(city);

min=@sum(link:dist*x);

@for(city(k):@sum(city(i)|i #ne# k:x(i,k))=1;

@sum(city(j)|j #ne# k:x(k,j))=1;);

@for(city(i):@for(city(j)|j #gt# 1 #and# i #ne# j:u(i)-u(j)+n*x(i,j)<=n-1););

@for(city(i):u(i)<=n-1);

@for(link:@bin(x));

end

在LINGO 10.0上运行程序返回如下结果：(限于篇幅，仅给出主要部分)

Global optimal solution found at iteration:96

Objective value:6610.000

Variable Value Reduced Cost

X(1, 1) 0.000000 0.000000

X(1, 2) 0.000000 702.0000

X(1, 3) 1.000000 454.0000

X(1, 4) 0.000000 842.0000

X(1, 5) 0.000000 2396.000

X(1, 6) 0.000000 1196.000

X(2, 1) 0.000000 702.0000

X(2, 2) 0.000000 0.000000

X(2, 3) 0.000000 324.0000

X(2, 4) 0.000000 1093.000

X(2, 5) 1.000000 2136.000

X(2, 6) 0.000000 764.0000

X(3, 1) 0.000000 454.0000

X(3, 2) 0.000000 324.0000

X(3, 3) 0.000000 0.000000

X(3, 4) 0.000000 1137.000

X(3, 5) 0.000000 2180.000

X(3, 6) 1.000000 798.0000

X(4, 1) 1.000000 842.0000

X(4, 2) 0.000000 1093.000

X(4, 3) 0.000000 1137.000

X(4, 4) 0.000000 0.000000

X(4, 5) 0.000000 1616.000

X(4, 6) 0.000000 1857.000

X(5, 1) 0.000000 2396.000

X(5, 2) 0.000000 2136.000

X(5, 3) 0.000000 2180.000

X(5, 4) 1.000000 1616.000

X(5, 5) 0.000000 0.000000

X(5, 6) 0.000000 2900.000

X(6, 1) 0.000000 1196.000

X(6, 2) 1.000000 764.0000

X(6, 3) 0.000000 798.0000

X(6, 4) 0.000000 1857.000

X(6, 5) 0.000000 2900.000

X(6, 6) 0.000000 0.000000

因此，最优旅行路线为1→3→6→2→5→4→1，其长度为96。

算例表明模型是正确的，根据模型设计的程序也是可行的。

4 结束语

本文首先分析了旅行商问题的难解性，然后借助数学规划方法建立了其混合整数规划模型，最后给出了基于LINGO软件的程序设计，从而技术性地避开了问题本身的NP-困难性，使问题的求解过程更便捷、更高效。当然，近似算法、启发式算法、遗传算法等也是求解旅行商问题的可能选择，值得另行研究。

[1] Zhu Dao-li,Xu Qing,Ye Yao-hua.Operations research[M]. Beijing:Higher Education Press, 2006.(in Chinese)

[2] Hu Yun-quan, Guo Yao-huang. The course of operations research[M]. 3rd edition.Beijing:Tsinghua University Press, 2007.(in Chinese)

[3] The compiling team of the course of operations research. The course of operations research[M]. Beijing:National Defense Industry Press, 2012.(in Chinese)

[4] Xue Yi,Geng Mei-ying.Operations research and experiments[M]. Beijing:Publishing House of Electronics Industry, 2008.(in Chinese)

[5] Xie Jin-xing, Xue Yi. Optimization modeling and LINGO/LINDO softwares[M]. Beijing:Tsinghua University Press, 2006.(in Chinese)

[6] Yuan Xin-sheng, Shao Da-hong, Yu Shi-lian. Applications of LINGO and EXCEL in mathematical modeling[M]. Beijing:Science Press, 2007.(in Chinese)

[7] Wei Guo-hua,Wang Fen.Linear programming[M]. Beijing:Higher Education Press, 1989.(in Chinese)

[8] Si Shou-kui, Sun Xi-jing. Algorithms of mathematical modeling with applications[M]. Beijing:National Defense Industry Press, 2011.(in Chinese)

附中文参考文献：

[1] 朱道立, 徐庆, 叶耀华. 运筹学[M]. 北京:高等教育出版社, 2006.

[2] 胡运权, 郭耀煌. 运筹学教程[M]. 第三版.北京:清华大学出版社, 2007.

[3] 运筹学教程编写组. 运筹学教程[M]. 北京:国防工业出版社, 2012.

[4] 薛毅, 耿美英. 运筹学与实验[M]. 北京:电子工业出版社, 2008.

[5] 谢金星, 薛毅. 优化建模与LINGO/LINDO软件[M]. 北京:清华大学出版社, 2006.

[6] 袁新生, 邵大宏, 郁时炼. LINGO和EXCEL在数学建模中的应用[M]. 北京:科学出版社, 2007.

[7] 魏国华, 王芬. 线性规划[M]. 北京:高等教育出版社, 1989.

[8] 司守奎, 孙玺菁. 数学建模算法与应用[M]. 北京:国防工业出版社, 2011.

WANGJi-qiang,born in 1976,PhD,associate professor,his research interests include combinatorial optimization, and theoretical computer science.

LINGO-basedmodelingmethodsforthetravelingsalesmanproblem

WANG Ji-qiang

(School of Mathematics and Quantitative Economics,Shandong University of Finance and Economics,Jinan 250014,China)

The traveling salesman problem is a classical optimization problem in graph theory. Its research has important theoretical meaning and practical value for other graphic optimization problems.Aiming at the difficulty in modeling the traveling salesman problem-how to avoid the “separation”phenomenon, three different solutions are proposed. Finally,a case study based on LINGO,the most popular optimization softwares, is given.

traveling salesman problem;model;integer program;LINGO

1007-130X(2014)05-0947-04

2012-11-12;

：2013-03-05

国家自然科学基金资助项目(10901093)

Q784;TP301.6

：A

10.3969/j.issn.1007-130X.2014.05.027

王继强(1976-),男,山东枣庄人，博士，副教授，研究方向为组合最优化和理论计算机科学。E-mail:sdcdmcm@126.com

通信地址：250014 山东省济南市山东财经大学数学与数量经济学院

Address:School of Mathematics and Quantitative Economics,Shandong University of Finance and Economics,Jinan 250014,Shandong,P.R.China