基于BDS/GIS协同的动态路由算法在物流配送系统中的应用

胡玉晶，黄 颖，2

（1.江苏科技大学张家港校区，江苏 张家港 215600；2.江苏科技大学中船工业现代物流研究中心，江苏 张家港 215600）

1 引言

物流配送环节是物流企业一个至关重要的环节，同时也是电子商务发展的“瓶颈”，其效率高低直接影响企业的周转效益，因此必须建立一个合理、高效、连续的物流配送体系，以达到降低物流配送服务的运营成本和物流损失、提高配送效率和利润的目的。

现代物流业的发展目标是以现代服务业和制造业为基础，以现代运输业为重点，利用现代通信技术和信息技术实现物流配送服务的信息化、标准化和智能化，其中智能化是现代物流发展的核心[1]。

目前物流配送网点多采用分布式下沉模式，保证能配送到全国的各个地方。通常物流中心收到订单并出库后，会采取分区配送，由各个区的货车司机进行站点与站点之间的配送。传统物流满载配送为了在最短的时间内、以最短的配送路线将所有货物送到对应的消费者手中，会采用蚁群算法、A*算法、Dijkstra 算法等进行路径优化[2]。但随着终端客户和配送车辆规模越大，各站点可配送性发生变化的可能性越大（例如今年疫情期间，几个站点由于处于重度疫区，取消配送），这种算法的计算时间成指数上升趋势，而且很难得到全局最优解或满意解。

因此本文基于以上分析提出一种新型的物流配送算法，即基于BDS/GIS协同的动态路由算法。BDS具有精确授时功能，在平面精度和高程精度方面与GPS略有不同，且高程精度高于GPS。BDS系统能够提供物流所在位置的经纬度，具备车辆定位与车辆跟踪功能；GIS 系统能够对物流配送进行实时监控，实现交通路线、车辆运行路线等信息的可视化。BDS与GIS系统不断地交换数据，就能建立时间、坐标、寻址功能一体化的车/货/人实时定位体系，进而实现物流配送的定位、导航、调试、追踪等。因此该算法在BDS/GIS技术协同下，能够满足实时更新状态下物流配送路径最短、用时最少的要求。

2 动态路由思想在物流配送系统中的理论研究

2.1 动态路由原理

路由是使用存储转发原则来执行的[3]，在TCP/IP协议的因特网环境下，将报文打包分组，报文到达一个路由器便查找路由表，找到一条到达目标网络的最佳路径信息后，存储转发最终到达目的地。在查找过程中，路由器通过动态路由算法找到到达目的地的最佳路由，其中涉及到节点的跳跃、延时以及分组数据包传输通信耗时，并且每个路由表都会实时更新。

动态路由的原理流程如图1所示。

2.2 动态路由思想在物流配送系统中的应用

计算机网络通过路由表实现信息传送路径选择。对于特定需求（低时延、高带宽）场景，可以通过进一步优化网络带宽分配来实现。

动态路由思想在物流中同样适用。中转场、分拣点等物流节点承担了快件转发任务，目前主要通过五级地址库与静态路由表实现路径的选择。但对于节点故障情况下，为实现物流服务的连续性，需要通过动态路由手段规避服务中断风险。例如由于疫情导致某中转节点出现故障，则需要重新规划路由表，动态地为终端客户提供服务。

图1 动态路由的原理图

将动态路由的思想应用到物流配送系统中，物品配送中转站相当于路由器；配送的商品相当于数据报文；完成配送线路最短、时间最少的物流就相当于查找到最佳路由线路；BDS/GIS提供的实时更新的交通路况相当于实时更新的路由表。从这种思想出发，基于BDS/GIS的动态路由算法能满足实时更新的物流配送系统耗时最少、效率最高的要求。

3 基于BDS/GIS协同的配送车辆调度系统结构

配送车辆调度系统依赖于多种技术支持，如BDS、GIS、通信技术以及互联网技术等。配送车辆调度系统可分为三大应用模块，即：车辆实时监控模块、车辆实时调度模块与路径规划模块。

3.1 BDS定位原理

