长安大学学报（自然科学版）070220

	长安大学学报（自然科学版） JOURNAL OF CHANG'AN UNIVERSITY(NATURAL SCIENCE EDITION) 2007 Vol.27 No.2 P.85-88

基于空间填充曲线和or-opt搜索求解旅行商问题

胡大伟　刘贵英　

摘　要：为探索求解大规模TSP(旅行商问题)有效实用方法,提出基于SFC(空间填充曲线)和or-opt混合算法来求解TSP,其中SFC方法能快速且有效地获得初始解,or-opt搜索算法可有效改进初始解.通过中国旅行商问题(CTSP)数据测试,无论是速度还是精度都能满足一定要求,证明这种混合算法能快速有效地解决TSP,并为解决大规模此类问题提供了一种新的思路.
关键词：交通工程;旅行商问题;空间填充曲线;or-opt算法;组合优化
分类号：U491.21　文献标识码：A
文章编号：1671-8879(2007)02-0085-04

Solving travelling salesman problem(TSP) based on space-filling curve and or-opt algorithm

HU Da-wei　 LIU Gui-ying　

作者简介：胡大伟(1963-),男,北京市人,教授,E-mail:dwhu@chd.edu.cn.
作者单位：胡大伟（长安大学,汽车学院,陕西,西安,710064）　
　　　　　刘贵英（长安大学,汽车学院,陕西,西安,710064）　

参考文献：

[1]Gilbert L.The traveling salesman problem:an overview of exact and appromixate algorithms[J].European Journal of Operatinal Research,1992,59:231-247.
[2]李明海,邢桂华.用MATLAB实现中国旅行商问题的求解[J].微计算机应用,2004,25(3):218-222.LI Ming-hai,XING Gui-hua.Resolution of Chinese traveling salesman problem in MATLAB[J].Microcomputer Application,2004,25(3):218-222.
[3]Join J,Loren K P.Heuristics based on spacefill curve for combinatorial problems in euclidean space[J].Management Science,1988,34(3):290-305.
[4]Jean Y P,Jean M P.An exchange heuristic for routing problems with time windows[J].Journal of Operational Research Society,1995,46:271 -288.
[5]Margot F.Quick updates for or-opt TSP heuristics[J].Operations Research Letters,1992,11(1):45-46.
[6]宣登殿,胡大伟,蔺宏良.基于GIS的城市物流配送系统规划方法[J].长安大学学报:自然科学版,2006,26(2):84-87.XUAN Deng-dian,HU Da-wei,LIN Hong-liang.Planning method of city logistics delivery system on GIS[J].Journal of Chang'an University:Natural Science Edition,2006,26(2):84-87.
[7]高尚.解旅行商问题的混沌蚁群算法[J].系统工程理论与实践,2005,(9):100-104.GAO Shang.Solving travelling salesman problem by chaos ant colony optimization algorithm[J].Systems Engineering Theory and Practice,2005,(9):100 -104.
[8]张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路学报,2004,17(1):79-81.ZHANG Bo,YE Jia-wei,HU Yu-cong.Application of optimizing the path by simulated annealing[J].China Journal of Highway and Transport,2004,17(1):79-81.
[9]Yran D,Jacoues D,Eric G,et al.An optimmal algorithm for the travelling salesman problem with time windows[J].Operations Research,1995,43(2):367-371.
[10]赵建有,闫旺,胡大伟.配送网络规划蚁群算法[J].交通运输工程学报,2004,4(3):79-81ZHAO Jian-you,YAN Wang,HU Da-wei.Ant colony algorithm of distribution network planning[J].Journal of Traffic and Transportation Engineering,2004,4(3):79-81.

收稿日期：2006年2月16日

出版日期：2007年3月30日