新冠疫情期间应急物资车辆路径优化方法

张凯月, 温海骏*, 陈跃鹏, 巨雨亭

(1.中北大学机械工程学院, 太原 030051; 2.先进制造技术山西省重点实验室, 太原 030051)

应急物流作为一类特殊的物流经营活动,通常具备突然性、弱经济性、不确定性和非常规化等特点[1]。新冠疫情的暴发,导致社会出现应急物流输运不畅、通道受阻等问题,使生活物资和必要医疗物资出现供需失衡[2]。疫情的特殊性使得生活医疗物资的品质和时间呈负相关性,且物资与隔离点间需实现精准配送。因此,在实现物资运输路况信息与隔离点需求信息透明化的基础上,实现物流配送路径动态改进,有利于提高疫情期间配送效率且实现应急物资精准配送。

目前中外学者可针对多种疫情背景下物资运输问题,提出路径规划方案。Mondal等[3]分析了疫情流行形势下混合不确定性多目标物流配送问题,并研究了应急物资开环及闭环供应链的可持续性意义;张春燕[4]和Jiang等[5]解决了大规模疫病背景下的生鲜农产品应急供应问题,并详细分析了物资需求程度不同对物流供应的影响。近年来大部分学者多采用改进算法及模型的方式来解决应急物资配送精度及效率问题。韩孟宜等[6]设计了混合遗传算法,寻求应急物资的配送路径更优解;康斌等[7]和白东[8]构建了多目标应急物资配送路径优化模型,提高了需求满足率。

当前中外研究从多种角度考虑了疫情背景下的应急物资配送路径规划方案,但研究方法一般未充分结合各类电子信息技术,同时对于解决物资运输过程信息透明化及动态信息作用下的路径规划问题的研究较少。由于疫情期间应急物流配送区域主要集中在市区,道路结构复杂,应急物资运输会受到多种动态不确定信息的干扰,因此,现借助智慧物流技术手段,解决物资储备充足的条件下由于交通延误无法实现物资及时送达的问题,建立智慧物流车辆运输系统架构使应急物流各环节作业有效配合,实现基于智慧物流系统的车辆调度方案动态调整。

1 疫情背景下的智慧物流架构体系

1.1 孪生数据驱动下的信息联动架构

目前智慧物流系统在对外国际贸易[9-10]、碳排放检测发展绿色城市[11-13]、农产品流通[14-15]等领域应用较多。疫情期间物流运输缺乏快速协同处理机制和方法,本文研究基于智慧物流系统,结合物联网、互联网等技术,实现物流各环节的数据集成,并对车辆路径优化方案进行动态干扰,通过智慧物流系统可视化保障疫情期间物流决策智能运行,如图1所示。

图1 信息联动模型Fig.1 Information linkage model

1.2 系统架构设计

疫情期间基于智慧物流系统的应急物资车辆运输系统架构主要分为数据获取层、数据传输层、模型处理层及可视化管理层4个层次,如图2所示。

图2 基于智慧物流系统的应急物资车辆运输系统架构Fig.2 Architecture of emergency material vehicle transportation system based on smart logistics system

(1)数据获取层主要为实现实时呈现物资需求信息、物流资源信息、通道及环境信息的功能。借助条形码、射频识别(radio frequency identification, RFID)等技术及时根据社会各项需求预测更新、完善所储备的应急物资;利用全球定位系统(global positioning system, GPS)、地理信息系统(geographic infor-mation system, GIS)技术及时获取物资流通过程的车辆实时定位信息;通过百度地图应用程序编程接口(application programming interface, API),获取实时交通路况拥堵情况,及实况路网数据。

(2)数据传输层主要利用5G网络的广域覆盖特性,实现同网络下的数据交互与传输,避免信息通讯的延迟,保证各项工作有序开展。

(3)模型处理层通过对应急物资车辆配送预测模型获取的数据,结合仿真模型的路径规划算法,对车辆调度方案进行实时动态调整和优化。

(4)可视化管理层通过前端应用设计交互界面,在平台内真实地反馈应急物资配送进度,整合不同条件下物流信息数据,保证应急物资配送每环节的信息透明化,实现智慧物流系统车路协同功能。

1.3 实时路况监测

