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

李四蘭 郭偉鈺 宋孟珂

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

關(guān)鍵詞：眾包配送;車輛路徑優(yōu)化;K-means算法;蟻群算法

中圖分類號(hào)：F252.14? ? 文獻(xiàn)標(biāo)識(shí)碼：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? 引? 言

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

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

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

1? 眾包模式下車輛的路徑優(yōu)化問題

1.1? 問題描述

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

1.2? 模型假設(shè)

（1）配送中心的位置已知，各個(gè)需求點(diǎn)的位置以及需求量已知。

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

（3）眾包模式下，配送車輛由眾包配送員自己提供，所以配送成本不包括車輛的啟動(dòng)成本和運(yùn)輸成本，僅包括眾包快遞員的報(bào)酬。

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

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

（6）眾包配送員將商品送達(dá)需求點(diǎn)后會(huì)產(chǎn)生一定的服務(wù)時(shí)間，且為定值。

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

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

（9）眾包配送員每配送一單報(bào)酬為一個(gè)固定值。

1.3? 符號(hào)說明

1.4? 構(gòu)建模型

1.4.1? 目標(biāo)函數(shù)

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

2? 基于改進(jìn)K-means聚類算法的眾包配送區(qū)域劃分

由于K-means算法無法事先知道需要的聚類數(shù)，初始聚類點(diǎn)的選擇是隨機(jī)產(chǎn)生的。隨機(jī)產(chǎn)生的初始聚類點(diǎn)可能會(huì)得到不同的聚類結(jié)果。本文先使用AP算法得到最佳的聚類數(shù)量，然后用K-means算法根據(jù)AP算法得到的聚類數(shù)量進(jìn)行聚類，并用輪廓系數(shù)評(píng)價(jià)聚類結(jié)果的優(yōu)劣，具體步驟如下：

步驟1：將某時(shí)間段內(nèi)的訂單利用百度地圖拾取坐標(biāo)的方式得到所有訂單分布的經(jīng)緯度;

步驟2：利用AP算法對(duì)需求點(diǎn)進(jìn)行聚類，得到最佳聚類數(shù)量K;

步驟3：設(shè)置聚類數(shù)量為K，并隨機(jī)選擇K個(gè)聚類中心。用K-means算法計(jì)算所有樣本點(diǎn)到聚類中心的歐氏距離，選取距離最小的聚類中心并將點(diǎn)規(guī)劃到其簇中;

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

步驟5：比較AP算法和改進(jìn)K-means算法的聚類結(jié)果，并通過輪廓系數(shù)得到最佳的聚類結(jié)果。

3? 眾包配送路徑優(yōu)化模型算法設(shè)計(jì)

3.1? 路徑轉(zhuǎn)移規(guī)則

當(dāng)螞蟻完全依賴隨機(jī)概率規(guī)則訪問下一個(gè)需求點(diǎn)，由公式（11）決定：

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

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

3.2? 信息素更新規(guī)則

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

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

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

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

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

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

針對(duì)超市和顧客的地理位置分布，首先使用AP算法對(duì)訂單需求的經(jīng)緯度坐標(biāo)進(jìn)行聚類分析，由于AP算法不需要預(yù)先規(guī)定聚類數(shù)，所以先運(yùn)用AP算法聚類得到151個(gè)需求點(diǎn)的聚類數(shù)量K值，得到聚類數(shù)量k值為4，如圖2所示。再使用

K-means算法進(jìn)行聚類，得到的聚類結(jié)果如圖3所示。

改進(jìn)的K-means聚類算法得到的需求點(diǎn)序號(hào)所屬的聚類號(hào)以及各聚類序號(hào)需求點(diǎn)的數(shù)量如表1所示：

為了檢驗(yàn)用AP算法改進(jìn)K-means算法的有效性，本文引用輪廓系數(shù)作為評(píng)價(jià)兩者相結(jié)合的聚類算法的標(biāo)準(zhǔn)。通過比較用AP算法改進(jìn)K-means算法與AP和K-means算法單獨(dú)使用的輪廓系數(shù)來驗(yàn)證所提出的有效性，指標(biāo)結(jié)果如表2所示。

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

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

參數(shù)設(shè)置：迭代次數(shù)=200、螞蟻個(gè)數(shù)=43、信息素重要程度=1、啟發(fā)式因子重要程度=3、信息素?fù)]發(fā)因子=0.85、更新信息素濃度常數(shù)=5。

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

傳統(tǒng)模式下車載量、快遞員報(bào)酬、車輛行駛速度、顧客服務(wù)時(shí)間、以及需求點(diǎn)的時(shí)間窗都相同的情況下，每輛配送車的啟動(dòng)成本為50元/輛。單位距離的行駛成本為10元/km，用蟻群算法分別計(jì)算眾包模式和傳統(tǒng)模式的路徑優(yōu)化如圖5、圖6所示。兩種配送模式比較如表4所示。

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

5? 總結(jié)與展望

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

參考文獻(xiàn)：

[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屆中國控制與決策會(huì)議，2018.

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

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

[5] 陳萍，李航. 基于時(shí)間滿意度的O20外賣配送路徑優(yōu)化問題研究[C] // 中國管理科學(xué)學(xué)術(shù)年會(huì)，2016.

[6] 石榮麗. 分享經(jīng)濟(jì)視閾下的眾包物流信息服務(wù)平臺(tái)模型構(gòu)建[J]. 華南理工大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2017，19（2）：15-21.

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

[8] 程月嬌，施炯，黃彬. 眾包物流環(huán)境下訂單合并及配送路徑優(yōu)化方法研究[J]. 浙江萬里學(xué)院學(xué)報(bào)，2017，30（4）：27-33.

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

[10] 范青. 基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化及應(yīng)用研究[D]. 西安：西安建筑科技大學(xué)（碩士學(xué)位論文），2014.

[11] 蔣麗，王靜，梁昌勇，等. 基于改進(jìn)蟻群算法的眾包配送路徑研究[J]. 計(jì)算機(jī)工程與應(yīng)用，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.