新冠疫情期間應急物資車輛路徑優化方法

張凱月, 溫海駿*, 陳躍鵬, 巨雨亭

(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)實驗驗證了該方法的可行性及有效性,能夠提高疫情期間應急物資配送過程信息交互功能及運輸效率。