無(wú)中心多點(diǎn)到多點(diǎn)配送問(wèn)題建模與求解

盧煒達(dá) 羅世平

[摘要]針對(duì)外賣配送客戶與訂單隨機(jī)產(chǎn)生，外賣騎手勞動(dòng)強(qiáng)度極大但服務(wù)效率不夠高等問(wèn)題，提出無(wú)配送中心的多點(diǎn)到多點(diǎn)配送問(wèn)題建模思路，并基于啟發(fā)式算法求解。算例選用常見(jiàn)的10個(gè)訂單業(yè)務(wù)，在一個(gè)社區(qū)內(nèi)隨機(jī)選擇10個(gè)取貨點(diǎn)和10個(gè)送貨點(diǎn)，求解證明騎手一個(gè)小時(shí)內(nèi)可以完成任務(wù)，方案可行有效。

[關(guān)鍵詞]外賣配送;無(wú)中心;多點(diǎn)到多點(diǎn);遺傳算法

[中圖分類號(hào)]F224.0;F252.14[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1005-152X（2021）12-0090-06

Modeling and Solution of Multiple-start/end Acentric Distribution Problem

LU Weida1，LUO Shiping2

（1. School of Business，Macau University of Science & Technology，Macau 999078;

2. School of Mathematical Sciences，South China Normal University，Guangzhou 510631，China）

Abstract：Due to the randomness of takeout delivery orders as well as their destinations，deliverers often have to work intensively at low service efficiency. In light of this，we proposed the line of thinking for the multi-point to multi-point distribution model without a distribution center，and solved it using the heuristic algorithm. Next through a numerical example involving ten common orders，we randomly selected 10 pickup points and 10 delivery points in a community，and applied the model to prove that a deliverer could complete its task within an hour，concluding that the model was feasible and effective.

Keywords：takeout delivery;acentric;multi-point to multi-point;genetic algorithm

0引言

外賣已經(jīng)成為人們生活不可或缺的部分。截至2021年6月，我國(guó)網(wǎng)上外賣用戶規(guī)模達(dá)4.69億。外賣行業(yè)市場(chǎng)規(guī)模達(dá)到了6 646.2億元[1]。外賣騎手在配送工作中，為了提高效率以滿足客戶和公司的要求，經(jīng)常超負(fù)荷工作或違反相關(guān)法律法規(guī)，造成人員傷亡。如2017年上半年，上海市公安局交警總隊(duì)數(shù)據(jù)顯示，在上海平均每2.5天就有1名外賣騎手傷亡。同年，深圳3個(gè)月內(nèi)外賣騎手傷亡12人。2018年成都交警7個(gè)月間查處騎手違法近萬(wàn)次，事故196件，傷亡155人次，平均每天就有1個(gè)騎手因違法傷亡。2018年9月廣州交警查處外賣騎手交通違法近2 000宗[2]。外賣騎手承受著巨大的壓力，外賣工作存在大量安全隱患。因此急需合理有效的外賣配送解決方案來(lái)滿足社會(huì)需求。

1問(wèn)題描述

外賣配送作業(yè)通常是騎手在收到客戶通過(guò)平臺(tái)下單的信息后，趕到下單店鋪取貨并送達(dá)客戶指定的目的地。為騎手提高工作效率，往往會(huì)多單并行操作，趕到多個(gè)訂單所表述的多個(gè)取貨點(diǎn)取貨并送達(dá)多個(gè)目的地，即遍歷訂單中全部的取貨點(diǎn)和送貨點(diǎn)，如圖1所不。但該問(wèn)題具有以下特點(diǎn)：（1）不同于典型TSP問(wèn)題[3]不分先后的簡(jiǎn)單遍歷，而是需要先取貨再送貨;（2）取貨順序不一定按訂單順序，送貨順序也不一定完全與取貨順序相同;（3）送貨不一定完成全部訂單的取貨后再開(kāi)始，可以是邊取邊送。

外賣配送問(wèn)題不同于一般的物流配送和VRP問(wèn)題[4-5]，如圖2所示。典型的物流配送和VRP問(wèn)題，是從配送中心取貨后，按單送到多個(gè)目的地，實(shí)現(xiàn)一到多的配送。外賣配送具有如下特性：（1）客戶及訂單的隨機(jī)性?？蛻艏坝唵蔚碾S機(jī)性使得配送線路及取貨、送貨順序具有動(dòng)態(tài)性。需要根據(jù)每組訂單實(shí)時(shí)動(dòng)態(tài)規(guī)劃配送線路。（2）對(duì)時(shí)間的強(qiáng)烈要求。不同于一般電商平臺(tái)購(gòu)物，外賣客戶下單后對(duì)等待時(shí)間有非常高的期待，一般不能超過(guò)一個(gè)小時(shí)，且追求越快越好！同時(shí)，賣家的商品需要準(zhǔn)備時(shí)間，很難做到下單即取。（3）無(wú)配送中心和中轉(zhuǎn)接駁站。騎手取貨后不必返回公司，也不能由配送中心安排訂單順序，而是根據(jù)平臺(tái)信息，邊取貨邊送貨。

因此，外賣配送問(wèn)題可描述為無(wú)配送中心的多點(diǎn)到多點(diǎn)的配送問(wèn)題。

2研究現(xiàn)狀

外賣問(wèn)題與VRP和TSP問(wèn)題非常相似，又不完全一樣。VRP自Dantzig和RamseF于1959年提出后即受到學(xué)術(shù)界極大的關(guān)注。圍繞VRP的理論模型、應(yīng)用環(huán)境及求解方法，呈現(xiàn)出大量的研究成果。

2.1VRP問(wèn)題及其數(shù)學(xué)建模研究

VRP問(wèn)題經(jīng)由Dantzig等學(xué)者研究總結(jié)分成不同的類型。主要有：（1）經(jīng)典旅行商問(wèn)題[3]（Traveling Salesman Problem，簡(jiǎn)稱TSP）;（2）帶時(shí)間窗[6，7]的車輛路線問(wèn)題（Vehicle Routing Problem with Time Windows，簡(jiǎn)稱VRPTW）;（3）帶容量限制的車輛路徑問(wèn)題（Capacitated Vehicle Routing Problem[8]，簡(jiǎn)稱CVRP）;（4）優(yōu)先約束車輛路線（Vehicle Routing Problem with Precedence Constraints[9]，簡(jiǎn)稱VRPPC））;（5）隨機(jī)需求車輛路線問(wèn)題（Vehicle Routing Problem with Random Demand[10]，簡(jiǎn)稱VRPRD）等問(wèn)題。

所有模型的目標(biāo)函數(shù)都是以總成本最優(yōu)為目標(biāo)的變形，如總里程最小、總時(shí)間最短等。

2.2VRP求解方法研究

VRP的求解主要包括傳統(tǒng)數(shù)學(xué)優(yōu)化方法和現(xiàn)代計(jì)算機(jī)算法。其中傳統(tǒng)數(shù)學(xué)優(yōu)化方法主要有：（1）先安排路線后分組的方法[11]（Route First-Cluster Second）;（2）先分組后安排線路的方法（Cluster First- Route Second）;（3）節(jié)約-插入算法[l2]（Saving-Inserting Algorithm）;（4）改進(jìn)-交換法（Improving-Exchange Algorithm）;（5）基于數(shù)學(xué)規(guī)劃的算法[13]（Mathematical Programming Based Algorithm）;（6）交互式優(yōu)化算法[14]（Interactive Method）。現(xiàn)代計(jì)算機(jī)算法主要有：（1）人工神經(jīng)網(wǎng)絡(luò)[15];（2）蟻群算法[16];（3）遺傳算法等。此外，分枝定界法和動(dòng)態(tài)規(guī)劃法也是較常用的求解VRP問(wèn)題的算法。

2.3外賣配送優(yōu)化研究

國(guó)內(nèi)關(guān)于外賣行業(yè)眾包物流的研究較多，包括以最后一公里的視野研究外賣配送問(wèn)題。王文杰，等[17]在隨機(jī)配送需求的情形下，同時(shí)考慮了眾包配送的配送人員特性以及訂單損失成本，研宄了眾包物流配送的定價(jià)問(wèn)題。方婷[18]分析了眾包物流配送的風(fēng)險(xiǎn)。李玉，等[19]采用演化博弈的研宄方法，從發(fā)貨商的角度出發(fā)，研宄了在保價(jià)制度下配送方的行為決策。

綜上所述，尚沒(méi)有見(jiàn)到把外賣問(wèn)題定義為無(wú)中心多點(diǎn)到多點(diǎn)配送問(wèn)題的研究。

3建模與分析

本文考慮情況，給定訂單（O₁，O₂，…，O_n）的取貨地點(diǎn)（R₁，R₂，…，R_n）和目標(biāo)地點(diǎn)（T₁，T₂，…，T_n），取貨地點(diǎn)與目標(biāo)地點(diǎn)一一對(duì)應(yīng)，即訂單O_i從地點(diǎn)R_i取貨并按要求送到T_i。不考慮多個(gè)訂單在同一地點(diǎn)取貨，或多個(gè)訂單送到同一地點(diǎn)，甚至混合交叉的情形。基于外賣騎手的特定行為能力，本文不考慮物流路徑優(yōu)化中的路線方向（包括機(jī)動(dòng)車限行規(guī)定等）及載貨能力與裝載順序的限制等。

以騎手當(dāng)前所在位置為任務(wù)的起始點(diǎn)，完成全部訂單送貨即結(jié)束，不考慮之后的行程。設(shè)從任一送貨點(diǎn)開(kāi)始，每個(gè)任務(wù)必須經(jīng)過(guò)全部的R_i（i=1，2，…，n），和T_i（i= 1，2，…，n）。在上述條件下，本文的目標(biāo)是找到總路程最短的路徑。

外賣配送任務(wù)是一個(gè)有條件限制的TSP問(wèn)題。每個(gè)訂單的履行，必須是先取貨，后送貨，即R_i在T_i之前（i= 1，2，…，n）。

設(shè)任意兩點(diǎn)i，j距離為C_ij，則目標(biāo)函數(shù)為：

設(shè)i點(diǎn)在路徑中的順序?yàn)榈贚_is個(gè)位置，則：

