旅行商问题的一种启发式算法

作者简介:洪玉振(1957—

),男,江苏东台人,副教授,硕士,主要从事管理信息系统和系统工程研究.旅行商问题的一种启发式算法

洪玉振1,张际东2,李　明1

(1.河海大学商学院,江苏南京　210098;2.河海大学外国语学院,江苏南京　210098)

摘要:用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n 列的顶点上的图,如何从这些图上搜索出近似最优解的方法.

关键词:旅行商问题;最短路径;有向图;启发式算法

中图分类号:O224　　　文献标识码:A 　　　文章编号:1000Ο1980(2007)02Ο0229Ο04

本文沿用文献[1]的符号和定义.在文献[1]的图1中,每个顶点v (p k )上用一个图来表示旅行商避开一个被访问城市p n 到它的所有最短路径.已知第k -1列上的图,根据文献[1]提供的最短路径的必要条件,确定第k 列上的图,重复这一步骤,求出第n 列上的图.

显然,这涉及动态规划的思想.Bellman 等[2Ο3]运用动态规划原理讨论了旅行商的路径优化问题.Clients ov

等[4Ο6]研究了路径问题中的离散Ο连续优化方法的应用.Chents ov 等[4,8]分析了动态规划应用于TSP 路径优化的过程.以上提及的动态规划在TSP 方面的应用基于Bellman 的最优性原理,而本文探讨的TSP 算法依据文献[1].

1　图和弧上的线性表

1.1　图G (v (p k )⁄r 1,r 2,…,r g )的定义

用图G (v (p k )⁄r 1,r 2,…,r g )来表示旅行商避开城市r 1,r 2,…,r n 到v (p k )的全部最短路径,定义它为2个符号集合:顶点的集合Ω(v (p k )⁄r 1,r 2,…,r g )和弧的集合A (v (p k )⁄r 1,r 2,…,r g ),即

G (v (p k )⁄r 1,r 2,…,r g )=(Ω(v (p k )⁄r 1,r 2,…,r g ),A (v (p k )⁄r 1,r 2,…,r g ))

(1)同理,定义由经过指定顶点v (q k -1)到v (p k )的全部最短路径的图:

G (v (p k )/v (q k -1)⁄r 1,…,r g )=(Ω(v (p k )/v (q k -1)⁄r 1,…,r g ),A (v (p k )/v (q k -1)⁄r 1,…,r g ))(2)仅当v (p j -1)和v (p j )是图G (v (p k )⁄r 1,r 2,…,r g )中同一路径上的2个相邻的顶点时,才存在一条从v (p j )到v (p j -1)的弧[v (p j ),v (p j -1)],v (p j )称之弧尾,v (p j -1)称之为弧头.顶点v (p k )和v (0)分别称之为图G (v (p k )⁄r 1,r 2,…,r g )的源点(S ource )和终点(Destination ).用η(v (p k )⁄r 1,r 2,…,r g )表示G (v (p k )⁄r 1,r 2,…,r g )的权,它等于到v (p k )的最短路径的权.

1.2　弧上的线性表

在G (v (p k )⁄p n )上的每一弧上定义一个线性表,用以记录它所属的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作.

在文献[1]的图1中,依次对第一行和第一列上的顶点到第n 行和第n 列上的顶点进行编号:1,2,…,n 2.这样,第i 行和第j 列上的顶点的编号为(j -1)n +i.为G (v (q k -1)⁄p n )上的每一条弧[v (q j ),v (q j -1)]建立一个线性表,记作L (v (q j ),v (q j -1)),线性表中数据元素为该弧所属子图源点的编号,按升序排列.对于G (v (q k -1)⁄p n )上顶点v (q x ),用π(q x )表示它的编号.顶点的编号和顶点存在一一对应的关系,有时为表示方便,用编号π(q x )代表顶点v (q x ).