北斗卫星导航系统BDS（BeiDou Navigation Satellite System）是一款我国自主研发的战略性卫星导航系统，可以为用户连续提供动态目标的三维位置、三维速度和时间信息，具有定位精度高、能够实时定位等特点，目前应用在车辆导航、监控等方面。但由于存在卫星导轨、钟差、大气延迟、多路径效应等误差，因此可配以地图匹配技术来减弱车辆导航的定位误差[4]。

利用BDS 系统在地球上任何地点、任意时刻都可以观测到4颗卫星，从而保障全天候绝对定位的可能性。BDS单点定位原理如下：

某观测站i的精确坐标已知，为（Xi,Yi,Zi）。由BDS收到的数据可计算出BDS 卫星的瞬间坐标（Xj,Yj,Zj），则BDS卫星j到地面观测站i的瞬间真实距离为：

而观测站BDS 接收机测得相应的伪距为，由此可得伪距改正数：

车载终端BDS 接收机接收到卫星时即可按定位的相关算法求得车载终端BDS 天线中心的坐标，进而实现车辆的实时定位监控。

3.2 基于BDS/GIS协同的配送车辆调度系统结构

GIS（Geographic Information System）以地理空间数据为基础，对实时数据进行采集、管理、操作、分析、模拟和显示[6]。我国百度地图、高德地图目前已是两个成熟的GIS系统，在配送车辆调度系统中最基本的应用是实时在电子地图上显示配送车辆运行及回访轨迹，通过地址编码及路网设计分析完成路径规划。

基于BDS/GIS 协同的配送车辆调度方法如下：

（1）车载终端BDS接收机接收BDS卫星信号，求解得到车载终端BDS天线中心的坐标并传送到车载中央处理器[7]；

（2）车载中央处理器将车辆经纬度、行驶速度和方向等信息重新打包，经过无线通信网络发往车辆监控中心；

（3）车辆监控中心结合来自物流服务中心的客户需求信息，利用大数据和云计算等相关技术，对实时数据信息进行综合分析和挖掘处理；

（4）在GIS支持下在电子地图上显示出车辆运行路线，为了提高服务效率和降低成本，对可调用车辆进行实时配送路径的优化更新，及时发送新的调度指令[8]；

（5）基于BDS/GIS 协同技术，将新的调度结果推送到系统终端，从而方便管理者、司机和客户查询配送车辆运行路径，掌握准确的配送服务到达时间。

基于BDS/GIS 协同的配送车辆调度系统结构如图2所示。

图2 基于BDS/GIS协同的配送车辆调度系统

4 基于BDS/GIS协同的配送车辆路径规划

利用现代通信技术和因特网技术，可以实时准确的获得客户需求、配送节点、配送车辆运行动态和实际交通路况等信息[9]。基于BDS/GIS协同的配送车辆调度系统，并运用蚁群算法，可以实现动态车辆路径规划，达到物流配送路径最短、耗时最少的目的。

4.1 蚁群算法基本原理

自然界中的蚂蚁总是能发现从巢穴到食物的最短路径。经研究发现，蚂蚁之间通过信息素来相互通信并互相影响。首先蚂蚁从巢穴出发，边走边按一定的时间比例释放信息素，找到食物后原路返回。路径越短，信息素越浓厚，后续蚂蚁选择这条路的概率越大，由此形成一种正反馈，并逐步逼近最优解。蚁群算法具有全局优化能力，主要由四个部分组成：状态转移策略、信息素局部更新、信息素全局更新和局部搜索算法[10]。

设g 为蚂蚁总数量，i、j（i,j=1,2,…,n）表示经过的路径节点；Tij(n)表示迭代n 次时，在节点i 和j 路径间的信息素浓度。初始迭代时，各条路径上信息素浓度相同，Tij(0)=h（h 为常数）。蚂蚁k（k=1,2,…,g）在运动过程中，根据各条路径上的信息素浓度决定转移方向；表示第n 次迭代蚂蚁k 从节点i 转移到节点j的概率。

