18
,
1,
1,
.
1,
{0,1} ,
ij
ji
ij
ij
ij
ijS
ij
xiV
xjV
st
KKV
xijV
≠
≠
∈
⎧
=∈
⎪
⎪
=∈
⎪
⎨
⎪
≤− ⊂
⎪
⎪
∈∈
⎩
∑
∑
∑
这里,K 为V 的所有非空子集, K 为集合 K 中所含图G 的顶点个数。前两个
约束意味着对每个顶点而言,仅有一条边进出,后一约束则保证了没有任何子回
路解的产生。于是,满足上述约束的解构成了一条 Hamilton 回路。除此之外,模
型还有其它一些等价的书写形式。
3.1.2 旅行商问题的分类
旅行商问题按不同的分类方法可以分成为不同的种类。
① 据距离矩阵划分
当 ,( , )
ij ji
ccijV=∈时,问题被称为对称型旅行商问题。反之,称为非对称型
旅行商问题。非对称型旅行商问题可以化为对称型旅行商问题,用对称型的方法
求解。
当对所有 ,, [1,]ijk n∈ ,有不等式
ij jk ik
cc c
≥ 成立时,问题被称为是满足三角
形不等式的,简写成三角型旅行商问题。三角形不等式在很多情况下是自动满足
的,如:只要距离矩阵是由一度量矩阵导出的即可。另一类自动满足的是闭包矩
阵,
ij
c
⎡⎤
⎣⎦
是的[]
ij
c 闭包,是指在{1, 2 , }n" 的完全图中,
ij
c 为边 (, )ij距离,则
ij
c 是
ij→ 之最短路长。一般而言,现实生活中的大多数问题都满足三角形不等式,它
是旅行商问题中的一种主要类型。个别不满足的,也可转换成其闭包问题,它们
的旅行商问题解是等价的。
当
ij
c 是欧氏距离时,则称为欧氏距离的旅行商问题。显然此类问题既是对称
型旅行商问题也是三角型旅行商问题。
② 根据顶点的分布形态划分
有均匀分布的(Uniform Points) 、聚集分布(Clustered Points)、随机距离矩阵
(Random Matrices),此外还有旅行商问题库(TSPLI B)中的实际范例。前三种都是
人工模拟产生的旅行商问题,主要用于测试算法对不同分布形态的旅行商问题的
表现,并计算算法的时间函数。后一种实际范例才是人们关注的重点。
③ 根据距离矩阵在数据文件中的存储方式划分和来源划分
MATRIX
型:距离矩阵直接给出。EUC_ 2D 或 CEIL_ 2D:给出顶点坐标,距
离矩阵需计算才能得到。CEO:给出顶点坐标,距离矩阵需计算才能得到,坐标
来源于地理坐标。
评论1