设G (v (q (χ)i )⁄p n )为G (v (q k -1)⁄p n )上第i 列上的第χ个包含弧[v (q j ),v (q j -1)]的子图,i ∈[j ,k -第35卷第2期2007

年3月河海大学学报(自然科学版)Journal of H ohai University (Natural Sciences )V ol.35N o.2Mar.2007

© 1994-2011 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

1],χ∈[1,a (i )],a (i )∈[1,n -2],亦即[v (q j ),v (q j -1)]∈A (v (q (χ)i )⁄p n ),则[v (q j ),v (q j -1)]上的线性

表为L (v (q j ),v (q j -1))=(π(q (1)j ),π(q (1)j +1),…,π(q (a (j +1))j +1),…,π(q (1)k -2),…,π(q (a (k -2))k -2),π(q (1)k -1)),这

里,π(q (1)j )=π(q j ),π(q (1)k -1)=π(q k -1).令L i (v (q i ),v (q i -1))={π(q (1)i ),…,π(q (a (i ))i )},则L (v (q j ),v (q j -1))可划分成以下子集:

L (v (q j ),v (q j -1))=L j (v (q j ),v (q j -1))∪L j +1(v (q j ),v (q j -1))∪…∪L k -1(v (q j ),v (q j -1))(3)

注意到线性表中数据元素两两相异,因此L j (v (q j ),v (q j -1))∪L j +1(v (q j ),v (q j -1))∪…∪L k -1(v (q j ),v (q j -1))=

(4)2　删除G (v (q k -1)⁄p n )中第p k 行上的顶点和弧

定理1　G R (v (q k -1)⁄p n )上的任意一条弧[v (q j -1),v (q j -2)]在到v (q k -1)的最短路径上的充分必要条件:当j ∈[2,k -1]时,

L (v (q j ),v (q j -1))(5)j ∈[1,k -2]时,存在弧[v (q (1)j +1),v (q j )],[v (q (2)j +1),v (q j )],…,[v (q (a (j +1))j +1

),v (q j )],且L (v (q j ),v (q j -1))={π(q j )}∪L (v (q (1)j +1),v (q j ))∪L (v (q (2)j +1),v (q j ))∪…∪L (v (q (a (j +1))j +1),v (q j ))

(6)

这里,a (j +1)∈[1,n -2].

证明:　

a.必要性.假设G R (v (q k -1)⁄p n )上的每条弧都在最短路径上,而[v (q k -1),v (q k -2)]为G R (v (q k -1)⁄p n )中的弧.

对于任一包含弧[v (q j ),v (q j -1)]的最短路径,v (q j +1),v (q j +2),…,v (q k -1)为包含[v (q j ),v (q j -1)]和[v (q j -1),v (q j -2)]的图的源点,但v (q j -1)为包含[v (q j -1),v (q j -2)]而不包含[v (q j ),v (q j -1)]的图的源点,因此,式(5)成立.

因为[v (q j ),v (q j -1)]在到v (q k -1)的最短路径上,[v (q j ),v (q j -1)]必须属于第k +1列上的一个或数个

子图G R (v (q (1)j +1)⁄p n ),G R (v (q (2)j +1)⁄p n ),…,G R (v (q (a (j +1))j +1)⁄p n ),因而弧[v (q (1)j +1),v (q j )],[v (q (2)j +1),

v (q j )],…,[v (q (a (j +1))j +1),v (q j )]存在.对于每一μ∈[1,a (j +1)],包含[v (q (μ)j +1),v (q j )]的图也包含[v (q j ),

v (q j -1)],而[v (q j ),v (q j -1)]在以v (q j )为源点的图上,但[v (q (μ)

j +1),v (q j )]不在,因此,式(6)成立.b.充分性.令[v (q j ),v (q j -1)]为G R (v (q k -1)⁄p n )上的满足式(5)和式(6)的弧,要证明存在最短路径.G R (v (q k -1)⁄p n )上所有弧都满足式(5),因此存在弧[v (q j -1),v (q j -2)],[v (q j -2),v (q j -3)],…,[v (q 1),v (q 0)],且

L (v (q j ),v (q j -1))(7)G R (v (q k -1)⁄p n )上所有弧都满足式(6),因此存在源点[v (q k -1),v (q k -2)],[v (q k -2),v (q k -3)],…,

