袁雨果

（集美大學誠毅學院商船系，福建廈門361021）

一、引言

改革開放以來，我國經(jīng)濟社會的快速發(fā)展、經(jīng)貿(mào)活動的不斷增多，特別是電子商務的發(fā)展，為快遞行業(yè)快速發(fā)展提供了良好的契機。國家統(tǒng)計局數(shù)據(jù)表明，2010—2019 年這10 年我國快遞業(yè)務迅速發(fā)展，業(yè)務量增長26 倍，業(yè)務收入也相應地由574.6 億元提升至7 498 億元①，如圖1 所示。一方面快遞行業(yè)在增量市場（如農(nóng)村快遞業(yè)務） 仍舊大有可為，另一方面快遞企業(yè)在存量市場上競爭卻不斷加劇。為了應對激烈的市場競爭環(huán)境，各快遞企業(yè)都試圖通過優(yōu)化自身物流系統(tǒng)，以達到提升效率、降低成本和增強服務滿意度的目標。近年來，客戶退貨維修或者物品回收等需求不斷增加，一些快遞企業(yè)也傾向于在進行 “ 最后一公里 ” 配送的同時攬收客戶需要寄出的物件（如京東物流） 以提升物流服務效率，使得在 “ 最后一公里 ” 配送過程中整合正向物流和逆向物流成為企業(yè)提升運營效率和降低物流成本的重要途徑[1]。

電子商務物流配送可以大致分為三個階段，即倉儲、主干網(wǎng)運輸和 “ 最后一公里 ” 配送[2]，其中 “ 最后一公里 ” 配送是指將物品從倉儲中心發(fā)送給終端客戶的過程[3]。很多研究指出， “ 最后一公里 ” 配送極大地影響電商物流的服務質(zhì)量和成本[2，4]，也是非常復雜的環(huán)節(jié)，因為它直接與終端客戶接觸，訂單數(shù)量大而規(guī)模小，而且終端客戶對配送方式、配送時間等要求都具有高度個性化和變動性等特點。

在此背景下，研究 “ 最后一公里 ” 車輛路徑優(yōu)化問題時考慮正向和逆向物流整合具有重要的意義。相比一般的 “ 最后一公里 ” 配送，本問題更為復雜，它包括兩個交互影響的階段：車輛配送和攬貨任務的分配、車輛路徑的優(yōu)化。這個問題可以被抽象為一個同時取送貨的帶有時間窗的車輛路徑規(guī)劃問題（Vehicle routing problem with simultaneous pick-up and delivery with time windows（VRPSPDTW））。VRPSPD已經(jīng)被廣泛證明是一個NP 難問題，很難通過精確算法高效而準確地解決大規(guī)模VRPSPD[5]，而啟發(fā)式方法則被認為是解決這類NP 難問題的有效方式。為此，結(jié)合遺傳算法和變鄰域搜索算法，設計了一個包括3 個步驟的啟發(fā)式方法。通過構(gòu)建100 個仿真場景，并通過統(tǒng)計分析的結(jié)果驗證了該啟發(fā)式方法具有較好的性能。

圖1 2010—2019 年我國快遞行業(yè)發(fā)展情況

二、文獻綜述

（一） “ 最后一公里 ” 物流問題

近年來我國電子商務快速發(fā)展，同時帶動了快遞等相關(guān)產(chǎn)業(yè)的發(fā)展。國家統(tǒng)計局數(shù)據(jù)表明，過去10 年快遞業(yè)務量和業(yè)務收入年均增長率分別達到44%和33%①。然而，在電商物流快速發(fā)展的過程中也暴露出了一些問題，特別是 “ 最后一公里 ” 配送成為制約電商物流提升服務質(zhì)量和降低物流成本的關(guān)鍵環(huán)節(jié)[6，7]。為了解決 “ 最后一公里 ” 配送存在的問題，一些創(chuàng)新的配送方式不斷被設計出來，比如自助收發(fā)箱和顧客自提站等模式[8]：Mikko 等[9]和Song 等[10]的研究均表明，相比傳統(tǒng)配送方式，在 “ 最后一公里 ” 配送環(huán)節(jié)中采用自助收發(fā)箱模式可以有效降低物流成本、提升配送效率。