L_is（i+n_）t，i=1，2，…，n，s，t=1，2，…，2n（3）

4算法設(shè)計(jì)

已知（R₁，R₂，…，R_n）和（T₁，T₂，…，T_n）分別是訂單O_i（i=1，2，…，n）的取貨點(diǎn)和送貨點(diǎn)坐標(biāo)，由給定坐標(biāo)可以計(jì)算出各點(diǎn)間的距離。

求解目標(biāo)是優(yōu)化到達(dá)全部取貨點(diǎn)（R₁，R₂，…，R_n）和送貨點(diǎn)（T₁，T₂，…，T_n）的順序，使其在滿足每訂單先取貨后送貨的前提下，總距離最短。

4.1染色體定義

將（R₁，R₂，…，R_n）編號(hào)為（1，2，…，n），（T₁，T₂，…，T_n）編號(hào)為（n+1，n+2，…，2n），組合構(gòu)成（1，2，…，n，n+1，n+2，…，2n）基因染色體。染色體是1到2n的隨機(jī)排列，但必須滿足R_i（i=1，2，…，n）在T_i（i=1，2，…，n）之前。

4.2目標(biāo)函數(shù)

目標(biāo)函數(shù)是染色體所對(duì)應(yīng)排列中各相鄰兩點(diǎn)間的距離之和，即一條路徑的總路程最短。設(shè)兩點(diǎn)間的距離為c_ij.1≤i，j≤2n。對(duì)任一排列i₁，i₂，…，i_2n的總路程為s=c_i1i2+c_i2i3+…+c_{（i2n-1）i2n}。

