無中心多點到多點配送問題建模與求解

盧煒達 羅世平

[摘要]針對外賣配送客戶與訂單隨機產生，外賣騎手勞動強度極大但服務效率不夠高等問題，提出無配送中心的多點到多點配送問題建模思路，并基于啟發式算法求解。算例選用常見的10個訂單業務，在一個社區內隨機選擇10個取貨點和10個送貨點，求解證明騎手一個小時內可以完成任務，方案可行有效。

[關鍵詞]外賣配送;無中心;多點到多點;遺傳算法

[中圖分類號]F224.0;F252.14[文獻標識碼]A[文章編號]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引言

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

1問題描述

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

外賣配送問題不同于一般的物流配送和VRP問題[4-5]，如圖2所示。典型的物流配送和VRP問題，是從配送中心取貨后，按單送到多個目的地，實現一到多的配送。外賣配送具有如下特性：（1）客戶及訂單的隨機性。客戶及訂單的隨機性使得配送線路及取貨、送貨順序具有動態性。需要根據每組訂單實時動態規劃配送線路。（2）對時間的強烈要求。不同于一般電商平臺購物，外賣客戶下單后對等待時間有非常高的期待，一般不能超過一個小時，且追求越快越好！同時，賣家的商品需要準備時間，很難做到下單即取。（3）無配送中心和中轉接駁站。騎手取貨后不必返回公司，也不能由配送中心安排訂單順序，而是根據平臺信息，邊取貨邊送貨。

因此，外賣配送問題可描述為無配送中心的多點到多點的配送問題。

2研究現狀

外賣問題與VRP和TSP問題非常相似，又不完全一樣。VRP自Dantzig和RamseF于1959年提出后即受到學術界極大的關注。圍繞VRP的理論模型、應用環境及求解方法，呈現出大量的研究成果。

2.1VRP問題及其數學建模研究

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

所有模型的目標函數都是以總成本最優為目標的變形，如總里程最小、總時間最短等。

2.2VRP求解方法研究

VRP的求解主要包括傳統數學優化方法和現代計算機算法。其中傳統數學優化方法主要有：（1）先安排路線后分組的方法[11]（Route First-Cluster Second）;（2）先分組后安排線路的方法（Cluster First- Route Second）;（3）節約-插入算法[l2]（Saving-Inserting Algorithm）;（4）改進-交換法（Improving-Exchange Algorithm）;（5）基于數學規劃的算法[13]（Mathematical Programming Based Algorithm）;（6）交互式優化算法[14]（Interactive Method）。現代計算機算法主要有：（1）人工神經網絡[15];（2）蟻群算法[16];（3）遺傳算法等。此外，分枝定界法和動態規劃法也是較常用的求解VRP問題的算法。

2.3外賣配送優化研究

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

綜上所述，尚沒有見到把外賣問題定義為無中心多點到多點配送問題的研究。

3建模與分析

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

以騎手當前所在位置為任務的起始點，完成全部訂單送貨即結束，不考慮之后的行程。設從任一送貨點開始，每個任務必須經過全部的R_i（i=1，2，…，n），和T_i（i= 1，2，…，n）。在上述條件下，本文的目標是找到總路程最短的路徑。

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

設任意兩點i，j距離為C_ij，則目標函數為：

設i點在路徑中的順序為第L_is個位置，則：

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

4算法設計

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

求解目標是優化到達全部取貨點（R₁，R₂，…，R_n）和送貨點（T₁，T₂，…，T_n）的順序，使其在滿足每訂單先取貨后送貨的前提下，總距離最短。

4.1染色體定義

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

4.2目標函數

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

4.3適應度函數

4.4初始種群

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

4.5選擇

采用二元競標法，將種群中的p_i個解隨機兩兩分為P_i/2組，比較每組兩個解的適應度，選擇適應度大的那個解。重復P_i次，將初始種群的P_i個解替換成適應度相對較大的P_i個解（會有重復解出現）。

4.6交叉

