王 爽 陳淮莉

(上海海事大學物流科學與工程研究院 上海 201306)

0 引 言

物流“最后一公里”的配送在物流領域具有舉足輕重的位置，其占據(jù)物流總配送成本的30%～50%，促使物流企業(yè)不斷創(chuàng)新來增強其競爭力。過去幾十年智能設備的進步催化出共享經(jīng)濟的新模式，共享經(jīng)濟使得閑置的自然資源成為財富，加之物流行業(yè)自身的驅(qū)動因素，利用共享經(jīng)濟降低物流成本、提高配送效率成為物流業(yè)革新的方向。其中沃爾瑪和亞馬遜首先提出“眾包物流”的理念，使得普通人而不僅僅是物流公司雇傭的員工，可以協(xié)同物流公司進行配送。近些年來電商的迅速發(fā)展給物流的配送領域帶來了新的機遇和挑戰(zhàn)，電商的快速發(fā)展給物流行業(yè)帶來了繁榮，同時電商客戶眾多，訂單時間地點分布不均以及運能的不穩(wěn)定給物流的最后一公里配送帶來了巨大挑戰(zhàn)。

“兼職員工”在制造業(yè)或者商品銷售領域應用較為廣泛,大量企業(yè)通過雇傭兼職員工來降低企業(yè)的運營成本。在物流行業(yè)，兼職員工主要集中在集散中心，配送領域很少會涉及兼職配送，主要原因在于技術(shù)的限制,但是隨著電子技術(shù)的發(fā)展，打破了以前技術(shù)的界限，兼職配送成為了可能。

車輛路徑問題又稱之為VRP問題，在物流領域被廣泛研究，VRP的相關研究每年以6%的趨勢實現(xiàn)增長。1964年Clarke和Wright首次提出了車輛調(diào)度問題，車輛路徑的問題研究涉及到經(jīng)典VRP問題、帶時間窗的VRP問題、帶有拾貨揀貨VRP問題，以及以保護環(huán)境為主題的GVRP問題。其中Andelmin等[1]通過啟發(fā)式局部搜索算法，利用多重構(gòu)圖重構(gòu)解決了綠色車輛的路徑問題。Goeke等[2]提出常規(guī)車輛以及電動車混合配送問題，研究在城市中如何通過電動汽車和普通車輛的混合配送來節(jié)約運輸成本。

眾包理念來源于共享經(jīng)濟，隨著科技進步，電子設備不斷更新，解決了眾包的技術(shù)問題，給眾包物流提供了一個有效的平臺，學者們對于合作共享的研究也深入到各行各業(yè)。Roshanaei等[3]研究了醫(yī)療領域的聯(lián)合手術(shù)室排程計劃，將醫(yī)院進行聯(lián)盟，醫(yī)生服務于不同的醫(yī)院，借此來解決醫(yī)療資源分配不均的問題，進一步提高醫(yī)療資源的利用率。范厚明等[4]針對生鮮品配送提出了多中心聯(lián)合配送半開放式的車輛路徑研究，快速對客戶需求做出響應，提高了生鮮品的配送效率，降低了損失率，從而降低了企業(yè)成本，進一步促進了生鮮行業(yè)的發(fā)展。陳萍等[5]針對外賣配送問題提出了基于時間滿意度的O2O外賣配送路徑優(yōu)化研究，引入了顧客的時間滿意度函數(shù)，求解客戶的最大滿意度。

對于眾包物流參與最后一公里配送問題 ，目前國內(nèi)外的科學研究還比較缺乏，研究與實踐不足以支持當前的需求。其中Archetti等[6]提出采用眾包車輛參與配送的研究，但是沒有考慮送貨的時間窗問題，有很強的局限性。Dahle等[7]研究了帶時間窗的眾包司機的提貨和交貨問題，提出了不同補償方案對于配送效率和顧客滿意度的影響。Hla等[8]研究了針對駕駛員行為控制的物流公司人員和眾包配送員的配送研究，引入了速度等級，通過控制速度，進一步降低成本，降低排放。國內(nèi)目前研究集中在眾包模式理論研究上，鮮少有關于物流公司和眾包車輛的聯(lián)合配送的研究文章。

