基于眾包配送模式的超市訂單分配與路徑規劃研究

李四蘭 郭偉鈺 宋孟珂

摘? 要：隨著互聯網的快速發展，O2O商業模式已經成為一種潮流。超市作為連接廣大消費者和生產者的終端場所，其在轉型升級的過程中也采用了全新的O2O商業模式。由于超市末端配送服務具有即時性，超市配送員大多數屬于社會閑散人員，并沒有接受過專業的培訓。導致在配送過程中發生無人接單、配送超時、顧客滿意度低等問題。造成這些問題的主要原因是眾包配送平臺訂單分配模式缺乏科學的并單指導，文章將杭州市B連鎖超市的151個訂單用改進的K-means算法進行聚類，再將聚類完成的訂單用蟻群算法進行路徑優化。最后驗證了所使用的方法在解決超市訂單分配和路徑優化問題方面的可行性和有效性。

關鍵詞：眾包配送;車輛路徑優化;K-means算法;蟻群算法

中圖分類號：F252.14? ? 文獻標識碼：A

Abstract： With the rapid development of internet， O2O business model has become a trend. As a terminal place connecting consumers and producers， supermarkets also adopt a new O2O business model in the process of transformation and upgrading. Due to the immediacy of the terminal distribution service in supermarkets， most of the delivery workers in supermarkets belong to the social idle people and have not received professional training. In the process of distribution， there are many problems， such as no order， delivery overtime， low customer satisfaction and so on. The main reason for these problems is that the order allocation mode of crowdsourcing distribution platform lacks scientific guidance. In this paper， 151 orders of B chain supermarket in Hangzhou are clustered by improved K-means algorithm， and then the clustered orders are optimized by ant colony algorithm. Finally， the feasibility and effectiveness of the method in solving the supermarket order allocation and path optimization problems are verified.

Key words： crowdsourcing distribution; vehicle routing optimization; K-means algorithm; ant colony algorithm

0? 引? 言

外賣眾包配送是眾包外賣平臺以眾包的形式從社會中獲取閑散的資源（眾包配送員），再將眾包外賣平臺獲取的外賣配送任務交由眾包配送員，最終通過眾包配送員完成外賣配送服務。在傳統配送模式下，要求車輛統一從配送中心出發，遍歷所有顧客需求點后仍需返回配送中心，其目標函數多為運輸成本較低、運輸距離較短等。而眾包配送作為一種新穎的第三方配送方式，在配送完成后無需返回配送中心，可直接在眾包平臺軟件點擊結束即可完成本次配送。具有更大的自主性和選擇權。

國外相比國內較早的開始研究眾包物流和路徑規劃問題，Klumpp（2017）[1]通過分析眾包物流商業模式，結合具體實際情況，提出了如何有效的評價眾包物流服務質量。LiX和LiY[2]討論了眾包外包O2O平臺的訂單分配和配送路徑優化的組合問題，但未考慮到眾包配送人員手動獲取訂單的實際情形。同時，國內學者也對該問題進行了研究。鄧娜、張建軍等（2018）[3]基于外賣訂單目前配送模式的缺點，提出了一種基于聚類分析和TSP路徑優化訂單集指派模式，按照取餐點、送餐點、需求量和訂單送達時間對訂單進行聚類分析，并規劃最優配送路線，驗證了提出的方法可以有效的加快訂單處理效率，紀漢霖等（2016）[4]分析了當前生鮮電商行業的發展現狀和存在問題，介紹了眾包配送在生鮮電商行業中的應用，以及眾包配送在生鮮電商行業中的優勢和缺陷，最后提出眾包信息化和完善眾包誠信制度建設的對策建議。

通過對眾包配送路徑優化文章的研究和分析，可以看出眾包模式在配送過程中還存在著諸多問題。針對連鎖超市末端配送范圍是三公里之內。本文采用改進的K-means聚類算法以各個消費者的地理位置坐標為標準對配送訂單進行聚類分析，使得同一類中消費者位置較近，每位騎手只能派送某一聚類范圍內的訂單。得到聚類結果后建立帶時間窗和車輛裝載量約束的配送路徑優化模型，以顧客滿意度最大為目標函數。最后用改進的蟻群算法對數學模型進行求解，得到多條配送行駛路線。

