基于综合路阻函数的多源最短路径计算

郭丽　刘磊　缑西梅

摘 要 路径优化是物流配送方案中最核心的问题。本文提出考虑行驶距离、拥堵程度及平均行驶时间的综合路阻函数计算方法，并提取OSM地图中路段数据构建有向图，基于Dijkstra算法求得最短路径。

关键词 路径优化 综合路阻函数 Dijkstra算法

中图分类号：TP311 文献标识码：A

0引言

高效率合理的配送是物流系统顺利运行的保证，配送线路安排的合理与否对配送速度、成本、效益影响很大。正确合理地安排车辆的配送线路，实现合理的线路运输，可以有效地节约运输时间，增加车辆利用率，从而降低运输成本，提高企业经济效益与客户服务水平，使企业达到科学化的物流管理，？这也是企业提高自身竞争力的有效途径之一。

路径优化是物流配送中的核心问题。路径优化总的解决思路如下：

（1）路网的表示

（2）道路权重的标定

（3）最短路径算法求解

（4）把图中的最短路径还原成现实路网中的路段集

1路网的表示

交通路网的构成实体不仅具有非空间属性数据，例如等级、长度、类别、行程时间或延误时间等；还具有空间属性数据，例如空间位置。本项目将路网信息使用图来进行表达，表示方式如下：

（1）顶点：代表道路的交叉口或者终点，Vertex记作V。

（2）边：代表两个结点之间的一条可以互通的有方向的道路，Edge记作E。

（3）权值：代表路段的某些特征属性的量化，如路段长度、独断平均行程时间，即道路权重。Weight记作W。

一般来说，路段两个方向的交通流情况并不一致，当采用与交通流有关的拥堵计算时，采用有向图更为合适，并且有向图跟有利于处理单行线、转向等特殊情况。所以本项目将路网抽象成为一个赋权有向图，从而确定路网中某两地间的最优路线问题，转化为图论中的最短路径问题。

本文将物流配送网络使用有向图G=（V，E，W）来表示。其中V为顶点集，V={Vi|i=1，2，…n}；E为边集，E={e（Vi，Vj）|Vi，Vj∈V}；W为权值集W={W（Vi，Vj）|Vi，Vj∈V}。

1.1 OpenStreetMap

OpenStreetMap（簡称OSM）是一个网上地图协作计划， OSM地理数据文件既包含了地理数据，又包含了对元数据的描述。每一个地理元素都拥有对应的元数据，用于记录数据修改的额时间、修改帐号和作者名称等等。OSM地理数据的描述采用的是一种包含拓扑性质的数据结构，其中与道路相关的地理元素主要包括节点（Node）和道路（Way）以及关系（Relation）。

1.1.1 Node节点

Node节点包括经纬坐标和高度信息。node通过经纬度定义了一个地理坐标点。同时，通过place=* and name=*来表示对象的名称。其他一些可选信息，如name等，在tag子标签中表示。

1.1.2 Way路线

Way表示地图中的一条线路，通过2-2000个点（nodes）构成。Way可表示如下3种。非闭合线，首尾不闭合的线路，通常可用于表示现实中的道路、河流、铁路等。闭合线，首尾相连的线路，例如可以表示现实中的环线地铁。区域，闭合区域，通常使用landuse=* 来标示区域等。

1.1.3 Realation关系

是有序列表nodes，ways和relations（合起来称为members成员）组成的，每一个成员可以选择拥有一个role角色，相互的关系通过role来定义。关系用来表示已经存在的nodes和ways之间的关系。

1.2数据解析及转换

作为一种以研究和共享为目的的空间路网数据，OSM 数据基元的属性值非常丰富，其尽可能地充分表达空间数据，以便不同领域的数据使用者方便提取。

OSM 路网数据和其他 GIS 数据一样，存储关系和逻辑关系是一种矢量关系，组成的点线面对象同样包括有对象的外在属性、对象的拓展与对象的空间位置。因此本项目中路网数据的拓朴关系是对Node和Node、Node和Way、Way和Way之间的相关关系、Relation与Relation之间的关系属性的数据描述。

