基于“動(dòng)態(tài)電子圍欄”的即時(shí)配送路徑優(yōu)化研究

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

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

關(guān)鍵詞：即時(shí)配送;路徑優(yōu)化;中途接單;動(dòng)態(tài)電子圍欄

一、引言

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

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

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

而本文則從單個(gè)配送員的角度出發(fā)，構(gòu)建了解決“在配送途中車輛運(yùn)力有余時(shí)是否接下途中出現(xiàn)的新訂單”問題的模型，并利用C#開發(fā)技術(shù)編程進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

二、問題分析及路徑優(yōu)化模型

1.問題分析

（1）問題描述

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

（2）問題的動(dòng)態(tài)性分析

該問題極具動(dòng)態(tài)性，下面通過案例進(jìn)行說明。

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

該時(shí)刻，訂單A出現(xiàn)了，其取貨點(diǎn)和送貨點(diǎn)分別為Q1和Q2。若接下訂單A，現(xiàn)有貨物和新訂單都能在相應(yīng)時(shí)間窗內(nèi)完成，配送員收益增加。

但若出現(xiàn)的訂單不是A，而是訂單B（見圖2）、訂單C（見圖3）和訂單D（見圖4），則不能接單，因?yàn)榻酉掠唵蜝，C，D會(huì)分別導(dǎo)致貨物3、4和訂單D延遲送達(dá)。

2.問題解決框架

問題的動(dòng)態(tài)性使傳統(tǒng)精確算法難以達(dá)到及時(shí)響應(yīng)的時(shí)效性要求，為此，本文提出了基于“兩層動(dòng)態(tài)電子圍欄”的問題解決框架，如圖5所示。其中：

第一層“動(dòng)態(tài)電子圍欄”：

以新訂單出現(xiàn)時(shí)配送員位置和車上時(shí)間最緊的訂單的送貨點(diǎn)為定點(diǎn)，以最短剩余配送時(shí)間內(nèi)所能行走的距離為定長的不規(guī)則區(qū)域。

第二層“動(dòng)態(tài)電子圍欄”：

以路徑中僅次于Q1的送貨點(diǎn)和次于的送貨點(diǎn)為定點(diǎn)，以路徑中送貨點(diǎn)次于Q1的訂單中時(shí)間最緊的訂單的剩余配送時(shí)間內(nèi)配送車輛所能行駛的距離為定長的多個(gè)不規(guī)則區(qū)域的重疊部分形成的區(qū)域。

3.基于“動(dòng)態(tài)電子圍欄”的即時(shí)配送路徑優(yōu)化模型

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

某時(shí)刻出現(xiàn)了一個(gè)新訂單Q，其取貨點(diǎn)和送貨點(diǎn)分別為Q1（xq1，yq1）和Q2（xq2，yq2），質(zhì)量和體積分別為mq和vq。則基于“動(dòng)態(tài)電子圍欄”的即時(shí)配送路徑優(yōu)化模型可以描述為：

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

模型中的符號(hào)含義如下表所示。

三、實(shí)驗(yàn)求解及結(jié)果分析

本文利用開C#發(fā)技術(shù)編程實(shí)現(xiàn)了基于“動(dòng)態(tài)電子圍欄”的即時(shí)配送路徑優(yōu)化模型的算法程序，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1.實(shí)驗(yàn)參數(shù)設(shè)置

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

2.實(shí)驗(yàn)結(jié)果及分析

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

由圖7可知，路線集中在出發(fā)點(diǎn)附近，因此可認(rèn)為配送員靠近出發(fā)點(diǎn)對配送訂單是有優(yōu)勢的，當(dāng)路線遠(yuǎn)離出發(fā)點(diǎn)時(shí)，程序會(huì)自動(dòng)篩選新訂單以糾正路線使之逐漸靠近出發(fā)點(diǎn)，形成良好循環(huán)，這與美團(tuán)外賣的配送集中在某一范圍類似，實(shí)驗(yàn)結(jié)果符合實(shí)際情況，驗(yàn)證了模型的有效性。

四、結(jié)論

1.本研究的創(chuàng)新點(diǎn)

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

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

（2）“動(dòng)態(tài)電子圍欄”的引入

本文提出的“電子圍欄”是由橢圓定義延伸而來，基于位置、配送時(shí)間等限制條件的不規(guī)則區(qū)域?！皠?dòng)態(tài)”體現(xiàn)在電子圍欄的兩個(gè)焦點(diǎn)——配送員的位置和即將配送的下個(gè)訂單的送貨點(diǎn)都是實(shí)時(shí)變化的，所以形成的不規(guī)則區(qū)域也是動(dòng)態(tài)變化的。

2.未來展望

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

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

（2）研究只從單個(gè)配送員出發(fā)，得到的優(yōu)化結(jié)果只是局部優(yōu)化。

因此，為更好地匹配現(xiàn)實(shí)情況，本研究可從以下兩方面進(jìn)行改進(jìn)：

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

（2）可對多個(gè)配送員展開研究，探索全局優(yōu)化時(shí)的情況。

參考文獻(xiàn)：

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

[2]金垚煒.基于二層規(guī)劃的無人機(jī)城市即時(shí)配送定位-路徑優(yōu)化研究[D].浙江工商大學(xué)，2018.

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

[4]趙琨，史艷華，史曉霞.基于遺傳算法的即時(shí)配送路徑優(yōu)化研究[J].現(xiàn)代商貿(mào)工業(yè)，2019（5）：31-32.

[5]張延強(qiáng).基于聚類的大規(guī)模即時(shí)配送問題研究[D].東華大學(xué)，2018.

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

[7]趙興龍.基于K-means-遺傳算法的眾包配送網(wǎng)絡(luò)優(yōu)化研究[D].北京交通大學(xué)，2016.

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