陳志強(qiáng)，吳 芳

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070)

目前食品配送服務(wù)仍處于持續(xù)發(fā)展階段[1]，需要考慮配送過(guò)程中的及時(shí)性與配送成本的節(jié)約性[2]，尤其在疫情災(zāi)害蔓延以及極端惡劣天氣無(wú)法保證時(shí)效等情況[3-5]，利用無(wú)人配送車(chē)恰是解決這類(lèi)問(wèn)題的有效手段.一方面是面對(duì)當(dāng)下肆虐疫情，無(wú)人配送車(chē)可杜絕人員間直接接觸，降低新冠狀病毒的傳染概率，為疫情隔離者或封閉小區(qū)居民提供生活必需品[6]，即使在一些國(guó)家的快遞配送人員因?yàn)閾?dān)心在配送過(guò)程中無(wú)法保持安全距離會(huì)感染新冠病毒而紛紛罷工的情形下，無(wú)人車(chē)配送依然可保證正常的配送業(yè)務(wù)順利進(jìn)行；另一方面無(wú)人配送車(chē)可在極端惡劣天氣中代替人員進(jìn)行物品運(yùn)輸，有效防止配送人員意外發(fā)生，提高配送的安全性.此外，考慮到無(wú)人配送車(chē)在日常配送中也可節(jié)省工作人員的工時(shí)支出，從而可進(jìn)一步降低配送成本，因此，推進(jìn)無(wú)人配送車(chē)行業(yè)發(fā)展愈加重要.

2017年初美國(guó)硅谷初創(chuàng)公司便推出無(wú)人配送車(chē)，為即時(shí)配送公司DoorDash提供服務(wù)，實(shí)現(xiàn)了在15至30分鐘時(shí)間內(nèi)完成一次配送.次年初，在“中國(guó)發(fā)展高層論壇2018年會(huì)”中，美團(tuán)公司首次亮相國(guó)內(nèi)的無(wú)人配送車(chē).截止目前，國(guó)內(nèi)外部分學(xué)者對(duì)無(wú)人配送路徑優(yōu)化問(wèn)題也進(jìn)行了大量研究，并取得一定的成果，王愚勤等[7]針對(duì)智能網(wǎng)聯(lián)無(wú)人車(chē)配送問(wèn)題，考慮了最大載重量及車(chē)載容量，建立關(guān)鍵點(diǎn)更新策略下的實(shí)時(shí)調(diào)整模型，并通過(guò)遺傳算法驗(yàn)證了模型可行性.王雷等[8]利用軟時(shí)間窗約束限定了配送車(chē)等待顧客時(shí)間，并運(yùn)用多種群遺傳算法(MPGA)確定運(yùn)輸成本.張洪海等[9]、Song等[10]、Roberge等[11]學(xué)者分別利用改進(jìn)A*算法、遺傳算法、PSO等算法分析了復(fù)雜環(huán)境下的無(wú)人配送最優(yōu)路徑問(wèn)題.

顧客滿(mǎn)意度往往是評(píng)價(jià)配送任務(wù)的關(guān)鍵指標(biāo)[12]，上述文獻(xiàn)均著重考慮了不同背景下的無(wú)人配送成本，部分忽略了服務(wù)對(duì)象在系統(tǒng)中的需求.其中含軟時(shí)間窗約束的路徑優(yōu)化研究，滿(mǎn)足了無(wú)人配送任務(wù)的及時(shí)性，而未將其作為目標(biāo)函數(shù)追求全部顧客最小等待時(shí)間.本文則針對(duì)無(wú)人配送車(chē)進(jìn)行約束限定，包括容載量約束、續(xù)航里程約束及服務(wù)范圍約束的同時(shí)，著重考慮顧客在運(yùn)輸系統(tǒng)中的重要性，引入配送車(chē)輛到達(dá)時(shí)間對(duì)客戶(hù)的影響程度，并以軟時(shí)間窗及時(shí)間成本為目標(biāo)函數(shù)尋求系統(tǒng)中每位顧客最小等待時(shí)間及總時(shí)間成本最小的最優(yōu)路徑.通過(guò)懲罰函數(shù)的設(shè)定淘汰滿(mǎn)意度較低的路徑，間接為顧客因等待過(guò)久所產(chǎn)生的焦慮感提供緩解措施.最后，基于遺傳算法中變異算子與禁忌搜索算法的結(jié)合，提高模型求解過(guò)程中的收斂能力與最優(yōu)解的逼近能力，為無(wú)人配送車(chē)路徑優(yōu)化問(wèn)題提供不同的求解算法.

