萬勇平 （江西財(cái)經(jīng)大學(xué)，江西 南昌 330013）

WAN Yongping (Jiangxi University of Finance and Economics,Nanchang 330013,China)

0 引 言

物流“最后一公里”問題促使許多公司尋找創(chuàng)新性的解決方案，以此來降低總體配送成本。零售巨頭沃爾瑪計(jì)劃通過商場購物的顧客順路配送在線購物的包裹，這樣就不需要專門的配送公司或者車輛進(jìn)行包裹配送，通過這種方式來達(dá)到降低配送成本的目的[1]。沃爾瑪于2017年開始該計(jì)劃的小規(guī)模試點(diǎn)，嘗試讓員工在下班途中兼職快遞員，為客戶投送包裹。同樣為了提升配送效率，亞馬遜英國在2016年開始測試使用無人機(jī)進(jìn)行終端配送，預(yù)計(jì)30分鐘才能完成的第一次配送測試任務(wù)僅僅用了13分鐘。無人機(jī)配送也可以看作是一種物流眾包，與有人駕駛的車輛一樣，會(huì)產(chǎn)生配送成本問題，都要考慮如何優(yōu)化配送路徑，降低配送成本。因此，研究VRPOD問題有著重要的經(jīng)濟(jì)意義，有助于降低物流終端配送成本，提高配送效率。

1 問題描述及算法介紹

1.1 問題描述

車輛路線問題（Vehicle Routing Problem,VRP）由Dantzig和Ramser[2]在1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束條件（如配送供需、配送時(shí)間、車輛負(fù)載、車輛行駛里程等）下，達(dá)到如路程最短、成本最小、耗費(fèi)時(shí)間最少等規(guī)劃目標(biāo)。由于VRP具有廣泛的現(xiàn)實(shí)運(yùn)用和巨大的經(jīng)濟(jì)價(jià)值，VRP問題自1959年被提出以來，該問題一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一，受到國內(nèi)外學(xué)者的長期關(guān)注。

眾包車輛路徑問題（The Vehicle Routing Problem with Occasional Drivers,VRPOD）是VRP的一個(gè)變種問題，在基本VRP問題基礎(chǔ)上引入了眾包的概念。在眾包模式下物流配送公司不僅自身擁有運(yùn)輸車輛進(jìn)行配送，同時(shí)以一定報(bào)酬為前提，將一部分的包裹眾包給有配送愿意的順路的司機(jī)，相比于傳統(tǒng)的配送模式這種模式的好處在于自身需要維持的運(yùn)輸車輛更少，這樣能降低固定資產(chǎn)的比例。同時(shí)由于招募的司機(jī)更少，人員成本更低。物流配送公司需要考慮的是，如何安排自有車輛和眾包車輛的配送路線以降低總的配送成本。

本文假設(shè)存在一個(gè)配送中心，中心自身維持一定數(shù)量的配送車輛，向顧客點(diǎn)配送包裹。自有運(yùn)輸車隊(duì)配送能力不夠，需要將一部分包裹外包，私人車主順路接受配送請求并完成配送任務(wù)以獲得報(bào)酬。為了將問題簡化，我們并沒有考慮所有的符合現(xiàn)實(shí)中的條件，例如本文限制每位司機(jī)每次只能服務(wù)一個(gè)客戶點(diǎn)，實(shí)際上眾包司機(jī)可以服務(wù)多個(gè)客戶點(diǎn)。但是，這并不妨礙我們從經(jīng)濟(jì)的角度考察眾包模式對于物流配送帶來的效益。

1.2 算法介紹

為了驗(yàn)證模型是可行的，使用掃描法求解VRPOD問題并將其與在VRP問題下的解進(jìn)行比較。掃描法是一種傳統(tǒng)的啟發(fā)式求解算法，掃描法最早由Gillett和Miller提出?；舅枷胧牵阂耘渌椭行臑樵c(diǎn)建立極坐標(biāo)表示各客戶點(diǎn)的位置。給每個(gè)客戶點(diǎn)編號，客戶點(diǎn)的角度越大編號越大。從配送點(diǎn)沿著任意方向畫一條直線，按照順時(shí)針或者逆時(shí)針方向，把客戶點(diǎn)按從小到大的順序排入車輛配送路線中，路線安排要滿足車輛負(fù)載的約束條件，當(dāng)約束條件達(dá)到上限時(shí)返回配送中心，形成一條配送路線。重復(fù)以上步驟，繼續(xù)向下掃描，直到所有客戶點(diǎn)都被安排到一個(gè)分組當(dāng)中，此時(shí)操作結(jié)束。

2 建立數(shù)學(xué)模型

VRPOD的基本變量定義如下所示：G=N,（）A 表示完全有向圖，N是圖上各點(diǎn)的集合，A是圖上各條邊的集合；點(diǎn)集合N由兩部分構(gòu)成：配送中心0，客戶點(diǎn)集合C；車輛集合V包含兩部分：自有車輛集合S，每輛車的最大載荷為Q，配送到成本為c；雇傭車輛集合K，為了將問題簡化，假定雇傭車輛配額獲得的報(bào)酬與其目的地?zé)o關(guān)，只與配送中心到客戶點(diǎn)的距離doi有關(guān)，并且對于同一個(gè)配送點(diǎn)，所有司機(jī)獲得的報(bào)酬是一樣的。這種做法符合實(shí)際情況，因?yàn)?，雇傭車輛的公司并不會(huì)關(guān)心雇傭車輛的目的地。實(shí)際上，司機(jī)接受配送的意愿受配送點(diǎn)到目的地的距離的影響，越近意愿會(huì)越高，但是這種情況下，問題將更加復(fù)雜。作為對雇傭司機(jī)車的補(bǔ)償，提高配送意愿，司機(jī)獲得的報(bào)酬p=ξc0k，同時(shí)ξ＞1。假設(shè)眾包配送成本與車輛初始位置無關(guān)，只與配送點(diǎn)到目的地的距離有關(guān)，且車輛負(fù)載滿足單個(gè)客戶點(diǎn)的需求。建立如下所示的線性規(guī)劃模型：

