V9 0 9 2 1 3上摘要T S P ( T r a v e l i n gS a l e s m a nP r o b l e m ，旅行商问题) 是组合优化领域的重要问题之一，同时也是众多现实问题的原形，对其开展深入广泛的研究具有重要的理论价值和实用价值。本文在借鉴国外前沿启发式算法思想的基础上，基于L i n K e r n i g h a n改进型算法引擎，开发了能够高效解决T S P 的可视化处理软件。在如下几方面傲了深入研究：首次将T S P 处理软件的开发作为一个研究课题。说明对T S P 问题的研究，应该将算法设计与软件构建并列考虑，并特别重视对完整软件的开发，以促进优秀算法的广泛传播和改善发展。本文对可视化T S P 处理软件的概念界定是一个研究亮点。基于概念界定设计了合理的软件功能架构，使T S P 问题生成的可视化、T S P 数据显示的可视化、T S P求解性能的可视化集一大成。在引进了经典的L i n - K e r n i g h a n 算法基础上，对该算法作了较大改进。特别深入的探讨了候选边集的生成方法，即运用最小1 一树和升级( A s e e m ) 操作确定n 接近度，由此对边的优先性排序。相比于传统的近邻法，a 一接近度法确定最优边的性能大大改善。本文特别重视阐述算法实现细节与其性能问的深刻联系，用两章的篇幅分别介绍了算法引擎的C 语言开发和可视化平台的V C 开发。其中在算法引擎章，围绕引擎的总体流程，对重要启发式算子的程序实现作了深入说明，并穿插了边成本的快速计算、存储和查找镶略；初始解的生成策略；数据结构的选择策略等。在可视化章，围绕软件模块架构，依次介绍了数据处理模块的开发、可视化模块的开发和扩展模块与算法引擎的整合，并穿插了大量的数据结构介绍和容器选取应用策略。这两章内容是难得的开发模块化的高效T S P 程序软件的指南。基于本文开发的可视化T S P 处理软件性能优良。首先，它广泛支持T S P L I B的T S P 、A T S P 、H C P 类问题，对T S P L I B 中大部分问题都在较短时间内求出了最优解，包括7 3 9 7 点的T S P 问题。其次，它的扩展模块支持T S P 问题快速生成、地图模式和坐标模式的人机交互操作。文中解决的案例和各类图示都说明该软件对广大研究、应用人员有重要的研究应用价值。硕士研究生：于龙振( 管理科学与工程)指导教师：藏更新副教授关键诃：T S P ) L i n - K e r n i g h a n 算法；改进：软件：可视化；T S P L I BI m p l e m e n t a t i o no ft h eV i s u a lP r o c e s sS o f t w a r eF o rS o l v i n gT S Pb a s e do nM o d i f i e dL i n K e r n i g b a nA l g o r i t h mA b s t r a c tT S Pi sat y p i c a lp r o b l e mo fi t sg e n r e ：c o m b i n a t o f i a lo p t i m i z a t i o n f u r t h e r t T l o r e T S Pi st h eo r i g i n a lf o r mo f m a n yr e a l i s t i cp r o b l e m s S o ，t h a t t a k i n gat h o r o u g ha n db r o a ds t u d yo nT S Ph a si m p o r t a n tt h e o r yv a l u ea n dp r a c t i c a lv a l u e T h i sp a p e rd e s c r i b e sa l le f e e c t i v eV i s u a lP r o c e s sS o f t w a r eF o rS o l v i n gT S Pw h i c h Sc o n s t r u c t i o ni 8b a s e d0 1 3t h eM o d i f i e dL i n K e r n i g h a nA l g o r i t h mE n g i n e S u b j e c t sa sf o l l o w sa r em a d eat h 0 1 “ 0 1 t g t ls t u d y F o rt h ef i r s tt i m e ，t h ed e v e l o p m e n to ft h eT S Pp r o c e s ss o f t w a r ei sc o n s i d e r e da sac e n t e rr e s e a r c hp r o b l e m I nf a c t a l g o r i t h m sd e s i g na n ds o f t w a r e sc o n s t r u c t i o na r et h et w od o m i n a t i n gf a c e t st h a td e t e r m i n et h ef i n a lS U C C E S S T h e r e f o r e ，i t sn e c e s s a r yt og i v ee m p h a s i so nt h eb o t hs i d e s T h ed e f i n i t i o no ft h eV i s u a lP r e c e s sS o f t w a r eF o rS o l v 协gT S P ( V P S - T S P li sar e s e a r c hi n n o v a t i o n A c c o r d i n gt ot h ed e f i n i t i o n ， V i s u a l ”e o n s i s i so fv i s u a l i z eo ft h es t a n d a r dp r o b l e mc r e a t e ，v i s u a l i z eo ft h ed a t ad i s p l a y , a n dv i s u a l i z eo ft h er e s u l ta n dt h ep e r f o r m a n c e A tt 1 1 ef a s tc h a p t e r , c l a s s i cL i n - K e r n i g h a na l g o r i t h mj si n t r o d u c e d o nw h i c hac o m p r e h e n s i v em o d i f i c a t i o ni sm a d et h e n A ni m p o r t a n tm e a s u r e 一旺- n e a l T l e S si su s e dt op r o d u c et h eC a n d i d a t eS e t ，C o m p a r e dw i t ht h en e a r e s tn e i g h b o rr n e a g u l 七, G - h e a r t l e s sb r i n g so u tm u c hb e t t e rp e r f o r m a n c e R e l a t i o n s h i pb e t w e e nt h ep r o g r a m sd e t a i la n da l g o r i t h m sp e r f o r m a n c ei st h o u g h tm u c ho f I tt a k e st w os e p a r a t ec h a p t e r st oi n t r o d u c et h ed e s i g no fa l g o r i t h m se n g i n e ( b y Cl a n g u a g e ) a n dt h ec o n s t r u c to ft h eV P s - T S P ( b yV i s u a IC + + ) A tt h es e c o n dc h a p t e r ,a c c o r d i n gt ot h ee n g i n e sg e n e r a lp r o c e d u r e i m p o r t a n th e u r i s t i co p e r a t o r sa r ep r e s e n t e da st h ef o r mo fp s e u d oc o d ei nt u r n A n d t h es t r a t e g i e sf o rs i m p l i f yt h ec o s t sc a l c u l a t e s t o r ea n dl o o k u p ：p r o d u c i n gi n i t i a lt o u r ；s e l e c t i n gs u i t a b l ed a t as r f u c t - t l r e , n c ，a r ep r e s e n t e d A tt h et h i r dc h a p t e r , a c c o r d i n gt oV P S - T S P sm o d u l a r i z a t i o r t , d e v e I o p m e n to ft h eD a t aP r o c e s s i n gM o d u l e V i s u a l i z eM o d t t l ea n di n t e r g r a t i o no f t h eE x t e n d e dM o d u l ea n dt h eA l g o r i t h mE n g i n e e ra r ep r e s e n t e di nd e t a i l s I naw o r c Lt h ep a p e ri saf u l lg u i d ef o rd e v e l o p i n gh i g hq u a l i t yT S Ps o f t w a r e T h et e s to fV P S - T S Pi si m p r e s s i v e A t 盘s t i tc a l ls u p p o r tm a n yk i n do fT S P( i n c l u d eT S EA T S Pa n dH C P ) a n dc a uf i n dt h eb e s tt o u ro fT S P L I B sm a j o r i t yp r o b l e m si nl i t t l et i m e ( t h el a r g e s tp r o b l e mh a sad i m e n s i o no f 7 3 9 7p o i n t s ) S e c o n d l y , i t sE x t e n d e dM o d u l es u p p o r t sq u i c k l yc r e a t i n gT S Pp r o b l