1 無(wú)人配送車(chē)的路徑優(yōu)化問(wèn)題描述

1.1 問(wèn)題分析

無(wú)人配送車(chē)路徑優(yōu)化問(wèn)題需從三大類(lèi)方向考慮：

1) 公司經(jīng)營(yíng)者角度：對(duì)配送公司而言，通過(guò)車(chē)輛路徑優(yōu)化，實(shí)現(xiàn)利益最大化是其追求的核心內(nèi)容.需保證在滿(mǎn)足容量限制約束、最遠(yuǎn)距離約束的前提下，盡可能多的完成服務(wù)工作、更全面的照顧到每一位客戶(hù)，間接性地增加顧客回購(gòu)概率，使運(yùn)輸成本、公司形象、經(jīng)營(yíng)口碑得到更好的改善[13].因此，本文將時(shí)間成本作為極小化目標(biāo)函數(shù)之一，以滿(mǎn)足經(jīng)營(yíng)者的要求.

2) 顧客角度：顧客是檢驗(yàn)每輛配送車(chē)路徑優(yōu)化是否有效的關(guān)鍵因素[14-15].為減少顧客因訂單到達(dá)時(shí)間的不確定性，導(dǎo)致配送車(chē)過(guò)晚到達(dá)配送點(diǎn)從而降低顧客期待值，或是過(guò)早到達(dá)造成配送時(shí)間的額外損失.需建立帶軟時(shí)間窗的目標(biāo)函數(shù)，并分別賦予配送車(chē)相對(duì)客戶(hù)的早或晚到達(dá)懲罰系數(shù)，增加配送作業(yè)的準(zhǔn)時(shí)性與滿(mǎn)意度.

3) 配送車(chē)自身能力要求[16]：需要在滿(mǎn)足配送車(chē)自身能力限制條件下運(yùn)行，即要求單輛車(chē)往返配送中心過(guò)程中行駛總里程在限定續(xù)航之內(nèi)、配送速度考慮安全因素應(yīng)低于某一闕值、最遠(yuǎn)可達(dá)距離因其公司經(jīng)營(yíng)范圍不得超出所設(shè)定值，以及因自身容量限制需在單趟配送過(guò)程中配送總?cè)莘e少于額定容量，以此可建立部分模型約束條件.

1.2 參數(shù)設(shè)定

本文以美團(tuán)公司在北京順義、亦莊及深圳地區(qū)的實(shí)際運(yùn)營(yíng)數(shù)據(jù)為參考，設(shè)定當(dāng)前狀態(tài)下配送車(chē)可用數(shù)量、點(diǎn)對(duì)點(diǎn)間距離、平均行駛速度、配送額定容載量，以及配送車(chē)到達(dá)理想時(shí)間等參數(shù)為給定值.并設(shè)定每次訂單按實(shí)際情況只進(jìn)行簡(jiǎn)單商品配送服務(wù)，第三方商家不參與配貨服務(wù)，一切貨物均由配送公司籌備.配送中心已知且不會(huì)發(fā)生變化的情況下，所有配送車(chē)經(jīng)各配送點(diǎn)有且只有一次，且均經(jīng)配送中心出發(fā)最終返回配送中心，該問(wèn)題中顧客只參與取貨活動(dòng).在此過(guò)程中滿(mǎn)足配送車(chē)額定容量及續(xù)航約束下，使配送車(chē)輛的時(shí)間窗懲罰成本最少、總行駛時(shí)間成本最小，解決無(wú)人配送車(chē)的路徑優(yōu)化問(wèn)題以滿(mǎn)足各參與者的利益最大化.