将运输路径定义为有向图G=(V,A),其中V={0, 1,2,…,n,n+1}表示路网中的节点,0和n+1为应急物资配送中心,N=V(〗0,n+1}表示隔离点集合,A视为节点与节点之间的弧的集合。则疫情期间应急物资调配网络可视为一个依赖时间变化的动态网络。本文选取太原市交通路网,QGIS软件获取太原市路网矢量图如图3所示。通过百度地图获取太原市实时路况如图4所示。疫情突发使得运输路径受堵或应急物资车辆运输过程中须按规定进行车辆消毒而造成的运输时间增加,可模拟为网络中弧上的权值发生改变,路阻模型可用美国联邦公路局(Bureau of Public Road, BRP)路阻函数表示,如式(1)所示。

图3 太原市交通路网矢量图Fig.3 Taiyuan traffic road network vector diagram

图4 太原市实时路况Fig.4 Real-time road conditions in Taiyuan

(1)

式(1)中:tr为道路流量为r时的车辆通行时间;tf为车辆顺畅通行时间;c为道路通行最大可承载交通流量;α、β为路阻函数代标定参数,取值α=0.15,β=4。

车辆从k从隔离点i开始行驶到隔离点j的行驶距离和实际运行时间之间的关系如式(2)所示。计算流量系数<0.7时,说明当前路况相对畅通,计算当前通行时间可不考虑路况;当流量系数≥0.7时,说明当前道路进入交通拥堵状态,实际行车时间同时受路阻函数及实际行驶总车速的影响。

(2)

2 问题的描述

在疫情期间的应急物资运输过程中,路径上的运输距离、费用等参数都随着时间的变化而变化,若运载工具在行驶过程中由于区域性疫情集中暴发,病人或密接等集中转移隔离导致的交通暂时性拥堵,则该时刻路段权值发生动态变化。应急物资配送按照据点需求紧急情况设置时间窗,同时为了节约资源,可在隔离点同时回收部分已在智慧物流系统录入的过期或不具备使用条件的物资。因此,疫情期间应急物资配送问题可模拟为时间窗约束条件下的同时取送货动态网络问题,以此保证物资配送的及时性与连贯性。

针对所研究问题,做出以下假设:①配送中心和隔离点的坐标经纬度已知,各坐标点间实际距离已知;②隔离点必须全部被服务,并且每个隔离点只允许访问一次;③隔离点的回收量、需求量已上传至智慧物流系统,且于车辆从配送中心出发时间点开始不发生动态变化;④各隔离点过期物资回收量、需求量均不超过车辆的最大负载能力;⑤按照隔离点需求紧急程度,规定各隔离点时间窗要求;⑥车辆需在隔离点规定的时间窗内完成配送任务。

2.1 模型的建立

(1)目标函数成本包括车辆固定成本和时间惩罚成本;车辆固定成本又分为车辆使用成本和运输油耗成本。目标函数为

(3)

式(3)中:Z为总成本;F为应急物资配送车辆固定使用成本;k为所需车辆总数;C为运输油耗成本;时间惩罚成本中,e为早于隔离点规定最早时间到达惩罚系数;l为迟于隔离点规定最晚时间到达惩罚系数;ETj为隔离点j规定的左时间窗;LTj为隔离点j规定的右时间窗;Hj为物资配送车到达隔离点的实际时间。

(2)根据以上分析,建立约束条件为

(4)

(5)

(6)

(7)

(8)

ETj≤Hj≤LTj

(9)

q0k≤Q

(10)

(11)

(12)

(13)

(14)

(15)

式中:Q为车辆最大载重;M为一个足够大的正数。

式(4)表示应急物资配送车辆需从配送中心出发与结束;式(5)～式(6)表示配送车辆k在运输路径上的流量限制;式(7)表示配送车辆以速度v从隔离点i到隔离点j的路程消耗时间;式(8)表示配送车辆k行驶时间的连续性,其中w为开始服务时间点,s为服务时长;式(9)表示车辆到达隔离点的服务时间需在隔离点的左右时间窗之内;式(10)表示车辆k在配送中心所装载应急物资总量q0k应小于车辆最大载重;式(11)表示配送车辆k在对所在路线的任意隔离点服务结束后的车辆装载量qj不超过最大载量;式(12)表示车辆k在配送中心装载物资计算公式;式(13)表示车辆k在对所在路线第一个客户服务结束后的车辆装载计算公式,其中pj为隔离点j的回收量;式(14)表示车辆k在对所在路线任意一个顾客(不包括第一个顾客)服务结束后的车辆装载计算公式;式(15)表示二值变量。

