旅行商问题
Ⅰ改良圈算法： 设初始圈 C = v 1 v 2 ⋯ v n v 1 C=v_{1}v_{2}\cdots v_{n}v_{1} C=v1v2⋯vnv1. (1) 对于 1 ≤ i < i + 1 < j ≤ n ： 若 w ( v i v j ) + w ( v i + 1 v j + 1 ) ≤ w ( v i v i + 1 ) + w ( v j v j + 1 ) , 则 在 C 中 删 去 边 v i v i + 1 和 v j v j + 1 , 添 加 边 v i v j 和 v i + 1 v j + 1 ， 以 C i j = v 1 v 2 ⋯ v i v j v j − 1 v j − 2 ⋯ v i + 1 v j + 1 v j + 2 ⋯ v n v 1 代 替 C 1 \leq i <i+1 <j \leq n：若w(v_{i}v_{j})+w(v_{i+1}v_{j+1}) \leq w(v_{i}v_{i+1})+w(v_{j}v_{j+1}),则在C中删去边v_{i}v_{i+1}和v_{j}v_{j+1},添加边v_{i}v_{j}和v_{i+1}v_{j+1}，以C_{ij}=v_{1}v_{2}\cdots v_{i}v_{j}v_{j-1}v_{j-2} \cdots v_{i+1}v_{j+1}v_{j+2} \cdots v_{n}v_{1}代替C 1≤i<i+1<j≤n：若w(vivj)+w(vi+1vj+1)≤w(vivi+1)+w(vjvj+1),则在C中删去边vivi+1和vjvj+1,添加边vivj和vi+1vj+1，以Cij=v1v2⋯vivjvj−1vj−2⋯vi+1vj+1vj+2⋯vnv1代替C
(2)转（1），直至无法改进，停止。
注：为得到更高精度，可以选择不同的初始圈，重复进行几次，以求得较精确结果。
例4.14（改良圈算法）
function main a=zeros(6); a(1,2)=56; a(1,3)=35; a(1,4)=21; a(1,5)=51; a(1,6)=60; a(2,3)=21; a(2,4)=57; a(2,5)=78; a(2,6)=70; a(3,4)=36; a(3,5)=68; a(3,6)=68; a(4,5)=51; a(4,6)=61; a(5,6)=13; a=a+a'; L=size(a,1); c=[5 1:4 6 5]; %选取初始圈 [circle,long]=modifycircle(a,L,c) %调用下面修改圈的子函数 %************************* % 以下为修改圈的子函数,可做模板 %************************* function [circle,long]=modifycircle(a,L,c); for k=1:L flag=0 ; %退出标志 for m=1:L-2 %m为算法中的i for n=m+2:L %n为算法中的j if a(c(m),c(n))+a(c(m+1),c(n+1))<a(c(m),c(m+1))+a(c(n),c(n+1)) c(m+1:n)=c(n:-1:m+1); flag=flag+1; %修改标志+1 end end end if flag==0 %一条边也没修改，直接返回 long=0; for i=1:L long=long+a(c(i),c(i+1)); end circle=c; %返回修改圈 return end endⅡ 旅行商问题的数学规划问题模型 设城市个数为 n n n,两城市 i i i与 j j j之间的距离为 d i j d_{ij} dij, x i j = 0 或 1 （ 1 表 示 走 过 城 市 i 到 j 的 路 ， 0 表 示 未 选 择 走 这 条 路 ） x_{ij}=0或1（1表示走过城市i到j的路，0表示未选择走这条路） xij=0或1（1表示走过城市i到j的路，0表示未选择走这条路）则有： 一般形式： m i n ∑ i ≠ j d i j x i j min \sum_{i \neq j}{d_{ij}x_{ij}} mini̸=j∑dijxij s . t . = { ∑ j = 1 n x i j = 1 , i = 1 , 2 , ⋯ , n （ 每 个 点 只 有 一 条 边 出 去 ） ∑ i = 1 n x i j = 1 , j = 1 , 2 , ⋯ , n （ 每 个 点 只 有 一 条 边 进 去 ） ∑ i , j ∈ s x i j ≤ ∣ s ∣ − 1 , 2 ≤ ∣ s ∣ ≤ n − 1 , s ⊂ { 1 , 2 , ⋯ , n } , 即 s 为 { 1 , 2 , ⋯ , n } 的 真 子 集 （ 除 起 点 和 终 点 外 ， 各 边 不 够 成 圈 ） x i j ∈ { 0 , 1 } , i , j = 1 , 2 , ⋯ , n , i ≠ j s_{.}t_{.}=\left\{ \begin{aligned} \sum_{j=1}^{n}{x_{ij}=1} ,\quad i=1,2,\cdots,n （每个点只有一条边出去）\\ \sum_{i=1}^{n}{x_{ij}=1} ,\quad j=1,2,\cdots,n （每个点只有一条边进去）\\ \sum_{i,j \in s}{x_{ij} \leq|s|-1,2 \leq|s| \leq n-1,s \subset \{1,2,\cdots,n\},即s为\{1,2,\cdots,n\}的真子集（除起点和终点外，各边不够成圈）} \\ x_{ij} \in \{0,1\},i,j=1,2,\cdots,n,i \neq j \end{aligned} \right. s.t.=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧j=1∑nxij=1,i=1,2,⋯,n（每个点只有一条边出去）i=1∑nxij=1,j=1,2,⋯,n（每个点只有一条边进去）i,j∈s∑xij≤∣s∣−1,2≤∣s∣≤n−1,s⊂{1,2,⋯,n},即s为{1,2,⋯,n}的真子集（除起点和终点外，各边不够成圈）xij∈{0,1},i,j=1,2,⋯,n,i̸=j 例4.15（Lingo程序）
model: sets: city /1..10/:u; link(city,city):dist,x; endsets data: dist= 0 8 5 9 12 14 12 16 17 22 8 0 9 15 17 8 11 18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 18 12 17 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 18 15 16 11 11 10 0 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(j,k)=1); @for(city(j)|j #gt# 1 and j #ne # k: u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*(j,k))); @for(link:@bin(x)); @for(city(k)|k #gt# 1: u(k)<=n-1-(n-2)*x(1,k); u(k)>=1+(n-2)*x(k,1)); end