2 模型建立

考慮時(shí)間成本與時(shí)間窗懲罰成本最小并結(jié)合實(shí)際可構(gòu)建數(shù)學(xué)模型，設(shè)定在某一確定配送周期內(nèi)可用配送車(chē)數(shù)量為m輛，若配送中心全部車(chē)輛均外出作業(yè)時(shí)顧客下單訂購(gòu)貨品，則該配送任務(wù)拖遲至下一周期完成.同時(shí)考慮在某一配送點(diǎn)臨近周?chē)赡艽嬖陬櫩投啻蜗聠蔚那闆r，根據(jù)配送任務(wù)所負(fù)責(zé)的區(qū)域?qū)⑼恢芷趦?nèi)下單較近的地點(diǎn)合并為一個(gè)配送點(diǎn)，并加以額為時(shí)間與實(shí)際工作相匹配.同時(shí)為保證時(shí)間及行程成本最優(yōu)，令其均由一輛配送車(chē)完成相應(yīng)的配送任務(wù)，即每一配送點(diǎn)下單次數(shù)不小于1次且不超過(guò)單輛車(chē)額定容量.

無(wú)人配送車(chē)路徑優(yōu)化目標(biāo)函數(shù)見(jiàn)下式：

(1)

(2)

式中：n表示配送點(diǎn)個(gè)數(shù)；m表示最大配送車(chē)編號(hào)；k表示配送車(chē)編號(hào)(k=1,2,3,…,m)；θα、θβ分別表示配送車(chē)相對(duì)客戶(hù)的早、晚到達(dá)懲罰系數(shù)；tijk表示第k輛車(chē)從i到j(luò)的行駛時(shí)間，h；sijk表示第k輛車(chē)從配送點(diǎn)i到j(luò)時(shí)，在j點(diǎn)對(duì)顧客服務(wù)時(shí)長(zhǎng)，h；pijk表示第k輛車(chē)從配送點(diǎn)i到j(luò)時(shí)，在j點(diǎn)額外時(shí)間，h；teij、tlij分別表示配送車(chē)從配送點(diǎn)i到達(dá)配送點(diǎn)j時(shí)，在j點(diǎn)的理想最早、晚時(shí)間，h；xijk表示決策變量，當(dāng)?shù)趉輛配送車(chē)訪(fǎng)問(wèn)路徑ij時(shí)為1，否則取0.

約束條件建立如下：

(3)

(4)

(5)

(6)

xijk(tik+si+tijk-tjk)≤0,(i≠j,k=1,2,…,m);

(7)

(8)

md,(k=1,2,…,m).

(9)

式中：sd表示單輛配送車(chē)?yán)m(xù)航里程，km；md表示配送服務(wù)最遠(yuǎn)距離，km；dij表示配送點(diǎn)i至配送點(diǎn)j的距離，km；Q表示單輛配送車(chē)的額定載容量，件；Iijk表示第k輛車(chē)從配送點(diǎn)i到j(luò)時(shí)，在j點(diǎn)顧客取貨次數(shù)，次.