4.3適應(yīng)度函數(shù)

4.4初始種群

設(shè)初始種群大小為P_i，將（1，2，…，2n）隨機(jī)排列并檢驗(yàn)點(diǎn)R_i（i=1，2，…，n）的位置是否都在T_i之前（i=1，2，…，n），符合條件的即為一個(gè)有效解。如此得到P_i個(gè)有效解，為初始種群。

4.5選擇

采用二元競(jìng)標(biāo)法，將種群中的p_i個(gè)解隨機(jī)兩兩分為P_i/2組，比較每組兩個(gè)解的適應(yīng)度，選擇適應(yīng)度大的那個(gè)解。重復(fù)P_i次，將初始種群的P_i個(gè)解替換成適應(yīng)度相對(duì)較大的P_i個(gè)解（會(huì)有重復(fù)解出現(xiàn)）。

4.6交叉

將二元競(jìng)標(biāo)法選擇后得到的解兩兩配對(duì)交叉。將解A和解B任選對(duì)應(yīng)的一段基因A^*和B^*進(jìn)行交叉，將A^*和B^*分別排在B和A的左邊，得到A^*B和B^*A，再檢驗(yàn)B和A中與A^*和B^*中重復(fù)的點(diǎn)將它們刪去，得到兩個(gè)新的解，并保證每個(gè)解中，對(duì)全部取貨點(diǎn)和送貨點(diǎn)不遺漏也不重復(fù)。設(shè)交叉概率p_C=C。

