人工智能背景下的配送網(wǎng)絡(luò)優(yōu)化方法研究*

葉春森，王雪軒， 時章漫， 黃成成

(1.安徽大學(xué) 商學(xué)院，合肥，230601； 2.安徽大學(xué) 物流與供應(yīng)鏈研究中心， 合肥 230601)

0 引 言

配送網(wǎng)絡(luò)優(yōu)化對提高配送效率、降低碳排放量、促進綠色配送發(fā)展具有重要意義。SBIHI A等[1]學(xué)者認為，為了有效降低碳排放量，有必要對傳統(tǒng)路線規(guī)劃問題的研究目標進行擴展，不僅考慮經(jīng)濟效益，還更應(yīng)該關(guān)注對社會和環(huán)境的影響。BAUER等[2]學(xué)者則建立了考慮碳排放的多式聯(lián)運模式下的決策優(yōu)化模型，并對東歐的鐵路運輸網(wǎng)絡(luò)進行了實證研究。CARLSSON J G和SONG S[3]提出基于卡車和無人駕駛飛機的聯(lián)合配送路線規(guī)劃問題。藩斌斌[4]綜述了國內(nèi)外不同背景下多目標路徑優(yōu)化算法的應(yīng)用及現(xiàn)有成果。蘇濤[5]構(gòu)建了基于再訂購點的電子商務(wù)低碳配送路徑優(yōu)化模型。李進等[6]研究了基于碳排放與速度優(yōu)化的帶時間窗車輛路徑問題。這些研究為建立人工智能與傳統(tǒng)配送融合的新模式奠定了基礎(chǔ)，但對其差異和優(yōu)勢分析的文獻還較少。本文在分析傳統(tǒng)卡車配送和無人機配送各自優(yōu)缺點的基礎(chǔ)上，提出卡車與無人機的聯(lián)合配送模式，分別以碳排放量與配送效率為目標，建立相關(guān)模型，提出相應(yīng)解法，以展示人工智能與傳統(tǒng)配送模式融合發(fā)展的重要意義。

1 單卡車和無人機聯(lián)合配送模式

1.1 傳統(tǒng)單卡車配送模式

在傳統(tǒng)配送路線選擇問題中，設(shè)集合U={p1，p2，…，pn}為某一區(qū)域的n個配送點集合，對任意的pi，pj∈U，令dij表示配送點pi與配送點pj之間的距離，xij=1表示配送點pi與配送點pj相連接，xij=0表示配送點pi與配送點pj不相連。特定的配送工具要走到上述的每一點，具體過程如圖1所示；其一次配送過程的最優(yōu)化問題則可建立如下數(shù)學(xué)模型：

(1)

(2)

其中目標函數(shù)式(1)表示為從任一配送點出發(fā)，途中經(jīng)過所有集合U={p1，p2，…，pn}中其他配送點節(jié)點后再回到出發(fā)點行駛距離最短。約束條件式(2)分別表示對于每個配送點有且僅有一條路徑出去；對于每個配送點有且僅有一條路徑進入。另外還有個約束條件為除了起點與終點外，各條路徑不構(gòu)成圈。

圖1 單獨卡車配送

1.2 卡車和無人機聯(lián)合配送模式

傳統(tǒng)單獨卡車配送相對于無人機配送具有規(guī)模經(jīng)濟性，但其單位配送成本高，而無人機單位配送成本低，并且可以在沒有人為干預(yù)的情況下運行，即不受道路交通影響的情況下高速行駛。但無人機載重量極低，行駛半徑小。針對單獨卡車與單獨無人機兩種配送模式的優(yōu)勢與不足，本文考慮在人工智能背景下對單獨卡車配送模式進行優(yōu)化，采用卡車與無人機聯(lián)合配送模式。確定一個無人駕駛的交付系統(tǒng)的效率飛行器(UAV)通過正在移動的卡車向客戶提供服務(wù)。即配送的過程為無人機從卡車上拿起一個包裹(卡車繼續(xù)行進)，并將包裹送達到相應(yīng)的配送點完成配送后即包裹交付后，無人機再返回到卡車裝載下一個包裹并進行配送，直至完成所有的配送任務(wù)?？ㄜ嚺c無人機聯(lián)合配送模式下的配送路線如圖2所示。其中實線軌跡圓為卡車的行駛路徑，軌跡圓周圍的虛線軌跡為無人機對各個配送點的配送路徑。采用這種聯(lián)合配送模式可以有效結(jié)合單卡車與單無人機兩種配送模式的優(yōu)勢與不足。