其中：式(1)表示目標(biāo)函數(shù)，優(yōu)化目標(biāo)是時(shí)間成本最小，包括全部車(chē)輛行駛時(shí)間、配送點(diǎn)服務(wù)時(shí)間以及額外損失時(shí)間.其中額外時(shí)間代表該配送點(diǎn)因顧客下單次數(shù)不唯一，或多位顧客同一配送點(diǎn)周?chē)聠卧斐傻臅r(shí)間損失，而各配送點(diǎn)間路程時(shí)間均由距離及速度參數(shù)所得；式(2)表示帶軟時(shí)間窗的目標(biāo)函數(shù)，指配送物品到達(dá)配送點(diǎn)的時(shí)間準(zhǔn)時(shí)程度，即顧客滿(mǎn)意程度；式(3)表示單輛配送車(chē)行駛總里程不大于續(xù)航里程；式(4)表示容量平衡，即每個(gè)配送點(diǎn)的駛?cè)胲?chē)輛與駛出車(chē)輛數(shù)相同；式(5)表示從配送中心出發(fā)的配送車(chē)，完成相應(yīng)任務(wù)后必須返回配送中心；式(6)表示單輛車(chē)完成一趟配送任務(wù)所送出配送物品總數(shù)(實(shí)際載容量)，不得高于額定載容量；式(7)表示同一路徑上連續(xù)兩個(gè)配送站點(diǎn)之間，前一個(gè)站點(diǎn)的車(chē)輛到達(dá)時(shí)刻不超過(guò)后一個(gè)站點(diǎn)的車(chē)輛到達(dá)時(shí)刻；式(8)表示每輛配送車(chē)均由配送中心出發(fā)；式(9)表示單輛配送車(chē)只可在經(jīng)營(yíng)公司劃定范圍內(nèi)活動(dòng).

3 算法設(shè)計(jì)與求解

結(jié)合問(wèn)題特性設(shè)計(jì)近似算法或啟發(fā)式算法，是求解大規(guī)模NP問(wèn)題的常用方法.而單純利用遺傳算法可能受交叉算子的性質(zhì)影響，使染色體間存在相似性，同時(shí)由于較小的變異概率會(huì)使種群多樣性增加緩慢，易于出現(xiàn)“早熟”現(xiàn)象[17].本文引入領(lǐng)域搜索能力較好的禁忌搜索算法恰能解決這類(lèi)問(wèn)題[18-19].利用遺傳算法中的變異算子與禁忌搜索算法相結(jié)合(TSM算子)，改善遺傳算法局部搜索能力，使近優(yōu)解或全局最優(yōu)解更易得到，算法步驟如下：

1) 確定編碼類(lèi)型，初始化種群；

2) 評(píng)價(jià)種群中每條染色體的適應(yīng)度；

3) 利用輪盤(pán)賭選擇適應(yīng)度高的個(gè)體；

4) 對(duì)該代種群中全部個(gè)體選擇性交叉，并直接進(jìn)入新種群；

5) 隨機(jī)選取部分染色體，利用禁忌搜索算法尋求變異子代并直接進(jìn)入新種群；

6) 判斷目前全部染色體的評(píng)價(jià)指標(biāo)，根據(jù)每代種群選取數(shù)量相同的最優(yōu)染色體作為下一代；

7) 確定是否滿(mǎn)足終止條件.若不滿(mǎn)足，返回執(zhí)行步驟3)；否則，跳出循環(huán)，得到滿(mǎn)意解.

3.1 染色體編碼

利用自然數(shù)編碼，確定配送車(chē)路徑選擇，編碼長(zhǎng)度為n+m-1(m≤n)，由大于車(chē)輛數(shù)(m)的部分表示車(chē)輛間隔，間隔間的連續(xù)數(shù)表示不同車(chē)輛的路徑選擇.染色體編碼示意圖如圖1所示，車(chē)輛數(shù)為5，配送點(diǎn)數(shù)量為10，其編碼長(zhǎng)度為14，隨機(jī)排列14以?xún)?nèi)的正整數(shù)，產(chǎn)生五條不同子鏈，圈外數(shù)值均表示從0點(diǎn)(配送中心)出發(fā)或返回.

圖1 染色體編碼示意圖

3.2 適應(yīng)度函數(shù)

依據(jù)上述編碼方式，隨機(jī)選取同種群數(shù)量一致的染色體作為初始種群.并利用懲罰函數(shù)(見(jiàn)式10)處理未滿(mǎn)足約束條件的個(gè)體，即當(dāng)某一個(gè)體違反額定容量限制，或是超出配送車(chē)?yán)m(xù)航里程時(shí)，賦予該個(gè)體罰函數(shù)降低適應(yīng)度，通過(guò)迭代淘汰該基因型.

(10)

