一种基于富网络属性路网的物流配送方法

摘要

一种基于富网络属性路网的物流配送方法，包括以下步骤：A1.获得带有至少OBJECTID*，Shape*，NAME，Shape_Length，TIME5个字段的路网矢量数据，原始数据需要处理才能拓扑分析。A2.采用自动方法处理不及、超过和节点不相交的3种情况。A3.构建路网数据对象模型。A4.对地图数据检查过的矢量数据进行路网的拓扑处理。A5.路网拓扑关系利用节点表达路段与路段之间的连通性，因此构建城市路网的拓扑关系主要是提取和处理节点、路段信息，从而建立拓扑关系。A6.配送路线代价权值的确定也是将配送问题的非线性转化为线性问题求解的关键。A7.配送问题模型的建立。A8.针对配送问题模型提出的一种经典的表上作业法，可编程实现。

主权项

1.一种基于富网络属性路网的物流配送方法，其特征在于：所述富网络属性路网的配送方法包括以下步骤： A1、获得带有至少包含OBJECTID*，Shape*，NAME，Shape_Length，TIME5个字段的路网矢量数据，对原始的矢量数据的不及、超过和节点不相交3种情况进行处理； A2、处理不及、超过和节点不相交的3种情况，分3步纠正数据错误： ①设置交点区间（即两条道路端点是否相交的最小距离）； ②找出道路图层中每条道路对象的起点和终点（道路线路实体对象分为折线和直线）； ③比较任意两线起点间距离，若距离大于零并且在交点区间内，则使亮点重合（用两点间的中点替代）； A3、路网数据对象模型。路网数据对象模型是构建道路拓扑、路径分析的基础。路径分析系统可采用Arc-Node（弧段——节点）模型，该模型可以描述为： 式中：D为道路路网，V_c为路网中的客户节点，V_d为路网节点，构成对应图中的顶点集；A为路网中量节点之间的弧段；R_s为道路的有向路段集，对应图的弧段集，可以用道路网络中的两个节点的拓扑关系表示；u,v为道路的起点和终点；Q^uv为路段的属性集，可以表示长度、平均时速、行程时段、交通流的速率、接到最高限速、车道的数目以及在交叉路口道路灯的切换的时间间隔等； A4、路网的拓扑处理。采用自动断链技术把道路在交点处分成首尾相接路段，使这些路段除自身的首尾节点外不与其他任何路段相交，具体步骤如下： ①先计算道路图层道路总数Num（包括线和折线）； ②从任意指定的第一条道路开始，依次判断与其周围的其它道路是否相交，若相交则获取交点坐标； ③根据起始点，交点1，交点2，…，交点l和终点将线顺序打断添入线表，原线删除； ④循环执行上述步骤，直到Num条线段经过打断处理，路网中不再有相交路段； ⑤由于Arc-Node模型存在平面强化的弊端，因此需要对图层中计算的平面相交，但实际并不相交的路段进行手动纠正，如立交桥等； A5、城市路网拓扑关系的建立。路网拓扑关系利用节点表达路段与路段之间的连通性，因此构建城市路网的拓扑关系主要是提取和处理节点、路段信息，从而建立拓扑关系。具体步骤如下： ①从线表第一条记录开始获取路段端点坐标，并创建对象添加到点表中； ②检查点表有无重复记录，若有则删除； ③根据节点的X或Y坐标值的大小对节点表重新排序； ④为点表中每一个对象的连通的路段条数字段和第一条连通路段所在位置字段赋值； ⑤为线表中每一个对象的路段长度字段，起点编号字段和终点编号字段赋值； A6、配送路线代价权值的确定；从道路网络模型的角度看，最短路径分析就是在指定道路网络中两点之间找到一条阻抗最小的路径；根据阻抗的不同定义，最短路径不仅仅指地理意义的距离最短，还可以引申到其他的度量，如时间、费用等。 此处基于城市路网，采用Dijkstra方法实现最短路径分析和最短时间分析。Dijkstra方法的基本思路是：从任意一点v_s（v_s∈V_c∪V_d）出发，逐步向目标节点v_d（v_d∈V_c∪V_d且v_d≠v_s）寻找最短路径或最短时间；在执行过程中，给每个顶点予以标号：P标号表示从v_s到该点的最短路径或最短时间的权，也称永久性标号，即一旦某点v_s得到P标号，其值在整个求解过程中不再改变；T标号表示从v_s到该点的最短距离或最短时间的权的上界，也被称为临时性标号或者是试探性标号，并把某一点的T标号改为P标号，最多经过k-1步（k为图中的顶点数），可求解出从v_s到各点的最短路径或最短时间； A7、配送问题可以描述为，存在m个物流仓库，每个物流仓库存储有不同量的货物；存在n个客户点，每个客户点对货物的需求各部相同；每个客户点需求的货物来自m个物流仓库中的某个或者某几个；下面为物流配送模型数学表达式： x_ij≥0 它包含m×n个变量，(m+n)个约束方程。其中x_ij表示从第i个物流仓库运送货物到第j个客户点的运量。表示从第i个物流仓库到第j个客户点之间的费用，它是由物流仓库坐标x_q，y_q、客户点坐标x_p，y_p和富网络属性变量net共同决定的，其中net是A3步骤中数据对象模型中的Q^uv，包括长度、平均时速、行程时段。同时b_i为第j个客户点需要配送货物的箱数；a_i为第i个物流仓库库存配送货物的箱数；A8、表上作业法。表上作业法是单纯形法在求解运输问题时的一种简化方法，其 实质是单纯形法，但具体计算和术语不同，可归纳为： ①找出初始基可行解。即在(m×n)产销不平衡表上给出m+n-1个数字格； ②求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步； ③确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整； ④重复②，③直到得到最优解为止。