利用改进的Floyd算法进行最短路径计算时,因不计算插入不影响最短路径值的中间节点后的路长,所以减少了计算量.在迭代计算最短路径时,在插入一个新的中间节点后,先比较路长,若d^(k-1)_it≥d^(k-1)_ij或d^(k-1)_tj≥d^(k-1)_ij, 说明在插入新节点v_t后,路长比未插入时长,则插入新节点后d^(k)_ij=d^(k-1)_ij, 不影响现有最短路径值^[9].此时,不需计算最短路径,而是直接进入下一节点的插入检验,因此提高了计算效率.改进的Floyd算法适于计算复杂城市路网中任意两点之间的最优路径.

步骤1:由有向网络图构建的初始距离矩阵(k=0)为

D⁽⁰⁾=(d⁽⁰⁾_ij)_n×n,

i=1, 2, …, n, j=1, 2, …, n(2)

在式(2)中,若i=j, 则d⁽⁰⁾_ij=0; 若i≠j且有v_i到v_j相连的边,则d⁽⁰⁾_ij为边的权值; 若i≠j且不存在v_i到v_j直接相连的边,则d⁽⁰⁾_ij=∞.

步骤2:在 D^(k-1)中, k≥1, 若i=j, 有d^(k)_ij=0; 若i≠j, 对于插入中间节点v_t, 若使d^(k-1)_it=∞或d^(k-1)_tj=∞(t=1,2,…,n; t≠i, j), 且d^(k-1)_ij≠∞, 则有d^(k)_ij=d^(k-1)_ij; 若i≠j, 对插入中间节点v_t, 若使d^(k-1)_it≥d^(k-1)_ij或d^(k-1)_tj≥d^(k-1)_ij(t=1, 2, …, n; t≠i, j), 则有d^(k)_ij=d^(k-1)_ij. 若以上情况都不符合,则分析:若i<j, 则有① t<j, d^(k)_ij=min{d^(k-1)_ij, d^(k)_it+d^(k)_tj}; ② i<t<j, d^(k)_ij=min{d^(k-1)_ij, d^(k)_it+d^(k-1)_tj}; ③ t>j, d^(k)_ij=min{d^(k-1)_ij, d^(k-1)_it+d^(k-1)_tj}. 这表明, 在i<j的情形下,对比d^(k-1)_ij与d^(k)_ij, 更新后的路长值为较小的值.若 i>j, 则有 ① t<j, d^(k)_ij=min{d^(k-1)_ij, d^(k)_it+d^(k)_tj}; ② j<t<i, d^(k)_ij=min{d^(k-1)_ij, d^(k-1)_it+d^(k)_tj}; ③ t>i, d^(k)_ij=min{d^(k-1)_ij, d^(k-1)_it+d^(k-1)_tj}. 这表明,在i>j的情形下,对比d^(k-1)_ij与d^(k)_ij, 更新后的路长值应为其中的最小值.

步骤3:比较 D^(k-1)与基于 D^(k-1)插入后的最短路径长,若 D^(k)= D^(k-1), 则输出为最短路径值; 否则,令k加1,并跳转到步骤2继续迭代^[10].

改进的Floyd算法是在t=i和t=j不参与计算的情况下,比较原路径和插入中间节点v_t后新形成的路径长度,若d^(k-1)_it≥d^(k-1)_ij或d^(k-1)_tj≥d^(k-1)_ij, 表示路径其中一段不小于原有路长,则不参与计算,而是继续与下一中间节点插入后的路径进行对比,如此经过多次迭代后,直至得到v_i到v_j的最短路径.改进的Floyd算法较未改进前剔除了对不影响最短路径值的中间节点插入后路长的计算,只计算距离起讫点之间直线的相近节点插入后的新路径,再与未插入前的距离d^(k-1)_ij对比,得到最短距离d^(k)_ij, 输出最短路径值矩阵 D^(k), 得到任意起讫点间的最短路径, 降低了计算复杂度, 提高了计算速度.

对于车辆行驶寻找最优路径问题,需要算出任意两节点之间的最短距离.改进的Floyd算法计算复杂度降低,计算效率高,且容易理解,代码编写也更简单.将改进Floyd算法应用于小区开放后车辆行驶路径优化模型的流程图如图1.

图1 路径优化模型的算法流程图
Fig.1 Algorithm flow chart of path optimization model

青西新区CBD范围内大部分属封闭小区,区域内道路资源紧张,带来了较为严重的交通问题.一方面,城市路网稀疏,干道承担了主要交通量,缺少下一层次的路网,令干道交通负荷过大,特别是区域内的路网交叉口供给能力不足而路段供给能力过剩,干道交通在很多交叉口发生拥堵,但在路段上却常处于不饱和状态,有违干道设计速度的要求,令微循环系统不畅.另一方面,城市交通因封闭小区切割带来的被迫绕行,降低了路网结构效率,同时交通线路与站点等覆盖率较低.调查范围内开放小区道路资源前后的基本路网如图2.