現(xiàn)對(duì)求解多目標(biāo)最小值問(wèn)題考慮線(xiàn)性加權(quán)，并加入罰函數(shù)得到個(gè)體適應(yīng)度函數(shù)見(jiàn)式(11)：

(11)

式中：fimin、fimax分別表示各目標(biāo)函數(shù)fi在當(dāng)前種群中的最值；Infi表示罰函數(shù)懲罰參數(shù)；μi表示無(wú)量綱變量的加權(quán)系數(shù)，并且適應(yīng)度值(Fi)直接與選擇概率正相關(guān).

3.3 算子操作

3.3.1 選擇算子

采用輪盤(pán)賭確定新種群個(gè)體，并在更新種群時(shí)保留上一代優(yōu)秀個(gè)體，防止基因型交叉對(duì)最優(yōu)個(gè)體的覆蓋.

3.3.2 交叉算子

利用隨機(jī)數(shù)確定交叉染色體及交叉位點(diǎn)，每一個(gè)體產(chǎn)生兩個(gè)交叉位點(diǎn)，交叉?zhèn)€體兩兩配對(duì)，將處于交叉點(diǎn)中間部分基因片段分別置于對(duì)方首段，并刪除尾端重復(fù)基因，其過(guò)程如圖2所示.

圖2 交叉算子操作示意圖

3.3.3 變異算子

根據(jù)變異概率隨機(jī)選取染色體進(jìn)行基因片段的交換、翻轉(zhuǎn)或是插入，并在變異體的基礎(chǔ)上利用禁忌搜索算法尋找領(lǐng)域最優(yōu)解.本文搜索算子采用兩交換法，其領(lǐng)域互換操作(SWAP)的領(lǐng)域解數(shù)量為n(n-1)/2個(gè)，且會(huì)因配送點(diǎn)個(gè)數(shù)的不同發(fā)生較大變化.若每次迭代對(duì)全部領(lǐng)域解進(jìn)行搜索比對(duì)，運(yùn)算效率將會(huì)大打折扣，因而本文從中隨機(jī)選擇部分領(lǐng)域解進(jìn)行尋優(yōu)處理，其選擇個(gè)數(shù)為4(n-1)個(gè)，當(dāng)且僅當(dāng)n≥8時(shí)算式成立.

4 實(shí)例計(jì)算與結(jié)果分析

4.1 算例描述

本文參考美團(tuán)公司在北京順義地區(qū)的實(shí)際運(yùn)行狀況，基礎(chǔ)模型參數(shù)設(shè)定如表1所列.本文選取其中一個(gè)配送中心進(jìn)行研究，設(shè)定該配送中心某一時(shí)段內(nèi)產(chǎn)生45次訂單配送任務(wù)，其中16次訂單為同一配送點(diǎn)的重復(fù)訂購(gòu).車(chē)輛行駛各點(diǎn)間平均速度取15 km/h，路程時(shí)間依據(jù)各點(diǎn)間距離與平均速度計(jì)算所得，配送車(chē)最早理想到達(dá)時(shí)間與最晚理想到達(dá)時(shí)間分別為相對(duì)原點(diǎn)(配送中心)路程時(shí)間前后的0.05 h與0.1 h，配送點(diǎn)坐標(biāo)及各類(lèi)時(shí)間參數(shù)如圖3所示.

表1 基礎(chǔ)模型參數(shù)

圖3 配送點(diǎn)坐標(biāo)及各類(lèi)時(shí)間參數(shù)

4.2 問(wèn)題求解

通過(guò)實(shí)例問(wèn)題與算法的分析，設(shè)置最大進(jìn)化代數(shù)為300代、變異概率為0.5、交叉概率為0.2、初始種群數(shù)目為300、禁忌長(zhǎng)度取5、領(lǐng)域解數(shù)量經(jīng)計(jì)算在本文中只取112個(gè)，此時(shí)可更快地獲得較好的結(jié)果，且不會(huì)輕易陷入局部最優(yōu)解.同時(shí)鑒于國(guó)內(nèi)眾多配送公司對(duì)顧客滿(mǎn)意度的重視，設(shè)軟時(shí)間窗目標(biāo)函數(shù)權(quán)重為0.66，時(shí)間成本權(quán)重為0.34.

