基于“動態電子圍欄”的即時配送路徑優化研究

劉嬌 田育靈 陳嫣 葉紫 魏榮華

摘 要：即時配送與傳統快遞有著較大區別，從事即時配送的物流企業和配送員都面臨著延遲送貨等問題。本文從中途接單出發，基于位置、時間等限制，化時間窗約束為距離約束，引入兩層“動態電子圍欄”，構建了解決“在配送途中車輛運力有余時是否接下途中出現的新訂單”問題的模型，并利用C#開發技術編程驗證了模型的有效性。

關鍵詞：即時配送;路徑優化;中途接單;動態電子圍欄

一、引言

隨著生活節奏的加快和“懶人經濟”的興起，社會對即時配送的需求越來越大，其業務范圍也由生鮮食品延伸至藥品、文件資料等。然而幾乎所有電商和配送員都采取“來者不拒、一律接單”的態度，延遲送貨時有發生，服務效率低下。在此背景下，許多學者都對即時配送路徑優化展開了研究。

張寧通過引入出租車作為補充運力，建立了即時配送問題的整數規劃模型。金垚煒針對無人機城市即時配送的定位及路徑優化問題，提出了無人機城市即時配送LRP二層規劃模型。王征、李婷玉等建立了基于多樣化方案池的即時配送訂單實時響應方法和基于多預測場景的在線優化調度方法。趙琨、史艷華等構建了滿足配送時間窗下的以配送員每次配送收入最大為目標函數的模型。慕靜、杜田玉等對時間窗進行模糊化處理，構建客戶滿意度函數，以最大化眾包物流配送人員的收益和客戶滿意度為目標，建立了眾包物流運力調度模型。

以上研究都是在取貨位置固定的情況下，對已有訂單的篩選、合并和再分配以實現配送成本最低、收益最高等目標。而針對取貨點位置不固定的研究則很少，但眾包配送中基于社會閑散運力的配送模式的取貨點大多不固定，這種模式也存在著延遲配送等問題。在此方面，趙興龍從網絡優化的角度出發，建立了帶有時間窗的眾包配送路徑基本優化模型和動態優化模型。

而本文則從單個配送員的角度出發，構建了解決“在配送途中車輛運力有余時是否接下途中出現的新訂單”問題的模型，并利用C#開發技術編程進行了實驗驗證。

二、問題分析及路徑優化模型

1.問題分析

（1）問題描述

“中途接單”問題可以描述為：在一次配送任務中，車上現有n個貨物，送貨點分別為P1、P2……Pn，配送員依次配送n個貨物，直至貨物全部配送完。在配送途中，產生了一些新訂單。新訂單和車上已有貨物都有各自的配送時間窗，若配送員能在規定時間窗內完成已有貨物和新訂單的配送，則接下新訂單可增加配送員的收益，反之，接下新訂單不僅不會增加收入，還會影響顧客滿意度、信用評分，甚至使配送員受到懲罰。

（2）問題的動態性分析

該問題極具動態性，下面通過案例進行說明。

如圖1所示，某時刻，配送員在P0處，車上現有4個貨物，送貨點分別為P1、P2、P3、P4，字母上方的數字為貨物的剩余配送時間，路徑上的數字表示從一個點到另一個點需要的時間。

該時刻，訂單A出現了，其取貨點和送貨點分別為Q1和Q2。若接下訂單A，現有貨物和新訂單都能在相應時間窗內完成，配送員收益增加。

但若出現的訂單不是A，而是訂單B（見圖2）、訂單C（見圖3）和訂單D（見圖4），則不能接單，因為接下訂單B，C，D會分別導致貨物3、4和訂單D延遲送達。

2.問題解決框架

問題的動態性使傳統精確算法難以達到及時響應的時效性要求，為此，本文提出了基于“兩層動態電子圍欄”的問題解決框架，如圖5所示。其中：

第一層“動態電子圍欄”：

以新訂單出現時配送員位置和車上時間最緊的訂單的送貨點為定點，以最短剩余配送時間內所能行走的距離為定長的不規則區域。

第二層“動態電子圍欄”：

