25542字硕士毕业论文地理信息系统中TSP的研究及其军事应用

介绍

1.1导言

20世纪60年代，地理信息系统主要解决与计算机制图相关的问题，如栅格数据和矢量数据的转换、自动拓扑、地图输出等。20世纪70年代是地理信息系统发展的巩固期，其间出现了大量专题地理信息系统软件。地理信息系统更加重视属性数据和空的分类管理、人机交互、数据处理、地图扫描输入等问题。20世纪80年代，随着图形工作站和计算机技术的发展，地理信息系统进入了一个突破性的发展时期，随着多功能、数据共享的地理信息系统软件和大量商用地理信息系统工具软件的出现，逐渐形成了[7]。20世纪90年代以来，地理信息系统得到了全面的应用和发展。它已经渗透到各行各业，成为科研、办公服务、个人应用、应急救援、决策支持等诸多相关系统的基础平台。军事地理信息系统是一个专业的地理信息系统。它可以存储、管理、获取和分析战区的地理环境信息，为战场决策提供相应的辅助信息。它是数字化战场建设的重要内容，是指挥自动化系统的基础平台，是现代武器系统的重要组成部分。

。随着军事任务的不断发展，军事地理信息系统在非战争军事行动中也发挥了重要作用。它已经成为信息条件下辅助决策不可或缺的重要工具。经过近半个世纪的发展，地理信息系统的数据输入、存储、可视化等功能在功能上已经基本得到了提高。因此空分析已经成为地理信息系统应用发展的主要方向。地理信息系统中空之间的分析主要包括空之间的数据统计分析、数字高程模型分析、空之间的数据叠加分析、空之间的数据缓冲区分析、空之间的数据网络分析等。其中，网络分析是地理信息系统空的重要组成部分，用于网络分析的网络模型是数学模型中离散模型的一部分。图论是分析和解决网络模型的有力工具[7]。在图论中，旅行推销员问题(TSP，缩写为TSP)被描述为旅行推销员如何从他的住所出发，至少经过一次所有的目标城市，然后回到他原来的地方，以及如何安排他的旅行路线以使总路线距离最小化。TSP是一个容易描述和难以解决的问题。网络分析中的许多实际应用可归因于TSP。

由于求解TSP问题困难、算法多样、建模复杂等诸多原因，在地理信息系统网络分析中建模和求解TSP问题的研究仍然较少，但这类问题有很多实际应用。因此，TSP问题在地理信息系统中的建模和应用具有很高的科研价值，值得深入探讨和研究。

1.2背景含义

2006年，“多样化军事任务”的概念出现在中国国防白皮书中。“多样化军事任务”包括作战行动和非战争军事行动(MOOTW)。2008年中国国防白皮书指出，我军应着力提高“在信息化条件下打赢局部战争”的能力，把非战争军事行动作为使用军事力量的重要形式。有许多类型的非战争军事行动，如:反恐行动、维持和平行动、非战斗疏散行动、救灾行动等。2008年汶川地震后，灾区许多基础设施遭到严重破坏，人民生命受到严重威胁。

在这种情况下，党中央、中央军委立即派出专业调查组深入灾区，对受灾乡镇进行调查总结，为中央抗震救灾指挥部提供必要的决策支持信息。这是典型的非战争军事行动。面对众多的灾害现场、有限的人力和紧迫的时间，选择最短的路线尤为重要。此外，非战争军事行动，如清理泄洪区、清理武器试验区、在战场运输弹药和清理火警区，对路线选择也有很高的要求。其中，“净空”是指相应区域内所有居民的疏散。战斗点的弹药运输需要在尽可能短的时间内向许多不同的战斗点分发弹药。这些实际问题具有共同的特点:需要现场通知和检查、突发性高、时间紧、任务重、资源和人类生活有限。因此，在这些问题中，路径的选择是非常重要的，选择错误的路径可能会因时间延迟而带来痛苦的代价。从这些问题的描述中可以看出，所有这些问题都可以归因于真实地理空中的TSP。作为运筹学中一个众所周知的问题，旅行商问题有(n-1)条可能的路线！/2种(n表示目标点数)。精确求解的计算时间可能需要几个小时、几天甚至几十天。近似解还需要应用专业算法和使用计算机求解。除了求解模型的困难之外，还需要复杂的建模过程来将地理空之间的实际问题构造成可用于求解的数学模型。因此，这类问题的路径选择相当复杂，不能通过盲目的手动随机选择来确定。需要专业软件来帮助决策。

