绪论
1.1 引言
20 世纪 60 年代，GIS 主要解决的是与计算机制图相关的问题，如：栅格数据与矢量数据的转换、自动拓扑、地图输出等。20 世纪 70 年代是 GIS 发展的巩固期，在这一时期出现了大量的专题 GIS 软件， GIS 更注重研究属性数据和空间数据的分类管理、人机交互、数据处理、地图扫描输入等问题。20 世纪 80 年代，随着图形化工作站和计算机技术的发展，GIS 进入发展的突破期，出现了多功能、数据共享的 GIS 软件和大量的商业GIS 工具软件，逐渐形成了 GIS 产业[7]。20 世纪 90 年代至今，GIS 得到了全面的应用与发展，已经深入到各行各业，成为科学研究、办公服务、个人应用、抢险救灾、决策支持等很多相关系统的基础平台。军事地理信息系统是一个专业地理信息系统，它能够存储、管理、获取和分析战区地理环境信息，为战场决策提供相应的辅助信息，是数字化战场建设的重要内容，是指挥自动化系统的基础平台，是现代武器系统的重要组成部分
。随着军事任务的不断发展，军事地理信息系统在非战争军事行动中也发挥出了重要的作用，它已经成为信息化条件下辅助决策的一个不可或缺的重要工具。经过近半个世纪的发展，在功能方面，GIS 的数据输入、存储、可视化等功能都已基本完善，因此空间分析成为 GIS 应用发展的一个主要方向。GIS 中的空间分析主要包括：空间数据统计分析、数字高程模型分析、空间数据的叠置分析、空间数据缓冲区分析、空间数据网络分析等。其中网络分析是 GIS 空间分析的一个重要组成部分，网络分析中用到的网络模型属于数学模型中离散模型的一部分。图论是分析与解决网络模型的一个有力工具[7]。图论中旅行售货员问题，简称 TSP（Traveling Salesman Problem），其描述为：一个旅行推销员从驻地出发，经过所有目标城市至少一次，然后返回原地，如何安排其旅行路线使总的路线距离最短。TSP 问题是一个易于描述难以解决的问题，网络分析中很多实际应用都可以归结为 TSP 问题。
由于 TSP 问题求解困难、算法多样、构模复杂等诸多原因，GIS 网络分析中对 TSP 问题建模与求解的研究还较少，但是这类问题的实际应用却是比较多的，因此 GIS 中 TSP 问题的建模与应用具有较高的科研价值，值得深入探讨与研究。
1.2 背景意义
2006 年的我国国防白皮书中，出现了“多样化军事任务”的概念，“多样化军事任务”包括战斗行动和非战争军事行动（MOOTW）。2008 年我国国防白皮书中，表示我军要以提高“打赢信息化条件下的局部战争”能力为核心，并将非战争军事行动作为使用军事力量的一个重要形式。非战争军事行动的种类有很多，例如：反恐行动、维和行动、非战斗性的疏散撤离行动、灾害救援行动等等。2008 年“汶川”大地震以后，灾区很多基础设施遭到严重破坏，人民群众的生命安全受到了严重的威胁。
在这种情况下，党中央和中央军委立即派出了专业调查组，深入灾区对受灾的各村镇进行调查汇总，为中央的抗震救灾指挥提供必要的决策支持信息，这是一个典型的非战争军事行动。面对众多的受灾地点、有限的人力和紧迫的时间，选择一条最短的路线就显得尤为重要。此外，泄洪区清场、武器试验区清场、战斗地点弹药运送、火灾警示清场等非战争军事行动，也都对路线的选择有着很高的要求。其中“清场”是指疏散对应区域内的所有居民，战斗点弹药运送需要在最短的时间内为多个不同的战斗点配送弹药。这些实际问题有着共同的特点：需要现场通知与检查、突发性高、时间紧、任务重、资源有限、人命关天。因此这些问题中，路线的选择非常重要，选择了错误的路线可能会因为时间的延误而带来沉痛的代价。从这些问题的描述可以看出，这类问题都可以归结为现实地理空间中的 TSP 问题。TSP问题作为一个运筹图论中的著名难题，其可能的路线有(n-1)!/2 种（n 表示目标点的个数），精确求解的计算时间可能需要几小时、几天、甚至几十天，近似求解也需要应用专业的算法利用计算机进行求解。除模型求解困难之外，将地理空间中的实际问题构建为一个可用于求解的数学模型，也需要一个复杂的建模过程。因此这类问题的路线选择相当复杂，不能通过盲目的人工随机选择确定，需要专业的软件进行辅助决策。
但是当前对 TSP 问题的研究还主要集中在求解算法上，对 GIS 中实际地理空间 TSP 问题的建模与自动求解的研究还相对较少。人类使用地图表示空间数据已经有相当长的历史，但是只有在 GIS 出现以后，空间数据才得以发挥其更多的作用。GIS 既可以对地理数据进行定量的分析，又可以将分析的结果用图形化的方式表达出来。GIS 兼顾数据思维与空间思维，与传统地图上的空间分析和只针对数据的定量分析相比有了质的提高。因此 GIS 逐渐成为科学研究、决策支持、办公服务等领域中相关系统的一个基础平台。TSP 问题作为 GIS 空间分析中，网络分析需要解决的一个重要问题，在军事行动和日常生活中的应用十分广泛，同时其构模与求解也需要计算机的支持，因此在 GIS 中对 TSP 问题建模与求解的研究，直接影响到 GIS 作为一个决策支持平台的完善性。综上所述，研究 GIS 中 TSP 问题的建模与应用，既具有非常重要的现实意义，又是决策信息化进程中 GIS 平台发展的必然要求。
1.3 研究现状
1.3.1 GIS空间分析的研究现状
空间分析是利用地理对象的拓扑关系、几何关系、地理属性等来研究相应事物的一种技术。自从地图产生以来，人们就开始进行着各类空间分析，比如：地理要素之间的距离量算、面积量算等。
第二章TSP问题典型算法对比分析.................6
2.1 精确算法..............6
2.2 近似算法..............7
2.3 本章小结..............9
第三章 GIS 中 TSP 模型的构建..............10
3.1 建模方式的选择...............10
3.2 图论相关知识的介绍............10
3.3 图论模型的构建...............11
第四章 TSP 问题求解算法的选择与改进...............18
4.1 算法的选择思路与选择指标..............18
4.2 选择基础算法.............19
4.3 遗传算法的改进...........20
总结
本文首先阐述了处理与分析地理空间中存在的 TSP 问题的必要性、紧迫性和复杂性，进而提出了研制具有 TSP 问题空间分析功能的 GIS 软件平台的解决思路。围绕这一解决思路本文的主要研究工作和创新点总结如下：
1. 分析了地理空间中 TSP 问题的结构特点，选择了适用于“点线结构”问题构模的图论建模方式。
2. 对比了“保留交叉点”和“忽略交叉点”两种模型要素抽象方式的优缺点，选择了“保留交叉点”的模型要素抽象模式。
3. 分析了地理空间数据中线要素和结点可能出现的情况，确定了模型中“边权值”的获取方式。
参考文献
[1] 杜端甫.运筹图论[M].北京:北京航空航天大学出版社,1990.
[2] 刘赞武.应用图论[M].长沙:国防科技大学出版社,2006.
[3] 张最良,李长生,赵文志,丁富力.军事运筹学[M].北京:军事科学出版社,1993.
[4] 王家耀,成毅,吴光明,等.地理信息系统的演进与发展[J].测绘科学技术学报,2008,25(4):235-240.
[5] 朱建青,张国梁.数学建模方法[M].郑州:郑州大学出版社,2003.
[6] 杨保安,张科静.多目标决策分析[M].上海:东华大学出版社,2008.
[7] 华一新,吴升,赵军喜.地理信息系统原理与技术[M].北京:解放军出版社,2001.
[8] 郭仁忠.空间分析[M].武汉:武汉测绘科技大学出版社,2000.
[9] 李水旺,孙振营,蔡中祥.应急救灾公路运输中的车辆分配问题[J].测绘科学技术学报,2012,29(1):47-50.
[10] 池建.精通 ArcGIS 地理信息系统[M].北京:清华大学出版社,2011.