王繼強

(山東財經(jīng)大學數(shù)學與數(shù)量經(jīng)濟學院，山東 濟南 250014)

基于LINGO的旅行商問題的建模方法*

王繼強

(山東財經(jīng)大學數(shù)學與數(shù)量經(jīng)濟學院，山東 濟南 250014)

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

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

1 引言

在圖論中，圖是由頂點和邊兩個要素構成的拓撲結構，其中頂點表示對象，邊表示對象之間的關系。任何兩相異頂點之間恰好存在唯一一條邊的圖稱為完全圖；在圖中，頂點和邊交錯出現(xiàn)的一個序列稱為鏈，邊不重復出現(xiàn)的一個封閉序列稱為圈，遍歷所有頂點的圈稱為哈密爾頓圈。

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

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

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

2 模型建立

首先引入決策變量：

則目標函數(shù)為：

約束條件為：

此外，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所示的多回路“分割”現(xiàn)象。

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

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

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

2.1 方法一

2.2 方法二

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

2.3 方法三

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

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

證明

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

事實上，若某一旅行路線存在多回路“分割”現(xiàn)象，則它至少有兩個回路，從而至少有一個回路不含城市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，上述約束條件變?yōu)?i-1)-i+n≤n-1，顯然成立；對xij=0，上述約束條件變?yōu)?i-1)-i+0≤n-1，顯然成立。

□

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

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

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

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

4 結束語

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

[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]. 北京:國防工業(yè)出版社, 2012.

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

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

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

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

[8] 司守奎, 孫璽菁. 數(shù)學建模算法與應用[M]. 北京:國防工業(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

國家自然科學基金資助項目(10901093)

Q784;TP301.6

：A

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

王繼強(1976-),男,山東棗莊人，博士，副教授，研究方向為組合最優(yōu)化和理論計算機科學。E-mail:sdcdmcm@126.com

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

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