基于开放街区的车辆行驶最优路径设计

潘福全，邢 英，魏金丽，杨金顺，张丽霞，刘尊民

青岛理工大学机械与汽车工程学院，山东青岛266520

近年来，住宅从传统邻里开发(traditional neighborhood development, TND)模式和以公共交通为导向的开发(transit-oriented development, TOD)模式等新城市主义到中高密度住区，都提倡了开放性、混合性、多样性和可持续性发展．如美国纽约巴特利公园城街道采取方格形网状的形式，将地块划分成小面积街区，使公共空间更加方便[1]；日本的新城建设模式采用了“沿道中庭型住栋”形式，在空间规划方面体现了开放型的空间结构街区和公共空间整体设计，如幕张滨城住宅区；新加坡2l世纪住宅的开放网络结构，以Punggol新镇为典型模式代表，采用了棋盘式的住宅模式，区块作为基本单元，注重公共交通与空间的整合[2]．随着居民日益多样化的居住生活追求，当前中国也出现了很多新类型、新模式的住区建设．北京建外SOHO是一个开放式混合型街区，通过多种功能的混合和空间层次上的设计，将道路与城市路网衔接，并设置中央公园，形成开放的空间结构，极大地改善了交通环境．上海创智坊以围合式的住宅街区作为基本单元，在空间形态上形成私密的庭院空间和开放的公共空间，采用较小的街区和较密的住宅区路网，形成舒适便捷的城市交通环境[3]．

关于小区开放对交通影响方向也有相关研究．LIN等[4]研究了在居住社区开放后对周边道路交通的影响；QIU等[5]基于小区开放的条件下对周边交通进行了研究；肖旭[6]在社区开放的条件下，分析了周边路网的通行能力；李良[7]通过研究小区开放对周边道路通行能力的影响，证明了开放街区可以有效缓解周边道路交通压力．2016年，《中共中央国务院关于进一步加强城市规划建设管理工作的若干意见》提出“新建住宅要推广街区制，原则上不再建设封闭住宅小区”的政策原则，旨在实现住宅小区内部道路的公共化利用和解决交通路网布局产生的问题，促进人们节约利用紧张的城市用地，树立“窄马路、密路网”的城市道路布局理念，打造方便快捷生活圈．

因此，通过改进Floyd算法，提高算法的求解速度，并应用到基于开放街区条件下的车辆行驶路线时间最优路径的计算，对实现道路资源的共享，缓解交通压力，具有重要意义．

1 最优路径方法分析

目前比较常用的最短路径算法包括Dijkstra、Bellman-Ford和Floyd算法，它们各有不同的适用范围，需根据所规划的路径特点选择适合的最短路算法．Floyd算法是一种动态路径规划算法，其主要的适用范围是：① 所有结点对的最短路径问题(all-pairs shortest paths, APSP)；② 在起讫点(origin-destination, OD)和线路密集的图上显示效果最好；③ 网络图上各线路的边权可正可负．所以，Floyd算法是针对在多源点之间寻找最优路径的外卖送餐类实际生活问题的较佳方法．

(1)

Floyd算法计算任意两点之间的最短路径长度是将初始矩阵D(0)依次插入多个中间节点数次迭代后计算得到的．将第k-1个距离矩阵D(k-1)的最短路径长度与基于D(k-1)插入新节点后得到的最短路径长度进行比较，最小值为D(k)的最短路径长度．多次迭代至无新数据[8]，即从所有可通过路径的长度中选出最小值作为两点之间的最短路径值．

1.1 改进的 Floyd算法

传统的Floyd算法在节点较多时，迭代次数会很多，增大了算法复杂度．本研究针对多顶点的最短路径问题，采用改进的Floyd算法降低计算量，通过计算不含负回路的路网中任意起讫点之间的最短路径，找到各顶点之间的最优路径．

1.1.1 算法思想

1.1.2 算法步骤

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

i=1, 2, …,n，j=1, 2, …,n

(2)

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

1.1.3 算法分析

1.2 应用分析

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

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

2 青西新区CBD外卖送餐路径调查及优化

本研究调查的中国青岛市西海岸新区(青西新区)中央商务区(central business district, CBD)，包括黄岛区全部行政区域的青岛西海岸新区的中央商务区(北至嘉陵江路，南至滨海大道，西至太行山路，东至衡山路)，详图请扫描论文末页右下角二维码见图S1．该范围内现存在小区封闭和街区隔离的现象，因城市公共道路与住宅小区内部的道路没有打通，导致区域交通拥堵严重，同时公交线路与站点覆盖不全，城市道路交通效率低下．为响应国家政策，解决城市交通公共道路网络覆盖率不高的问题，青西新区CBD也将逐步建设开放小区，并开放已建封闭住宅．在基于开放街区下，以青西新区CBD范围内的外卖送餐车辆行驶为例来设计最优路径．

2.1 青西新区CBD现状调查

2.1.1 路网现状调查

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

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

2.1.2 外卖送餐的起讫点及路线分布现状调查

以青西新区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

2.2 青西新区CBD外卖送餐路径优化

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

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

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

表1 现状路线外卖送餐所用时间

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

表2 路线优化后外卖送餐所用时间

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

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

2.3 方案评价

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

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

3 结 论

基于小区开放的国家政策导向，将改进Floyd算法应用到车辆行驶路线的最优设计中，并以青岛西海岸新区CBD内外卖送餐为例，分析算法对驾驶人选择车辆行驶路线参考价值，得到以下结论：

1)在开放街区的条件下，基于改进的Floyd算法求解的最优路径可避免绕路，减少了行驶路线长度，节省了行驶时间，避免了交通拥堵的同时，降低了行车途中的交通安全隐患．

2)小区开放令道路资源得以共享，提升了周边道路通行能力，提高了直达性，促进城市土地的高效利用．