4.7重組變異

設(shè)重組變異的概率p_M=M，應(yīng)滿足：

p_C+p_M=1（4）

重組變異時(shí)，將進(jìn)行交換、逆轉(zhuǎn)和插入。設(shè)交換概率p_S=S，逆轉(zhuǎn)概率p_R=R，插入概率p_I=I。應(yīng)滿足：

p_S+p_R+p_I=1（5）

將一個(gè)解中任選兩點(diǎn)進(jìn)行如下操作：

（1）交換。交換兩點(diǎn)位置。

（2）逆轉(zhuǎn)。將兩點(diǎn)間所有點(diǎn)的排列順序逆轉(zhuǎn)。

（3）插入。將排在左邊的點(diǎn)移動(dòng)到右邊點(diǎn)的右邊。

4.8選擇種群中的最優(yōu)解

交叉和變異后產(chǎn)生的新排列有可能出現(xiàn)不符合R_i（i=1，2，…，n）在T_i（i=1，2，…，n）之前的前提。因此交叉和變異后都需要檢驗(yàn)排列是否是有效解。判斷為有效排列后再替換原排列。

4.9循環(huán)迭代

種群經(jīng)過(guò)二元競(jìng)標(biāo)，交叉和變異之后得到新的種群。將新種群中個(gè)體適應(yīng)度最大，即種群中最優(yōu)的解選出得到第一代最優(yōu)解。將新種群再經(jīng)上述二元競(jìng)標(biāo)，交叉和變異后得到第二代最優(yōu)解。

循環(huán)迭代上述操作（4.5～4.8）直到?jīng)]有更優(yōu)解出現(xiàn)或達(dá)到預(yù)設(shè)上線M次。

具體優(yōu)化求解流程如圖3所示。

5算例分析

圖4為3×4個(gè)街區(qū)組成的服務(wù)社區(qū)。街道間距單位為1km，即社區(qū)南北寬3km，東西長(zhǎng)4km。設(shè)外賣騎手在某一時(shí)間段內(nèi)，收到了10個(gè)訂單，即有10個(gè)取貨點(diǎn)和10個(gè)對(duì)應(yīng)送貨點(diǎn)，以任一取貨點(diǎn)為起點(diǎn)開(kāi)始求解完成任務(wù)的總路程及所需時(shí)間。

