基于數字孿生的物流配送調度優化

曾艾婧，劉永姜，陳躍鵬，孟小玲，溫海駿

(中北大學機械工程學院，太原 030051)

在人工智能、物聯網等技術的推動下，產業轉型成為工業發展浪潮中生存的趨勢，物流行業也已從傳統物流發展為智能物流[1-2]。物流配送服務作為物流行業中的基本業務是物流企業面向客戶服務的最后一環，具有十分重要的地位[3]。而物流配送成本占據整個物流系統的很大比重，其中物流配送中車輛調度和路徑優化將直接影響到物流配送成本的高低。

針對車輛配送調度問題，大多學者主要是對算法的優化進行研究，孫秀巧等[4]探討了有限巡邏車資源路徑、調度優化建模問題，并在改進遺傳退火算法的基礎上加入動態規劃算法對巡邏車進行分配；王澤等[5]考慮電量消耗的車輛調度模型，并將遺傳算法與枚舉法相結合計算出配送車輛懲罰成本最小時的最優發車時刻。近年來，為了更高效地解決該問題，部分學者將先進信息技術與調度系統融合以得到更加智能有效的解決方案，張雨[6]將多Agent系統與分布式蟻群算法相結合，研究了基于分布式多Agent下的港口作業調度優化方法；周克良等[7]闡述了在信息物理系統(cyber physical systems，CPS)架構下構建一個垃圾轉運系統，并將遺傳算法作為系統內的算法內核，通過實例分析證明CPS系統架構下的垃圾預轉系統的有效性；朱濤等[8]基于大數據驅動提出了智能化公交實時調度和管理技術。

配送過程中各種不確定因素，導致其復雜化不斷增加，以至于產生額外的配送成本，為此來越多的學者開始關心如何實現配送過程透明化，相繼提出了基于物聯網、產業互聯等技術的智能物流配送模式[9]，而數字孿生(digital twins，DT)[10]這一概念的提出為物流配送提供了一種全新的解決思路。近年來，數字孿生作為一種新興的智能技術在制造領域得到了廣泛的應用，中外學者分別提出了基于數字孿生的數控機床虛擬交互系統[11]、面向工廠規劃的數字孿生技術[12]、基于數字孿生的產品生命周期預測方法[13]、總裝配生產線數字孿生技術[14]、數字孿生建筑信息模型[15]、基于數字孿生的航班保障預警系統[16]等，實現了網絡物理的融合。

基于此，現引入數字孿生技術來對配送過程進行高效管理，將配送過程由“黑箱”模式轉換為配送過程中配送車輛狀態、人員狀態、道路狀態等的實時狀態透明化，以實現物資的精準配送。

1 數字孿生驅動下的物流配送調度系統構建

1.1 基于數字孿生的物流配送調度系統模型

為使數字孿生進一步在具體物流配送研究中得到應用，根據文獻[17]中的五維DT和建模方法，提出了一個結合具體物流配送過程的數字孿生應用模型，其主要包括物理配送作業面、虛擬配送作業面、物流配送系統服務、物流配送孿生數據和系統連接，如圖1所示。

圖1 物流配送DT五維模型

同時，物流配送的DT模型可以表示為

DT=(PE、VE、SS、TD、SC)

上述表達式解釋如下。

物理配送作業面(physical entity, PE)是在實際物流配送過程中，物流配送中心根據客戶需求，在給定的約束條件下，通過對車輛進行合理調配完成指定的配送任務。

虛擬配送作業面(virtual entity, VE)是物理配送作業面在虛擬空間的數字化“鏡像”，利用智能軟件對真實的物流配送工程進行仿真。

物流配送系統服務(system service, SS)本質上是集成了追蹤、評估、優化和控制等算法的數學模型，其根據車載終端提供的真實數據在虛擬空間中進行數據分析，構建以配送總成本最低為優化目標的數學模型，進而依靠數字孿生系統的算法內核實現迭代優化。

物流配送孿生數據(twin data, TD)是將配送過程的真實數據、虛擬配送的模擬數據和服務數據進行融合，并隨著實時配送狀態的變化而不斷更新與優化。在物流配送過程中，TD的一個作用是為VE提供采集到的實時追蹤數據，使VE可以精確地對真實物流配送進行仿真模擬；其次是為PE反饋虛擬配送預測數據，從而可以對實際中的物流配送調度進行動態調整。

系統連接(system connection, SC)的作用是將以上4個部分連接成一個整體，使得物流配送數字孿生系統能夠進行實時而且有效的數據傳遞，從而達到真實配送過程與虛擬仿真的交互與協同。

1.2 基于數字孿生的物流配送調度整體框架

數字孿生旨在將物理實體及過程進行數字化表現，通過孿生數據驅動顯示物理信息的融合，借助仿真軟件模擬物理實體在現實情況下的運作流程，因此提出了物流配送調度系統數字孿生框架，其主要包括物理層、服務層、虛擬層三部分，如圖2所示。

圖2 物流配送調度系統數字孿生框架

