一种基于车辆自组网的城市快递配送方法

一种基于车辆自组网的城市快递配送方法
【技术领域】
[0001] 本发明属于信息技术、城市交通、快递配送领域，特别是涉及一种基于车辆自组网 的城市快递配送方法。
【背景技术】
[0002] 随着经济的发展以及人们网上购物习惯的形成，快递行业得到了迅猛的发展，快 递企业越来越多，产生的快件量也逐年增加。一方面，快件量的增加导致快递企业的配送成 本逐步增高，另一方面，随着各个快递企业的物流配送车辆的增多，极大地增加城市交通的 负担。因此，对传统快递配送模式的改进和创新，减少快递企业物流成本、缓解城市交通拥 挤有着非常重要的作用。
[0003] 快递配送模式是物流企业的核心，相关研宄人员对快递配送过程中的网点选址、 运输班次规划、交通工具选取都做了深入的研宄，一些企业还各自进行了配送模式的探索 尝试，包括京东的自建仓储模式以及阿里巴巴菜鸟网络的"中国智能骨干网"项目等。快递 配送中的网点选址、运输班次规划等研宄主要侧重于企业在建立配送网络之前的理论设计 与规划，而企业的配送模式尝试更是进一步对这种理论设计的实践，他们都是利用企业自 身的资源来实现快递的配送。当然也有一些快递企业之间存在互相合作关系，比如两家快 递企业共用仓储或者借用对方物流车队等，但这还是局限于利用现有的物流资源，并没有 很好的解决由于快递量增长导致快递爆仓、快递配送成本高升以及越来越严重的城市交通 拥堵问题。
[0004] 伴随着"互联网+"概念的提出，以及近年来打车拼车软件（嘀嘀、Uber)、私家车 租赁（PP租车）等模式的迅速普及，在快递配送过程引入第三方车辆（出租车、公交车、私 家车）的条件已经越来越成熟。因此，本发明提出了利用第三方车辆参与快递运输的快递 配送方法。
[0005] 到目前为止，尚未见到有关本发明涉及的基于车辆自组网的快递配送方法的报 道。

【发明内容】

