基于數(shù)字孿生的物流配送調(diào)度優(yōu)化

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

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

在人工智能、物聯(lián)網(wǎng)等技術(shù)的推動下，產(chǎn)業(yè)轉(zhuǎn)型成為工業(yè)發(fā)展浪潮中生存的趨勢，物流行業(yè)也已從傳統(tǒng)物流發(fā)展為智能物流[1-2]。物流配送服務(wù)作為物流行業(yè)中的基本業(yè)務(wù)是物流企業(yè)面向客戶服務(wù)的最后一環(huán)，具有十分重要的地位[3]。而物流配送成本占據(jù)整個物流系統(tǒng)的很大比重，其中物流配送中車輛調(diào)度和路徑優(yōu)化將直接影響到物流配送成本的高低。

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

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

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

1 數(shù)字孿生驅(qū)動下的物流配送調(diào)度系統(tǒng)構(gòu)建

1.1 基于數(shù)字孿生的物流配送調(diào)度系統(tǒng)模型

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

圖1 物流配送DT五維模型

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

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

上述表達式解釋如下。

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

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

物流配送系統(tǒng)服務(wù)(system service, SS)本質(zhì)上是集成了追蹤、評估、優(yōu)化和控制等算法的數(shù)學(xué)模型，其根據(jù)車載終端提供的真實數(shù)據(jù)在虛擬空間中進行數(shù)據(jù)分析，構(gòu)建以配送總成本最低為優(yōu)化目標的數(shù)學(xué)模型，進而依靠數(shù)字孿生系統(tǒng)的算法內(nèi)核實現(xiàn)迭代優(yōu)化。

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

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

1.2 基于數(shù)字孿生的物流配送調(diào)度整體框架

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

圖2 物流配送調(diào)度系統(tǒng)數(shù)字孿生框架

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

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

(3)虛擬層。虛擬層是整個數(shù)字孿生驅(qū)動的物流配送調(diào)度系統(tǒng)框架中最為關(guān)鍵的一層，其是以底層物理層采集的實時數(shù)據(jù)為基礎(chǔ)依靠內(nèi)核算法進行實時動態(tài)調(diào)整迭代優(yōu)化，實現(xiàn)車輛的重調(diào)度和路徑的優(yōu)化，最后將最優(yōu)方案通過5G無線網(wǎng)絡(luò)輸出至車載終端，為實時調(diào)度提供決策支撐。

2 問題描述與數(shù)學(xué)建模

2.1 問題描述

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

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

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

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

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

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

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

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

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

2.2 數(shù)學(xué)模型

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

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

(1)

(2)車輛使用成本。

(2)

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

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

(3)

根據(jù)以上分析，建立數(shù)學(xué)模型為

minC=min(C1+C2+C3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

EETi≤Aik≤ELTi

(11)

(12)

(13)

(14)

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

2.3 算法內(nèi)核分析

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

圖3 遺傳算法主要流程

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

圖4 實數(shù)編碼

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

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

Fitness(i)=C

(15)

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

(16)

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

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

2 實驗與驗證

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

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

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

表3 物流配送模型相關(guān)參數(shù)設(shè)定

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

表4 維修站坐標

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

圖5 物流配送調(diào)度數(shù)字孿生體模型

基于數(shù)字孿生技術(shù)對配送過程進行模擬仿真，并得出滿足總成本約束的最優(yōu)物流配送路徑如圖6所示，優(yōu)化迭代過程如圖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輛車在服務(wù)完客戶15后出現(xiàn)故障，在維修站27進行維修后繼續(xù)完成配送任務(wù)，同樣第3輛車在完成客戶6的配送后出現(xiàn)工作，在維修站26進行維修，并在維修后完成配送任務(wù)，配送總成本為30 458元，迭代次數(shù)為319。

圖6 最優(yōu)配送路徑

圖7 優(yōu)化迭代圖

傳統(tǒng)物流配送優(yōu)化仿真方法下得到的滿足總成本約束的物流配送路徑與優(yōu)化迭代過程如圖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元，迭代次數(shù)為595。

圖8 傳統(tǒng)物流配送最優(yōu)路徑

圖9 傳統(tǒng)物流配送優(yōu)化迭代圖

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

4 結(jié)論

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

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

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

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

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