[v (q j +1),v (q j )],且

L (v (q k -1),v (q k -2)).

在G R (v (q k -1)⁄p n )中,假设以v (q j )为弧头的弧为[v (q (β)j +1),v (q j )],β∈

[1,t ];以v (q j )为弧尾的弧为[v (q j ),v (q (α)j -1)],α∈[1,s ].为每条以v (q j )为弧尾的弧[v (q j ),v (q (α)j -1)]建立一个参照表并初始化:

L ′(v (q j ),v (q (α)j -1))= ,α∈

[1,s ].对于每一[v (q (β)j +1),v (q j )],检查是否存在弧[v (q j ),v (q (α)j -1)]使L (v (q (β)j +1),v (q j ))若不存在,则删除[v (q (β)j +1),v (q j )].每条以v (q j )为弧头的弧必须与所有以v (q j )为弧尾的弧进行比较,以确

定它是否并入后者对应的参照表.完成比较后,检查每一L ′(v (q j ),v (q (α)j -1))是否仍为空集.若为空集,则删

除[v (q j ),v (q (α)j -1)];若不为空集,则使L (v (q j ),v (q (α)j -1))=L ′(v (q j ),v (q (α)j -1)).

3　生成图G (v (p n -1)⁄p n )

依次生成G (v (p 1)⁄p n ),G (v (p 2)⁄p n ),…,G (v (p n -1)⁄p n ).首先生成第一列上顶点的图G (v (p 1)⁄032河海大学学报(自然科学版)

第35

卷© 1994-2011 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

p n ).当d (0,p 1)<+∞时,对于每一p n ∈[1,n ],只要p n ≠p 1,则为最短路径,其权重w (0,p 1)=d (0,p 1).在这种情况下,Ω(v (p 1)⁄p n )={v (0),v (p 1)};A (v (p 1)⁄p n )={[v (p 1),v (0)]};η(v (p 1)⁄p n )=w (0,p 1);L (v (p 1),v (0))=(π(p 1)).

若d (0,p 1)=+∞,则η(v (p 1)⁄p n )=+∞,这时,G (v (p 1)⁄p n )不存在.当k ∈[2,n -1]时,现给定第(k -1)列上顶点的所有的图G (v (q k -1)⁄p n ).当p k ≠q k -1且0Ω(v (p k )/v (q k -1)⁄p n )={v (p k )}∪ΩR (v (q k -1)⁄p n )(9)

A (v (p k )/v (q k -1)⁄p n )={[v (p k ),v (q k -1)]}∪A R (v (q k -1)⁄

p n )(10)η(v (p k )/v (q k -1)⁄

p n )=η(v (q k -1)⁄p k )+d (q k -1,p k )

(11)L (v (p k ),v (q k -1))=(π(p k ))(12)　　完成G (v (p k )/v (q k -1)⁄p n )后,初始化G (v (p k )⁄p n ):Ω(v (p k )⁄p n )= ,A (v (p k )⁄p n )= .置η(v (p k )⁄p n )=min {η(v (p k )/v (q k -1)⁄p n )/v (q k -1)∈Γk -1}.若η(v (p k )/v (q k -1)⁄p n )=η(v (p k )⁄p n ),则将G (v (p k )/v (q k -1)⁄p n )并入G (v (p k )⁄p n ):

Ω(v (p k )⁄p n )∪Ω(v (p k )/v (q k -1)⁄p n )]Ω(v (p k )⁄p n )(13)

A (v (p k )⁄p n )∪A (v (p k )/v (q k -1)⁄p n )]A (v (p k )⁄p n )(14)

