眾包車輛路徑問題

萬勇平 （江西財經大學，江西 南昌 330013）

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

0 引 言

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

1 問題描述及算法介紹

1.1 問題描述

車輛路線問題（Vehicle Routing Problem,VRP）由Dantzig和Ramser[2]在1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束條件（如配送供需、配送時間、車輛負載、車輛行駛里程等）下，達到如路程最短、成本最小、耗費時間最少等規劃目標。由于VRP具有廣泛的現實運用和巨大的經濟價值，VRP問題自1959年被提出以來，該問題一直是網絡優化問題中最基本的問題之一，受到國內外學者的長期關注。

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

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

1.2 算法介紹

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

2 建立數學模型

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

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

3 算例分析

設定算例各點的位置信息格式為 （序號、X坐標、Y坐標、需求量），其中序號0表示配送中心，1到11表示客戶點，需求量（單位：噸） 為各點需要配送貨物重量，各點具體信息如下： （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）。根據各點的坐標使用Excel計算各點之間的距離（歐式距離），獲得距離矩陣表1：

3.1 經典VRP問題分析

在經典VRP問題當中，所有的客戶點需要配送中心的車輛進行服務，這樣就需要擁有足夠的車輛來滿足配送任務。但是，由于配送任務的需求是不確定的，有時高有時低，配送中心要擁有的運力高于平均運送需求，這樣就會造成運力浪費，間接提高配送成本。在本例當中，配送中心需要有3輛車才能完成服務所有客戶點的任務。

表1 各點距離矩陣

圖1 經典VRP問題配送路線

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

根據表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。根據得到數據計算每條路線的配送成本，得到經典VRP問題路徑及成本如表2所示：

表2 經典VRP問題路徑及成本

3.2 VRPOD問題分析

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

圖2 VRPOD問題配送路徑

根據表3的距離矩陣和圖2的配送路徑，車輛1和車輛2行駛里程不變仍然分別為97.5和99.7km，車輛3的總路程d0,10=25.6km，車輛4的總里程d0,11=45.5km，計算得到總配送成本為 （968+355.5ξ）元。

表3 配送路線及成本

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

表4 效益表

4 結束語

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