將二元競標法選擇后得到的解兩兩配對交叉。將解A和解B任選對應的一段基因A^*和B^*進行交叉，將A^*和B^*分別排在B和A的左邊，得到A^*B和B^*A，再檢驗B和A中與A^*和B^*中重復的點將它們刪去，得到兩個新的解，并保證每個解中，對全部取貨點和送貨點不遺漏也不重復。設交叉概率p_C=C。

4.7重組變異

設重組變異的概率p_M=M，應滿足：

p_C+p_M=1（4）

重組變異時，將進行交換、逆轉和插入。設交換概率p_S=S，逆轉概率p_R=R，插入概率p_I=I。應滿足：

p_S+p_R+p_I=1（5）

將一個解中任選兩點進行如下操作：

（1）交換。交換兩點位置。

（2）逆轉。將兩點間所有點的排列順序逆轉。

（3）插入。將排在左邊的點移動到右邊點的右邊。

4.8選擇種群中的最優解

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

4.9循環迭代

種群經過二元競標，交叉和變異之后得到新的種群。將新種群中個體適應度最大，即種群中最優的解選出得到第一代最優解。將新種群再經上述二元競標，交叉和變異后得到第二代最優解。

循環迭代上述操作（4.5～4.8）直到沒有更優解出現或達到預設上線M次。

具體優化求解流程如圖3所示。

5算例分析

圖4為3×4個街區組成的服務社區。街道間距單位為1km，即社區南北寬3km，東西長4km。設外賣騎手在某一時間段內，收到了10個訂單，即有10個取貨點和10個對應送貨點，以任一取貨點為起點開始求解完成任務的總路程及所需時間。

圖4中，圓圈（1，2，…，10）為訂單（1，2，…，10）的取貨點，方框（1，2，…，10）為對應的送貨點。為求解方便，取貨點用（1，2，…，10）表示，送貨點用（11，12，…，20）表示，如圖5所小。則構成初始基因染色體種群為（1，2，…，20）。設定最左下角點20的坐標位置為（0，0），合成表達后的（1，2，…，20）各點坐標為：（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）}，各點間的距離見表1。

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

按“算法設計”的流程求解，求解迭代過程如圖7 所示，求得最優路線圖如圖8所示，最佳里程為19。

最優解路徑順序為：

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

假設快遞員平均時速20km，則需要大約57min，即一個小時以內可完成10個訂單配送，滿足一個小時完成全部訂單的目標要求。

本算例沒有考慮到實際取送貨時的等待時間，但設每個街區街道間距為1km，10個訂單覆蓋3×4=12km²的社區，其服務距離超過實際服務范圍，所求解有一定的可信度。

考慮兩個極端情況作為對照：（1）當外賣騎手按照順序將外賣訂單全部取完再送，則總路程為49.3，總時間約需要150min。（2）如果按照取一個送一個的順序，總路程為44.9，總時間需要約135min。由此可見，使用本算例采用的算法給出的優化解極大地縮短了配送時間，可大大提高配送效率、節約人力成本。

6結語

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

本文所考慮的情形還相對簡單，未來會考慮帶時間窗限制條件下多車協同完成的調度和路徑規劃等更復雜情況下的建模，也會利用更先進的智能算法來求解。

[參考文獻]

[1]艾媒咨詢.外賣行業數據分析：2020年中國外賣行業市場規模達6 646.2 億元[EB/OL].（2021-04-13）[2021-10- 08].http：//k.sina.com.cn/article_1850460740_6e4bca440_ 2000sqad.html.

[2]賴祐萱.外賣騎手困在系統里[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]徐倩倩.考慮商家出餐時間的外賣路徑優化[D].上海：東華大學，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，FURUTA 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，FLOUDAS 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]徐興，錢譽欽，趙蕓，等.基于改進蟻群算法的立體倉庫三維空間路徑優化[J].計算機集成制造系統，2021，27（1）：206-213.

[17]王文杰，孫中苗，徐琪.考慮社會配送供應能力的眾包物流服務動態定價模型[J].管理學報，2018，15（2）：293-300.

[18]方婷.眾包物流的風險與對策：以三家眾包物流平臺為例[J].中國管理信息化，2018，21（23）：151-152.

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