考慮外協(xié)服務的車輛路徑優(yōu)化問題

葛顯龍, 宋純冰

(1.重慶交通大學 經(jīng)濟與管理學院,重慶 400074; 2.重慶交通大學 智能物流網(wǎng)絡重慶市重點實驗室,重慶 400074)

0 引言

近年來，許多線下零售企業(yè)紛紛開始發(fā)展其線上零售業(yè)務，如永輝生活，重百優(yōu)選等，但傳統(tǒng)零售商如何實現(xiàn)線上業(yè)務與線下配送的融合，提供具有成本效益的送貨上門服務，是傳統(tǒng)零售企業(yè)轉型的關鍵。沃爾瑪和亞馬遜等企業(yè)提出的一個新的解決方案是“眾包”，即吸引普通人在前往目的地的路途中協(xié)助運輸包裹。因此考慮使用外協(xié)服務來解決“最后一公里”配送具有重要的現(xiàn)實意義。

考慮外協(xié)服務的車輛路徑問題的基礎是將配送服務外包給具有承運能力的線下客戶，這與眾包配送研究息息相關。趙興龍[1]以眾包配送網(wǎng)絡為研究對象，研究了眾包配送網(wǎng)絡中存在的延時配送和無人接單問題。隨著新零售與即時物流概念的興起，楊曉莉[2]從眾包物流公司收益和客戶滿意度角度，對配送型眾包物流的人貨供需匹配進行深入研究，提出了一種定價與匹配相關聯(lián)的模型。Savelsbergh和Van Woensel[3]證實了眾包配送中的主要挑戰(zhàn)是確定找到車輛出發(fā)的最佳時機以及車輛之間包裹的最佳分配比的策略。Agatz等[4]系統(tǒng)地概述了開發(fā)乘車共享技術時出現(xiàn)的優(yōu)化挑戰(zhàn)和相關的運籌學模型。Furuhata等[5]提出了一個用于了解現(xiàn)有拼車系統(tǒng)中關鍵因素的分類。Lee和Savelsbergh[6]對外協(xié)配送問題建立了整數(shù)規(guī)劃模型，并提出啟發(fā)式算法求解。Stiglic等[7]探討了使用集合點來改善乘車共享系統(tǒng)性能的優(yōu)點。Baldacci等[8]提出了一種用于求解拼車問題的基于列生成的精確解方法。Masson等[9]討論了人與貨物之間的運輸資源共享。Li等[10]研究了出租車與乘客共同運送包裹的情景。Ghilas等[11]和Masson等[12]探討了貨運中使用公共交通的可能性及潛在優(yōu)勢。Fatnassi等[13]在城市物流自動化運輸系統(tǒng)背景下研究了客運和貨運的整合。Archetti等[14]研究了沃爾瑪公司的愿景，并將其稱為偶然駕駛員的路線問題。

以上文獻分析了共享運輸資源的研究情況，且多數(shù)研究都傾向于客運。與本文研究類似的Archetti等[14]考慮了使用臨時駕駛員補充傳統(tǒng)配送服務，但該學者研究的問題中沒有考慮時間窗的設置。在考慮時間窗和城市配送的車輛路徑問題中，葛顯龍等[16,17]研究了電商企業(yè)的“自建物流+第三方物流”配送模式，建立了基于第三方軟時間窗約束的車輛路徑模型，并設計相應的求解算法進行求解。

因此，本文考慮使用外協(xié)服務來補充傳統(tǒng)配送服務，建立帶時間窗的車輛路徑問題模型(VRPTWOS，Vehicle Routing Problems with Time Windows and Outsourced Services)，運用匈牙利算法加混合遺傳算子的模擬退火算法對模型進行求解。最后結合算例對本文提出的模型與算法進行了檢驗與分析。

1 問題描述

考慮外協(xié)服務的車輛路徑問題主要針對具有線上、線下銷售同時具有物流配送服務的大型零售企業(yè)，如大型連鎖超市。超市具有線下到店客戶與線上客戶兩種，且超市意愿使用線下客戶來協(xié)助完成線上客戶訂單的配送，未能由協(xié)作車輛服務的線上客戶將由普通車輛完成配送。將協(xié)助配送的線下客戶稱為協(xié)作車輛，超市日常用于配送的車輛稱為普通車輛。