以路徑中僅次于Q1的送貨點和次于的送貨點為定點，以路徑中送貨點次于Q1的訂單中時間最緊的訂單的剩余配送時間內配送車輛所能行駛的距離為定長的多個不規則區域的重疊部分形成的區域。

3.基于“動態電子圍欄”的即時配送路徑優化模型

假設配送車輛以速度u勻速行駛，車上已有n個貨物，其送貨點為Pi（i=1，2，…，n），坐標為（xi，yi），質量為mi，體積為vi;配送員的實時位置為P0，其坐標為（x0，y0）。

某時刻出現了一個新訂單Q，其取貨點和送貨點分別為Q1（xq1，yq1）和Q2（xq2，yq2），質量和體積分別為mq和vq。則基于“動態電子圍欄”的即時配送路徑優化模型可以描述為：

其中，i滿足i=1，2，…，n，最近，。

模型中的符號含義如下表所示。

三、實驗求解及結果分析

本文利用開C#發技術編程實現了基于“動態電子圍欄”的即時配送路徑優化模型的算法程序，并進行了實驗驗證。

1.實驗參數設置

如圖6所示，研究區域為30km×30km的矩形城市區域，車輛以30km/h的速度勻速行駛，配送車輛的額定載重為10kg，額定容積為36L，初始位置為（15.0，15.0），此時車上已有三個貨物，其重量、體積、取貨點、送貨點及配送時間窗如圖所示。

2.實驗結果及分析

在程序運行前，先生成一些數據作為待判斷的新訂單。在一組數據中，程序一旦檢測到有效訂單，便不再檢驗后續訂單，而是重置配送員的位置和已有貨物信息。將程序運行20次的結果繪制成路徑，如圖7所示。

由圖7可知，路線集中在出發點附近，因此可認為配送員靠近出發點對配送訂單是有優勢的，當路線遠離出發點時，程序會自動篩選新訂單以糾正路線使之逐漸靠近出發點，形成良好循環，這與美團外賣的配送集中在某一范圍類似，實驗結果符合實際情況，驗證了模型的有效性。

四、結論

1.本研究的創新點

（1）“中途接單”問題的訂單篩選解決方案

目前即時配送路徑優化的研究集中于對已有訂單的合并和再分配，幾乎不涉及配送途中車輛運力有余時的接單問題。本文則提供了一種解決方案。

（2）“動態電子圍欄”的引入

本文提出的“電子圍欄”是由橢圓定義延伸而來，基于位置、配送時間等限制條件的不規則區域。“動態”體現在電子圍欄的兩個焦點——配送員的位置和即將配送的下個訂單的送貨點都是實時變化的，所以形成的不規則區域也是動態變化的。

2.未來展望

本文的研究立足于較理想的狀態，存在以下問題：

（1）在涉及配送時間的計算中，將配送過程簡化成了勻速行駛，但現實情況并不一定能保持勻速。

（2）研究只從單個配送員出發，得到的優化結果只是局部優化。

因此，為更好地匹配現實情況，本研究可從以下兩方面進行改進：

（1）綜合路網擁堵情況、天氣狀況等，基于時間線建立車輛的行駛速度函數，使車輛的行駛速度盡可能符合實際情況。

（2）可對多個配送員展開研究，探索全局優化時的情況。

參考文獻：

[1]張寧.基于眾包物流平臺的同城快遞配送問題研究[D].大連理工大學，2019.

[2]金垚煒.基于二層規劃的無人機城市即時配送定位-路徑優化研究[D].浙江工商大學，2018.

[3]王征，李婷玉，侯鑫垚.基于多樣化方案池的即時配送訂單實時響應方法[J].管理科學，2018（6）：92-103.

[4]趙琨，史艷華，史曉霞.基于遺傳算法的即時配送路徑優化研究[J].現代商貿工業，2019（5）：31-32.

[5]張延強.基于聚類的大規模即時配送問題研究[D].東華大學，2018.

[6]慕靜，杜田玉，劉爽，等.基于即時配送和收益激勵的眾包物流運力調度研究[J].運籌與管理，2018（5）：58-65.

[7]趙興龍.基于K-means-遺傳算法的眾包配送網絡優化研究[D].北京交通大學，2016.

作者簡介：劉嬌（1998.11- ），女，四川南充人，本科在讀，從事物流與供應鏈領域研究