盡管上述多元化的配送方式在一定程度上提升了電商物流 “ 最后一公里 ” 配送的效率，但是無法解決車輛回程空載所造成的成本問題。為了進一步降低 “ 最后一公里 ” 配送的成本，學界和業(yè)界都開始探索在 “ 最后一公里 ” 中整合正向物流和逆向物流，即考慮在進行配送的同時實現(xiàn)攬貨。比如，郭月[11]分析了農(nóng)村地區(qū) “ 最后一公里 ” 配送和 “ 最初一公里 ” 攬收存在的主要問題，如需求量不足、配送成本高、設施不完善等，為此提出了 “ 選擇取送貨 ” 模式，從而為物流企業(yè)網(wǎng)點下沉提供有效的解決方案；何瑩瑩[12]針對家電行業(yè)中存在頻繁的退換貨從而導致逆向物流的現(xiàn)象，構(gòu)建了考慮同時取送貨的家電物流路徑優(yōu)化模型，并設計了混合粒子群算法進行求解。由此可見，同時考慮配送和攬收是傳統(tǒng) “ 最后一公里 ” 配送的變體，可以通過同時取送貨的車輛路徑問題進行建模。

（二） 同時取送貨的車輛路徑優(yōu)化

車輛路徑問題（Vehicle routing problem，VRP）最早由Dantzing 和Ramser[13]于1959 年提出，它是運籌學的一個熱門研究問題。由于其應用的廣泛性和在經(jīng)濟社會發(fā)展（如物流、交通等） 中的重要價值，國內(nèi)外很多學者針對VRP 進行了大量的研究，并提出多種變體以更好地解決所研究的問題。這其中，Min[14]針對圖書館取送書任務的實際，在VRP 的基礎(chǔ)上考慮同時取送貨的問題，首次提出了VRPSPD。在此之后，很多學者開始嘗試基于VRPSPD 解決物流和交通等領(lǐng)域的問題，比如：Liu[15]將VRPSPD 運用于家庭醫(yī)療物流優(yōu)化中，并針對該問題構(gòu)建了兩個混合整數(shù)規(guī)劃模型，同時提出了相應的解決算法；Shi[16]同樣針對家庭醫(yī)療物流問題，提出了一種隨機規(guī)劃模型；Alshamrani[17]則將VRPSPD 運用于解決具有逆向物流的美國紅十字會的血液配送問題，并提出了解決該問題的啟發(fā)式算法。現(xiàn)有研究往往根據(jù)所解決問題的特征，對VRPSPD 做進一步拓展，形成一些新的變體，如：考慮車輛異質(zhì)性（Heterogeneous VRPSPD）[18]、考慮車輛存在多個起止點的情況（Multi-depot-VRPSDP）[19]、考慮多層次配送問題（Multi-echelon VRPSPD）[20]、研究車輛行駛時間隨機的情況（Stochastic travel-time VRPSPD）[21]和節(jié)點具有時間窗約束的情況（VRPSPD-time windows）[22]。同時，這些研究提出了大量的算法來求解VRPSPD相關(guān)的問題，如蟻群算法[23]、粒子群算法[24]、局部搜索算法[25]、遺傳算法[26]、分支定界算法[27]、變鄰域搜索算法（VNS）[28]、分支定界和離散螢火蟲算法（DFA） 等[29]，以及將上述若干種算法相結(jié)合設計的啟發(fā)式方法。

三、數(shù)學模型構(gòu)建

整合正逆向物流的 “ 最后一公里 ” 車輛路徑優(yōu)化問題可以視為考慮同時取送貨的帶有時間窗的車輛路徑問題（VRPSPDTW）。在保證該問題的主要特征的前提下，為突出主要問題特征而不失一般性，做出如下假定：1.所有車輛的起止節(jié)點都為同一個物流配送站點；2.一個客戶可能只需要配送服務或只需要攬貨服務，或兩種服務同時需要；3.同一個客戶有且僅有一臺車輛服務；4.每臺車輛都完全相同。為了便于問題的描述，表1 羅列了所涉及的變量及其相應的解釋。

