基于遺傳禁忌混合算法的軟時間窗無人配送車路徑優(yōu)化

陳志強(qiáng)，吳 芳

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

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

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

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

1 無人配送車的路徑優(yōu)化問題描述

1.1 問題分析

無人配送車路徑優(yōu)化問題需從三大類方向考慮：

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

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

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

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

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

2 模型建立

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

無人配送車路徑優(yōu)化目標(biāo)函數(shù)見下式：

(1)

(2)

式中：n表示配送點(diǎn)個數(shù)；m表示最大配送車編號；k表示配送車編號(k=1,2,3,…,m)；θα、θβ分別表示配送車相對客戶的早、晚到達(dá)懲罰系數(shù)；tijk表示第k輛車從i到j(luò)的行駛時間，h；sijk表示第k輛車從配送點(diǎn)i到j(luò)時，在j點(diǎn)對顧客服務(wù)時長，h；pijk表示第k輛車從配送點(diǎn)i到j(luò)時，在j點(diǎn)額外時間，h；teij、tlij分別表示配送車從配送點(diǎn)i到達(dá)配送點(diǎn)j時，在j點(diǎn)的理想最早、晚時間，h；xijk表示決策變量，當(dāng)?shù)趉輛配送車訪問路徑ij時為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表示單輛配送車?yán)m(xù)航里程，km；md表示配送服務(wù)最遠(yuǎn)距離，km；dij表示配送點(diǎn)i至配送點(diǎn)j的距離，km；Q表示單輛配送車的額定載容量，件；Iijk表示第k輛車從配送點(diǎn)i到j(luò)時，在j點(diǎn)顧客取貨次數(shù)，次.

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

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

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

1) 確定編碼類型，初始化種群；

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

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

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

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

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

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

3.1 染色體編碼

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

圖1 染色體編碼示意圖

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

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

(10)

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

(11)

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

3.3 算子操作

3.3.1 選擇算子

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

3.3.2 交叉算子

利用隨機(jī)數(shù)確定交叉染色體及交叉位點(diǎn)，每一個體產(chǎn)生兩個交叉位點(diǎn)，交叉?zhèn)€體兩兩配對，將處于交叉點(diǎn)中間部分基因片段分別置于對方首段，并刪除尾端重復(fù)基因，其過程如圖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個，且會因配送點(diǎn)個數(shù)的不同發(fā)生較大變化.若每次迭代對全部領(lǐng)域解進(jìn)行搜索比對，運(yùn)算效率將會大打折扣，因而本文從中隨機(jī)選擇部分領(lǐng)域解進(jìn)行尋優(yōu)處理，其選擇個數(shù)為4(n-1)個，當(dāng)且僅當(dāng)n≥8時算式成立.

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

4.1 算例描述

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

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

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

4.2 問題求解

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

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

圖4 評價(jià)函數(shù)收斂曲線

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

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

5 結(jié)論

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

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

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