式中：afterk={1,2,…,n}为蚂蚁k 下一步可以选择的节点,并且afterk随着蚂蚁不断选择下一个节点进行动态调整。ηij(n)表示第n 次迭代中蚂蚁运动轨迹（i,j）的可见度，一般取ηij(n)=1/dij(n)，dij(n)表示从节点i运动到节点j的距离。用参数p表示蚂蚁信息素的持久度，1-p 表示信息素的挥发程度，α 表示轨迹的相对重要性，β表示轨迹可见度的相对重要性。迭代次数n 每增加一次，各条路径上的信息素就要挥发一次，当所有蚂蚁完成一次迭代循环，各路径上信息素的浓度根据式（2）和式（3）做调整。

式（2）中Tijk(n)为第k只蚂蚁在第n次迭代循环中留在节点i与j之间路径上的信息素浓度;ΔTij(n)为第n次循环中g只蚂蚁在路径上释放的信息素浓度之和。

式（3）中的三种模型，第一个为acs 模型，Q 是常数，表示信息素的浓度；Lk表示第k 只蚂蚁在本次迭代中走过所有路径长度，该模型利用整体信息，蚂蚁一次循环后更新所有路径上的信息素。第二、三种模型，利用局部信息，即蚂蚁在完成每一步（从一个节点到达另一个节点）后更新所有路径上的信息素。对于模型二：蚂蚁经过（i,j）时，浓度为Q/dij的信息素被释放在这条边上；对于模型三：蚂蚁经过（i,j）时，浓度为Q的信息素被释放在这条边上。显然，利用整体信息求解较为合适，所以我们采用式（3）中的模型一。α、β、Q、p根据求解规模确定其取值。当迭代数固定住且求解值不变或者变化不明显时，算法停止。

4.2 蚁群算法函数模型的建立

在配送车辆调度系统中，将某一时间段内一定数量的商品送到所有消费者手中，付出的代价主要为完成所有配送任务造成的路径和时间上的代价。

调度环境主要由配送点、配送车辆、客户需求和实时路况组成。规划模型需要满足以下相关约束条件：

（1）对每个配送点客户只服务一次，即一个地区的客户只能被分配在一条路径上；

（2）配送车辆均从配送中心出发，在完成配送任务后均返回配送中心；

（3）每辆车配送任务均不超过其最大载重量；

（4）配送的货物质量相同，在数量相同的情况下满足客户需求的程度是相同的。

将调度问题凝练为一个目标规划问题，根据上述约束条件的描述，目标函数综合考虑时间代价和路径代价，此处我们增加协统度指标，作为BDS/GIS技术支持下实时路况更新的多个配送车辆协同作业的协调性[11]。目标函数如下：

式中：T—完成所有配送任务造成的时间浪费指标；

C—完成总配送任务造成的路径浪费指标；

U—多个配送车辆协同度指标；

a—时间浪费指标T的权重；

b—路径浪费指标C的权重；

c—多个配送车辆协同度指标U的权重。

4.3 目标函数求解及基于BDS/GIS 协同的路径规划流程

根据式（4），T 为总时间的估计值，即配送车辆完成所有配送节点任务所花费的总时间代价的估计值，取配送车辆总路径代价的最大值来表示；C为总路径代价的估计值，即所有配送车辆完成所有任务花费的路径代价估计值的总和；U为协同度，取配送车辆路径代价估计值的方差，反映其离散程度。函数表达式分别为:

蚁群算法运算时，在模型中更新记录各迭代中目标函数值所对应的路径方案，当迭代数固定住且求解值不变或者变化不明显时，算法停止。这便是目标函数的最优解。

综上所述，基于BDS/GIS协同的配送车辆路径规划如图3所示。

5 基于动态路由算法的物流配送实例分析

5.1 物流配送实例设计

根据车载终端BDS，发送数据信息到交通监控中心，通过大数据和云计算对各个配送车辆进行任务分配，利用蚁群算法计算出各个物流中转站之间的成本代价权值，各个站点根据BDS/GIS支持下实时更新的成本代价权值更新路由表，物流配送车辆根据最新路由信息，实时更新最佳配送路径，最终将所有商品送到各个配送站点[12]。

图3 基于BDS/GIS协同的配送车辆路径规划