表1 變量定義及解釋

（一） 目標函數(shù)

如果車輛k 從客戶i 直接到客戶j，則0-1 離散變量為1，否則則車輛k 行駛的總距離hk可以通過式（1） 計算，其中cij為客戶i 與客戶j 之間的空間距離。如果車輛k 被調(diào)用，則0-1 變量δk=1，否則δk=0，如式（2） 所示。本研究的目的是實現(xiàn)所有配送和攬收任務的總成本最低，如式（3） 所示，式中α 表示使用一臺車輛的固定成本，而β 則表示每輛車單位距離所需要的變動成本。

（二） 約束條件

所有客戶的配送或攬貨需求都要被滿足，且每個客戶有且只有一臺車輛服務，如式（4） 所示，其中N 表示客戶位置集合，R 為所有位置集合（R=N∪{0}）。根據(jù)上述假設，所有車輛的起止點都為相同的物流站點，如式（5） 所示。式（6） 確保車輛空間路徑的連通性，即車輛服務客戶后需要離開該客戶。所使用車輛的數(shù)量不能超過現(xiàn)有最大車輛數(shù)量K，如式（7） 所示。

青春如果沒有了奮斗，沒有了掙扎，沒有了希望，沒有了絕望，還叫什么青春？青春是一生當中最迷茫、焦慮、充斥著絕望、挑戰(zhàn)的時候，但是為什么所有的人都說青春美好呢？

yij為經(jīng)過?。╥，j）的客戶i 之前的客戶攬貨總和，而zij為經(jīng)過?。╥，j）的客戶i 之后的客戶貨物配送總和?？蛻魯堌浐退拓浀那闆r分別如式（8） 和（9）所示，每輛車的載貨量在任意時刻都不能超過車輛最大容量Q，如式（10） 所示。

四、算法設計

VRPSPD 已經(jīng)被廣泛證明是一個NP 難問題，很難通過精確算法高效而準確地解決大規(guī)模VRPSPD[5]。為此，結(jié)合遺傳算法和變鄰域搜索算法，設計一個包括3 個步驟的啟發(fā)式方法，該方法的流程圖如圖2 所示。

（一） 解編碼

圖2 算法流程圖

根據(jù)表1 的定義，車輛數(shù)量為K、客戶數(shù)量為N。在解編碼過程中引入虛擬客戶的概念來構(gòu)建染色體，每條染色體代表一個解，具體處理如下：隨機確定一個0～K-1 的整數(shù)作為虛擬客戶的數(shù)量，則該問題可以轉(zhuǎn)換為單車輛的路徑優(yōu)化問題，即車輛從物流中心出發(fā)，完成所有任務后，又回到同一物流中心。以圖3 為例來說明解編碼的過程，在該圖中包括12 個客戶，4 輛車。在0 到3 之間隨機產(chǎn)生一個整數(shù)。假設隨機產(chǎn)生的數(shù)為2，標記為13 和14。對客戶集{1，2，…，13，14}排序，假定得到的一條染色體為0-3-4-7-9-13-10-1-2-5-14-8-6-11-12-0。將染色體中的虛擬客戶（13 和14） 替換為物流配送中心0，即可得到0-3-4-7-9-0-10-1-2-5-0-8-6-11-12-0。以 “ 0 ” 為標記將該染色體進行拆分，得到{0-3-4-7-9-0}，{0-10-1-2-5-0}和{0-8-6-11-12-0}等3 條子染色體，分別表示3 輛車所分配的客戶及線路。

圖3 解編碼過程（示例）

（二） 初始解集構(gòu)造

根據(jù)上述解編碼方式，可以構(gòu)造大量解。然而，在構(gòu)建過程中也可能會產(chǎn)生一些違反前述約束條件的解，可稱為非可行解。為了提升后續(xù)解優(yōu)化的效率，需要提前將非可行解刪除，只允許可行解進入初始解集。初始解產(chǎn)生流程如下：