1? 眾包模式下車輛的路徑優化問題

1.1? 問題描述

本文所研究的是在眾包配送模式下連鎖超市如何高效配送貨物使得顧客滿意度最大化。主要可以描述為一個配送中心O向n個消費者進行訂單配送，V=0，1，2，3，…，n表示各個節點的集合，N=1，2，3，…，n表示各個消費者需求點的集合，O表示超市配送中心。每個消費者的需求量為qi=1，2，3，…，n。每一輛配送車運輸貨物的最大載貨量是相同的，均為Q，且maxq≤Q。

1.2? 模型假設

（1）配送中心的位置已知，各個需求點的位置以及需求量已知。

（2）配送員使用電動車作為配送車輛，所有配送車輛的類型一致，即配送車輛的載重量、油耗、行駛速度均相等，單位運輸成本為定值。

（3）眾包模式下，配送車輛由眾包配送員自己提供，所以配送成本不包括車輛的啟動成本和運輸成本，僅包括眾包快遞員的報酬。

（4）每輛配送車均從配送中心出發，車輛完成配送任務后不需要返回商家。

（5）每輛配送車的載貨量不能超過其最大載重量。

（6）眾包配送員將商品送達需求點后會產生一定的服務時間，且為定值。

（7）所有眾包配送員均能完成配送任務，即不存在接單后不配送的情況。

（8）配送員在配送過程中不考慮天氣、交通狀況等外界意外事件的發生。

（9）眾包配送員每配送一單報酬為一個固定值。

1.3? 符號說明

1.4? 構建模型

1.4.1? 目標函數

maxf=xz-cy? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

其中：

c=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

1.4.2? 約束條件

qy≤Q， k∈S? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

y=1， i∈N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

t=t+t+? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

x=s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

ET≤t≤LT， i∈N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

n=n? ? 0≤n≤n? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

x∈0，1， ？坌i∈N， ？坌j∈N， ？坌k∈S? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

y∈0，1， ？坌i∈N， ？坌k∈S? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（10）

公式（1）為目標函數，第一項表示眾包配送人員配送報酬，第二項表示每個需求點配送完成后，超出客戶要求的時間窗的懲罰成本。整個目標為眾包配送人員的配送報酬達到最大，即顧客的滿意度最大。公式（2）為眾包配送員在不同時間內到達，懲罰成本的分段函數。公式（3）為載重約束，表示每一輛配送車的載重量不能超過其最大容量。公式（4）表示同一個需求點只能由一輛車提供配送服務。公式（5）表示連續服務兩個消費者的時間遞推關系。公式（6）表示所有的配送車輛均從連鎖超市出發。公式（7）表示各個需求點只在一定時間段內接受服務。公式（8）表示每個需求點都必須得到配送服務。公式（9）、公式（10）為0-1型變量。公式（9）表示第k輛車是否從需求點i服務到需求點j，若服務值為1，否則為0。公式（10）表示第k輛車是否服務于第i個需求點，若服務值為1，否則為0。

2? 基于改進K-means聚類算法的眾包配送區域劃分

由于K-means算法無法事先知道需要的聚類數，初始聚類點的選擇是隨機產生的。隨機產生的初始聚類點可能會得到不同的聚類結果。本文先使用AP算法得到最佳的聚類數量，然后用K-means算法根據AP算法得到的聚類數量進行聚類，并用輪廓系數評價聚類結果的優劣，具體步驟如下：

步驟1：將某時間段內的訂單利用百度地圖拾取坐標的方式得到所有訂單分布的經緯度;

步驟2：利用AP算法對需求點進行聚類，得到最佳聚類數量K;

步驟3：設置聚類數量為K，并隨機選擇K個聚類中心。用K-means算法計算所有樣本點到聚類中心的歐氏距離，選取距離最小的聚類中心并將點規劃到其簇中;