上述對于物流公司和眾包車輛的聯(lián)合配送研究中，在計算成本時，很少有文獻考慮到物流公司員工的啟動成本，即物流公司配送員工工資問題,以及對眾包車輛接單范圍研究過少，沒有考慮到眾包司機只有在滿足一定的距離范圍才愿意進行訂單的配送。對此，本文將眾包車輛接單范圍及眾包車輛目的地引入到本次研究中，通過研究物流公司和眾包車輛的聯(lián)合配送，減少物流公司配送人員的數(shù)量，提高物流配送資源的利用率，實現(xiàn)對物流配送的新的規(guī)劃。

1 問題描述及模型建立

本文所研究的問題簡稱為VRPOD問題,可描述如下：某物流配送網(wǎng)絡有m個取貨點，集合對應為I,I={1,2,…，m},對應n個客戶，集合對應為J,J={m+1，m+2，…，m+n}。我們定義從i點配送到點m+i，V是所有點的集合，V=I∪J,0點為物流公司車輛出發(fā)點，物流公司車輛記作KR，隨機分布的眾包車輛記作KO，k∈K=KR∪KO,眾包車輛的原始位置記做o(K),眾包車輛的目的地為d(k)，客戶需求的時間窗記作(ETi，LTi)，lTi表示在客戶接受范圍內(nèi)最晚送達時間。邊集合E={(i,j)|i,j∈V},長度為dij，物流公司的配送成本由配送員配送的啟動成本(即配送員工資)和配送費用組成，從i到j的配送成本記作Oijk，k∈KR，車輛到達時間為Tik，k∈K，K=KR∪KO,服務時間為tik，車輛容量為Qq，q=A,B,C，q=A代表物流公司配送車輛容量，q=B,C時，為眾包配送車輛容量，代表三種不同的類型車輛。lik表示車輛k在i節(jié)點的載重，dj表示j點的需求量，當dj大于等于0。本文規(guī)定眾包車輛盡可能多配送訂單，物流公司配送車輛要從配送中心出發(fā)完成配送后返回配送中心，物流公司的每一輛車可以在時間窗不沖突的條件下完成多個訂單的配送。當選擇眾包車輛配送時，需要滿足眾包車輛的目的地位置d(K)到配送點J的位置d(jk)<ε(ε為常數(shù))，眾包車輛才擁有配送資格。βijk表示訂單是否可以通過眾包車輛從i配送到達j，wijk表示眾包車輛k是否去配送訂單;λ是眾包車輛的報酬系數(shù),為一個常數(shù);C為物流公司配送員工資，為一個常數(shù)。我們規(guī)定眾包車輛只能配送一單，并且每個訂單通過眾包配送成本會低于通過物流公司配送?？紤]到眾包物流的參與以及物流配送過程中會受到天氣環(huán)境以及配送人員對于路況的熟悉程度的影響從而導致訂單配送超時情況,引入客戶滿意度成本,最后一公里配送中客戶的滿意度主要與配送的時效性有關，所以通過配送的時效性來代表客戶滿意度?？蛻魸M意度成本主要由兩部分構(gòu)成,G(i)為客戶滿意度成本系數(shù),b為一個常數(shù)。根據(jù)上述參數(shù)建立數(shù)學模型如下:

(1)

(2)

(3)

(4)

(5)

(6)

ωijk≤βijki∈I,j∈J,k∈Ko

(7)

(8)

(9)

Tik+tt,n+i≤Tn+i,kk∈K,i∈J

(10)

(lik+Lj-ljk)xijk=0

i∈V,i∈J,k∈KR

(11)

Li≤lik≤Qqi∈V,k∈K

(12)

xijk={0,1}

(13)

βijk={0,1}

(14)

ωijk={0,1}

(15)

目標式(1)表示總費用最小，費用包括物流公司配送員的工資，配送的運輸成本和對眾包司機的報酬三部分組成。約束條件中：式(2)限制物流公司配送車輛從配送中心出發(fā)。式(3)限制物流公司配送車輛完成配送任務最后返回配送中心。式(4)表示是否通過物流公司配送。式(5)表示物流運輸?shù)钠胶怅P系。式(6)表示眾包車輛是否擁有配送資格。式(7)表示擁有配送資格的眾包司機是否決定配送訂單。式(8)表示每一個訂單只能通過一次配送。式(9)表示客戶滿意度系數(shù)與配送時間的關系。式(10)表示訂單配送的先后順序。式(11)表示物流公司配送車輛容量限制。式(12)表示配送的重量不能超過配車輛的最大容量。式(13)-式(15)表示變量取值為0-1變量。

2 算法及求解

