快速路径寻找优良的地理信息体系网络数据结构策划和算法探究.pdf

快速路径寻找优良的地理信息体系网络数据结构策划和算法探究

引言

路径寻优问题是组合优化中的经典问题，在物流优化决策中，

如从原料采购点到生产制造、从制造工广到仓储、从配送中心到各配送终

端、从回收点到回收中心等物流过程中，都会遇到路径寻优问题。路径寻

优的目标一般通过道路网络中边的权重来表示，根据不同的求解要求，目

标函数可以为路径的距离、行车时间以及成本等。

随着地理信息系统(GeographicalInformationSystem，简称

GIS)在物流领域的广泛应用，物流软件业提出了在大规模复杂道路网络中

实现快速路径寻优的计算要求。对于单源点的最短路问题，目前被普遍使

用的一种多项式算法是Dijkstra算法，该算法能够有效地求解一般规模

的最短路问题，但对于大规模复杂道路网络，仍然表现出较大的时间延

迟，满足不了目前GIS系统在物流优化决策支持中的应用要求。而目前一

些文献中采用的启发式算法，由于不能保证最优性，无法在物流优化决策

中得到一般性的应用。

本文针对GIS的道路网络，对GIS网络结构进行重建，设计一

种层次数据结构设计，并给出相应的算法，可实现快速路径寻优，能有效

地支持物流决策的实时计算功能。

1.1研究背景

现代物流管理的快速发展对物流水平的提高提出了严峻的要

求，而快速路径寻优问题存在于物流配送流程中的各个环节:间、从工厂

到仓储物流的仓库之间，从仓库到配送中心和配送中心到各个配送点之

间、从回收物流中的回收中转站点到回收总站之间都存在着寻找单点一单

点、单点一多点、多点一多点之间的最短路问题。在整个流程中，最短路

求解的目标在不同的应用环境下代表的实际含义也不同，可能是总距离最

短也可能是总时间最短等。在物流管理中，主要从物流成本和物流效益的

角度来赋予实际问题中最短路的目标含义，如:将物品从配送点到客户之

间的配送过程中，客户可能是优先级非常高的顾客并且要求第一时间送

达，此种情况下就要求从物流效益中的客户满意度指标出发，寻找以总时

间最短为目标的一条最优路径将物品送达。

信息技术的发展和商业的日益国际化推动了物流管理的发展，

除去部分垄断性行业，全球化趋势促进了企业间竞争趋向完全竞争，为了

提高核心竞争力，企业不仅考虑如何提高利润，同时也注重控制总成本。

所以，降低物流总成本也成了影响企业竞争力的因素之一，做好企业物流

管理中的路径规划，在错综复杂的配送网络中及时有效地得到最优配送路

径，为物流企业完善管理手段、减低管理成本、提高经济效益、最终提升

核心竞争力提供了机遇。

随着GIS在物流管理中的广泛应用，实际的路径寻优问题依附

于GIS道路网络图进行规划求解，GIS可以图文并茂地将道路网络的地理

信息及属性信息显现在可视化界面上，并且具有良好的数据存储功能，可

以直观地、科学地提供决策支持。物流配送一般发生大规模的道路网络图

中，道路网络范围可能是社区，城市，同时也可能发生在整个国家或者整

个洲，依附于GIS道路网络图进行的物流配送中的路径寻优属于大规模的

最短路问题。

实际GIS网络图中进行的实时批量路径寻优问题，可以看成多

次求解单源点最短路问题，目前图论中已经提出了多种经典的最短路求解

算法，本文将在第三章详细地对单源点算法进行综述和评价。可以发现，

这些算法在大规模道路网络中的实施主要显现两个方面的不足:

1.最短路问题的最优求解算法需要花费较长的时间来处理大规

模网络图的数据，这样，要得到最优路径，需要等待过长的响应时间。最

短路最优求解算法中经典Dijkstra算法求解的是单点到网络中其余所有

点之间的最短路，当在大规模网络图中进行实际应用查询最短路时，在得

到单点到单点或者单点到部分多点之间的最短路时，Dijkstra算法的大

范围搜索和大量数据处理，将延长等待结果的时间。

3算法综述19-28

3.1最优化算法19-26

3.1.1标号方法19-20

3.1.2BF和BFP算法20-22

3.1.3Dijkstra算法22-23

3.1.4DIKBM、DIKBA23-24