步驟4：所有需求點分配完畢后，重新計算聚類中心，比較與前一次的聚類中心是否相同，若相同，則停止迭代輸出聚類結果;若不同，則返回步驟3;

步驟5：比較AP算法和改進K-means算法的聚類結果，并通過輪廓系數得到最佳的聚類結果。

3? 眾包配送路徑優化模型算法設計

3.1? 路徑轉移規則

當螞蟻完全依賴隨機概率規則訪問下一個需求點，由公式（11）決定：

p=? ? ? ? ? ? ? ? ? ? ? ?（11）

其中：q為隨機產生的數，取值在0到1之間。τ是路徑i，j上的信息素濃度，η是路徑i，j上的啟發式因子，Ω為需要訪問的需求點的集合，ω和ω分別表示與信息量和通往下一需求點的時間窗口寬度和到達下一需求點的時間相關的權重系數。ω和ω取值均在0和1之間，且滿足ω+ω=1。

3.2? 信息素更新規則

本文采用全局更新信息素的方法，其更新規則如下：

τt+1=1-p·τt+pΔτt? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12）

Δτt=Δτ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （13）

信息素濃度τt+1等于t時刻的信息素濃度的殘留值與t到t+1時刻之間的信息素Δτ為相關路徑ij上的信息素增量。

4? 案例分析——以杭州市B連鎖超市為例

本文選取杭州市B連鎖超市11：00～12：00內的151條訂單數據來驗證本文提出數學模型和方法的有效性和可行性。首先利用MATLAB軟件繪制出B連鎖超市在時間段11：00～12：00內需要配送151個需求點訂單的經緯度散點圖，如圖1所示。從圖1中可以看出消費者的地理位置分布比較分散，且距離遠近不同，通過隨機分配訂單是不合理的，需要將訂單聚類后再進行分配，保證配送資源的合理利用。

針對超市和顧客的地理位置分布，首先使用AP算法對訂單需求的經緯度坐標進行聚類分析，由于AP算法不需要預先規定聚類數，所以先運用AP算法聚類得到151個需求點的聚類數量K值，得到聚類數量k值為4，如圖2所示。再使用

K-means算法進行聚類，得到的聚類結果如圖3所示。

改進的K-means聚類算法得到的需求點序號所屬的聚類號以及各聚類序號需求點的數量如表1所示：

為了檢驗用AP算法改進K-means算法的有效性，本文引用輪廓系數作為評價兩者相結合的聚類算法的標準。通過比較用AP算法改進K-means算法與AP和K-means算法單獨使用的輪廓系數來驗證所提出的有效性，指標結果如表2所示。

通過表2的輪廓系數可以看出用AP算法改進K-means算法的聚類方式對超市訂單的顧客需求點進行聚類的方法較好，驗證了本文提出的方法的有效性。

基于上文的聚類結果，選取聚類序號為1的顧客需求點進行路徑優化。利用Excel軟件進行高斯克—克呂格投影換算，將經緯度坐標換算成高斯平面直角坐標。例如配送超市0的經緯度為（120.129254，30.294442），換算之后得到的平面直角坐標為（5 123，5 668）。建立坐標系，并用Matlab繪制散點圖，如圖4所示。

參數設置：迭代次數=200、螞蟻個數=43、信息素重要程度=1、啟發式因子重要程度=3、信息素揮發因子=0.85、更新信息素濃度常數=5。

眾包模式下假設配送員車輛最大載重量為80kg，眾包配送每單報酬5元，車輛平均行駛速度15km/h，每個顧客的服務時間均為5分鐘，所有顧客需求點的時間窗均為11：00～12：00，超出時間窗的懲罰成本每單10元。眾包配送路徑優化模型求解結果如表3所示：

傳統模式下車載量、快遞員報酬、車輛行駛速度、顧客服務時間、以及需求點的時間窗都相同的情況下，每輛配送車的啟動成本為50元/輛。單位距離的行駛成本為10元/km，用蟻群算法分別計算眾包模式和傳統模式的路徑優化如圖5、圖6所示。兩種配送模式比較如表4所示。

