眾包車(chē)輛路徑問(wèn)題

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

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

0 引 言

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

1 問(wèn)題描述及算法介紹

1.1 問(wèn)題描述

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

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

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

1.2 算法介紹

為了驗(yàn)證模型是可行的，使用掃描法求解VRPOD問(wèn)題并將其與在VRP問(wèn)題下的解進(jìn)行比較。掃描法是一種傳統(tǒng)的啟發(fā)式求解算法，掃描法最早由Gillett和Miller提出。基本思想是：以配送中心為原點(diǎn)建立極坐標(biāo)表示各客戶點(diǎn)的位置。給每個(gè)客戶點(diǎn)編號(hào)，客戶點(diǎn)的角度越大編號(hào)越大。從配送點(diǎn)沿著任意方向畫(huà)一條直線，按照順時(shí)針或者逆時(shí)針?lè)较颍芽蛻酎c(diǎn)按從小到大的順序排入車(chē)輛配送路線中，路線安排要滿足車(chē)輛負(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；車(chē)輛集合V包含兩部分：自有車(chē)輛集合S，每輛車(chē)的最大載荷為Q，配送到成本為c；雇傭車(chē)輛集合K，為了將問(wèn)題簡(jiǎn)化，假定雇傭車(chē)輛配額獲得的報(bào)酬與其目的地?zé)o關(guān)，只與配送中心到客戶點(diǎn)的距離doi有關(guān)，并且對(duì)于同一個(gè)配送點(diǎn)，所有司機(jī)獲得的報(bào)酬是一樣的。這種做法符合實(shí)際情況，因?yàn)椋蛡蜍?chē)輛的公司并不會(huì)關(guān)心雇傭車(chē)輛的目的地。實(shí)際上，司機(jī)接受配送的意愿受配送點(diǎn)到目的地的距離的影響，越近意愿會(huì)越高，但是這種情況下，問(wèn)題將更加復(fù)雜。作為對(duì)雇傭司機(jī)車(chē)的補(bǔ)償，提高配送意愿，司機(jī)獲得的報(bào)酬p=ξc0k，同時(shí)ξ＞1。假設(shè)眾包配送成本與車(chē)輛初始位置無(wú)關(guān)，只與配送點(diǎn)到目的地的距離有關(guān)，且車(chē)輛負(fù)載滿足單個(gè)客戶點(diǎn)的需求。建立如下所示的線性規(guī)劃模型：

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

3 算例分析

設(shè)定算例各點(diǎn)的位置信息格式為 （序號(hào)、X坐標(biāo)、Y坐標(biāo)、需求量），其中序號(hà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問(wèn)題分析

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

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

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

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

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

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

3.2 VRPOD問(wèn)題分析

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

圖2 VRPOD問(wèn)題配送路徑

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

表3 配送路線及成本

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

表4 效益表

4 結(jié)束語(yǔ)

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