王繼強(qiáng)

(山東財(cái)經(jīng)大學(xué)數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院，山東 濟(jì)南 250014)

基于LINGO的旅行商問(wèn)題的建模方法*

王繼強(qiáng)

(山東財(cái)經(jīng)大學(xué)數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院，山東 濟(jì)南 250014)

旅行商問(wèn)題是圖論中一類(lèi)經(jīng)典的最優(yōu)化問(wèn)題，其研究對(duì)于其他圖優(yōu)化問(wèn)題的解決具有重要的理論意義和實(shí)際價(jià)值。針對(duì)旅行商問(wèn)題建模中的困難之處——如何避免“分割”現(xiàn)象，提供了三種不同的解決方法，并給出了基于當(dāng)今最流行的優(yōu)化計(jì)算軟件LINGO的實(shí)證分析。

旅行商問(wèn)題；模型；整數(shù)規(guī)劃；LINGO

1 引言

在圖論中，圖是由頂點(diǎn)和邊兩個(gè)要素構(gòu)成的拓?fù)浣Y(jié)構(gòu)，其中頂點(diǎn)表示對(duì)象，邊表示對(duì)象之間的關(guān)系。任何兩相異頂點(diǎn)之間恰好存在唯一一條邊的圖稱(chēng)為完全圖；在圖中，頂點(diǎn)和邊交錯(cuò)出現(xiàn)的一個(gè)序列稱(chēng)為鏈，邊不重復(fù)出現(xiàn)的一個(gè)封閉序列稱(chēng)為圈，遍歷所有頂點(diǎn)的圈稱(chēng)為哈密爾頓圈。

旅行商問(wèn)題又稱(chēng)旅行售貨員問(wèn)題或貨郎擔(dān)問(wèn)題，是一個(gè)經(jīng)典的圖的優(yōu)化問(wèn)題[1～3]，其內(nèi)容是：一個(gè)商人要從自己所在的城市出發(fā)去若干個(gè)城市銷(xiāo)售商品，經(jīng)過(guò)其余各城市恰好一次后，再回到出發(fā)地。若任意兩個(gè)城市之間的距離已知，問(wèn)：他應(yīng)如何選擇旅行路線(xiàn)，才能使總旅程最短？

從圖的角度看，旅行商問(wèn)題是要從一個(gè)邊賦權(quán)的完全圖中找出一個(gè)邊權(quán)之和最小的哈密爾頓圈---最優(yōu)哈密爾頓圈。遺憾的是，旅行商問(wèn)題是著名的NP-困難問(wèn)題之一，即它不可能存在多項(xiàng)式時(shí)間精確算法，除非P=NP；然而，隨著計(jì)算機(jī)科學(xué)與技術(shù)的迅猛發(fā)展，特別是LINGO、LINDO[4～6]等高性能計(jì)算軟件的成功研發(fā)與廣泛應(yīng)用，即便在圖的規(guī)模相當(dāng)大時(shí)，人們也仍然能夠迅速地求得其最優(yōu)解。

為便于建立旅行商問(wèn)題的數(shù)學(xué)模型，不妨假設(shè)：旅行商從城市1出發(fā)，遍訪(fǎng)城市2、…、n各一次后，再回到城市1；城市i和j之間的距離為dij，其中dii=+∞，這一假設(shè)將使得最優(yōu)旅行路線(xiàn)中不可能存在從城市i到i的環(huán)。在實(shí)際計(jì)算中，+∞可用一個(gè)充分大的正數(shù)來(lái)代替。

2 模型建立

首先引入決策變量：

則目標(biāo)函數(shù)為：

約束條件為：

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

不難知道，滿(mǎn)足以上約束條件的變量xij(i,j=1,…,n)不一定構(gòu)成一條可行的旅行路線(xiàn)。如在n=6的旅行商問(wèn)題中，令x12=x23=x31=1，x45=x56=x64=1，其余xij=0，則不難驗(yàn)證它們對(duì)應(yīng)問(wèn)題的一個(gè)可行解，但卻構(gòu)成如圖1所示的多回路“分割”現(xiàn)象。

Figure 1 Phenomenon of separation圖1 “分割”現(xiàn)象

因此，應(yīng)在模型中添加約束條件，以避免“分割”現(xiàn)象的發(fā)生。

下面重點(diǎn)介紹三種避免“分割”現(xiàn)象的方法。

2.1 方法一

2.2 方法二

對(duì)于上述兩種方法，注意到城市集合{1,2,…,n}的非空真子集共有2n-2個(gè)，當(dāng)然上述約束條件也有2n-2個(gè)，這要求在實(shí)際計(jì)算中需有一定的編程技巧。

