地理网络分析作为GIS空间分析的重要组成部分,在交通、物流、电商等众多领域中的作用日益重要。随着分析范围逐渐扩大,数据量不断膨胀,日益复杂的计算任务对基础网络分析算法提出了更高要求。地理网络分析中包含若干复杂性较高的问题,如p-中位问题、车辆路径问题等,均属于NP难题,通常采用启发式算法进行求解。但是随着实际应用中问题规模的增大,传统串行算法已无法满足复杂应用场景对计算效率和求解规模的需求。针对传统串行算法计算效率低、处理规模有限的问题,本文拟将并行技术与启发式算法相结合,利用新型硬件架构下的并行计算资源来提高传统算法的求解效率和处理规模。论文主要进行了以下工作:(1)归纳与总结了并行启发式算法在地理网络分析中的应用模式。将并行技术和启发式算法应用于地理网络分析时,存在一些共性的问题和通用的技术手段。因此,有必要对这些问题和方法进行归纳总结,提出一个通用的应用框架,以指导针对具体问题的并行算法的设计与开发。首先,本文对各类地理网络问题的特点及其潜在的并行特性进行了分析,并根据计算复杂性将现有网络分析问题划分为简单问题、计算密集型问题和NP-难题三大类,将后两类作为本文的主要研究对象。然后,总结了两种可应用于地理网络分析的并行启发式算法构建方案。第一种为具有普适性的算法并行模式,即针对串行算法中计算耗时较多的部分进行并行化以提高计算效率。这种方法能够在保证求解质量不变的条件下提高算法的计算效率。第二种为基于网络分割的并行化模式,主要针对一些具有局域特性的问题。该方法不具有普适性,且会损失一定的求解质量,但是在某些问题上可以获得极高的效率,并能用于求解一些串行算法无法解决的超大规模问题。此外,本文还对并行地理网络分析算法中涉及到的一些通用的数据存储策略、算法测试与优化方法等进行了归纳。通过以上工作,总结了一套切实可行的应用模式与通用流程,对后续针对具体问题的并行启发式算法的设计与实现具有指导意义。(2)提出了求解p-中位问题的并行分散搜索算法。在设施选址问题中,经典启发式算法和元启发算法是应用最为广泛的两类算法。经典启发式算法计算效率高,但通常求解质量较差;元启发算法能够获得高质量的解,但计算效率远低于前者。针对以上问题,本文拟利用并行技术提高元启发算法的效率,并以p-中位问题的求解为例,构建了高效的并行分散搜索算法。该并行算法以分散搜索框架为基础,采用主从模式对其中耗时较多的初始解优化和解组合过程进行并行化:针对初始解优化过程,采用粗粒度的并行策略,将不同解的优化任务分配至不同进程同时进行;针对解组合过程,采用细粒度的并行策略,对子集空间进行区域分解,然后分配至不同进程以实现解组合的并行执行。本文采用通用测试集和模拟路网数据进行了相关实验。首先,采用通用测试集or-library中规模较大的几个实例对算法的正确性进行验证。结果表明,本文算法具有较高的求解质量,在大部分实验中均得到了最优解,即使没有取得最优解其偏差也在0.3%以内。然后,采用模拟路网数据对算法的并行效率和求解质量进行了测试。在三个不同规模的测试数据集中,应用本文算法使用1~6个进程分别进行实验,将其计算结果和运行时间与一种高效的经典启发式算法——densham-rushton(dr)算法进行对比。实验结果表明:本文算法具有良好的加速比,当进程数为5时运行时间比串行分散搜索算法减少了近60%,已经与dr算法相当;其求解质量与串行分散搜索算法相同,较dr算法提高了0.4%~0.9%不等。综上所述,本文提出的并行分散搜索算法能够在与经典启发式算法相当的时间内获得更高质量的解,兼顾了计算效率和求解质量。(3)提出了求解地理网络车辆路径问题(vrp)的并行算法。地理网络vrp问题不同于图论vrp,在应用图论中的算法对其进行求解时需要先进行od矩阵(origin-destinationmatrix)计算将其转化为图论vrp。在大规模地理网络vrp中,这一转化过程的时间和空间开销都是相当庞大的。为此,本文拟从od矩阵计算和禁忌搜索过程两方面入手,对传统串行分析过程进行并行化,以提高地理网络vrp问题的整体求解效率。同时,考虑具体硬件平台的特性,针对pc集群环境对算法进行设计。首先,在od矩阵计算过程中采用并行johnson算法提高计算效率,并通过分布式存储策略将巨大的空间开销分散在各计算节点上,有效避免单节点内存不足的问题,提升算法的处理规模。然后,采用邻域分解的策略对禁忌搜索过程进行并行化,并通过精简的通信数据结构提高通信效率。最后,基于6个不同规模的模拟路网vrp实例,采用1~8个进程对算法进行对比实验。实验结果表明,本文算法能够在保证计算精度的前提下(平均偏差率在2.11%~2.87%之间)高效的求解大规模地理网络vrp问题,且具有良好的扩展性;同时能够在pc集群环境中获得良好的加速性能,采用8个进程时的算法加速比在4.46~6.32之间。(4)提出了基于网络分割的并行p-中位算法。通过对串行算法的并行化可以提高求解p-中位问题的效率,但是随着问题规模的增大,算法的空间瓶颈问题限制了其处理规模。本文利用p-中位问题的局域性特点,提出了一种基于网络分割的并行启发式算法,通过网络分割降低问题规模,提高计算效率。该算法首先利用METIS图划分工具对网络进行分割,通过设置合理的点权向量和划分参数将网络分割为均衡的子块;然后在子块内使用启发式算法进行独立求解;最后,通过特殊设计的归并方法调整中位点分配,优化全局解质量。本文在两个不同规模的模拟网络中进行了对比实验,结果表明:①该算法效率极高,多进程时的求解时间较串行算法可减少一到两个数量级;②算法的求解质量略差于串行算法,但在分块数合适时偏差可以控制在0.3%以内;③在串行算法无法求解的大规模问题中,该算法可采用多进程进行有效求解,且加速性能十分理想。综上所述,本文提出的基于网络分割的并行p-中位算法能够在保证一定求解精度的前提下大幅提升计算效率,且算法的处理规模能够随着计算节点数的增加而增大,可用于求解串行算法无法解决的超大规模p-中位问题。