引言
路径寻优问题是组合优化中的经典问题，在物流优化决策中，如从原料采购点到生产制造、从制造工广到仓储、从配送中心到各配送终端、从回收点到回收中心等物流过程中，都会遇到路径寻优问题。路径寻优的目标一般通过道路网络中边的权重来表示，根据不同的求解要求，目标函数可以为路径的距离、行车时间以及成本等。
随着地理信息系统(Geographical Information System，简称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.2 BF和BFP算法............ 20-22
3.1.3 Dijkstra算法............ 22-23
3.1.4 DIKBM、DIKBA............ 23-24
3.1.5 PAPE、TWO__Q............ 24-25
3.1.6 Threshold算法............ 25-26
3.1.7 Topological Ordering............ 26
3.2 启发式算法............ 26-28
4 GIS网络的层次............ 28-43
4.1 干道网络的构建............ 28-31
4.1.1 干道判别准则............ 28-30
4.1.2 干道判别............ 30-31
4.2 干道网络的............31-32
4.3 GIS网络的多级............ 32-34
4.4 GIS网络的层次数据结构............ 34-43
5 基于GIS多级干道网络............43-53
5.1 双向搜索算法............ 43-44
5.2 双向搜索算法............ 44-46
5.3 双向算法搜索............46-47
5.4 基于GIS多级干道............ 47-53
总结
这一章对本文的研究工作进行总结，并拟出进一步研究方向。
本文针对大规模GIS道路网络，在D.Schultes 02005)提出的层次数据结构基础上，进一步考虑GIS道路网络中存在车辆通行限制(吨位限制)的情形，对GIS网络的数据结构进行重新建构，并给出相应的最短路最优算法。研究内容包括:
1.利用GIS道路网络结点度数小、干道网络、道路通行有限制的特点，应用两阶段法进行干道判别，构建底层干道网络，并通过图的压缩处理方法完成多层干道网络的构建。