每個線上客戶具有需求和時間窗要求，違反時間窗配送將產生懲罰成本，懲罰成本與早到或遲到的時間長度成正比。假設所有協(xié)作車輛都在商店內表明其協(xié)作配送意愿，因此，所有協(xié)作車輛的起點為商店。協(xié)作車輛最多可以向客戶完成一次交付，并且協(xié)作車輛在接受服務線上客戶的訂單時需符合自己的出行時間，因此協(xié)作車輛的交付完全符合線上客戶的時間窗要求。當協(xié)作車輛與線上客戶訂單未能匹配成功時，其路徑如圖1(a)所示，該客戶需要由普通車輛完成配送。當協(xié)作車輛與線上客戶訂單匹配成功時，其路徑如圖1(b)所示，協(xié)作車輛從超市完成線上客戶訂單后不用返回超市。

客戶需求必須由普通車輛或協(xié)作車輛服務。由協(xié)作車輛服務的行程包括從超市行駛到線上客戶的需求位置，以及由客戶的位置到協(xié)作車輛的目的地。采取Archetti等[14]對臨時司機的補償，協(xié)作車輛收到pif=ρdoi的補償，ρ表示協(xié)作車輛的運輸補償系數(shù)，且0<ρ<1。當不考慮臨時駕駛員時，問題簡化為標準的帶時間窗的容量車輛路徑問題(CVRPTW)。

圖1 協(xié)作車輛與線上客戶匹配示意圖

2 建立數(shù)學模型

2.1 符號說明

2.2 協(xié)作車輛與線上客戶訂單匹配

首先考慮協(xié)作車輛的出行時間與客戶時間窗的關系。協(xié)作車輛的服務時間滿足線上客戶時間窗，如式(1)、(2)所示。同時還需使協(xié)作車輛在完成服務后返回其目的地的時間不晚于其能接受的最晚時間，如式(3)所示。

af+toi≥ai

(1)

af+toi≤bi

(2)

af+toi+diNj≤bf

(3)

協(xié)作車輛接受的繞行距離最大為從超市到協(xié)作車輛目的地距離的δ倍，其中δ表示協(xié)作車輛的協(xié)作靈活度，且δ≥1，如式(4)所示。

doi+diNf≤δdoNf

(4)

ωif≤βif,?i∈NC,f∈F

(5)

(6)

ωif∈0,1,?i∈NC,f∈F

(7)

βif∈0,1,?i∈NC,f∈F

(8)

式(5)表示確保將線上客戶分配給愿意為該客戶提供服務的協(xié)作車輛。式(6)確保協(xié)作車輛最多只能為一個線上客戶提供服務。由此可得到協(xié)作車輛與線上客戶訂單匹配的結果。式(7)、式(8)為0-1變量。

2.3 建立VRRTWOS數(shù)學模型

根據(jù)上述分析，建立VRPTWOS問題的數(shù)學模型。

(24)

目標函數(shù)(9)為最小化總成本，包括普通車輛的路徑成本、使用成本、軟時間窗懲罰成本以及協(xié)作車輛的補貼成本。約束(10)表示普通車輛流量平衡。約束(11)保證普通車輛路線以超市為起止點。約束(12)表示每個需求點只能被普通車輛服務一次。約束(13)確保滿足客戶需求。約束(14)為普通車輛的容量約束。約束(15)保證普通車輛必須空載回到配送中心。約束(16)表示每輛普通車輛服務的線上客戶數(shù)量不能超過總的線上客戶數(shù)量。約束(17)為計算普通車輛行駛時間公式。約束(18)表示普通車輛離開客戶點的時間與到達時間，服務時間之間的關系。約束(19)為普通車輛行駛時間計算。約束(20)表示普通車輛違背軟時間窗的懲罰成本。約束(21)確保每個客戶都只被服務一次。約束(22)～(24)為0-1變量。

3 算法設計

考慮到模型的特殊性，設計的算法分為兩部分。第一部分完成協(xié)作車輛與線上訂單的匹配。第二部分對于剩余未能匹配的線上客戶訂單，問題簡化為帶軟時間窗的車輛路徑問題，設計帶遺傳算子的混合模擬退火算法求解，模擬退火算法魯棒性強，適合并行處理，結合遺傳算子能夠提高算法全局搜索能力和收斂速率。

3.1 編碼設計

采用自然數(shù)編碼方式表示方案的解，以客戶編號作為解的元素，0作為配送中心。每個解可分為幾條路線，必須包含所有客戶點，每條路線包含配送中心和至少一個客戶點，解的路線之間由配送中心0隔開。

3.2 設計協(xié)作車輛與線上訂單的匹配算法