2.2 头脑风暴算法内核分析

智慧物流系统下的应急物资车辆调度相当于在传统车辆调度系统的基础上增强了数据信息的透明化、精准化展示,使算法内核结合物流系统对各信息要素的收集、更新与反馈,对车辆配送方案进行实时动态调整,结合道路拥堵情况使整个物流配送过程的路线、配送时间及成本不断地迭代优化,并于智慧物流系统可视化管理层实现最优路径规划方案的实时调整与双向交互功能。本文将选用头脑风暴算法作为内核对疫情期间的应急物资车辆路径规划问题进行求解,主要流程如图5所示。

图5 头脑风暴算法协调逻辑Fig.5 Brainstorming algorithm coordination logic

3 实验验证

假设以山西省人民医院为中心,有应急物资配送车辆10辆,针对太原市迎泽区15个隔离点建立基于智慧物流系统的应急物资车辆配送方案。基于百度地图API选取15个隔离点如表1所示,覆盖包括居民住宅小区、写字楼及学校,并获取其地理坐标经纬度、各点需求量、回收量、时间窗及各点服务时间如表2所示。各隔离点间相对距离均取百度地图导航实际最短路径如表3所示。

初始种群数为50,聚类数目为5,运用MATLAB结合头脑风暴算法内核,得出未考虑路况信息的应急物资车辆配送方案如图6所示,最优配送方案选用4辆车,最佳路径为,路线1:0-13-2-1-0;路线2:0-10-15-11-12-0;路线3:0-7-6-4-3-0;路线4:0-5-8-9-14-0。

根据疫情期间道路通行情况的突发性变化,动态调整6条路径6-4、10-3、11-5、13-1、15-10、15-11之间的道路拥堵情况,经过150次迭代后,得出基于智慧物流系统的应急物资配送车辆路径优化方案如图7所示,其最佳路径为,路线1:0-10-15-0;路线2:0-14-6-4-3-1-0;路线3:0-5-7-8-9-0;路线4:0-2-13-11-12-0。

表2 隔离点坐标经纬度、需求量、回收量、时间窗及服务时间Table 2 Coordinates of isolation point latitude and longitude, demand, recovery, time window and service time

疫情期间应急物资车辆路径规划主要集中在道路交通网复杂多变的市区,智慧物流系统结合各类电子信息技术,使物流配送过程信息透明化,能够更加准确且直观地显示物资配送实际路线的动态变化,基于百度地图显示应急物资车辆在太原市内1个配送中心,15个隔离点的配送路径如图8所示,其百度地图实际导航全局配送路线如图9所示,以路线3为例展示详细配送路线如图10所示。

图6 最优配送路径Fig.6 Optimal distribution path

图7 基于智慧物流系统的最优配送路径Fig.7 Optimal distribution path based on smart logistics system

表3 配送中心及隔离点间百度地图最短相对距离

经分析,传统应急物资车辆配送方案的行驶距离为19 730 m, 基于智慧物流系统的应急物资车辆配送方案行驶总距离为19 820 m,经结合实际路况对其路径进行优化后,行驶距离差距不大,仅相差90 m,但其配送时间却获得4.8%的缩减,较为符合在新冠肺炎疫情背景下对应急物资配送及时性的需求。

4 结论

提出了一种基于智慧物流系统的应急物资车辆路径优化方法。

图9 百度地图全局配送路线Fig.9 Baidu map global distribution route

图10 路线3配送路径展示Fig.10 Route 3 delivery path display

(1)在传统物流的基础上结合智慧物流系统框架,使疫情当下的应急物资配送实现信息透明化。

(2)基于百度地图API获取隔离点实际地理坐标信息进行实验验证,并将头脑风暴算法作为内核建立数学模型。

(3)以路况变化为主要考虑因素,实现了基于智慧物流系统的车辆调度方案动态调整。

(4)实验验证了该方法的可行性及有效性,能够提高疫情期间应急物资配送过程信息交互功能及运输效率。