2.3 方法三

為避免出現(xiàn)上述多回路“分割”現(xiàn)象，還需特別增加下列約束條件[6]：

其中，ui≥0(i=1,…,n)是為了構(gòu)造上述約束條件而特別針對(duì)每一頂點(diǎn)引入的輔助變量，沒(méi)有實(shí)際意義。

證明

(1)任一存在多回路“分割”現(xiàn)象的旅行路線(xiàn)都不滿(mǎn)足上述約束條件(無(wú)論ui、uj如何取值)。

事實(shí)上，若某一旅行路線(xiàn)存在多回路“分割”現(xiàn)象，則它至少有兩個(gè)回路，從而至少有一個(gè)回路不含城市v1，如圖1中回路v4→v5→v6→v4，即x45=x56=x64=1,但變量u4、u5、u6及x45、x56、x64一起并不滿(mǎn)足下列約束條件：

這是因?yàn)樯鲜鋈齻€(gè)不等式左、右分別相加后將得出矛盾的結(jié)果：18≤15。

(2)任一可行的旅行路線(xiàn)都滿(mǎn)足上述約束條件(只要ui、uj適當(dāng)取值)。

事實(shí)上，設(shè)v1→vs→vt→…→vi→vj→…→vk→v1是一條可行的旅行路線(xiàn)(即TSP的一個(gè)可行解為x1s=xst=…=xij=…=xk1=1，其余xij=0)，則令ui=i-1，uj=i。于是，對(duì)xij=1，上述約束條件變?yōu)?i-1)-i+n≤n-1，顯然成立；對(duì)xij=0，上述約束條件變?yōu)?i-1)-i+0≤n-1，顯然成立。

□

綜上所述，可建立如下混合整數(shù)規(guī)劃模型：

3 實(shí)證分析

算例六個(gè)城市，距離矩陣如表1所示。

Table 1 Distance matrix

下面以方法三提供的模型為例編寫(xiě)如下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上運(yùn)行程序返回如下結(jié)果：(限于篇幅，僅給出主要部分)

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

因此，最優(yōu)旅行路線(xiàn)為1→3→6→2→5→4→1，其長(zhǎng)度為96。

算例表明模型是正確的，根據(jù)模型設(shè)計(jì)的程序也是可行的。

4 結(jié)束語(yǔ)

本文首先分析了旅行商問(wèn)題的難解性，然后借助數(shù)學(xué)規(guī)劃方法建立了其混合整數(shù)規(guī)劃模型，最后給出了基于LINGO軟件的程序設(shè)計(jì)，從而技術(shù)性地避開(kāi)了問(wèn)題本身的NP-困難性，使問(wèn)題的求解過(guò)程更便捷、更高效。當(dāng)然，近似算法、啟發(fā)式算法、遺傳算法等也是求解旅行商問(wèn)題的可能選擇，值得另行研究。

[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)

附中文參考文獻(xiàn)：

[1] 朱道立, 徐慶, 葉耀華. 運(yùn)籌學(xué)[M]. 北京:高等教育出版社, 2006.

[2] 胡運(yùn)權(quán), 郭耀煌. 運(yùn)籌學(xué)教程[M]. 第三版.北京:清華大學(xué)出版社, 2007.

[3] 運(yùn)籌學(xué)教程編寫(xiě)組. 運(yùn)籌學(xué)教程[M]. 北京:國(guó)防工業(yè)出版社, 2012.

[4] 薛毅, 耿美英. 運(yùn)籌學(xué)與實(shí)驗(yàn)[M]. 北京:電子工業(yè)出版社, 2008.

[5] 謝金星, 薛毅. 優(yōu)化建模與LINGO/LINDO軟件[M]. 北京:清華大學(xué)出版社, 2006.

[6] 袁新生, 邵大宏, 郁時(shí)煉. LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用[M]. 北京:科學(xué)出版社, 2007.

[7] 魏國(guó)華, 王芬. 線(xiàn)性規(guī)劃[M]. 北京:高等教育出版社, 1989.

[8] 司守奎, 孫璽菁. 數(shù)學(xué)建模算法與應(yīng)用[M]. 北京:國(guó)防工業(yè)出版社, 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(10901093)

Q784;TP301.6

：A

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

王繼強(qiáng)(1976-),男,山東棗莊人，博士，副教授，研究方向?yàn)榻M合最優(yōu)化和理論計(jì)算機(jī)科學(xué)。E-mail:sdcdmcm@126.com

通信地址：250014 山東省濟(jì)南市山東財(cái)經(jīng)大學(xué)數(shù)學(xué)與數(shù)量經(jīng)濟(jì)學(xué)院

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