（1） 引入n 個虛擬客戶（0≤n≤K-1），構(gòu)建客戶集合{v1，…，vN，vN+1，…，vN+n-1}；

（2） 基于（1） 得到的客戶集，根據(jù)前一節(jié)假定生成一條染色體以表征一個解；

（3） 拆分（2） 中生成的染色體，以得到每輛車的服務客戶及物流線路；

（4） 計算車輛完成所有任務所行駛的距離hk、整個過程中車載重量、服務每個客戶的時間（5） 若該解為可行解，即滿足各個約束條件，則將該染色體保存至初始解集合中，否則舍棄該染色體并重新返回步驟（1）；

（6） 如果初始解集合中包含的解數(shù)量達到算法預設的種群規(guī)模數(shù)量，則初始解集合構(gòu)造的過程結(jié)束，否則返回步驟（1） 以生成新的解。

（三） 解集進化

解集進化是整個啟發(fā)式方法的核心環(huán)節(jié)，為了提升方法的性能，根據(jù)本問題的特征，將進化過程分為兩個階段：全局優(yōu)化和局部優(yōu)化。遺傳算法最早由Holland 在1975 年提出，由于具有較強的全局搜索能力等眾多特點，遺傳算法被廣泛應用于解決車輛路徑優(yōu)化問題[26]。由Mladenovic＇和Hansen 提出的變鄰域搜索算法通過系統(tǒng)地執(zhí)行鄰域變換程序以獲得更好的解，它具有很好的局部搜索能力[30]。根據(jù)上述兩種方法的特點以及本問題的特征，本啟發(fā)式方法在全局優(yōu)化中采用遺傳算法，而局部優(yōu)化則采用變鄰域搜索算法。

1.全局優(yōu)化

遺傳算法包括交叉互換、變異和復制等算子，本啟發(fā)式方法在進行全局優(yōu)化時采用單點變異和雙點變異兩種算子。分別以圖4 和圖5 來說明單點變異和雙點變異的過程。對于單點變異，首先從解集中隨機選擇一個解（如3-4-7-9-13-10-1-2-5-14-8-6-11-12），并從該染色體中隨機選擇一個基因（如圖4 的 “ 1 ” ）。以該變異點為節(jié)點，將染色體截取為3-4-7-9-13-10 和2-5-14-8-6-11-12 兩個染色體片段，并交換兩個染色體片段的位置以形成新的染色體，即：2-5-14-8-6-11-12-1-3-4-7-9-13-10。

圖4 單點交叉變異

染色體雙點變異的過程如圖5 所示，同樣從解集中隨機選擇一條染色體（如2-5-14-8-6-11-12-1-3-4-7-9-13-10），并在該染色體中任意選擇兩個基因（如圖5 的 “ 8 ” 和 “ 4 ” ）。以兩個變異基因為節(jié)點將染色體截取為3 個片段：2-5-14，6-11-12-1-3 和7-9-13-10。其中，采用倒序的方式對兩個變異基因間的片段進行重新排序，從而得到新染色體，即2-5-14-8-3-1-12-11-6-4-7-9-13-10。

圖5 兩點交叉變異

2.局部優(yōu)化

由于VNS 具有結(jié)構(gòu)簡單和魯棒性較強等特點[31]，因此被廣泛應用于VRP 的相關(guān)研究中[28]。VNS 系統(tǒng)地將鄰域分為兩個相互作用的階段，變鄰域下降階段（VND） 的目的在于得到局部最優(yōu)，而擾動階段來跳出當前局部最優(yōu)。這里，采用兩種擾動策略來完成VNS 的擾動：1） 隨機移動虛擬客戶在染色體的位置，如圖6（a） 所示。2） 調(diào)整虛擬客戶的數(shù)量，如圖6（b） 所示。具體而言，1） 當現(xiàn)有染色體的虛擬客戶數(shù)量為K-1，則隨機減少一個虛擬客戶；2） 當現(xiàn)有染色體的虛擬客戶數(shù)為0 時，則增加一個虛擬客戶并隨機插入到染色體的其中一個位置；3） 當現(xiàn)有虛擬客戶的數(shù)量介于1 和K-2 之間，則隨機增加或減少一個虛擬客戶。VND 中依次包含的結(jié) 構(gòu) 有Insert、Move-Best、Two-Opt、Swap-Best、Extract-Insert 和Extract2-insert[32]。