图2 小区开放前后基本路网
Fig.2 (Color online)The basic road network before and after the opening of the community

以青西新区CBD的澳龙花园、绿岛印象和香江花园等小区作为终点,去掉分散的外卖点,仅保留外卖餐馆较密集的中心地带作为此地区的代表取餐点为起点.调查区域内外卖点聚集地分布情况请扫描论文末页右下角二维码查看图S2.

外卖送餐过程包括订单接收、餐品处理、递送取餐和终端送餐.送餐员接到订单信息后抵达外卖点取餐,从起点出发,并运送至小区终点为外卖送餐模式.图3为调查区域内OD的位置以及外卖送餐的现状路线.由图3可见,一方面,封闭小区会在周边形成较多丁字路和断头路,不利于城市密集路网的形成,造成周边交通堵塞.另一方面,封闭小区令街区被隔离,造成道路和土地等资源的浪费,也破坏了城市街区的社会性.送餐员从接到订单,到抵达外卖点,再到目的小区的过程中,途经很多封闭小区,而绕行会造成人力与时间的浪费.若全部小区都是开放的,开放街区令送餐车辆有更多可选路线.基于开放的密集新路网设计OD最优路径,则能让外卖工作人员更加节省路上时间,大幅提高工作效率.

图3 调查范围内OD及送餐现状路线
Fig.3 (Color online)The OD points and the current route of food delivery in the survey area

由图3可见,在调查区域内,已有部分已建成的封闭小区.绕行不仅增加了送餐时间,甚至常有送餐员因送餐时间的要求,为赶时间发生交通违法行为,产生极大的道路安全威胁隐患.目前,城市内电动车及摩托车行车速度一般为20～40 km/h,取最低速度,即设外卖送餐员驾车行驶所用速度为20 km/h,由此可计得在送餐现状路线条件下的外卖送餐所用时间如表1.其中,A～G为店铺外卖起点,1～20为小区.

按照国家政策,未来小区将逐步开放,使内部道路公共化.一旦小区道路公共化并与周边环境结合,就可形成有助于改善交通拥挤问题的城市布局.小区内部道路的公共化利用,可提高城市路网密度,增加道路面积,减小交叉口规模,提升道路通行能力、交通网络连通性和微循环系统性能,通过分担干道交通量,使道路交通流均衡分布^[11],缓解了交通压力,改善交通出行的环境,节省人们出行时间和各种社会资源.

本研究基于调查范围内封闭小区全部开放的假设,通过将最短路问题的理论运用到车辆行驶路线优化问题中.以外卖送餐为例,将外卖中的任意起点与小区终点相对应,利用改进Floyd算法计算出任意OD间优化后的最短路径长度,从而完成最优路径设计.

表1 现状路线外卖送餐所用时间
Table 1 The time used for the present route for takeout delivery min

判断外卖起点到小区终点是否有直接相连的路线,若有直接相连的路线,则值为该路线的值; 若不存在直接相连的边,则值为∞,由此来构建初始矩阵D⁽⁰⁾. 将同一小区内所有出行顶点的某一集中点作为小区重心,即终点,并基于 D⁽⁰⁾, 选择任意外卖点与小区重心之间的路线依次插入交叉口顶点作为节点,利用改进Floyd算法避免对不影响最短路径值的中间节点插入后路长的计算,得到距离外卖起点和小区终点之间直线的相近节点插入后的新路径,并与未插入之前的路径距离进行对比,得到最优路径长度,最终输出最优路径矩阵 D^(k). 在得到任意外卖点与小区之间的最短路径后,设外卖员行车速度为20 km/h,则他在路线优化后送餐所用的时间如表2.

表2 路线优化后外卖送餐所用时间
Table 2 The time used after route optimization for takeout delivery min

采用Visual C编译软件实现改进Floyd算法求最短路径,寻找任意OD间的最优路径,实现优化调查范围内小区开放后的外卖送餐路线网,结果如图4.

图4 小区开放后优化外卖送餐路网
Fig.4 (Color online)The optimized takeout delivery network after the opening of the community

在开放街区条件下,调查范围内的小区内部道路被公共化,与城市原有路网道路衔接,形成更高效的新城市路网.开放街区下的外卖员可自由通过小区内部道路,避免不必要绕行,道路可直达性大增,送餐行驶路线长度大减.与街区隔离时相比,经改进Floyd算法优化的路径,令送餐员在路上花费的时间平均减少了30.4%.可见,小区开放可以有效缓解周边道路的交通压力,提高城市道路利用率,避免社会资源的浪费,提高城市生活品质.

但是,该方案仅假设了在车辆行驶中无因意外造成的延误,忽略了高峰期造成的拥堵,以及因突发意外事故等因素造成的时间延误.