(1)物理層。物理層需要物理實體即配送車輛具備決策和通信能力，并可以采集物流配送設備的位置信息、車輛狀況、駕駛行為以及路況等部分的實時信息數據。具體主要是利用GPS系統實時采集車輛位置信息與運輸軌跡、利用貨運車輛基于SAEJ1939/CAN總線協議的OBDII接口對車輛運行狀態進行數據采集，以實現對故障車輛的及時維修，并通過5G技術將配送過程實時相關數據上傳至服務層。

(2)服務層。服務層的主要任務是為基于數字孿生的物流配送調度系統提供數據支撐服務，基于對物理層提供的實時參數信息數據與孿生層輸出的決策數據的融合和分析，實現物理層與孿生層的交互反饋，從而為整個系統提供智能執行、精確控制和可靠運維等服務。

(3)虛擬層。虛擬層是整個數字孿生驅動的物流配送調度系統框架中最為關鍵的一層，其是以底層物理層采集的實時數據為基礎依靠內核算法進行實時動態調整迭代優化，實現車輛的重調度和路徑的優化，最后將最優方案通過5G無線網絡輸出至車載終端，為實時調度提供決策支撐。

2 問題描述與數學建模

2.1 問題描述

所研究的物流配送調度問題是建立在已知客戶點的空間位置和需求量，配送中心的位置以及車輛最大載重量條件下，單個配送中心的基礎上，通過采集m輛車對一定區域內的n個客戶配送同質貨物的實時配送數據，以數字孿生技術為依托模擬配送過程，并將迭代優化得到的最優配送方案反饋至物理模型，以使綜合成本最低。另外，該數字孿生模型考慮了配送過程中故障車輛的維修處理問題。并在數學模型中引入了軟時間窗，對物資有可能會無法按時被送達的情況進行一定的懲罰。

針對所研究的問題，做出以下假設：

(1)每輛車僅配送于一條路徑，且都從配送中心出發，最后返回配送中心。

(2)每個客戶都必須被服務并有且只被訪問一次。

(3)每輛車所配送的客戶需求總量不能超過車輛的載重量。

(4)每輛車服務其路徑上的每個客戶時，應在客戶規定的時間窗內到達配送地點，或早或晚都將面臨懲罰。

(5)配送中心貨源充足，配送貨物為單一品種。

(6)車輛在行駛途中保持勻速行駛，且不考慮道路交通擁擠等狀況。

(7)客戶的開始服務時間即為車輛到達的時間，且每個客戶的服務時間相同。

2.2 數學模型

綜合考慮運輸成本、車輛使用成本和懲罰成本，具體說明如下。

(1)運輸費用。運輸成本是指貨物運輸過程中消耗的燃料消耗成本，運輸成本與運輸距離成正比，即

(1)

(2)車輛使用成本。

(2)

式(2)中：C2為總車輛使用成本；fk為第k輛車的固定成本。

(3)懲罰成本。將添加一個軟時間窗口，這意味著要求車輛盡可能在指定的時間窗口內到達，或早或晚到達都會產生懲罰成本，即

(3)

根據以上分析，建立數學模型為