圖4中，圓圈（1，2，…，10）為訂單（1，2，…，10）的取貨點(diǎn)，方框（1，2，…，10）為對(duì)應(yīng)的送貨點(diǎn)。為求解方便，取貨點(diǎn)用（1，2，…，10）表示，送貨點(diǎn)用（11，12，…，20）表示，如圖5所小。則構(gòu)成初始基因染色體種群為（1，2，…，20）。設(shè)定最左下角點(diǎn)20的坐標(biāo)位置為（0，0），合成表達(dá)后的（1，2，…，20）各點(diǎn)坐標(biāo)為：（x，y）={（1，2），（4，0），（3，0），（4，1），（0，3），（1，1），（1，0），（3，3），（2，0），（4，3），（2，2），（0，2），（4，2），（2，3），（3，1），（0，1），（1，3），（2，1），（3，2），（0，0）}，各點(diǎn)間的距離見(jiàn)表1。

設(shè)初始種群大小為P_i=50，迭代次數(shù)為M=1 000，交叉概率為p_C=0.8，變異概率為p_M=0.2。

按“算法設(shè)計(jì)”的流程求解，求解迭代過(guò)程如圖7 所示，求得最優(yōu)路線圖如圖8所示，最佳里程為19。

最優(yōu)解路徑順序?yàn)椋?/p>

7（取貨）→9（取貨）→3（取貨）→2（取貨）→4（取貨）→13（目標(biāo)3送貨）→10（取貨）→8（取貨）→14（目標(biāo)4送貨）→17（目標(biāo)7送貨）→5（取貨）→12（目標(biāo)2送貨）→1（取貨）→11（目標(biāo)1送貨）→19（目標(biāo)9送貨）→15（目標(biāo)5送貨）→18（目標(biāo)8送貨）→6（取貨）→16（目標(biāo)6送貨）→20（目標(biāo)10送貨）

假設(shè)快遞員平均時(shí)速20km，則需要大約57min，即一個(gè)小時(shí)以內(nèi)可完成10個(gè)訂單配送，滿足一個(gè)小時(shí)完成全部訂單的目標(biāo)要求。

本算例沒(méi)有考慮到實(shí)際取送貨時(shí)的等待時(shí)間，但設(shè)每個(gè)街區(qū)街道間距為1km，10個(gè)訂單覆蓋3×4=12km²的社區(qū)，其服務(wù)距離超過(guò)實(shí)際服務(wù)范圍，所求解有一定的可信度。

考慮兩個(gè)極端情況作為對(duì)照：（1）當(dāng)外賣騎手按照順序?qū)⑼赓u訂單全部取完再送，則總路程為49.3，總時(shí)間約需要150min。（2）如果按照取一個(gè)送一個(gè)的順序，總路程為44.9，總時(shí)間需要約135min。由此可見(jiàn)，使用本算例采用的算法給出的優(yōu)化解極大地縮短了配送時(shí)間，可大大提高配送效率、節(jié)約人力成本。

6結(jié)語(yǔ)

在第三方外賣平臺(tái)興起之前，一部分餐館也為臨近的客戶提供送餐上門服務(wù)。這種情形類似于一個(gè)配送中心（即餐館）和多個(gè)配送目的地，與VRP的模型描述相近。現(xiàn)在的第三方外賣服務(wù)平臺(tái)往往要服務(wù)龐大數(shù)量的外賣供應(yīng)商和客戶?，F(xiàn)有研究不論是關(guān)于VRP的還是TSP的，都與現(xiàn)實(shí)情況有一定程度的差異，并不能很有效的解決現(xiàn)實(shí)中的外賣配送問(wèn)題。本文梳理外賣服務(wù)特征，提出了無(wú)中心多點(diǎn)到多點(diǎn)配送建模與求解方案。所提思路在保障外賣服務(wù)要求的前提下，實(shí)現(xiàn)了最優(yōu)路徑的求解。在實(shí)施路徑優(yōu)化的過(guò)程中，在保證每單“先取后送”，每組訂單不必“先取先送、后取后送”的前提下，優(yōu)化路徑的同時(shí)也實(shí)現(xiàn)了訂單取貨順序的優(yōu)化。算例證明可以有效提高工作效率，保障服務(wù)水平。

