动态物流路径优化方案研究

动态物流路径优化方案研究动态物流路径优化方案的研究，是建立在对给定区域优先保证特殊供货点， A,B,C后进行区域划分基础上，(x，y)确定合适的车辆数、行车路径，实时记录车辆当前位置坐标的一种动态管理过程。1模型假设(1)假设各处路况都是相同的，物流运输车行驶不受天气、堵车等因素影响，物流运输车在道路上均能按平均车速行驶。(2)假设物流运输车在供货过程中除了运输时间，不做其他任何停留和休息，人员换班时间不计。(3)假设所有物流运输车24小时供货，连续正常工作，没有发生机械故障等问题，不考虑其他与路径优化求解无关的问题情况。2动态物流路径优化的模型设计与实现2.1确定动态物流运输中车辆数确定动态物流运输中车辆数一般利用 Floyd算法，Floyd是求任意两点间最短距离一种方法，在交通分配中应用较为广泛。用 Floyd算法求出所有节点间的最短距离矩阵 D并将区域平面内的道路交叉口节点分别标号为 1,2……k,求最短距离矩阵的Floyd算法步骤如下：先根据题目数据给初始矩阵 D赋值，其中没连通的节点的赋值为R,以便于更新。进行迭代计算，对任意两点 (i,j)，若存在，使D(i,k)D(k,j)：：：D(i,j)，则更新D(i,j)=D(i,k)D(k,j)。