[0006] 本发明的目的是克服现有技术的不足，提供一种基于车辆自组网（车载网）的城 市快递配送方法。
[0007] 本发明的目的是通过以下技术方案来实现的：一种基于车辆自组网的城市快递配 送方法，该方法包括如下步骤：
[0008] (1)利用城市道路及交通数据将配送区域聚类成k个区块，具体包括以下子步骤：
[0009] (I. 1)基于城市道路信息以及交通数据，利用k-means聚类算法将城市的所有街 区聚类成k个区块；k-means聚类算法在计算距离时采用的是两个街区间的车辆行驶距离， 该距离可以从在线地图服务（百度地图、谷歌地图）或者历史交通数据获得；
[0010] (1.2)在聚类得到的每个区块的热点区域设置快递存放点以及通信模块（RSU)， 作为该区块的中心；所述热点区域为公交车站、购物中心、机场或中央商务区等车流量较大 的区域；
[0011] (2)利用车辆历史轨迹计算步骤1中区块间的链路信息，所述链路信息包括车辆 运行时间和车辆到达间隔，其中车辆运行时间用于描述链路的时延，车辆到达间隔用于描 述链路的容量；这里主要考虑两类城市公共车辆，即公交车和出租车。不同的公共交通工具 有着不同的运行模式，公交车的运行模式相对固定，其车辆运行时间、车辆到达间隔可通过 车辆历史轨迹直接计算得到；出租车的运行模式相对随机，它受乘客的需求、司机的驾驶习 惯以及实时交通状况影响，通过分析车辆历史轨迹发现，区块间出租车的运行时间在每天 相同的时间段内基本相同，该运行时间可由车辆历史轨迹计算得到，车辆到达间隔服从指 数分布X~e(X)，指数分布参数X可根据车辆历史轨迹拟合得到；
[0012] (3)根据步骤1和2获得的区块以及链路信息，进行拓扑建模，构建加权有向图 g，具体为：根据区块及链路构成加权有向图g=(V，e，W)来建模快递配送网络，其中V， e，W分别为节点集、边集以及边的权重集合；节点ieV为步骤1聚类得到的区块，边<i， j>Ge为区块之间的链路，它表示快件可以通过交通工具从节点i运送到节点j;边的权 重《GW为快件在链路上运输的花费，取决于快件配送的服务标准；
[0013] (4)从步骤3构建的加权有向图g中搜索得到快件起点到终点的子图sub_g，具体 为：根据快件的起点和终点，利用深度优先搜索算法从加权有向图g中搜索得到所有从起 点到终点的路径构成的子图sub_g;
[0014] (5)对步骤4中得到的子图sub_g，利用Dijkstra最短路径算法求取权重最小的 快递配送路径P，即费用最小的最优配送路径；
[0015] (6)将快件按照步骤5得到的路径p进行配送，具体包括以下子步骤：
[0016] (6. 1)快件首先放入起点区块的快递存放点，并向起点区块的RSU录入快件信息， 所述快件信息包括快件的单号、起点区块ID、终点区块ID、放入起点区块时间、快件大小、 快件重量；
[0017] (6.2)起点区块RSU将该快件的起点与终点区块信息上传服务器，服务器按照步 骤1-5计算得到最优的快递配送路径p，并将该快件单号与最优的配送路径p的信息发送给 路径P经过的所有区块的RSU;
[0018] (6.3)当车辆进入快件当前所在区块时，车辆通过车载通信模块向区块RSU发送 注册信息，报告车辆当前位置、目的地；
[0019] (6. 4)基于车辆注册信息，区块RSU根据车辆选取原则选择与快件下一跳路线重 合的车辆并向其发送广播信息通知其前来取件，所述车辆选取原则为：由于相同链路上出 租车的运行时间一般要小于公交车的运行时间，并且出租车的到达间隔服从指数分布，所 以当出租车的到达间隔小于公交车与出租车在链路上运行时间之差时，则选择出租车，否 贝IJ选择最先到达的交通工具；所述广播信息包括区块中心位置、快件的下一跳区块、快件大 小、快件重量；
[0020] (6. 5)车辆接受取件请求后，到达区块中心的快递存放点将快件取走并开往快件 的下一跳区块；
[0021] (6. 6)车辆进入下一区块后，车辆向区块RSU发送注册信息，报告车辆的位置、目 的地以及携带的快件信息；区块RSU通知当前车辆附近的其它车辆来负责快件的下一跳运 输，如果没有符合要求的车辆，当前车辆将快件暂时存放在区块的快递存放点以等待开往 下一跳的车辆到达；
[0022] (6. 7)重复步骤（6. 3) (6. 4) (6. 5) (6. 6)直到快件到达终点区块的快递存放点；
[0023] (6. 8)终点区块RSU通知收件人前来取件，完成快递配送过程。
[0024] 本发明的有益效果是：根据该配送模式能极大地降低快递配送成本，利用城市车 辆替代快件运输车辆，改善城市交通拥堵状况。
【附图说明】
[0025] 图1是以上海市为例，区块17到区块2的链路以及区块24到区块17的链路上出 租车到达间隔分布示意图；
[0026] 图2是以上海市为例，快件从虹桥机场运送到浦东机场，利用DFS深度优先搜索算 法得到的子图；
[0027] 图3是根据图2中的子图利用Dijkstra最短路径算法得到快递配送路径。
【具体实施方式】
[0028] 下面结合附图详细描述本发明，本发明的目的和效果将变得更加明显。
[0029] 本发明一种基于车辆自组网的城市快递配送方法，包括如下步骤：
[0030] (1)利用城市道路及交通数据将配送区域聚类成k个区块，具体包括以下子步骤：
[0031] (I. 1)基于城市道路信息以及交通数据，利用k-means聚类算法将城市的所有街 区聚类成k个区块；k-means聚类算法在计算距离时采用的是两个街区间的车辆行驶距离， 该距离可以从在线地图服务（百度地图、谷歌地图）或者历史交通数据获得。以上海市为 例，通过k-means聚类算法可以将上海市区聚成40个区块，比如区块18代表虹桥机场，而 区块37代表浦东机场。
[0032](1.2)在聚类得到的每个区块的热点区域设置快递存放点以及通信模块（RSU)， 作为该区块的中心；所述热点区域为公交车站、购物中心、机场或中央商务区等车流量较大 的区域。
[0033] (2)利用车辆历史轨迹计算步骤1中区块间的链路信息，所述链路信息包括车辆 运行时间和车辆到达间隔，其中车辆运行时间用于描述链路的时延，车辆到达间隔用于描 述链路的容量；这里主要考虑两类城市公共车辆，即公交车和出租车。不同的公共交通工具 有着不同的运行模式，公交车的运行模式相对固定，其车辆运行时间、车辆到达间隔可通过 车辆历史轨迹直接计算得到；出租车的运行模式相对随机，它受乘客的需求、司机的驾驶习 惯以及实时交通状况影响，通过分析车辆历史轨迹发现，区块间出租车的运行时间在每天 相同的时间段内基本相同，该运行时间可由车辆历史轨迹计算得到，车辆到达间隔服从指 数分布X~e(X)，指数分布参数X可根据车辆历史轨迹拟合得到；图1是以上海市为例， 经过步骤1聚类得到的区块17到区块2的 链路以及区块24到区块17的链路上出租车到 达间隔分布示意图，可以看出到达间隔服从指数分布。
[0034] (3)根据步骤1和2获得的区块以及链路信息，进行拓扑建模，构建加权有向图 g，具体为：根据区块及链路构成加权有向图g = (V，e，W)来建模快递配送网络，其中V， e，W分别为节点集、边集以及边的权重集合；节点ieV为步骤1聚类得到的区块，边<i， j>ee为区块之间的链路，它表示快件可以通过交通工具（公交车或出租车）从节点i运 送到节点j;边的权重《ew为快件在链路上运输的花费，取决于快件配送的服务标准；例 如该快件对时间有较高要求，那权重可以为运送时延。
[0035] (4)从步骤3构建的加权有向图g中搜索得到快件起点到终点的子图v，e，w，具 体为：根据快件的起点和终点，利用深度优先搜索算法（DFS，D印th-First-Search)从加权 有向图g中搜索得到所有从起点到终点的路径构成的子图sub_g。图2是以上海市为例，快 件从虹桥机场运送到浦东机场，利用深度优先搜索算法得到的子图，其中节点18为虹桥机 场，节点37为浦东机场，边上的数值代表边的权重。
[0036] (5)对步骤4中得到的子图sub_g，利用Dijkstra最短路径算法求取权重最小的 快递配送路径P。图3是根据图2中的子图利用Dijkstra最短路径算法得到快递配送路径 P，即费用最小的最优配送路径。
[0037] (6)将快件按照步骤5得到的路径p进行配送，具体包括以下子步骤：
[0038] (6. 1)快件首先放入起点区块的快递存放点，并向起点区块的RSU录入快件信息， 所述快件信息包括快件的单号、起点区块ID、终点区块ID、放入起点区块时间、快件大小、 快件重量。
[0039] (6.2)起点区块RSU将该快件的起点与终点区块信息上传服务器，服务器按照步 骤1-5计算得到最优的快递配送路径p，并将该快件单号与最优的配送路径p的信息发送给 路径P经过的所有区块的RSU。
[0040] (6.3)当车辆进入快件当前所在区块时，车辆通过车载通信模块向区块RSU发送 注册信息，报告车辆当前位置、目的地。
[0041] (6. 4)基于车辆注册信息，区块RSU根据车辆选取原则选择与快件下一跳路线重 合的车辆并向其发送广播信息通知其前来取件，所述车辆选取原则为：由于相同链路上出 租车的运行时间一般要小于公交车的运行时间，并且出租车的到达间隔服从指数分布，所 以当出租车的到达间隔小于公交车与出租车在链路上运行时间之差时，则选择出租车，否 贝IJ选择最先到达的交通工具；所述广播信息包括区块中心位置、快件的下一跳区块、快件大 小、快件重量。
[0042] (6. 5)车辆接受取件请求后，到达区块中心的快递存放点将快件取走并开往快件 的下一跳区块。
[0043] (6. 6)车辆进入下一区块后，车辆向区块RSU发送注册信息，报告车辆的位置、目 的地以及携带的快件信息。区块RSU通知当前车辆附近的其它车辆来负责快件的下一跳运 输，如果没有符合要求的车辆，当前车辆将快件暂时存放在区块的快递存放点以等待开往 下一跳的车辆到达。
[0044] (6. 7)重复步骤（6. 3) (6. 4) (6. 5) (6. 6)直到快件到达终点区块的快递存放点。
[0045] (6. 8)终点区块RSU通知收件人前来取件，完成快递配送过程。
[0046] 本发明是一种基于车辆自组网的城市快递配送方法，该方法利用第三方车辆（出 租车、公交车等）来对快件进行多跳运输，通过城市道路信息以及车辆历史运行轨迹来规 划快件每一跳的运输方案。将配送区域划分为若干个区块，在每个区块设置一个快递存放 点，利用车辆历史数据规划出快件从起点到终点的路径所经过的区块。快递通过这种多跳 自组网的方式由第三方车辆从起点运到终点。该方法能极大地降低快递配送成本，改善城 市交通拥堵状况。
【主权项】
1. 一种基于车辆自组网的城市快递配送方法，其特征在于，包括如下步骤： (1) 利用城市道路及交通数据将配送区域聚类成k个区块，具体包括以下子步骤： (I. 1)基于城市道路信息以及交通数据，利用k-means聚类算法将城市的所有街区聚 类成k个区块；k-means聚类算法在计算距离时采用的是两个街区间的车辆行驶距离，该距 离可以从在线地图服务（百度地图、谷歌地图）或者历史交通数据获得； (1.2)在聚类得到的每个区块的热点区域设置快递存放点以及通信模块（RSU)，作为 该区块的中心；所述热点区域为公交车站、购物中心、机场或中央商务区等车流量较大的区 域； (2) 利用车辆历史轨迹计算步骤1中区块间的链路信息，所述链路信息包括车辆运行 时间和车辆到达间隔，其中车辆运行时间用于描述链路的时延，车辆到达间隔用于描述链 路的容量；这里主要考虑两类城市公共车辆，即公交车和出租车；不同的公共交通工具有 着不同的运行模式：公交车的运行模式相对固定，其车辆运行时间、车辆到达间隔可通过车 辆历史轨迹直接计算得到；出租车的运行模式相对随机，它受乘客的需求、司机的驾驶习惯 以及实时交通状况影响，通过分析车辆历史轨迹发现，区块间出租车的运行时间在每天相 同的时间段内基本相同，该运行时间可由车辆历史轨迹计算得到，车辆到达间隔服从指数 分布X~e ( λ )，指数分布参数λ可根据车辆历史轨迹拟合得到； (3) 根据步骤1和2获得的区块以及链路信息，进行拓扑建模，构建加权有向图P ，具体为：根据区块及链路构成加权有向图f =(兄来建模快递配送网络，其中 兄&你分别为节点集、边集以及边的权重集合；节点? e V为步骤1聚类得到的区块，边 < >e ￡为区块之间的链路，它表示快件可以通过交通工具从节点i运送到节点j;边 的权重ω e 为快件在链路上运输的花费，取决于快件配送的服务标准； ⑷从步骤3构建的加权有向图反中搜索得到快件起点到终点的子图sM』，具体为： 根据快件的起点和终点，利用深度优先搜索算法从加权有向图G中搜索得到所有从起点到 终点的路径构成的子图 (5) 对步骤4中得到的子图sub』，利用Dijkstra最短路径算法求取权重最小的快递 配送路径P，即费用最小的最优配送路径； (6) 将快件按照步骤5得到的路径p进行配送，具体包括以下子步骤： (6. 1)快件首先放入起点区块的快递存放点，并向起点区块的RSU录入快件信息，所述 快件信息包括快件的单号、起点区块ID、终点区块ID、放入起点区块时间、快件大小、快件 重量； (6. 2)起点区块RSU将该快件的起点与终点区块信息上传服务器，服务器按照步骤1-5 计算得到最优的快递配送路径P，并将该快件单号与最优的配送路径P的信息发送给路径P 经过的所有区块的RSU ; (6. 3)当车辆进入快件当前所在区块时，车辆通过车载通信模块向区块RSU发送注册 信息，报告车辆当前位置、目的地； (6. 4)基于车辆注册信息，区块RSU根据车辆选取原则选择与快件下一跳路线重合的 车辆并向其发送广播信息通知其前来取件，所述车辆选取原则为：由于相同链路上出租车 的运行时间一般要小于公交车的运行时间，并且出租车的到达间隔服从指数分布，所以当 出租车的到达间隔小于公交车与出租车在链路上运行时间之差时，则选择出租车，否则选 择最先到达的交通工具；所述广播信息包括区块中心位置、快件的下一跳区块、快件大小、 快件重量； (6. 5)车辆接受取件请求后，到达区块中心的快递存放点将快件取走并开往快件的下 一跳区块； (6. 6)车辆进入下一区块后，车辆向区块RSU发送注册信息，报告车辆的位置、目的地 以及携带的快件信息；区块RSU通知当前车辆附近的其它车辆来负责快件的下一跳运输， 如果没有符合要求的车辆，当前车辆将快件暂时存放在区块的快递存放点以等待开往下一 跳的车辆到达； (6. 7)重复步骤（6. 3)-(6. 6)直到快件到达终点区块的快递存放点； (6. 8)终点区块RSU通知收件人前来取件，完成快递配送过程。
【专利摘要】本发明公开了一种基于车辆自组网的城市快递配送方法，利用城市道路及交通数据将配送区域聚类成k个区块；利用车辆历史轨迹计算区块间的链路信息；根据区块以及链路信息进行拓扑建模，构建加权有向图来刻画城市车载网络；从加权有向图中搜索得到快件起点到终点的子图；利用Dijkstra最短路径算法求取子图中权重最小的快递配送路径p，即最优快递配送路径；最终将快件按路径p进行配送；根据该配送模式能极大地降低快递配送成本，利用城市公共车辆替代快件运输车辆，改善城市交通拥堵状况。
【IPC分类】G06Q50/28, G06K9/62, G06Q10/04
【公开号】CN104881710
【申请号】CN201510239145
【发明人】陈积明, 何建平, 谭旭, 程鹏
【申请人】浙江大学
【公开日】2015年9月2日
【申请日】2015年5月11日