minC=min(C1+C2+C3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

EETi≤Aik≤ELTi

(11)

(12)

(13)

(14)

式中：Q為配送車輛的最大載重。式(5)表示車輛從配送中心出發進行配送，完成后將返回配送中心；式(6)～式(8)表示每個客戶有且只能被一輛車服務一次；式(9)表示每輛車所承載的貨物總量不應超過車輛的載重量Q；式(10)表示車輛到達配送點的時間與客戶的開始接受服務時間相同；式(11)表示車輛的到達時間必須在客戶i規定的服務時間窗內；式(12)是二值變量，值取1時表示車輛k由客戶i行駛到客戶j；式(13)是二值變量，值取1時表示車輛k對客戶i服務；式(14)是二值變量，取值1時表示車輛k完成了客戶i的服務。

2.3 算法內核分析

數字孿生驅動下的物流配送調度系統等同于在原有的物流配送調度系統基礎上添加了一個虛擬層面的物流配送調度系統，算法內核在物理和虛擬空間之間根據實時反饋的物理信息以及孿生數據對車輛配送安排進行實時動態調整，從而使整個物流配送過程不斷地迭代優化。將遺傳算法作為內核對物流配送調度問題進行求解，算法的主要流程如圖3所示。

圖3 遺傳算法主要流程

(1)編碼。采用實數編碼的方式，該方法比較簡單，易于表示單配送中心問題的解利用自然數對客戶進行編碼，將客戶點作為基因，編碼如圖4所示，其中0表示物流配送中心。

圖4 實數編碼

(2)解碼。對上述實數編碼進行解碼，即表示配送中心安排一輛車先滿足客戶4的物資需求，再服務客戶9，當車輛達到最大載重量時，配送中心將安排別的車輛，對未配送客戶進行服務，以此類推，直到滿足每個客戶的需求。

(3)適應度函數。針對物流配送調度問題，將綜合配送成本作為染色體的適應度值，其函數為

Fitness(i)=C

(15)

(4)個體選擇。將精英保留策略與輪盤賭法結合對個體進行選擇，先利用輪盤賭法，即根據染色體的適應度值進行選擇，每個個體被選擇的概率為

(16)

(5)交叉。采用部分映射法進行交叉，即先對父代進行常規的兩點交叉,再根據交叉區域內各基因值之間的映射關系來修改交叉區域之外的各個基因組的基因值[18]。

(6)變異。根據編碼特點，選用兩點互換的方式產生變異算子，并在互換后，通過重新判斷該個體是否滿足約束條件確定互換后的個體是否可行。

2 實驗與驗證

以某配送中心為例，通過實地調研和數據咨詢，收集整理相關信息數據，將該配送中心配送區域內的25個客戶作為研究對象，建立基于數字孿生的物流配送調度系統。表1列出了部分配送中心和客戶之間的相對距離，配送中心及部分客戶坐標點、部分配送點的需求量、早晚時間窗等信息(表2)以及物流配送模型相關參數設定(表3)。

表1 配送中心及客戶之間相對距離

表2 客戶坐標點、需求量、時間窗和服務時間

表3 物流配送模型相關參數設定

基于數字孿生技術的優化仿真方法為保證更加精準模擬實際配送過程，在傳統的物流配送調度模型中加入兩個車輛維修站，用以解決運輸途中車輛故障等問題，維修站的位置坐標如表4所示。

表4 維修站坐標

根據以上案例，并結合采集的實時相關數據，運用Plant Simulation仿真軟件建立的物流配送調度數字孿生體模型如圖5所示。遺傳算法參數設置如下：染色體長度即客戶數目：25，種群中的群體規模：40，最大迭代次數：1 500，交叉率：0.99，變異率：0.1，精英保留策略概率：0.1。

圖5 物流配送調度數字孿生體模型

基于數字孿生技術對配送過程進行模擬仿真，并得出滿足總成本約束的最優物流配送路徑如圖6所示，優化迭代過程如圖7所示，其配送方案如下：動用4輛車進行配送，最佳運輸路徑為第1輛車：0-18-8-7-19-11-10-22-0；第2輛車：0-21-2-15-27-23-4-25-24-0；第3輛車：0-6-26-17-16-14-13-0；第4輛車：0-5-12-3-9-20-0，其中第2輛車在服務完客戶15后出現故障，在維修站27進行維修后繼續完成配送任務，同樣第3輛車在完成客戶6的配送后出現工作，在維修站26進行維修，并在維修后完成配送任務，配送總成本為30 458元，迭代次數為319。

圖6 最優配送路徑

圖7 優化迭代圖

傳統物流配送優化仿真方法下得到的滿足總成本約束的物流配送路徑與優化迭代過程如圖8、圖9所示，其物流配送方案如下：動用4輛車進行配送，最佳運輸路徑為第1輛車：0-12-24-3-9-20-10-1-0；第2輛車：0-13-14-16-17-8-6-0；第3輛車：0-2-15-23-25-4-21-5-0；第4輛車：0-22-11-19-7-18-0，配送中成本為33 480元，迭代次數為595。

圖8 傳統物流配送最優路徑

圖9 傳統物流配送優化迭代圖

從實驗結果可以看出，針對客戶規模為25的配送問題，基于數字孿生優化仿真方法得到的物流配送總成本比在傳統優化仿真方法下的物流配送總成本降低了9.92%。將基于數字孿生技術優化方法模擬得到的最優配送方案通過5G無線技術傳輸至物理層，司機通過車載系統接收到實時反饋信息就可以對配送路線與方案進行合理的調整，實現配送過程的透明化。

4 結論

物流配送調度過程的復雜性一直是研究的難點，其主要原因是客戶需求的多樣化和配送過程的不確定因素，嚴重降低了物流配送的效率，制約了智能物流的發展，數字孿生技術的發展應用為解決物流配送調度問題提供了契機，主要結論如下。

(1)在深入研究數字孿生理論的基礎上，提出了物流配送調度DT五維模型及其整體架構，其中結合了車載診斷系統和GPS衛星定位系統對車輛運輸信息進行實時采集，并通過5G無線通信技術進行傳輸。

(2)將遺傳算法作為物流配送系統內核，充分考慮配送過程中遇到的實際問題，建立帶有軟時間窗以總成本最小為目標的物料配送數學模型。

(3)在前面研究的基礎上，結合某配送中心實例，采用仿真軟件Plant Simulation模擬3D物流配送真實場景來保證仿真模型和實際配送之間的一致性，并以配送過程中車況的不確定性為例，利用數字孿生技術實現對車況發生變化后的路徑再優化。

(4)通過算法內核對配送過程進行模擬仿真，得到物流配送路徑及配送總成本，將其與通過傳統物流配送優化方法仿真得到的配送路徑與總成本進行對比，驗證了基于數字孿生技術的物流配送優化仿真方法可以根據路況或車況出現的擾動對配送路徑與方案進行即時的調整。