　　对于每一[v (q j ),v (q j -1)]∈A (v (p k )/v (q k -1)⁄p n ),若它已存在于A (v (p k )⁄p n ),则将这2条相同的弧上的2个线性表的并集作为A (v (p k )⁄p n )中该弧的线性表;若它不存在于A (v (p k )⁄p n ),则[v (q j ),v (q j -1)]在A (v (p k )/v (q k -1)⁄p n )中的线性表就是它在A (v (p k )⁄p n )中的线性表.当η(v (p k )⁄p n )=+∞时,G (v (p k )⁄p n )不存在.重复以上步骤,生成到第n -1列上的图G (v (p n -1)⁄p n ).

4　近似最优解搜索

4.1　生成G (v (p n ))

用表示到第n 列上顶点v (p n )的路径.

当w (p 0,p 1,…,p n )=min {w (q 0,q 1,…,q n -1,p n )/∈S n -1}时,定义为最短路径.图G (v (q n ))由到v (q n )的全部最短路构成,它定义为2个符号集合:顶点的集合Ω(v (q n ))和弧的集合A (v (q n )),亦即G (v (q n ))=(Ω(v (q n )),A (v (q n ))).

用图G (v (q n )/v (r n -1))表示经过v (r n -1)到v (q n )的全部最短路径.当d (r n -1,q n )<+∞时,生成G (v (q n )/v (r n -1))如下:

Ω(v (q n )/v (r n-1))={v (q n )}∪Ω(v (r n-1)⁄q n )(15)

A (v (q n )/v (r n -1))={[v (q n ),v (r n-1)]}∪A (v (r n -1)⁄q n )(16)

η(v (q n )/v (r n -1))=η(v (r n -1)⁄q n )+d (r n -1,q n )(17)

L (v (q n ),v (r n-1))=(π(q n ))

(18)　　对于每一[v (r j ),v (r j -1)]∈A (v (q n )/v (r n -1)),在L (v (r j ),v (r j -1))中的最后一个元素后插入π(q n ).

置η(v (q n ))=min {η(v (q n )/v (r n -1))/v (r n -1)∈

Γn -1}.如果η(v (q n )/v (r n -1))=η(v (q n )),将G (v (q n )/v (r n -1))并入G (v (q n )):Ω(v (q n )/v (r n -1))∪

Ω(v (q n ))]Ω(v (q n ));A (v (q n )/v (r n -1))∪A (v (q n ))]A (v (q n )),同时将G (v (q n )/v (r n -1))中的所有线性表并入G (v (q n )).

4.2　搜索最优解

如果在第n 列至少存在一个顶点v (q n ),满足η(v (q n ))<+∞和d (q n ,0)<+∞,则旅行商访问的第n

个城市取决于η(v (p n ))=min {η(v (q n ))+d (q n ,0)/v (q n )∈

Γn }.定理2　G (v (p n ))上存在最短路径的充分必要条件:存在一个弧的系列

[v (p n ),v (p n -1)],[v (p n -1),v (p n -2)],…,[v (p 1),v (p 0)],且

π(p n )∈L n (v (p n ),v (p n -1))

(19)π(p n-1)∈L n -1(v (p n -1),v (p n-2)),π(p n )∈L n (v (p n-1),v (p n -2));…;

(20)

132第2期洪玉振,等　

旅行商问题的一种启发式算法© 1994-2011 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

π(p 1)∈L 1(v (p 1),v (p 0)),π(p 2)∈L 2(v (p 1),v (p 0)),…,π(p n )∈L n (v (p 1),v (p 0))(21)

　　证明:

a.必要性.假设G (v (p n ))上存在最短路径.k =n 时,弧[v (p n ),v (p n -1)]存在,L (v (p n ),v (p n -1))=L n (v (p n ),v (p n -1))=(π(p n )),因此π(p n )∈L n (v (p n ),v (p n -1)).假设k =j 时,存在[v (p j ),v (p j -1)],且π(p j )∈L j (v (p j ),v (p j -1)),π(p j +1)∈L j +1(v (p j ),v (p j -1)),…,π(p n )∈L n (v (p j ),v (p j -1))).