運(yùn)用Matlab軟件建立遺傳禁忌搜索混合算法，并對(duì)該算例進(jìn)行求解，經(jīng)多次迭代后，得到無(wú)人配送車(chē)最佳開(kāi)行方案.為反映迭代過(guò)程解的收斂性，繪制評(píng)價(jià)函數(shù)變化曲線(xiàn)如圖4所示，并得到最優(yōu)總時(shí)間成本為5.14 h，最優(yōu)軟時(shí)間窗目標(biāo)為0.84.計(jì)算結(jié)果顯示各配送點(diǎn)最早到達(dá)時(shí)間均滿(mǎn)足最早理想時(shí)間的要求，且由配送車(chē)到達(dá)時(shí)間超出理想時(shí)間范圍外最大參數(shù)(最大晚到時(shí)間差)反映當(dāng)前路徑下車(chē)輛晚到情況，其各車(chē)輛所經(jīng)最優(yōu)子鏈及參數(shù)如表2所列.

圖4 評(píng)價(jià)函數(shù)收斂曲線(xiàn)

表2 最優(yōu)路徑及參數(shù)

問(wèn)題求解過(guò)程中在迭代至250次時(shí)，評(píng)價(jià)函數(shù)便已逐步收斂，對(duì)照多次運(yùn)行結(jié)果該算法降低了陷入局部最優(yōu)解的可能性，充分驗(yàn)證算法有效性.針對(duì)運(yùn)算結(jié)果，各項(xiàng)數(shù)值均滿(mǎn)足約束條件，各子鏈為該算例下的最優(yōu)路徑，其中存在2輛配送車(chē)不參與本次配送任務(wù)，為時(shí)間成本的節(jié)省及顧客滿(mǎn)意度的提高尋找到最優(yōu)方案.

5 結(jié)論

無(wú)人車(chē)輛配送系統(tǒng)利用無(wú)人車(chē)輛替代人工配送，有利于降低人工費(fèi)用支出等運(yùn)營(yíng)成本，有利于實(shí)現(xiàn)配送業(yè)務(wù)的自動(dòng)化，有利于提升配送效率和服務(wù)質(zhì)量，尤其有利于應(yīng)對(duì)特殊時(shí)期或特殊事件影響下配送需求訂單“爆倉(cāng)”而服務(wù)能力嚴(yán)重不足的矛盾.

本文針對(duì)無(wú)人配送車(chē)路徑優(yōu)化問(wèn)題進(jìn)行研究，重點(diǎn)考慮顧客層面感知滿(mǎn)意度的重要性，使用帶軟時(shí)間窗的目標(biāo)函數(shù)及懲罰函數(shù)，淘汰滿(mǎn)足總時(shí)間成本最小而存在個(gè)別滿(mǎn)意度較低的全部路徑.并利用遺傳算法中變異算子與禁忌搜索算法的結(jié)合，克服了“早熟”導(dǎo)致的缺陷，提高了解的精確度，為最優(yōu)路徑選取提供適當(dāng)?shù)乃惴?本文所研究?jī)?nèi)容可在配送系統(tǒng)中盡可能降低總時(shí)間成本，推動(dòng)資源的有效利用.并且在“零接觸”的配送模下，滿(mǎn)足大多數(shù)生活物質(zhì)送到準(zhǔn)時(shí)性的要求，降低因配送延時(shí)所引起的不滿(mǎn)情緒.

本文所提出的方法對(duì)于快速尋找較為滿(mǎn)意的路徑成效明顯，但忽略了現(xiàn)實(shí)道路擁堵延誤與配送特殊服務(wù)對(duì)配送時(shí)間造成的影響，也忽略訂單優(yōu)先級(jí)等問(wèn)題，后期應(yīng)結(jié)合現(xiàn)實(shí)情況進(jìn)行更加深入細(xì)致的研究.