由于考慮眾包模式的車輛路徑問題比較復雜，精確算法往往很難在短時間內(nèi)得到精確求解。國內(nèi)采用的大多數(shù)均為啟發(fā)式算法和混合式啟發(fā)式算法，考慮到VRPOD問題中相比經(jīng)典VRP問題多考慮了眾包司機這一因素，并且對眾包司機配送條件加以限制，考慮因素眾多，算法的求解效率和降低成本都很重要。采用基于聚類分析的遺傳算法進行求解。第一步先進行聚類分析得出眾包司機配送的訂單，本文假設采用眾包物流配送一個訂單的配送成本是低于通過物流公司的配送成本的，通過聚類分析得出能夠通過眾包配送的最大訂單量；第二步對物流公司配送的訂單進行遺傳算法求解。

2.1 “訂單-目的地”配對策略

將要配送的訂單位置與眾包車輛目的地按照經(jīng)緯度進行配對。例如訂單i對應的“訂單-目的地”按照配送訂單經(jīng)緯度位置，眾包車輛目的地經(jīng)緯度位置進行配對。

2.2 聚類過程

K-means算法是最經(jīng)典、應用最廣泛的聚類分析方法，其目標是使得類內(nèi)距離盡可能小，類間距離盡可能大。本文采用K-means算法對“訂單-目的地”進行聚類，聚類的數(shù)目即為采用眾包車輛配送的最大數(shù)目。由于待聚類對象的維度一致，且費用與距離呈現(xiàn)正相關性，無需加權(quán)，且配送屬于距離配送，因此在聚類中采用歐氏距離進行聚類，成本函數(shù)表示為類內(nèi)距離平方和與類間距離平方和之比：

(16)

式中：D=1,2，3,4表示的是訂單位置和顧客目的地的四個經(jīng)緯度集合；vji表示j的第i維，cl表示離對象j最近的類中心；cli表示cl集第i維的值；Ψlj表示對象j是否屬于類l，是為1，否為0。

聚類算法步驟如下：

Step1初始化聚類數(shù)目k=λ0(λ0=max{符合眾包配送條件約束的臨時車輛數(shù)，當前需要配送的訂單數(shù)})。

Step2初始化k個聚類中心。

Step3計算每個對象j到每個聚類中心cl的距離，將每個對象賦予距離最近的類。

(17)

Step4計算各類cl中所包含的對象ψlj的總和，從每一個類挑出距離最近的一個對象，把其他對象賦予距離次近的類，同時調(diào)整ψlj值。綜上，可以得出最大臨時車輛的配送情況，且k的值會隨臨時車輛數(shù)量的變化而發(fā)生變化。該算法把每一類看作一輛眾包配送車輛，類中涉及的訂單由此輛眾包車輛來完成配送。

2.3 傳統(tǒng)配送方式的路徑優(yōu)化策略

Step1染色體編碼。對于通過物流公司配送的訂單，我們規(guī)定一個客戶只能被一輛車服務，所以染色體中的客戶不存在重復的客戶點。如果一個客戶存在多個訂單我們模擬為多個客戶，根據(jù)車輛行駛順序編碼的形式進行編碼,用(G1,G2,，…，Gn+k)表示染色體,Gi=0表示配送中心,k代表目前存在的車輛數(shù)量,假如目前有三輛車進行訂單配送,行駛路徑為{(1,2)(3,4,5,6)}若目前有固定車輛和滿足條件的臨時配送車輛一共五輛車,則編碼為(1,2,0,3,4,5,6,0,7,0,0,0)。

Step2初始種群的形成。我們采用隨機生成的方法形成初始種群,隨機產(chǎn)生M條可行解路徑,每條路徑均為一條染色體,M條染色體可以構(gòu)成一個種群規(guī)模為M的初始種群,然后以這個初始種群進行迭代。初始解的質(zhì)量的優(yōu)劣直接影響搜索的速度和質(zhì)量，所以初始解的質(zhì)量也很重要。

Step3計算適應度函數(shù)。我們以本文的優(yōu)化目標作為適應度函數(shù)，以路徑{3,4,5,6}為例，適應度函數(shù)T=C+c34d34+c45d45+c56d56+c60+d60，適應度函數(shù)為成本函數(shù)，計算每條路徑的成本函數(shù),即為本次路徑的適應度。

Step4進化操作。進化操作包括交叉、變異、選擇，從適應度數(shù)值中選擇出比較適合環(huán)境的個體。

2.4 算例分析