当k =j -1时,因为是最短路径,因此弧[v (p j -1),v (p j -2)]存在,且以v (p j -1),v (p j ),…,v (p n -1)为源点的图的子图G (v (p j -2)⁄p n )存在,亦即L (v (p j -1),v (p j -2))满足:π(p j -1)∈L j -1(v (p j -1),v (p j -2)),π(p j )∈L j (v (p j -1),v (p j -2)),…,π(p n )∈L n (v (p j -1),v (p j -2))).因此,k =j -1时成立.

b.充分性.j ∈[1,n ],弧[v (p j ),v (p j -1)]存在,且满足π(p j )∈L j (v (p j ),v (p j -1)),π(p j +1)∈L j +1(v (p j ),v (p j -1)),…,π(p n )∈L n (v (p j ),v (p j -1))).对于任一j ∈[1,n ],是最短路径,是最短路径,因此是最短路径.

顺着弧的指向,按下列顺序搜索解:[v (p n ),v (p n -1)]→[v (p n -1),v (p n -2)]→…→[v (p 1),v (p 0)].

5　结　　语

被避开的城市p k +1,p k +2,…,p n 有C k n 种组合,亦即第k 列上图的总数最多达C k n .显然,当城市数很大时

要获得每一组合对应的图是困难的.因此,本文讨论图G (v (p k )⁄p n )的数目.每列上只有n 个顶点,p n ∈[1,n ]且p n ≠p k ,因此,每个顶点上最多有n -1个图,每一列上最多有n ×(n -1)个图.根据文献[1],只需要获得图G (v (p k )⁄p n )而不是图G (v (p k )⁄p k +1,p k +2,…,p n ).

参考文献:

[1]洪玉振.TSP 最短路径的必要条件初探[J ].河海大学学报:自然科学版,2006,34(6):717Ο720.

[2]BE LLM AN R.Dynamic programming treatment of the traveling salesman problem[J ].J Ass oc C om put Mach ,1962,9(1):61Ο63.

[3]HE LD M ,K ARP R M.A dynamic programming approach to sequencing problems[J ].J S oc Industr and Appl Math ,1962,10(1):196Ο210.

[4]C LIE NTS OV A G,K OROT AYE VA L N ,SESEKI N A N.On a m odification of the method of dynamic programming in a successive approach

problem[J ].Zh Vychisi Mat Fiz ,19,29(8):1107Ο1113.

[5]BUS LAYE VA L T ,CHE NTS OV A G.On the problem of the decom position of the process of successive choice of variants [J ].Mat

M odebrovarne ,1991,3(4):103Ο113.

[6]CHE NTS OV A G,K OROT AYE VA L N ,NAZ AROV E M.An assignment problem[J ].C om put Maths Math Phys ,1993,33(4):443Ο452.

[7]REI NE LT G.TSP LI B ΟA traveling salesman problem library[J ].ORS A Journal of C om puting ,1991,3(4):376Ο384.

A heuristic algorithm for traveling salesman problem

H ONG Yu 2zhen 1,ZHANG Ji 2dong 2,LI Ming 1

(1.Business School o f Hohai Univer sity ,Nanjing 210098,China ;

2.College o f International Languages and Culture ,Hohai Univer sity ,Nanjing 210098,China )

Abstract :A vector graph ,com posed of vertices and arcs ,was ad opted to express all the shortest paths to a vertex av oiding a certain city ,and a linear list ass ociated with each arc was defined to track the graphs including the corresponding arc.T hus ,the problem whether a vertex or an arc is on the shortest path of a graph was turned to a linear list operation.W ith the meth od ,the su fficient and necessary condition for all arcs in a graph lying on the shortest path was deduced.By generation of graphs at vertices from the first column to the n th column ,the optimal approximate s olution was found.As a conclusion ,there are at m ost n -1graphs at each vertex ,and at m ost n ×(n -1)graphs for each column ,therefore ,n ot the graph G (ν(p k )⁄p k +1,p k +2,…,p n ),but the graph G (ν(p k )⁄p n )is needed to be obtained.

K ey w ords :traveling salesmen problem ;shortest path ;vector graph ;heuristic alg orithm

232河海大学学报(自然科学版)第35

卷

© 1994-2011 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net