圖2 卡車與無人機協(xié)調(diào)配送

2 卡車與無人機聯(lián)合配送路徑規(guī)劃

聯(lián)合配送模式下首先確定卡車行駛的路徑，本文將卡車的最優(yōu)配送路徑規(guī)劃為一個圓，再基于卡車配送路徑上確定無人機對每一個配送點配送的起始點與返回點。

2.1 卡車配送路徑的規(guī)劃

對于卡車配送路徑的規(guī)劃，首先采用重心法求得各配送點的重心坐標，接著以重心為圓心，以各配送點到圓的距離和最短為目標函數(shù)確定其半徑，求得的圓即為卡車的配送路徑。具體步驟如下：

(1) 重心法確定圓心。假設(shè)U={p1，p2，…，pn}為一個區(qū)域內(nèi)n個配送點的集合，將配送點的坐標設(shè)為(pix，piy)，其中i=1，2，…，n，配送點的重心坐標設(shè)為P(x0，y0)，重心點到各配送點的運輸費用設(shè)為w1di，其中w1為無人機運輸費率(單位為元/km)，di為重心點到各配送點的直線距離，其中di為

di=[(x0-pix)2+(y0-piy)2]1/2

再以重心到各個點的總費用T最小為目標函數(shù)，求出重心坐標，其中T為

(2) 確定路徑圓的半徑。以各配送點的重心點為圓心，以各配送點到圓面的距離和最短為目標，求得路徑圓的半徑R。即：

2.2 無人機配送路徑規(guī)劃

2.2.1 效率約束下的無人機配送路徑規(guī)劃模型

對區(qū)域內(nèi)n個配送點集合U={p1，p2，…，pn}，其中i=1，2，…，n，卡車與無人機聯(lián)合配送模式下，令卡車行駛的速度為φ0，無人機行駛的速度為φ1，配送時間為T1，目標函數(shù)則求解最短配送總時間。對每個配送點pi，確定無人機從卡車配送路徑上配送起飛點Ii及配送返回點Oi。為簡化計算，考慮在極坐標系下建立模型，以卡車配送路徑的圓心P(x0，y0)為原點，則各個配送點的坐標可表示為pi(ρ，θ)，無人機對每個配送點pi的配送起飛點可表示為Ii(R，θIi)，返回點可表示為Oi(R，θOi)，在極坐標系下以配送時間最短為目標函數(shù)建立模型如下：

(3)

(4)

目標函數(shù)(3)中‖·‖表示兩點之間的距離，T1為無人機單獨行駛配送的總時間與卡車載著無人機行駛總時間之和。約束條件(4)分別表示為卡車在配送過程中無返程現(xiàn)象；無人機的上一個配送返回點處于下一個配送起點之前；對于每個配送點pi，無人機配送的行駛時間要大于卡車在無人機起飛點Ii及配送返回點Oi間的行駛時間。

2.2.2 碳排放約束下的無人機配送路徑規(guī)劃模型

物流活動中的碳排放主要來源于物流活動中消耗各類物質(zhì)和能源所帶來的間接或者直接的二氧化碳排放?，F(xiàn)以在物流活動過程所消耗的燃料量來核算碳排量，其代換公式為碳排量=燃料消耗量×CO2排放系數(shù)[7-8]。為簡化問題，假設(shè)物流活動中的燃料消耗量與運輸距離有關(guān)，設(shè)單位距離下卡車配送的燃料消耗量為β0，無人機燃料消耗量為β1，已知CO2排放系數(shù)為e0。

