發布時間：所屬分類：計算機職稱論文瀏覽：1次
摘 要： 摘要： 眾包配送平臺通過集結社會閑散運力為應對激增的外賣實時配送需求提供了新的思路，其核心的訂單分配與路徑優化問題作為影響其配送成本與效率的關鍵問題受到關注。針對該問題中訂單的實時性、時效性、配送員的自由性等特征，建立以平均每單配送距離以及平均每單完
摘要： 眾包配送平臺通過集結社會閑散運力為應對激增的外賣實時配送需求提供了新的思路，其核心的訂單分配與路徑優化問題作為影響其配送成本與效率的關鍵問題受到關注。針對該問題中訂單的實時性、時效性、配送員的自由性等特征，建立以平均每單配送距離以及平均每單完成時間最小為目標的實時訂單分配與路徑優化模型。分別設計了貪婪策略、最小差值策略用于求解該問題。最后通過大量的數值仿真研究驗證了兩個策略的有效性，發現最小差值策略所得的平均每單配送距離更短，而貪婪策略所得的平均每單完成時間更短。進一步研究了兩種策略在不同配送員容量限制、配送員數量、訂單密度等參數變化時的適用性，需要控制成本宜采用最小差值策略，追求配送效率宜采取貪婪策略，研究結果可為眾包配送平臺的訂單分配與路徑優化策略的選擇提供決策支持。
關鍵字：實時配送;訂單分配;路徑優化;眾包平臺;外賣
1 引言
近年來，中國外賣市場規模激增，2019 年的外賣用戶已超過 4 億人，對末端配送提出了嚴峻的考驗。在最后 3 公里的配送能力與服務質量成為制約外賣市場發展瓶頸之際，美團、京東眾包等眾包配送平臺迅速崛起，通過集結社會閑散運力，為解決外賣實時配送難題提供了一條新的途徑。
顧客在美團、餓了么等眾包外賣平臺上下單，商家通過平臺接受訂單，同時商家通過平臺發布配送需求訂單信息，包括取送貨地點、貨物種類數量和預計配送時間等，平臺通過訂單分配的方式或讓配送員搶單的方式將配送訂單分發給相應的配送員，每個配送員具有車容量限制，且其工作時間與開始工作的地方具有絕對的自由。每個配送員接受相應的配送訂單后需要到商家取貨后送達至顧客以完成配送訂單。在該過程中，由于配送訂單的發布具有實時性，每個訂單都要求在盡可能短的時間內完成，即具有很強的時效性，且每個訂單的取送貨地點一一匹配。同時考慮到高峰期配送訂單數量龐大、地理位置分散、配送員具有動態性且隨機分布等特點，要尋求配送成本低、顧客滿意度高的訂單分配與路徑規劃方案具有極大的挑戰性。本文針對基于眾包平臺的外賣實時配送問題的上述特征，研究以降低配送成本、提高配送時效為目的的實時訂單分配與路徑優化科學問題。
與基于眾包平臺的外賣實時配送問題相關的文獻包括眾包配送服務問題和帶取送貨的動態車輛路徑問題(Dynamic Vehicle Routing Problem with Pickup and Delivery)的相關研究。
針對眾包配送中的服務組合和路徑優化問題，南飛雁[1]研究了眾包配送中的服務組合問題，采取 k 聚類算法先組合訂單后分配，有效降低配送人員即時搶單導致的訂單人均分配不均、超時等問題。李占強[2]研究了眾包配送中服務匹配與優選問題，建立匹配機制和灰色關聯度服務評價的模型分別優化匹配機制和服務質量。針對動態取送貨車輛路徑問題，程月嬌等[3]考慮靜態和動態的接單模式，設計一種基于用戶出行信息的訂單匹配方法，并用蟻群算法求解。張力婭等[4]以顧客滿意度和配送成本為目標函數，建立了考慮客戶優先級的、帶時間窗的、動態的、多車場取送貨車輛路徑模型，用改進的迭代局部搜索算法求解。張旭梅等 [5]以隨機動態環境下運輸過程中的裝卸混合問題為研究對象，根據隨機動態裝卸混合問題的實際應用分別將車輛數由單車輛推廣至多車輛、目標函數由單目標推廣至多目標、“需求服從均勻分布”的假設條件放寬為“需求服從一般分布”進行討論，針對各情形提出了相應的求解策略，對各求解策略進行了漸近性分析，并對其求解效果進行了仿真。張玉州等[6]以外賣配送服務總延誤時間最短為目標，設計了一種基于滾動時域控制的外賣配送問題模型，用最近鄰域算法求解，并以實際案例對比 FCFS 和 NN 算法。李桃迎等[7]以外賣配送成本增量總和為目標函數，并考慮了隨機參數對計算復雜度的影響，用 R 語言測試模型和算法。寧濤等[8]以最小化成本和最大化客戶滿意度為目標，把動態車輛路徑問題轉換為靜態車輛路徑問題，采用兩階段建模，用改進的量子蟻群算法求解。魏瑛琦[9]針對動態車輛路徑問題，采用兩階段建模方式，將動態車輛路徑問題轉化為靜態車輛路徑問題，采用時間片段原則處理動態事件，用改進的量子蟻群算法求解。吳騰宇等[10]研究了帶有取送貨的在線旅行商問題 (Traveling Salesman Problem, TSP)，針對需求點在不同網絡上的情形分別設計了 TAIB 算法和 IGNORE 算法求解。Azi et al[11]針對多交付路線的動態車輛路徑問題，設計一個自適應的大型鄰域搜索啟發式算法求解，在動態情況下將考慮發生未來請求的多個可能場景，以決定是否有機會將新請求包含到當前解決方案中，當車輛離開倉庫時配送路線將被關閉。 Mitrovic-Minic et al [12]研究未來請求不能隨機建模或預測的動態 PDPTW，分配新的請求時，最好考慮一項決定對短期和長期的影響，描述了基于雙視界的動態 PDPTW 啟發式算法。 Vonolfen et al [13]考慮在問題的動態變量中，不是所有的信息都是預先可以得到的，而是在規劃過程中被揭示出來的，提出一種基于進化計算和模擬模型的直接策略搜索方法，針對不同的問題特征設計專門化等待策略。Branke et al [14]考慮一個動態車輛路徑問題，讓車輛在旅行期間在適當的位置等待以最大限度地提高額外客戶被整合到其他固定旅游路線中的可能性，得到一輛車和兩輛車的最佳等待策略。綜上所述，在現有文獻中，對一一匹配嚴格的動態取送貨車輛路徑問題的研究中針對模型和算法的文獻較少，本文研究內容與以上文獻的最大區別在于配送員的位置是動態隨機分布的，本文研究的是基于眾包外賣平臺具有實時取送貨、配送員隨機分布等特點的現實問題。
綜上所述，通過分析眾包外賣即時配送的特點，以平均每單配送距離最小和平均每單完成時間最小為目標，構建基于眾包平臺的外賣實時配送訂單分配和路徑優化模型，針對不同應用場景，分別設計貪婪策略、最小差值策略用于求解該模型，旨在降低物流配送成本，提高配送效率。考慮了配送員數量、車容量、訂單密度等參數對策略穩定性的影響，通過數值仿真實驗驗證模型和算法的有效性，并對設計的算法的優劣進行評價。
2 問題描述與建模
給定一個道路交通網絡圖𝐺 = (𝑉, 𝐸)，其中頂點集合𝑉 = *𝑣1, 𝑣2, … , 𝑣𝑛1 +，邊集合𝐸 = *𝑒1, 𝑒2, … , 𝑒𝑛2+，所有需要服務的訂單均在網絡圖𝐺中產生，𝑙(𝑣𝑖 , 𝑣𝑗)表示網絡圖中𝑣𝑖與𝑣𝑗之間的距離，所有訂單是實時產生的，共有𝑛個訂單，訂單序列表示為𝜎 = *𝑂1,𝑂2, … ,𝑂𝑛+，將產生的訂單表示為𝑂𝑖 = (𝑟𝑖 , 𝑢𝑖 , 𝑑𝑖)，其中𝑟𝑖表示訂單需求的釋放時間，𝑢𝑖 ∈ 𝑉表示訂單的取貨點位置，𝑑𝑖 ∈ 𝑉表示訂單的收貨點位置，𝑖 ∈ 𝐼 = *1,2, … , 𝑛+，考慮多個配送員進行配送服務，車容量均為𝐶，即每個配送員同時最多能為𝐶個訂單服務，在外賣配送過程中，商家通過平臺不斷接受訂單，平臺會繼續給配送員分配訂單，要研究的問題是如何實時分配訂單給對應的配送員，如何為配送員進行路徑規劃，使得平均每單的配送距離最小和平均每單完成時間最小。
為了研究的方便提出如下 4 條假設：假設 1：在網絡圖中每個點既可以是取貨點又可以是送貨點，但同一個點不能是一個訂單的取貨點和送貨點;假設 2：當每出現一個新訂單時，配送車輛需要到取貨點取貨然后送至送貨點以完成該訂單，不考慮配送員在該服務點的等待時間;假設 3：允許車輛在其初始位置或任何取、送貨位置等待，配送完成后不必返回原起始位置;假設 4：配送員均以速度𝑣行進。
由于動態實時取送貨車輛問題(Dynamic real-time pickup delivery vehicle problem， DRVRP)是 NP—hard 問題，運用精確算法求解在時間性能和求解規模等方面均存在局限性，考慮到該模型中的訂單釋放時間是不能提前已知的，所以無法設計最優化算法，故設計插入式啟發式算法求解。基于此，對該問題提出兩種求解策略，貪婪策略和最小差值策略，以下將分別對兩種策略進行描述和分析。對各策略的穩定性和適用范圍進行分析，以及參數與目標函數的關系進行仿真。
3 求解策略
下面將給出貪婪策略和最小差值策略，分析兩種策略在隨機參數變化的情形下的穩定性，并通過對目標函數配送員完成平均每單距離和平均每單完成時間的分析比較，分析兩種策略在不同的應用場景下的有效性和適用性。
3.1 貪婪策略
核心思想：將新產生的訂單分配給距離取貨點最近的且滿足車容量限制的配送員。其具體步驟如下：
第一步：當沒有訂單產生時，配送員在原始位置等待，當產生一個新訂單時，轉第二步;
第二步：計算新訂單的取貨點距離各個配送員的距離，將新訂單分配給距離取貨點最近的且滿足車容量限制的配送員;
第三步：為新分配訂單了的配送員規劃路徑;
(3.1)當配送員的配送路徑中有𝑛個待服務的訂單，即有2𝑛個點，配送員每接受一個新訂單也會新產生兩個點，將取貨點插入原來的路徑中的2𝑛 + 1個空點的任意位置;(3.2)然后將送貨點插入在取貨點以后的任意位置，計算每次插入送貨點以后總的配送路徑的距離;(3.3)比較所有插入方式所得到總的配送路徑的距離，選取最小的距離所對應的插入方式插入新訂單的取送貨點，即配送員的配送路徑。
3.2 最小差值策略
核心思想：將新產生的訂單分配給以最佳插入方式插入所得到的配送距離與不插入狀態下的配送距離的差值最小的且滿足容量限制的配送員。
最小差值策略與貪婪策略的核心步驟區別如下：
第二步：用插入法將新訂單的取送貨點插入每個配送員的初始配送路徑中，計算所有插入方式所得到的配送距離;
第三步：為新分配訂單了的配送員規劃路徑;
(3.1)將所有插入方式所得到的配送距離進行比較，選取配送距離最小的最佳插入方式，計算將新訂單以最佳方式插入和不插入狀態下各個配送員配送距離的差值;(3.2)將各個配送員配送距離的差值比較排序，把訂單分配給配送距離的差值最小的配送員，同時得到該配送員的最佳配送路徑。
3.3 最小差值策略與貪婪策略框架圖
4 數值仿真研究
為驗證模型與設計算法的真實有效性，在此用數值仿真軟件編程，采用貪婪策略和最小差值策略，分別使用插入式算法對算例進行數值仿真。實驗采用數值仿真軟件在 PC 機上運行(i5-3230M 處理器，4G 內存，Windows10 64 位操作系統)。
本文以重慶市南岸區南坪為中心點，向周圍輻射 1.5 公里選取某些商家住宅小區的地理坐標為仿真研究網絡圖，以配送員平均完成每個訂單所行駛的距離和所花費的時間為目標函數，分別從訂單分配和路徑選擇兩個模塊進行策略的設計和算法的求解，通過設定不同參數(如車容量、配送員數量、訂單密度)對目標函數的影響，找出對目標函數最為敏感的影響因素，分析不同策略在不同參數影響下的適用性以及策略在同一參數數值變化下的穩定性。參數設置：車容量𝐶為 6，配送員數量 為 6，訂單密度(即是訂單數量與仿真時間的比值)為 1.11 時是車輛裝載率較好的基礎參照數據，仿真時間為 180 分鐘，仿真次數為 100 次，網絡規模用給定的網絡圖中任意兩點間距離的平均值𝑙為̅ 1.56 千米。
由表 2 第 3、9、16 行可知，采用貪婪策略，完成訂單的平均時間約為 8 分鐘，考慮商品制作時間 10 分鐘，配送員取送餐上樓等時間 5 分鐘，現實中的訂單配送時間大約 30 分鐘，兩者差值約為 7 分鐘，完成訂單的平均距離約為 7.2 公里，考慮現實中配送距離約為 3 公里，來回大約 6 公里，兩者差值約為 1.2 公里;采用最小差值策略，完成訂單的平均時間約為 13 分鐘，考慮商品制作時間 10 分鐘，配送員取送餐上樓等時間 5 分鐘，現實中的訂單配送時間大約 30 分鐘，兩者差值約為 2 分鐘，完成訂單的平均距離約為 5 公里，考慮現實中配送距離約為 3 公里，來回大約 6 公里，兩者差值約為 1 公里。他們的差值均在合理范圍內，所設計的兩種策略均有效。
由表 2 第 3 至 8 行可知，當增大車容量時，對于平均完成訂單的距離而言，采用貪婪策略和最小差值策略均是先增大后減小，對于平均完成訂單的時間而言，采用貪婪策略和最小差值策略均是先增大后減小，其方差極小，車容量的變化對目標函數的影響并不明顯，可以忽略不計。由表 2 第 9 至 14 行可知，當增大配送員數量時，對于平均完成訂單的距離而言，采用貪婪策略和最小差值策略均減小，配送員數量的變化對最小差值策略的影響略大于貪婪策略，對于平均完成訂單的時間而言，采用貪婪策略和最小差值策略均減小，配送員數量的變化對貪婪策略的影響略大于最小差值策略;其方差較小，且配送員數量的變化對目標函數的影響較小，增大配送員數量在一定范圍內可以減少訂單的等待時間，可以通過增加一定的配送員數量降低配送成本同時提高配送效率。由表 2 第 15 至 20 行可知，當增大訂單密度時，對于平均完成訂單的距離而言，采用貪婪策略和最小差值策略均增大，對于平均完成訂單的時間而言，采用貪婪策略和最小差值策略均增大，其方差波動明顯，因此訂單密度的變化對目標函數的影響極其不穩定，但訂單密度增大，商品制作時間較長，平均完成每單的距離和時間也會相應的延長。
由圖 2 可知，無論參數如何改變，對于平均完成每個訂單的距離而言，貪婪策略總是優于最小差值策略，這是因為貪婪策略對實時訂單的分配規則是將新產生的訂單分配給距離取貨點最近的且滿足車容量限制的配送員;對于平均完成每個訂單的時間，最小差值策略總是優于貪婪策略，這是因為最小差值策略對實時訂單的分配規則是將新產生的訂單分配給以最佳插入方式插入與不插入時兩者距離差值最小的且滿足容量限制的配送員。故而從商家角度出發，為了降低配送成本宜采用最小差值策略，從顧客角度出發，從配送時效看宜采用貪婪策略。
5 結論
針對眾包平臺的外賣即時配送訂單分配與路徑優化研究，以配送距離和配送時間為目標函數，建立了外賣即時配送車輛路徑優化的 DRVRP 模型，并設計了貪婪策略和最小差值策略求解動態實時取送貨車輛問題，通過數值仿真實驗驗證了算法的有效性。實驗表明，對兩種策略對比分析可以得出，在相同條件下，訂單密度的變化對目標函數的影響比較明顯，當車容量、配送員數量和訂單密度增加時，對平均完成每個訂單的距離而言，最小差值策略優于貪婪策略，這是因為最小差值策略的訂單分配規則是將新產生的訂單分配給以最佳插入方式插入與不插入時兩者距離差值最小的且滿足容量限制的配送員;對平均完成每個訂單的時間而言，貪婪策略優于最小差值策略，這是因為貪婪策略的訂單分配規則是將新產生的訂單分配給距離取貨點最近的且滿足車容量限制的配送員。因此，從商家角度來看，為了降低配送成本宜采用最小差值策略，從顧客角度出發，從配送時效看宜采用貪婪策略，研究結果可為眾包配送平臺的訂單分配與路徑優化策略的選擇提供決策支持。基于眾包平臺的外賣實時配送問題進一步還可以研究考慮配送員離開系統時間(即是配送員的工作時間)情形下的訂單分配與路徑優化問題。——論文作者：余海燕1,2*，蔣仁蓮 1
參考文獻
[1] 南飛雁. 眾包配送中的服務組合研究[D]. 浙江理工大學, 2018.
[2] 李占強. 眾包配送中服務匹配與優選問題研究[D]. 北京交通大學, 2018.
[3] 程月嬌, 施炯, 黃彬. 眾包物流環境下訂單合并及配送路徑優化方法研究[J]. 浙江萬里學院學報, 2017, 30(4): 27-33.
[4] 張力婭, 張錦, 肖斌.考慮顧客優先級的多目標 O2O 外賣即時配送路徑優化研究[J/OL]. 工業工程與管理:1-12. 31.1738.T.20200316.1854.002.html.
[5] 張旭梅, 陳久梅, 肖劍. 隨機動態多車輛裝卸混合問題及求解策略研究[J]. 系統工程學報, 2012, 27(1):61-68.
[6] 張玉州, 葉亮, 鄭軍帥. 基于滾動時域控制的動態外賣配送問題優化[J]. 計算機技術與發展, 2019, 29(10): 83-88+94.
[7] 李桃迎, 呂曉寧, 李峰, 等. 考慮動態需求的外賣配送路徑優化模型及算法[J]. 控制與決策, 2019, 34(2): 406-413.
[8] 寧濤, 焦璇, 魏瑛琦, 等. 基于量子蟻群算法的隨機需求的動態車輛路徑問題[J]. 大連交通大學學報, 2018, 39(5): 107-110.