首先，获取需进行配送的物流网络中的节点列表，其中节点使用经纬度表示，数据格式如下所示。

其中，每一行代表一个待配送网点的地址信息，第一个数字代表网点地址的经度，第二个数字代表网点地址的纬度。

如图1所示，在拿到待配送网点信息后，文件中的所有的点构成了路网的初始点集V，通过循环读取点集中的顶点，去ways表中查找是否有以该顶点为弧头的边，有则将该边上存在的所有nodes加入到点集中，并建立对应的边集E。由此建立，获取配送网点之间的详细路网。

2路网边权评价方法

路网的边权代表了当前两点之间的出行代价，很多学者也称之为路阻。对于路网边权的评价，实际上就是路阻函数的设计过程，即出行费用的计算过程。从可计量性和数据可获得性方面考虑，在实际考虑出行费用时，一般都采用被占用的时间或者能够反映被占用时间长短的其他指标，例如排队长度、耗油量、拥挤程度等等。因此在路径选择中，我们设计了考虑出行时间、行驶距离和拥挤程度三方面的综合路阻函数。

2.1行驶距离

行驶距离是静态的路阻数据，用C1i=Li表示，其中Li是路段i的长度。单独使用行驶距离作为路阻函数时，较适用于网络道路质量相近、交通流分布均匀的情况，这时指定OD对之间的最佳路径是固定不变的。

2.2平均行程时间

平均行程时间是最常用的动态路阻形式，用表示。指在第k个时段，车辆在该路段上运行时所用的平均时间，包括形式时间和停车延误时间。endprint

2.3拥堵程度

在交通网络中，“拥挤”是指道路上的车辆不能以正常速度行驶的现象，表现为行驶时间延长和停车延误增加。一般可用排队商都和路段的流量与同性能力之比来衡量。本项目定义反映拥堵程度的路阻函数为C3i（k）=ti（k）/t0。其中，ti（k是k时段i路段的平均运行时间，而是车辆以规定的最高速度通过该路段所需要的时间，是固定值。C3i（k）越小，拥堵程度越低，C3i（k）越大，拥挤程度越严重。

物流配送路径选择时，首先需要预定配送时间，行驶距离，当前时段的拥堵程度等综合情况。因此本项目设计了综合路阻函数为：

Ci（k）=h（C1i，C2i（k），C3i（k））

=b1C1i- +b2C2i- （k）+b3C3i- （k）

3基于Dijkstra算法的最短路徑算法

本项目将求解配送网络任意网点间的最短距离时，将通过上一节所示方法求得任意两路段间的路径长度、拥堵程度以及行驶时间，并通过综合路阻函数求得任意两路段间的出行费用，具体格式如下：

第一列和第二列代表路段出点的经纬度，第三列和第四列代表路段入点的经纬度，最后一列代表路段上的出行费用。

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路求得任意配送点间的最短送货线路。

4总结

本文基于OSM开源地图数据，获取物流配送点中，配有交叉路口信息的有向图。提出一种以拥堵系数及路径长度作为权值的最短路径求解方法，有效的提高了在物流配送中最短路径的精确度。

基金项目：本文为河南省科技攻关计划项目（162102310580，162102310582，172102210526，172102210593），河南省教育厅科学技术研究重点项目（15B520040，16A520099，17B520042）研究成果。

参考文献

[1] 刘海燕，李宗平，叶怀珍.物流配送中心选址模型[J].西南交通大学学报，2000，35（03）：311-314.

[2] 杨弋，顾幸生.物流配送车辆优化调度的综述[J]. 东南大学学报：自然科学版，2003，33（z1）：105-111.

[3] 廖良才，王栋，周峰.基于混合遗传算法的物流配送车辆调度优化问题求解方法[J].系统工程，2008，26（08）：27-31.endprint