基于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）針對蟻群算法，是否可以與其他算法混合，提高其尋優質量和尋優速度，也是后續值得繼續探討的方向。