本文所考慮的情形還相對(duì)簡(jiǎn)單，未來(lái)會(huì)考慮帶時(shí)間窗限制條件下多車協(xié)同完成的調(diào)度和路徑規(guī)劃等更復(fù)雜情況下的建模，也會(huì)利用更先進(jìn)的智能算法來(lái)求解。

[參考文獻(xiàn)]

[1]艾媒咨詢.外賣行業(yè)數(shù)據(jù)分析：2020年中國(guó)外賣行業(yè)市場(chǎng)規(guī)模達(dá)6 646.2 億元[EB/OL].（2021-04-13）[2021-10- 08].http：//k.sina.com.cn/article_1850460740_6e4bca440_ 2000sqad.html.

[2]賴祐萱.外賣騎手困在系統(tǒng)里[EB/OL].（2020-09-08）[2021- 10-08].https：//baijiahao.baidu.com/s？id=1677231323622016633_&wfr=spider&for=pc.

[3] DANTZIG G B，RAMSER J H.The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.

[4] SAVELSBERGH M.Local search for routing problem with time windows[J].Annals of Operations Research，1985，2（3）：285-305.

[5]徐倩倩.考慮商家出餐時(shí)間的外賣路徑優(yōu)化[D].上海：東華大學(xué)，2021.

[6] He Y，Hui C- W.A binary coding genetic algorithm for multi-purpose process scheduling：A case study[J].Chemical Engineering Science，2010，65（16）：4 816-4 828.

[7] ARCHETTI C，SPERANZA M G，Hertz A.A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem[J]. Transportation Science，2006，40（1）：64-73.

[8] GAMBARDELLA L M，DORIGO M.An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem[J].INFORMS Journal on Computing，2000，12（3）：237-255.

[9]BRAYSY O，et al.An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle- Routing Problem with Time Windows[J].Transpotation Science，2008，42（3）.

[10] MAKINO Y，F(xiàn)URUTA K，KANNO T.Interactive Method for Service Design Using Computer Simulation[J].Service Science，2009，1（2）：121-134.

[11] ANDREAS A K，SMITH J C.Mathematical Programming Algorithms for Two- Path Routing Problems with Reliability Considerations[J].INFORMS Journal on Computing，2008，20（4）：553-564.

[12] LAI H C，NAKAGAWA T，MUROGA S.Redundancy check technique for designing optimal networks by branch- and- bound method[J].International Journal of Computer & Information Sciences，1974，3（3）：251 -271.

[13] GOUNARIS C E，WIESEMANN W，F(xiàn)LOUDAS C A. The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty[J].Operations Research，2013，61（3）：677- 693.

[14] Erera A L，MORALES J C，SAVELSBERGH M. The Vehicle Routing Problem with Stochastic Demand and Duration Constraints[J].Transportation Science，2010，44（4）：474-492.

[15] Solomon M M，J Desrosiers. Time Window Constrained Routing and Scheduling Problems[J].Transportation Sci- ence，1988，22（1）：1-13.

[16]徐興，錢譽(yù)欽，趙蕓，等.基于改進(jìn)蟻群算法的立體倉(cāng)庫(kù)三維空間路徑優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2021，27（1）：206-213.

[17]王文杰，孫中苗，徐琪.考慮社會(huì)配送供應(yīng)能力的眾包物流服務(wù)動(dòng)態(tài)定價(jià)模型[J].管理學(xué)報(bào)，2018，15（2）：293-300.

[18]方婷.眾包物流的風(fēng)險(xiǎn)與對(duì)策：以三家眾包物流平臺(tái)為例[J].中國(guó)管理信息化，2018，21（23）：151-152.

[19]李玉，吳斌，王超.基于前景理論的眾包物流配送方行為決策演化博弈分析：基于發(fā)貨方視角[J].運(yùn)籌與管理，2019，28（6）：129-135.