步驟1利用協(xié)作車輛的出行時間與客戶允許的時間窗服務時間進行初步匹配。

步驟2篩選符合距離約束的結果。

步驟3使用匈牙利算法，得到每個協(xié)作車輛服務一個線上客戶的同時總成本最小的匹配結果。

步驟4將成功匹配的線上客戶訂單從線上客戶訂單列表中刪除。

3.3 設計混合模擬退火算法

(1)初始解的生成

步驟1對于未被成功匹配的線上客戶訂單，使用節(jié)約里程算法，在不考慮容量約束的前提下生成超市到線上客戶點的TSP解。即只有一輛普通車輛從超市出發(fā)服務所有的未被成功匹配的線上客戶后返回超市。

步驟2判斷路線上的線上客戶需求是否符合普通車輛的容量約束，超出容量限制則通過分車算子拆分為兩條路徑。

步驟3對于符合普通車輛容量約束的線路，判斷普通車輛到達線上客戶點的時間是否在規(guī)定的時間窗約束內，若滿足則生成初始可行路徑。

(2)設計遺傳算子

選擇算子采用傳統(tǒng)輪盤賭算子。

交叉算子采用保留最佳子串策略。任選兩條染色體作為父代1和父代2，保留父代1中載重量最大的子串，并將其作為選中基因提前，同時選擇父代1中除超市外的另外兩個隨機基因作為固定基因，并將選擇基因和固定基因以外的基因剔除。將父代2中與上述未被剔除基因相同的部分剔除，并將父代2中剩余除超市外的基因依次插入父代1中。按照規(guī)定的容量約束重新插入超市。

變異算子為隨機選擇一條染色體，在該染色體中隨機選擇一個變異位置，若該位置不為0，則隨機生成一個新基因替換原有基因。若變異位置基因為0，則重新選擇變異位置。

(3)設計模擬退火擾動算子

模擬退火算法中采用隨機擾動算子，其步驟如下表示

步驟1產生新狀態(tài)sj=Genete(s);

步驟2ifmin{1,exp[(-C(sj)-C(s))]}≥random[0,1),s=sj;

步驟3min{1,exp(-ΔC/t)}作為狀態(tài)函數(shù)接受準則。

4 算例分析與仿真

4.1 實例仿真

以重慶某零售超市及其周邊117個小區(qū)為例，超市D00為配送中心，C1-C67表示線上客戶，F(xiàn)1-F50表示線下客戶的目的地。線上客戶的需求及時間窗已知，見附件中表1，線下客戶的出行時間已知，如附件中表2所示。

為驗證在實際情況中使用外協(xié)服務可以帶來何種程度的成本節(jié)約，在補償系數(shù)ρ=0.1，協(xié)作靈活度δ=1.5，即在高協(xié)作靈活度，適中補償系數(shù)下進行測算，假設普通車輛容量為100件，普通車輛啟動成本200元，兩種車輛的單位運輸成本均為5元，普通車輛違背時間窗單位懲罰成本為2元，兩種車輛的行駛速度均為30公里/小時的情況下，對VRPTW和VRPTWOS成本分別進行10次測算。

表1 參數(shù)靈敏度分析

測算結果顯示，使用外協(xié)服務可以有效降低總成本。在不使用外協(xié)服務時，平均成本為1716.055元，需使用7輛普通車輛來完成全部67個線上客戶訂單。在考慮使用外協(xié)服務時，有23個線上客戶訂單可以由協(xié)作車輛服務，只需5輛普通車輛完成剩余44個線上客戶訂單，總配送成本為1298.7元。在3次測試中，平均成本節(jié)約為24.32%，普通車輛使用數(shù)減少28.57%。為驗證在不同補償系數(shù)以及不同協(xié)作靈活度的情況下對結果的影響，使用補償系數(shù)ρ=0.05,0.1,0.2和協(xié)作靈活度δ=1.1,1.3,1.5的多種可能組合對實例求解，結果如表1所示。

由表1可知，協(xié)作靈活度越大時，即協(xié)作車輛可以接受配送的范圍越廣時，總配送成本越低，同時當協(xié)作靈活度增大時，協(xié)作車輛與線上客戶訂單的匹配程度增加，在一定程度上減少普通車輛的使用。同時隨著補償系數(shù)的增大，總配送成本的降低越小。經(jīng)過測算，當ρ=0.3時，在低協(xié)作靈活度的情況下已經(jīng)無法降低總配送成本。