然而，目前对TSP的研究主要集中在求解算法上，而对地理信息系统中实际地理空之间TSP的建模和自动求解的研究相对较少。很长一段时间以来，人类一直使用地图来表示空之间的数据，但是只有在地理信息系统出现之后，[/k0/]之间的数据才能发挥更多的作用。地理信息系统不仅可以对地理数据进行定量分析，还可以图形化地表达分析结果。地理信息系统将数据思维与空思维相结合，这比仅针对传统地图数据的空分析和定量分析有了质的改进。因此，地理信息系统逐渐成为科研、决策支持、办公服务等地方相关系统的基础平台。TSP作为地理信息系统空网络分析中需要解决的一个重要问题，广泛应用于军事行动和日常生活中。同时，它的建模和求解也需要计算机的支持。因此，地理信息系统中TSP建模与求解的研究直接影响到地理信息系统作为决策支持平台的完善。综上所述，研究TSP在地理信息系统中的建模与应用不仅具有重要的现实意义，也是决策信息化过程中地理信息系统平台发展的必然要求。

1.3研究现状

1.3.1地理信息系统空分析研究现状

空之间的分析是一种利用地理对象的拓扑关系、几何关系和地理属性来研究相应事物的技术。自从地图出现以来，人们一直在进行各种类型的分析空，例如地理要素之间的距离测量和面积测量。

第二章对旅行商问题的典型算法进行了比较和分析……6

2.1精确算法...................6

2.2近似算法...................7

2.3本章总结...................9

第三章地理信息系统中TSP模型的构建...................10

3.1建模方法的选择……10

3.2图论相关知识介绍……10

3.3图论模型的构建……11

第四章TSP算法的选择和改进……18

4.1算法和选择指标的选择...................18

4.2选择基本算法……19

4.3遗传算法的改进……20

摘要

摘要:首先阐述了地理空中处理和分析TSP问题的必要性、紧迫性和复杂性，然后提出了开发具有TSP问题空分析功能的地理信息系统软件平台的解决方案。本文的主要研究工作和创新点总结如下:

1.分析了地理空中TSP问题的结构特征，选择了一种适用于“点线结构”问题建模的图论建模方法。

2.比较了模型元素“保持相交”和“忽略相交”两种抽象模式的优缺点，选择了“保持相交”的模型元素抽象模式。

3.分析了地理空之间数据中可能出现的线元素和节点，确定了模型中“边缘权重”的获取方法。

参考

杜端福。运筹学图论[。北京:京航空航空航天大学出版社，1990。

刘赞武。应用图论[。长沙:国防大学出版社，2006。

[3]张志良、李长胜、赵文志、丁福礼。军事行动研究[。北京:军事科学出版社，1993。

王家耀，程毅，吴光明，等。地理信息系统的演变与发展[。测绘科学与技术杂志，2008，25(4):235-240。

张郭亮，朱剑清。数学建模方法[。郑州:郑州大学出版社，2003。

[6]杨宝安，张克敬。多目标决策分析[。上海:东华大学出版社，2008。

[7]华宜欣、吴胜、赵军喜。地理信息系统原理与技术[。北京:中国人民解放军出版社，2001。

[8]郭任重。空[分析。武汉:武汉测绘大学出版社，2000。

李瑞旺，孙振英，蔡忠祥。[紧急救援公路运输中的车辆分配。测绘科学与技术杂志，2012，29(1):47-50。

[10]郗鉴。精通[地理信息系统。北京:清华大学出版社，2011。