（3）直到所有点的距离不再更新停止计算。则得到最短路距离矩阵D(i,j=1,2,3..…D(i,j=1,2,3..…k)定义1设P（Vi,Vj）是赋权图G从Vi到Vj的路径，则称Pe（Vi,Vj）为路径P（Vi,Vj）的权。定义2在赋权图G中，从顶点Vi到Vj的具有最小权的路径p*（V,Vj）称为Vi到Vj的最短路。最短路径问题通常将它们抽象为图论意义下的网络问题 [1]，问题的核心就变成了求网络图中任意两供货节点之间的最短路。供货点间距离用矩阵 D来表示。点间距离用矩阵D来表示。式中：p（Vi,Vj）——两供货点之间的路径；G――赋权图；Vi――区域中第个需要供货的点；Pe（Vi,Vj） 每条路径的权重；p*（y,Vj）――两供货点之间的最短路径；D——最短距离矩阵。根据供货区平面图，用阶数为kk的0-1矩阵d用来表示各供货点之间连通与否， 假设0节点i到j之间可连通d・.=丿ij1节点i到j之间可连通其中：i,j=1,2……k且dij为了使物流运输车在一次遍历中以最少的重复路径进行供货，减少互不连通回路个数，引入额外变量*=（1,2……）k，并加入一个充分约束条件Ui-Ujndj-n-1,1：：i=j虫k,n=k若i与j可构成回路，则有

dj=iUi—Uj兰-1uj_Uj启-1得，0_2不等式成立，节点i与j可构成回路。若与不构成回路，则有4=o』dji=0Ui 一Uj 王k一1uj一Uj 王k一1得，0丄2(k-1)，等式矛盾，节点i与j不可构成回路。综上所述，可得到供货区平面内任意两个连通节点之间的最短路径模型如下:nminz八dijDiji,j吕严n为dij—1j—1, >ki=1¥n为dj i二1，……,kj二st.jUi一Uj+ndjj兰n-1, 1vi式j兰n,n=kdj=0或1i,j=1,……,kUi为整数，i=1,……,kH为整数，j=1,……,k式中：U式中：Ui为减少互不连通回路个数而设置的额外变量;n――表示整个供货区域中的所有道路交叉节点数;Dij――供货点与点之间的最短连通距离。2.3各物流运输车动态坐标位置数据求解2.3.1行车方式(1)辐射形行车路线：指运输车行使时从起点到终点后任按照原路线返回。 (2)环形行车路线：指运输车从起点出发单向行驶， 绕行一周，经过子区域内各个交叉点，不走重复路线，回到出发点。(3)混合形行车路线：即是包含辐射形和环形两种结构形式的行车路线。根据各个子区域内行车效果评价指标的要求， 辐射形结构形式的行车路线显然是不优化的， 因而选用环形或混合形行车路线。2.3.2运输车坐标位置求解(1)物流运输车正常运输时， 每秒钟步长为y/36O0(m)(为了保证位置精确，步长设定按秒计算的方式；还有就是为了减小迭代过程中未走完路径不能被最小步长整除， 而进入下一路径循环计算所引起的误差)。(2)根据道路的起始节点和下一节点的横纵坐标，来确定该条道路与水平正方向的夹角B。 (3)第j次迭代计算时，物流运输车的横坐标位置为该条道路初始节点横坐标值加上 p<v/3600(m)xco曲(j=1,2,3「)，纵坐标为该条道路初始节点纵坐标值加上。(4)判断物流运输车位置，若未走完该条道路则返回步骤 (3),若走完该条道路以下一节点继续步骤(2),直至把运输路线走完为止。3实例应用的分析现有某地商品销售连锁店的分布节点区域图，如图 1所示。图1中以“X”表示道路交叉口节点，A,B,C分别表示三个优先供货部位，图中的圆区域表示优先供货车辆能覆盖的供货范围(圆以A,B,C为圆心，以2km为半径的圆，半径大小确定，后面会有具体计算说图1整个区域道路交叉口节点表示图3.1确定动态物流运输中车辆数由交叉口坐标，每条道路起始、终止交叉口编号，计算出每条道路的道路长度， 所求出的每条道路长度如下表1所示。表1每条道路长度单位：m序号起始交叉口编号终止交叉口编号道路长度1122754.221351033.73252034.14221850.8536720.2该区域内共有 458条道路，根据表1利用Floyd可求解出所有道路长度和为 551760m，这样可以得出需求车辆上限值nn551760nI'v（辆）,vi是根据该物流部门统计的一组车辆行驶速度数据，为了保证其它i4意外情况发生依然能保证正常供货， 可以适当放宽车辆需求额度；也可以应用概率方法以供货时间和供货满意度为指标，得到满足该条件下车辆需求置信区间。式中：w――第辆运输车行驶速度。所求出的最短距离矩阵D如表2所示。表2任意两点最短距离矩阵 单位：m02754.26300.55256.34788.37020.797047668.7?2754.203546.32502.12034.14266.56949.84914.5?6300.53546.301044.21512.2720.23403.51368.2?5256.32502.11044.204681764.44447.72412.4?4788.32034.11512.246802232.44915.72880.4?7020.74266.5720.21764.42232.402683.3648?97046949.83403.54447.74915.72683.302035.3?7668.74914.51368.22412.42880.46482035.30?????????0考虑到重点部位的优先供货需求， 以A,B,C点为圆心，半径为Vi（2/60）=y/30（km）画圆（图1设定v=60km），找到a，b，C所构成的三角形的外接圆的圆心 （图中星号表示V- _该点），画半径Vi（2/60）Lkm圆，从而求得保证在随机缺货时间 t内到达优先供货部30位的最小圆区域。在该圆区域内专门配备一辆供货车， 可使优先部位的供货时间和供货满意度的显著性要求得到更好满足，并明显优于按照指定路线供货的情形。 模型还要对整个供货销售点的随机缺货时间进行统计，统计各供应点的缺货时间 t报表，当然也可以应用概率方法估算t为上述最小圆确定提供实际理论根据。然后剔除已经被最小圆覆盖的节点，得出该区域内还有 402条道路，根据剔除后的节点再次求解，可求解出所有道路长度和为493621m，这样可以得出需求车辆上限值n493621n/vVi（辆），考虑优先供货情况及正常供货情况，得出一共需求车辆数目。iT3.2最短路径模型区域划分原则，考查实际的城市物流运输分区情况，在模型中分区原则规定如下：(1)结合人口密集区、道路网密集程度，越密集，分区应越多。 (2)各个子区域内的节点数相当。(3)各个子区域的面积相近。将商品销售连锁店的区域应用上述区域划分原则进行划分， 在模型计算过程中通过Lingo动态规划法求解，现以划分后区域 7内12个供货节点为例，计算其最佳行车路线方案，得到如图2所示行车路线(其他区域通过区域划分后，计算方法一样) 。计算得到物流运输车行驶路程 16899.40km，其中：x(1,3)=1x(2,1)=1x(3,6)=1x(4,8)=1x(5,2)=1x(6,11)=1x(7,4)=1x(8,9)=1x(9,5)=1x(10,7)=1x(11,12)=1x(12,10)=1, 表示12个节点供货路径先后顺序(x(i,j)=1表示i—j，然后找下一节点 x(j,k)=1，得到i—j，这样依次，转换成图1，转换成图1中对应的供货节点:D193~D255~D275~D297T298~D291~D276~D260~D287~D289~D270~D211D193在聚类过程中，下一供货点是否聚类到当前路径， 既考虑到当前车辆可容纳的负荷， 又充分利用了已知的需求信息， 综合考虑了下一供货点的需求情况。 这样就能得出任意时刻， 下一供货点归属那个供货路径， 是否聚类到当前所在区域车辆供货路径中， 给出优劣判断的依据，还可以为上述的联动操作提供方案， 这样使得实际供货更具备柔性过程特征， 减小供货时间提高供货满意度。3.3各物流运输车正常运行坐标位置数据求解通过上述计算得到在一个供货周期内，物流运输车在划分后区域内正常行使距离与路径，结合最短距离矩阵及通过“先聚类后排序”确定每辆车对应的供货节点，利用 lingo动态规划法得出其最佳供货行车路线，借助智能交通系统 ITS中的路径诱导系统RGS，充分利用交通信息资源给与有效的路径诱导， 为当前时刻运输车提供所在位置的最优行车路线， 相互之间对突发事件进行联动操作， 这样可以实现动态管理物流路径， 克服传统意义上的确定路径非实时监控缺点。通过Matlab程序计算：设定供货车辆平均行驶速度时，得到 7供货区域内供货车辆正常行使位置坐标如下表 3所示。表3任意一时刻运输车坐标单位：m\时|'间\位置\123456789101112131415626261616060592958585757565656x516172738394940y3029292929282828282827272727260281593715947250290785644220984动态物流运输中车辆数合理性检验根据参考文献［2］，圆在近似正方形区域内的覆盖效率大约 80%〜85%，当供货节点缺货后，可以提高车辆的平均行驶速度，假设变为 w/l(km/h)，则在供货规定时间内覆盖圆的22圆形面积为：二Wti/(I60)km。整个区域的面积估算为xy(km)2(x,y表示供货区域对应的x,y坐标(单位：km))则覆盖该区域所需圆的个数为Xxy/SxMxtj/(I汉60)丫9.,(［］表示取整)，则在该区域内需要y/伉x(y0/(I江60应丿辆车运输车则可实现80%以上的供货覆盖率。这与通过Floyd算法得出总运输路径需车辆数相吻合，从而验证了模型求解的正确性。模型计算建立过程中对上下货时间没考虑等， 可以把将这些作为一个随机数进行分析， 可用均匀分布或泊松分布来描述该因素的影响， 把这些元素加入到供货周期中，假设