圖2為使用混合遺傳算子的模擬退火算法得到的不考慮外協(xié)服務時的實際普通車輛運行路線。

圖2 不考慮外協(xié)服務時的實際普通車輛運行路線

在考慮外協(xié)服務時對未能成功匹配的客戶重新編號為1- 44，使用混合遺傳算子的模擬退火算法求解得到普通車輛路徑解，在百度地圖中得實際運行線路如圖3所示。

圖3 考慮外協(xié)服務時的普通車輛實際運行路線

由圖2、圖3可以看出，考慮使用外協(xié)服務時的實際運輸距離要少于不使用外協(xié)服務時，并且線路數(shù)也有所減少。由于南坪商圈的實際交通道路錯綜復雜，存在單行道、隧道、立交等特殊情況，因此在實際車輛運行路線中存在繞行的情況。同時由于客戶包含時間窗需求，所以在實際的運行線路圖中存在線路重疊。

4.2 算例分析

為了驗證算法的有效性，本文進行了算例的分析驗證。我們從Solomon算例中選取了三種不同客戶分布的實例來進行驗證，并在算例中隨機選擇50個客戶作為線下自提客戶，其余50個作為線上客戶。在補償系數(shù)ρ=0.1,δ=1.5，普通車輛的最大裝載為100件，普通車輛啟動成本200元，普通車輛和協(xié)作車輛的單位運輸成本均為5元，普通車輛違背時間窗單位懲罰成本為2元，普通車輛和協(xié)作車輛的行駛速度均為30公里/小時的情況下對算例進行了測算，具體結果如表2所示。

從結果可以看出，我們的匹配方式可以實現(xiàn)最高66%的匹配率，平均匹配率可達42%，證明了我們的匹配方式的可行性。表6顯示，使用線下客戶外協(xié)服務可以帶來最多54.76%的成本節(jié)約，平均的成本節(jié)約為34.01%，同時可以帶來平均38.06%的車輛使用數(shù)的減少。從而證明了我們算法的有效性。

為進一步驗證本文算法的有效性，將混合遺傳算子的模擬退火算法分別于遺傳算法和模擬退火算法進行性能對比，以67個線上客戶位置節(jié)點為例，分別在不考慮外協(xié)服務時和考慮外協(xié)服務時進行驗證，運算結果如表3所示。

經(jīng)過測算，在不考慮外協(xié)服務時，三種算法均使用7輛普通車輛完成67個線上客戶點的運輸，混合模擬退火算法得到的平均解和最優(yōu)解均優(yōu)于遺傳算法和模擬退火算法?；旌线z傳算子的模擬退火算法得到的平均解比遺傳算法成本節(jié)約了6.31%，對比模擬退火算法成本節(jié)約了3.61%。

在考慮外協(xié)服務時，由于匹配算法相同，在同種情況下協(xié)作車輛的匹配率相同，均為存在23個線上客戶由協(xié)作車輛完成配送。三種算法均使用5輛普通車輛完成剩余線上客戶訂單的配送。此時混合遺傳算子的模擬退火算法取得的最優(yōu)解和平均解依然由于遺傳算法和模擬退火算法?；旌线z傳算子的混合遺傳算子的模擬退火算法得到的平均解比遺傳算法成本節(jié)約了5.41%，對比模擬退火算法成本節(jié)約了2.59%。由此可得，本文設計的算法在尋優(yōu)能力上優(yōu)于遺傳算法與模擬退火算法。

表2 算例測試結果

表3 不考慮外協(xié)服務時算法性能比較

5 結論

針對開展線上銷售的新型零售企業(yè)的末端配送問題，引入了外協(xié)服務的概念，使用線下自提客戶來協(xié)助完成部分線上客戶訂單的配送，建立了考慮外協(xié)服務的最小化總成本的數(shù)學模型，并使用混合遺傳算子的模擬退火算法進行求解，最后結合算例分析得出了以下結論：(1)針對協(xié)作車輛與線上客戶的匹配設計了匹配算法，可以得到平均為42%的匹配成功率。(2)使用外協(xié)服務來解決相對應的配送問題可以在一定程度上降低配送成本和減少普通車輛的使用。

本文研究的目的是對使用外協(xié)服務來解決實際配送問題提供初步探討。對于未來的研究，可以關注協(xié)助車輛的不同停車意愿對于總配送成本的影響，也可將連鎖零售超市看作多個配送中心的車輛路徑問題來進行新的探討。在后續(xù)的研究中會繼續(xù)考慮和關注這兩個方面。