基于自營式外賣的配送路徑優化問題

◇南京農業大學信息管理學院 王淑雅

近年來外賣行業迅速發展，在快消費時代引起了一股浪潮，然而隨著外賣業的發展，如何提升外賣服務業的水平也成了熱門話題，其中外賣配送路徑的優化問題有為重要，其直接影響到了顧客體驗以及配送成本。本文主要針對商家自營式外賣配送形式，立足于實際案例，通過TSP規劃求解以及節約算法解決單配送車輛不考慮載重、多配送車輛考慮載重、多配送車輛考慮載重與時間窗的外賣配送路徑優化問題，并對三種方案進行對比，分析其可行性進而實際解決某餐廳的外賣配送路徑設計問題。

配送問題一直都是各生產企業、物流企業所關心的問題，商品的運輸與配送是從連接市場與消費者，實現商品價值的重要步驟。隨著經濟形式的多樣化，末端配送已經隨處可見，在當下熱門的外賣行業中，配送直接影響著外賣行業的成本以及顧客的滿意度，其中成本包括時間成本、油耗成本等，而顧客的滿意度主要體現在外賣是否能夠準時安全到達上，所以無論從商家角度還是顧客角度實現配送路徑更加優化都是至關重要的。

1 背景介紹

1.1 我國外賣現狀

隨著“互聯網+”商業模式的迅速發展，互聯網餐飲行業也得到了快速的發展，其中外賣在全國餐飲消費總額的比重越來越大。據統計，2014年，全國餐飲消費總額數為4500億元，按照16%的餐飲年增幅，2016年全國餐飲消費總額預計將達到7000億元。其中，外賣占去拿過餐飲消費總額的10%，截止2016年，外賣市場規模預計將要達到700億元[1]。近年來，眾多的外賣APP也在搶占市場，其中最具有代表性的有“美團”、“餓了么”、“百度外賣”等外賣平臺，這些平臺的構建反過來也促進了外賣行業的發展，外賣行業不斷壯大已經成為了必然趨勢。具體情況如表1所示[1]。

表1 我國互聯網外賣商家現狀

隨著外賣需求的不斷增加，對外賣服務質量的要求也進一步提升，其中外賣配送作為外賣行業的重要環節受到了各大平臺以及顧客的廣泛關注。在配送過程中配送路徑的選擇決定了配送的時間，進而直接決定了外賣服務的質量。而在現實生活中配送員選擇配送路徑往往都是通過經驗進行主觀判斷，這樣不僅會導致配送效率低下，更有可能造成配送時間不在規定范圍，產生等待成本或者懲罰成本，使顧客的滿意度受到印象，進而影響提供商的品牌效應，因此對配送路徑進行優化是非常重要的。

1.2 商家自營式外賣配送形式

目前主流的配送形式主要有：商家自營配送、雇傭配送員配送、外賣平臺配送。本文的主要介紹自營式外賣配送形式。所謂商家自營配送就是點餐者從消費端下單后，經由外賣平臺傳達至商家，商家承擔起了備餐、配送的任務，將包裝好的食物送至點餐者手中。大多數商家位于配送需求點附近，配送者對配送路線十分了解，在配送過程中會選擇最為“經濟”的路線，用最短的時間配送最多的單數。這種配送方式帶給消費者的體驗因商家而異，配送效率越高的商家，消費者對于此次消費的體驗相對更滿意[2]。

這種配送形式的主要特點是由商家直接配送，即商家派出配送員進行若干配送點的配送，配送員完成配送任務后要返回商家，是一個閉環線路的配送問題。商家自營式外賣配送的優點在于配送員只需要在一個商家處取貨，取貨形式相對簡單，出發點與終點固定。目前這樣的配送方式主要應用于公司或者學校附近這樣外賣需求較大的地段。

1.3 研究內容

本文基于外賣現狀的大背景下，針對商家自營式外賣這一具體外賣配送形式進行研究，主要解決自營式外賣的外賣配送線路優化問題，幫助其擺脫“經驗模式”，而可以通過實際的運算分析得到科學的配送路徑，以高效率地服務顧客，滿足顧客需求，同時盡可能地降低時間成本。

本文主要解決三大問題：

（1）通過TSP規劃問題EXCEL求解法求解單車輛、無載重約束下的配送路徑優化方案。

（2）通過節約算法通過EXCEL求解有載重約束條件的配送路徑優化方案，并求解出所需要的配送車輛數。

（3）在（2）的基礎上考慮時間窗約束，對節約算法進行深化求解時間窗與載重同時約束下的配送路徑優化方案與所需配送車數量。

在求解三種情況下的配送路徑優化方案后進行對比，總結各自的優缺點，進而說明優化方案的可行性。

2 案例分析

2.1 案例介紹

本文所研究的案例背景來源于翟勁松[3]論文中的實例，以下數據均來自該論文。以某餐廳（編號0）為背景，在某天11:30到12:30時間段內對其9個配送點（編號1到9）進行外賣配送服務，已知各配送點之間的配送時間和到商家之間的行駛時間如表2所示。