圖6 兩個VNS 擾動策略實例

在局部優(yōu)化中基于上述2 個擾動策略和6 個鄰域結(jié)構(gòu)：首先產(chǎn)生一個初始解，并執(zhí)行第1 個擾動策略以得到該初始解的擾動解，記為S（i）；針對該擾動解S（i），依次執(zhí)行上述6 個鄰域結(jié)構(gòu)，不斷優(yōu)化該擾動解，直至找到局部最優(yōu)解。如果找到的局部最優(yōu)解優(yōu)于S（i），則重復執(zhí)行第1 個擾動策略，否則則執(zhí)行第2 個擾動策略。重復上述過程，但所有擾動策略執(zhí)行完畢后，則VNS 的過程結(jié)束，該過程將輸出優(yōu)化后的解。

五、算例分析及討論

為了驗證本方法的性能，通過模擬產(chǎn)生100 個仿真場景。具體而言，隨機產(chǎn)生一組客戶集合（包括客戶的數(shù)量、客戶的位置、客戶取送貨重量、客戶的時間窗）、配送中心的位置以及車輛最大數(shù)量。同時，為便于比較，引入標準遺傳算法作為比較基準。為了減少誤差，對于每個仿真場景，都用兩種算法分別運行30 次，并對這30 次結(jié)果取平均值（如圖7）。

圖7 兩種算法總成本對比

為了探索兩種方法的性能是否有統(tǒng)計學意義上的差異，使用配對樣本t 檢驗的方法對二者的結(jié)果進行進一步分析。檢驗結(jié)果分別如表2 和表3 所示：遺傳算法得到的總成本均值為978.74，標準偏差為271.30，而啟發(fā)式方法得到的成本均值和標準偏差分別為823.82 和280.96，t（100）=23.90，p＜0.05，說明在0.05 的顯著性水平下，相比于遺傳算法，啟發(fā)式方法得到的總成本顯著較低。

表2 描述統(tǒng)計（遺傳算法Vs.啟發(fā)式方法）

表3 配對樣本t 檢驗結(jié)果（遺傳算法Vs.啟發(fā)式方法）

六、研究總結(jié)與展望

近年來，我國電子商務的快速發(fā)展帶動了快遞行業(yè)的發(fā)展，相應地也加劇了該行業(yè)的競爭。 “ 最后一公里 ” 作為電子商務物流活動的最后環(huán)節(jié)，在提升物流效率、降低物流成本和提高服務滿意度等方面具有重要意義；與此同時， “ 最后一公里 ” 同樣也面臨眾多問題和挑戰(zhàn)。

“ 最后一公里 ” 整合正逆向物流的車輛優(yōu)化問題，被抽象為一個VRPSPDTW，設計一個基于遺傳算法和變鄰域搜索算法的3 步驟啟發(fā)式方法來求解該問題。通過構(gòu)建100 個仿真場景，并通過統(tǒng)計分析的結(jié)果驗證了該啟發(fā)式方法具有較好的性能。

盡管所設計的啟發(fā)式方法能夠較好地解決同時取送貨的帶有時間窗的車輛路徑規(guī)劃問題，但是隨著客戶規(guī)模的增加，算法的效率還有待提升。除此之外，由于交通擁擠、等待客戶等情況時有發(fā)生，這就使得將交通時間和服務客戶時間視為確定值往往與實際情況不符合。因此，未來在研究 “ 最后一公里 ” 物流車輛路徑優(yōu)化時，需要進一步考慮這些隨機因素。

注釋：

①數(shù)據(jù)來源：國家統(tǒng)計局.