卡車與無人機聯(lián)合配送模式下，令卡車與無人機總的碳排放量為E1，以整個配送過程中碳排放量最小為目標函數(shù)建立模型如下：

2πRβ0e0

(5)

其中目標函數(shù)(5)中前半部分為整個配送過程中無人機配送的碳排放量，后半部分為卡車配送的碳排放量。

3 模型求解

3.1 單卡車配送路徑規(guī)劃模型求解

單卡車配送問題是一個NP難問題，遺傳算法能較好地解決這一問題。其求解單卡車配送問題有三步：首先對配送點進行編碼，從而產(chǎn)生解集的初始種群M；其次通過設(shè)定Pc和Pm產(chǎn)生新的種群，不斷繁衍進化；當?shù)竭_預(yù)訂迭代次數(shù)T后，收斂于最適應(yīng)環(huán)境的個體即為問題滿意解[9-10]。同時令單獨卡車配送碳排放量E0=θβ0e0，配送效率T0=θ/φ0，以完善單卡車配送模型。

3.2 聯(lián)合(無人機)配送路徑規(guī)劃模型求解

本文通過LINGO軟件對效率約束下聯(lián)合配送模式的路徑規(guī)劃進行求解，由于模型的變量較多，本文在求解過程中對初始解的設(shè)置進行了特定編制，從而快速得到最優(yōu)解。

在碳排放量約束條件下，當卡車的行駛路徑確定時，以無人機配送距離最短為目標確定的無人機配送路徑即為模型的最優(yōu)解。求得各個配送點與卡車行駛路徑圓心的連線與圓的交點即為無人機最優(yōu)配送起始點與配送返回點，此時配送起始點與返回點重合。

4 算 例

4.1 算例描述

已知區(qū)域內(nèi)有12個待配送的需求點，假設(shè)其坐標分別為

p1(24.80，12.75)p2(28.65，14.55)

p3(34.26，12.74)p4(22.09，20.12)

p5(18.39，15.49)p6(12.99，20.33)

p7(14.71，13.03)p8(8.47，15.41)

p9(8.28，10.86)p10(19.84，10.54)

p11(34.71，20.73)p12(35.72，16.50)

其中坐標軸的單位為km。已知具體相關(guān)參數(shù)值如表1所示。

表1 相關(guān)參數(shù)及數(shù)值

4.2 結(jié)果對比

在單卡車配送路徑規(guī)劃的遺傳算法求解中，令M=20，T=100，Pc=0.6，Pm=0.05，結(jié)果如圖3所示：

圖3 單卡車配送模式優(yōu)化路徑Fig.3 Optimization path of single truck distribution mode

由卡車與無人機聯(lián)合配送模式，求得聯(lián)合配送模式下卡車配送路徑圓心坐標為P(21.01，14.94)，圓的半徑R=7.657。通過求解碳排放及效率約束下的無人機配送路徑規(guī)劃模型，得到兩種約束條件下卡車與無人機的最優(yōu)配送路徑，如圖4—圖5所示。

通過模型結(jié)果可得單獨卡車配送碳排放量及效率值與卡車和無人機聯(lián)合配送碳排放量及效率值對比，如表2所示。

由表2中的結(jié)果可知，卡車與無人機的聯(lián)合配送模式相比于單獨的卡車配送模式在配送效率以及碳排放量有明顯優(yōu)化。

圖4 配送效率約束下最優(yōu)配送路徑Fig.4 Optimal distribution path under the constraint of distribution efficiency

圖5 基于碳排放量優(yōu)化后配送路徑Fig.5 Optimal distribution path under carbon emission constraints

模 式配送效率碳排放量卡車配送模式T0=1.832 5 hE0=286.970 7 kg聯(lián)合配送模式T1=1.071 9 hE1=249.591 5 kg

5 總 結(jié)

本文提出卡車與無人機聯(lián)合配送模式，建立相應(yīng)模型，設(shè)計相關(guān)求解方法，對指導(dǎo)人工智能在配送中的應(yīng)用具有指導(dǎo)意義。