葉春森，王雪軒， 時(shí)章漫， 黃成成

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

0 引 言

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

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

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

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

(1)

(2)

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

圖1 單獨(dú)卡車配送

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

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

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

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

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

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

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

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

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

再以重心到各個(gè)點(diǎn)的總費(fèi)用T最小為目標(biāo)函數(shù)，求出重心坐標(biāo)，其中T為

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

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

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

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

(3)

(4)

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

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

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

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

2πRβ0e0

(5)

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

3 模型求解

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

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

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

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

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

4 算 例

4.1 算例描述

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

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)

其中坐標(biāo)軸的單位為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

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

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

由表2中的結(jié)果可知，卡車與無人機(jī)的聯(lián)合配送模式相比于單獨(dú)的卡車配送模式在配送效率以及碳排放量有明顯優(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é)

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