根據(jù)本文的研究思路以及模型的特點，給出相應的參數(shù)設置，并且利用MATLAB進行求解，驗證模型的正確性。我們假設訂單配送時間在[0，60]的區(qū)間之間，即模擬一小時的訂單配送情況。

通過用MATLAB隨機分別生成20個客戶位置信息和10、20個隨機車輛位置信息，首先采用傳統(tǒng)配送方案,即訂單完全通過物流公司進行配送。對于這種情況本文采用遺傳算法進行路徑規(guī)劃；其次分別假設存在10輛和20輛眾包車輛，并且眾包車輛參與配送。由于訂單配送情況是動態(tài)的,影響訂單配送的因素也是事先無法預測的,為了驗證模型的準確性,采用MATLAB生成隨機數(shù)生成程序隨機產(chǎn)生訂單延遲配送情況。由于在現(xiàn)實中除特定節(jié)假日訂單配送的準確性很高，因此假設訂單延遲配送的概率為0.05%，其中在顧客接受的配送時限延遲配送概率為0.03%，在顧客接受范圍之外的延遲配送概率為0.02%。隨機生成的客戶位置如表1所示，眾包車輛情況如圖1和圖2所示，眾包車輛類型及容量限制如表2-表4所示，相關參數(shù)設置如表5所示。

表1 客戶分布情況

續(xù)表1

表2 眾包車輛基本情況(車輛數(shù)目為10)

表3 眾包車輛基本情況(車輛數(shù)目為20)

表4 車輛容量分布

表5 測試集參數(shù)設置

首先不考慮眾包配送的情況，則問題簡化為傳統(tǒng)配送問題采用遺傳算法求解，求解的最優(yōu)配送如圖3和表6所示。

表6 傳統(tǒng)配送最優(yōu)路徑

然后采用物流公司和眾包車輛相結(jié)合的配送方式，先對客戶進行聚類分析。聚類原則為盡可能采用眾包車輛配送，眾包司機每次僅配送一單，根據(jù)眾包車輛目的地位置及訂單位置，在滿足眾包車輛配送的條件下采用行駛距離最少原則進行聚類分析。聚類結(jié)果如表7、表8所示。

表7 當眾包車輛為10時

表8 當眾包車輛為20時

對傳統(tǒng)車輛配送通過遺傳算法求解，當眾包車輛數(shù)目為10時(方案1)，配送路線如圖4所示，最優(yōu)略徑如表9所示，眾包車輛配送信息如表10所示。

表9 方案1最優(yōu)路徑

表10 方案1眾包車輛配送信息

當眾包車輛數(shù)目為20時(方案2)，配送路線如圖5所示，最優(yōu)路徑如表11所示，眾包車輛配送信息如表12所示。

表11 方案2最優(yōu)路徑

根據(jù)MATLAB隨機生成的數(shù)據(jù)得到采用傳統(tǒng)配送延遲配送的配送點為點8，延遲配送的戶滿意度成本為5元，采用10輛眾包車輛參與配送的延遲配送點為點9，延遲成本為10元，采用20輛眾包車輛參與配送的延遲配送點為點1和點7延遲成本分別為15元和3元。兩種配送成本比較如表13所示。

表13 配送成本比較

3 結(jié) 語

由上述案例可知，眾包配送的引入可以降低物流的運輸成本，眾包車輛參與配送的數(shù)目越多，成本降低得越多，眾包參與最后一公里配送能夠在一定限度上節(jié)約配送成本。且眾包車輛參與配送能夠在原有基礎上增加配送能力，減少物流公司配送車輛的數(shù)量，在同等訂單需求下，眾包車輛參與配送能夠以更便捷的速度更低廉的成本達到配送需求，可以更好解決物流特定節(jié)假日產(chǎn)生的大量訂單需求。

針對目前物流配送運能不均的現(xiàn)狀和物流資源不能合理利用的問題，引入眾包物流的概念，可以在一定限度上解決上述問題，同時可以進一步使得閑置資源得到最大化的利用，進一步解決了物流資源不夠充分的問題，降低運輸成本，提高資源的利用率，為目前配送問題提出了切實可行的解決方案,并且為企業(yè)節(jié)約運輸成本。眾包車輛參與配送主要與其目的地和報酬率有一定的關系，不同的報酬率可能會造成不同的影響，這是一個值得進一步探討的問題。本文只考慮一個眾包車輛只配送一個訂單，沒有考慮一個眾包車輛配送多單的情況，也沒有考慮隨機訂單的情況，使得本文有一定的局限性。