由于眾包配送模式下配送完成后不用返回配送中心，相比于傳統配送模式車輛配送完成后返回配送中心。眾包配送減少了配送里程配送路徑不再是一個閉環。從表4可以看出，眾包配送比傳統配送車輛行駛里程少5 650m。同時眾包配送不考慮車輛成本，對連鎖超市來說成本只有眾包配送員的工資和超時配送的懲罰成本。在規定時間內送達不會產生懲罰成本。而對于傳統的配送模式，連鎖超市的成本C包括車輛的啟動成本c、車輛的運輸成本c以及配送員的工資c三部分組成。配送成本相比眾包配送增加了，為了保證顧客的滿意度。兩種模式均在規定的時間里完成配送，但是成本相差很大。

5? 總結與展望

本文以眾包外賣配送為研究對象，從眾包配送平臺的角度出發，聚焦于解決訂單分配和路徑優化問題。以杭州市B連鎖超市為例，考慮顧客要求的時間窗，配送車輛的載重量等因素，將配送所有訂單的配送路線最短、配送人員薪酬最高、顧客滿意度最大、懲罰成本最低作為目標對訂單先進行聚類。對聚成一類的需求點進行路徑優化，并與傳統配送模式相比較得出眾包配送在路徑距離、成本等方面都優于傳統配送模式。眾包配送多為社會閑散人員，在一定程度上增加了我國的就業率。車輛配送路徑優化模型中假設車輛都是同一類型且在配送中速度是均勻的，而現實中眾包配送員的配送車輛可能存在各種各樣的差異，配送途中的速度情況都有一定的不確定性，很難滿足模型中提出的假設條件。在以后的研究中應提出更加符合實際情況的模型。其次，眾包配送人員專業性低于全職配送員，所以目前只能考慮一些小額訂單，未來可以考慮眾包配送員的優選問題，在眾包配送過程中選擇服務質量較好的配送騎手。

參考文獻：

[1]? Klumpp M. Crowdsourcing in Logistics： An Evaluation Scheme[M]. Bermen： Springer International Publishing， 2017：401-411.

[2] LiX， LiY. Crowd sourcing Takeout Distribution Route Optimization Considering Pickup and Delivery[C] // 第30屆中國控制與決策會議，2018.

[3] 鄧娜，張建軍. O20外賣訂單配送任務分配模式研究[J]. 上海管理科學，2018，40（1）：63-66.

[4] 紀漢霖，周金華，張深. 生鮮電商行業眾包模式研究[J]. 物流工程與管理，2016（1）：93-95.

[5] 陳萍，李航. 基于時間滿意度的O20外賣配送路徑優化問題研究[C] // 中國管理科學學術年會，2016.

[6] 石榮麗. 分享經濟視閾下的眾包物流信息服務平臺模型構建[J]. 華南理工大學學報（社會科學版），2017，19（2）：15-21.

[7] 馬冠群. 基于眾包物流模式的同時送取車輛路徑問題研究[D]. 濟南：山東大學（碩士學位論文），2019.

[8] 程月嬌，施炯，黃彬. 眾包物流環境下訂單合并及配送路徑優化方法研究[J]. 浙江萬里學院學報，2017，30（4）：27-33.

[9] 張曉雯，盛宇華. 共享經濟背景下生鮮電商“最后一公里”眾包配送問題研究[J]. 價格月刊，2017（10）：66-69.

[10] 范青. 基于改進蟻群算法的物流配送路徑優化及應用研究[D]. 西安：西安建筑科技大學（碩士學位論文），2014.

[11] 蔣麗，王靜，梁昌勇，等. 基于改進蟻群算法的眾包配送路徑研究[J]. 計算機工程與應用，2019，55（8）：250-255.

[12]? Miranda D M. The vehicle routing problem with hard time windows and stochastic travel and service time[M]. Pergamon Press， Inc， 2016.

[13]? Kang Y， Lee S， Chung B D. Learning-based logistics planning and scheduling for Crowdsourcing parcel delivery[J]. Computers & Industrial Engineering， 2019，132（6）：271-279.

[14]? Zhang D， Cai S， Ye F， et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences， 2017，394：167-182.