上述模型中：式（1）為目標(biāo)函數(shù)，xij為二進(jìn)制變量（0或者1），表示自有車輛是否訪問邊（i,j）；cij表示自有車輛訪問邊（i,j）時(shí)付出的成本；pik表示眾包車輛k訪問客戶i所得的報(bào)酬；wik是一個(gè)二進(jìn)制變量，表示眾包車輛k是否訪問客戶點(diǎn)i。式（2）和式（3）為流約束，表示同一個(gè)客戶點(diǎn)只能被訪問一次。si表示客戶點(diǎn)i被自有車輛訪問過，是一個(gè)二進(jìn)制變量。式（4）中，qi表示客戶點(diǎn)i的包裹重量，自有車輛的載貨量不能超過車輛的最大負(fù)載。式（5）表示一位雇傭車輛最多只能服務(wù)1個(gè)客戶點(diǎn)。式（6）表示每位客戶分配到1輛雇傭車輛。式（7）表示每個(gè)客戶點(diǎn)只能被1輛車訪問。

3 算例分析

設(shè)定算例各點(diǎn)的位置信息格式為 （序號、X坐標(biāo)、Y坐標(biāo)、需求量），其中序號0表示配送中心，1到11表示客戶點(diǎn)，需求量（單位：噸） 為各點(diǎn)需要配送貨物重量，各點(diǎn)具體信息如下： （0,50,50,0），（1,48,85,0.2），（2,45,70,0.3）， （3,35,75,0.2）， （4,33,58,0.15）， （5,39,40,0.2）， （6,45,30,0.1）， （7,58,34,0.2）， （8,70,30,0.25），（9,70,56,0.2），（10,70,66,0.2），（11,75,88,0.15）。根據(jù)各點(diǎn)的坐標(biāo)使用Excel計(jì)算各點(diǎn)之間的距離（歐式距離），獲得距離矩陣表1：

3.1 經(jīng)典VRP問題分析

在經(jīng)典VRP問題當(dāng)中，所有的客戶點(diǎn)需要配送中心的車輛進(jìn)行服務(wù)，這樣就需要擁有足夠的車輛來滿足配送任務(wù)。但是，由于配送任務(wù)的需求是不確定的，有時(shí)高有時(shí)低，配送中心要擁有的運(yùn)力高于平均運(yùn)送需求，這樣就會(huì)造成運(yùn)力浪費(fèi)，間接提高配送成本。在本例當(dāng)中，配送中心需要有3輛車才能完成服務(wù)所有客戶點(diǎn)的任務(wù)。

表1 各點(diǎn)距離矩陣

圖1 經(jīng)典VRP問題配送路線

通過使用掃描法得到如圖1的配送路線圖，車輛1的路線為：0→1→2→3→4→0；車輛2的線路為：0→5→6→7→8→9→0；車輛 3 的線路為：0→10→11→0。

根據(jù)表2的距離矩陣和圖1的配送線路，得到車輛1行駛里程mileage1=d01+d12+d23+d34+d40=97.5km。車輛2行駛里程mileage2=d05+d56+d67+d78+d89+d90=99.7km，車輛3行駛里程mileage3=d0,10+d10,11+d11,0=93.7km。根據(jù)得到數(shù)據(jù)計(jì)算每條路線的配送成本，得到經(jīng)典VRP問題路徑及成本如表2所示：

表2 經(jīng)典VRP問題路徑及成本

3.2 VRPOD問題分析

在眾包模式下，配送中心不再需要維持3輛配送車，在這里設(shè)定為2輛，其配送路線如圖2所示。此時(shí)，總共需要4輛車才能完成派送任務(wù)，其中車輛1和2為自有車輛，車輛3和4為眾包車輛。

圖2 VRPOD問題配送路徑

根據(jù)表3的距離矩陣和圖2的配送路徑，車輛1和車輛2行駛里程不變?nèi)匀环謩e為97.5和99.7km，車輛3的總路程d0,10=25.6km，車輛4的總里程d0,11=45.5km，計(jì)算得到總配送成本為 （968+355.5ξ）元。

表3 配送路線及成本

為了檢驗(yàn)ξ值對成本節(jié)約的影響，計(jì)算不同參數(shù)情況下，節(jié)約成本及節(jié)約率大小，如表4。在本例中ξ值越小，成本節(jié)約的越多。但是ξ值越低，司機(jī)參與眾包的意愿會(huì)隨著降低，影響他們的積極性，所以ξ值不是越小越好。本例當(dāng)中ξ的取值范圍在1到1.3之間。為了維護(hù)雙方的利益，1.2是一個(gè)比較合適的值。當(dāng)然，在實(shí)際情況下，不僅存在直接配送成本，還有間接配送成本，如車輛購置、維護(hù)和人員工資支付等。在眾包模式下，由于需要維持的車輛和司機(jī)更少，間接成本更低，物流企業(yè)可以承受的ξ值可以更高。

表4 效益表

4 結(jié)束語

本文在經(jīng)典VRP問題的基礎(chǔ)上引入了物流眾包，同時(shí)建立了VRPOD的線性規(guī)劃模型，運(yùn)用了掃描法求解了VRP問題下和VRPOD問題下的解，通過兩種問題解的對比，從而驗(yàn)證在物流“最后一公里”配送中引入眾包模式能在一定程度上降低終端配送成本。