表2 各點之間的行駛時間

已知各顧客點的需求量以及顧客點需求的時間窗如表3所示，且商家所擁有的配送車輛最大載重量為15份。

表3 各點的需求量和時間窗

2.2 問題解析

本文設定該餐廳為自營配送式餐廳，采用商家自行配送的方法，商家在接到訂單后派出配送員對9個顧客需求點進行配送，配送完畢后回到商家處。本文所要解決的問題即如何科學合理的規劃配送路徑，使得商家可以以最低的成本獲得最大的效益，同時顧客可以達到期望的滿意度。

本文采取層層推進的邏輯方式，首先對于該問題進行最簡單的巡回路徑規劃，即TSP問題規劃，在一輛配送車輛無時間限制、裝載限制的條件下進行不重復的路徑配送，遵循單回路、單一性、遍歷性的原則設計配送路線。其次，在配送車輛具有裝載容量限制的情況下，規劃多配送車輛多回路的配送輛路徑，并可以求得適當的配送車輛數。最后在考慮時間窗于長在容量的情況下，即使得客戶滿意度最高的情況下進行配送路徑規劃，求得所需要的配送車輛以及各個點到達的具體時間，并對三種結果進行對比得出有關配送路徑優化的最終結論。

3 優化方法

3.1 TSP問題路徑優化法

TSP（TravelingSalesman Problem）自1959年提出已經過去了半個多世紀，TSP問題是一個NP難問題，目前為止都沒有一種高效且精準地求解方法。高效精準地求解TSP問題在車輛路徑規劃、O20物流配送等很多領域都有著非常重要的意義。TSP問題的目標是在一系列點集中尋找一條最短回路,并要求每個點只訪問一次，目前主要的求解方法為啟發式智能算法,如遺傳算法、蟻群算法和蝙蝠算法等[4]。

由于本文所解決的問題相對來說較為簡單，所涉及到的顧客點較少，因此可以直接通過混合整數線性規劃算法求解，用EXCEL構建規劃求解模型配以適當的約束條件即可。

3.2 節約算法

節約算法又稱為節約里程算法，是在滿足某些約束條件下將兩個以上的回路合并成一個回路后實現總的運輸距離縮短的方法。這種方法可以解決在車輛數目不確定的配送路線的優化問題，可以解決共同配送給中路徑、人員等問題[5]，在路徑優化問題中有著廣泛的應用。

其思路為，假設P點為配送中心，A和B是兩個需求點，PA的距離為a，P-B的距離為b，A-B的距離為c。在初始情況下P分別對A和B進行配送，即從P-A-P，所需要的距離為2a，從PB-P，所需要的距離為2b。而此時如果將A-B連接，即A和B不需要單獨配送，而通過一次配送就滿足，那么路徑就改變為PA-B-P，所需要的距離為a+b+c。此時需要比較2a+2b與a+b+c之間的數量大小關系。假設不考慮載重量的問題，當2a+2b>a+b+c時則采用第二種配送路徑，當2a+2b

圖1 節約算法思路圖

節約算法的主要步驟為：①計算各個需求點之間的最短距離；②使用節約里程法進行計算。兩個需求點之間的節約里程為兩個需求點與配送點之間的距離之和減去兩個需求點之間的最短距離；③對節約里程數進行排序；④形成初始解。在滿足車輛限載、客戶需求量大小、時間限制等等所有條件的限制下，根據第一步的得到的最短路徑，進行配送點與需求點之間一對一直達配送，計算得出總里程數；⑤對回路進行合并，得出路徑優化方案。從節約里程排序中找出產生該節約里程的兩個配送點i、j，再判斷連接 i、j的回路是否存在合并的可能性。如果一個回路是以（p，i）開始，最后以（j，p）結束，同時滿足車輛配載，時間因素等多種限制，那么這個回路可以進行合并。刪除兩個回路中的部分路徑，然后引入新的連接（i，j），得到新的回路（p，...，i，j，...，p）。重復上述過程直至沒有回路形成，從而得出路徑優化；⑥確定路徑優化的最優方案。重復上述的合并過程，得出多種路徑優化的方案并進行對比，得出最優方案。

4 優化方案

4.1 單配送車輛不考慮載重優化方案

本文首先不考慮配送車輛的載重量以及其他約束條件，假定該餐廳僅有一輛配送車輛的情況下想要實現對所有顧客需求點進行配送，在該情況下設計相應的路徑優化方案。

根據案例背景建立模型如下：

對上述模型用EXCEL進行規劃求解，求解約束設置如下，并得到最終的求解結果為配送路徑為0-2-1-8-3-7-6-5-9，所需要的配送總時間為71min，載重量36份，所需時間較長，無法及時滿足顧客的所有需求。

圖3 EXCEL求解結果

4.2 多配送車輛考慮載重優化方案