假设某物流企业有一批客户货物需要配送。某一配送车辆根据DC 下达任务需要配送五个站点的货物。车辆出发时的路由表权值见表1。

表1 初始时刻各个站点间的权值表

5.2 实例分析与结果

根据表1 画出A、B、C、D、E 站点网络图，如图4所示。

图4 站点网络图

得知A 到E 有A-B-E，A-B-C-E，A-B-D-E，AC-E，A-C-D-E五条路径，分别计算出各路径的成本代价权值之和为55，82，50，53，57，因此A到E的最短路径为A-B-D-E，按照此种方法计算出所有节点之间的成本代价权值，最终得出所有站点的路由表，以A站点和B站点为例，见表2、表3。

表2 A站点的路由表

表3 B站点的路由表

根据路由表计算得出完成所有站点配送任务所花费的最少成本代价权值为68，最短配送路径为AB-D-E-C,可保证配送效率最高。

基于以上分析，假设配送车辆在初始站点A 时查找路由表，选择去B，到达B处后去往D处，此时基于BDS/GIS获取的外部交通路况发生变化，使得实时更新的各站点成本代价权值发生变化，见表4。

表4 BDS/GIS实时信息更新后的各个站点权值表

根据表4 画出更新后的站点网络图，如图5 所示。

图5 更新后的站点网络图

由于此时A、B、D 三个站点均已配送完毕，所以此时需要关注D-C-E 路由表和D-E-C 路由表累计成本代价权值，见表5。

表5 D站点的路由表

在D 点处根据更新后的路由表，完成剩下两个配送站点的配送任务所需花费的最少成本代价权值为14，最短配送路径为D-C-E，此时总配送路径为A-B-D-C-E，可保证配送效率最高。

6 总结与展望

6.1 总结

本文通过对动态路由原理以及对动态路由思想在物流配送系统中应用的分析，建立了基于BDS/GIS协同的配送车辆调度系统模型，并结合交通情况对调度过程中的行车路线进行了基于BDS/GIS 协同的具体路径规划，实现了物流配送过程中满足客户需求耗时最短、配送路径最少、配送效率最快的结果。

本文建立基于BDS/GIS 协同的配送车辆调度系统模型，研究了BDS/GIS 原理，BDS 系统能够提供物流所在位置的经纬度，具备车辆定位与车辆跟踪功能；GIS 系统能够对配送物流进行实时监控，实现交通路线、车辆运行路线等信息的可视化。BDS与GIS系统不断地交换数据，就能建立时间、坐标、寻址功能一体化的车/货/人实时定位体系，进而实现配送物流的定位、导航、调试、追踪等应用。基于BDS/GIS协同技术，将实时车辆配送的调度结果推送到系统终端，可以方便管理者、司机和客户查询配送车辆运行路径，掌握准确的配送服务到达时间。

本文采用蚁群算法对车辆配送过程中的路径进行规划，可以得出每两个配送站点之间的成本代价权值，基于BDS/GIS协同技术可以结合外部交通路况实时更新各个站点的路由表，物流配送车辆根据最新路由信息，实时更新最佳配送路径，最终将所有商品送到各个配送站点。因此基于BDS/GIS 协同的动态路由算法在物流配送体系中能够确保在最短的时间满足客户需求，节约时间和资源，确保物流配送系统的高效运行。

6.2 展望

本文建立了基于BDS/GIS 协同的配送车辆调度系统模型，并采用蚁群算法对配送过程中的路径进行优化，保障物流配送系统的高效运行。但本文仍存在一些待解决的问题：

（1）对于一些已知平面内整体布局的路径规划，蚁群算法可以快速地规划出最优路径。但如果区域边界模糊、内部节点模糊，则需要从更高维度空间来布局平面内路径规划。

（2）本文主要针对物流中心配送到客户节点，未考虑到运输往返过程中装载资源平衡性问题，返回时有时为了平衡运输资源，并不采用点与点对流，而是经过多节点运输后返回配送中心。因此往返过程中配送货物与退货等资源运输的平衡性便是下一步研究的主要内容。

（3）针对蚁群算法，是否可以与其他算法混合，提高其寻优质量和寻优速度，也是后续值得继续探讨的方向。