本小節主要討論多配送車輛且有載重約束的優化方案，通過案例背景已知配送車輛載重上限為15，也就是說每輛配送車輛最多職能一次性裝載15份外賣，如果該配送車輛路徑上的外賣需求量超過了15則需要另一輛配送車輛進行配送。本小節主要通過節約算法對配送車輛的路徑進行規劃，并且求解出在該需求背景下該餐廳需要配置多少輛配送車輛。

約值按照降序的方式進行排序，具體如下所示。

首先在表2的基礎上計算連接各需求點的節約值并對這些節

表4 各需求點連線節約值

表5 節約值排序

由該表可以看出，一些連接點的節約值為負數，即對這兩各需求點進行連接不但不會減少配送時間還會增加配送時間，這顯然是不可行的，因此對節約值為負數的連接點可以直接不予考慮。

按照節約值的大小，即上表的順序依次判斷各連接點是否滿足節約算法的連接規則，即是否在同一條線路上，是否與基點，即餐廳0相鄰，得到最終的配送路徑規劃如下所示。

圖4 多車輛考慮載重情況下的配送路徑優化圖

根據配送路徑優化圖可以得到在該配送方式下需要3輛配送車輛同時配送，配送路線分別為0-2-1-8-7-0，0-3-6-0，0-4-9-5-0，所需時間分別為45，23，26，由于同時配送所以所需時間為45，各配送車倆的載重量均為50%以上，具體數值如下表所示。

表6 多車輛考慮載重情況下配送路徑優化結果

4.3 多配送車輛考慮載重與時間窗的優化方案

除了考慮載重量與車輛這些硬件設備，即商家所必須的設備外，不可忽視的是顧客滿意度，而顧客滿意度衡量的指標即為是否在規定的配送時間內收到外賣。在實際生活中我們常?？梢栽O置外賣具體在某一規定時間送達，遲到或者早到都是不可以的，正如案例中所給出的顧客需求一般，于是在4.2的基礎上本小節主要考慮了時間窗的限定利用節約算法再次進行求解。雖然考慮了時間窗，但是節約算法的本質是沒有改變的，只是在原來的基礎上除了載重這一限定條件外計算時間，只有在時間窗內才可以連接兩需求點，并且由于考慮了時間窗因素此時在同一路徑上的配送具有先后順序，不可顛倒，節約值與排序同4.2，這里不再贅述。

根據案例所給出的數據，本文假定在每一個配送點的逗留時間為2min，即配送員將外賣送至地點后聯系顧客等待顧客收取外賣需要2min的時間。11:30為初始配送時間0，依次類推，在初始時刻，當配送車輛從餐廳到往任務點i時，若則若t0i=ETi， 取Si=ETi其中ETi表示該需求點的最早可接受外賣時間，LTi表 示該需求點最晚可接受外賣的時間，Si為外賣到達的時間，根據此規則可以得到初始情況如下。

表7 各配送點的特征與要求

在該表的基礎上通過節約算法進行計算，計算過程以及結果如下所示。

圖5 節約算法計算流程圖

圖6 多配送車輛考慮載重與時間窗的配送路徑

根據配送路徑的優化結果可以得到在該種配送方式下以共需要5輛配送車輛，才能滿足配送需求，使得各個配送點都不會出現提前或者推遲的情況，配送路線分別為7→8，2→4→9，1→6，3，5，配送時間分別為33，25，38，7，25，由于各配送線路同時配送故整體配送完成需要時間為38min，然而為了滿足時間窗，在規定時間內送達，單跳線路的整體載重率不高，載重存在浪費現象，具體配送路徑設計情況如下表。

表8 多配送車輛考慮載重與時間窗的配送路徑優化結果

4.4 方案對比

通過4.1～4.3三種情況下的配送方案對比可以直觀看到各方案下所需要的配送時間、配送路徑、載重量等數據如下表所示。

表9 方案對比表

從上表中可以清晰看出，方案1配送路徑最少，所需時間最多，所需車輛最少，方案二平均載重率最高，方案三配送路徑數最多，平均載重率最低，所需車輛數最多。

由此可得，為了滿足時間窗的需求，使得所有的顧客都可以在期望的時間內收到外賣會使得載重率與車輛數增多，即會使得經營成本增加，而只使用一輛配送車輛是不可行的，其所需要的時間等相關特征值均不具有優勢，如果不考慮時間窗多配送車輛的載重率與所需車輛數都較為理想。

從方案對比中也可以看出物流問題中的效益背反理論，為了給顧客提供更加高質量的需求就必須要浪費一定的車輛資源，這是一個此消彼長的過程，關鍵在于商家該怎樣決策，從長遠的角度看顧客的滿意度是企業是否能夠經營下去的關鍵，適當的資源浪費是合理的，故方案3最為合理。

5 結語

本文主要以實際案例為背景，通過TSP求解算法與節約算法從三個方面提出了不同的外賣配送路徑的具體優化方案，并進行了對比，從而分析不同約束條件下的不同配送路徑優化方案，并從實際的角度簡要分析了方案的可行性，為該餐廳提出了可行的配送指導方案，提高了該餐廳的市場競爭力與顧客服務水平，對相關的外賣行業也可以進行進一步的引申應用。