基于自營式外賣的配送路徑優(yōu)化問題

◇南京農(nóng)業(yè)大學(xué)信息管理學(xué)院 王淑雅

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

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

1 背景介紹

1.1 我國外賣現(xiàn)狀

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

表1 我國互聯(lián)網(wǎng)外賣商家現(xiàn)狀

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

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

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

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

1.3 研究內(nèi)容

本文基于外賣現(xiàn)狀的大背景下，針對商家自營式外賣這一具體外賣配送形式進(jìn)行研究，主要解決自營式外賣的外賣配送線路優(yōu)化問題，幫助其擺脫“經(jīng)驗?zāi)Ｊ健?，而可以通過實際的運算分析得到科學(xué)的配送路徑，以高效率地服務(wù)顧客，滿足顧客需求，同時盡可能地降低時間成本。

本文主要解決三大問題：

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

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

（3）在（2）的基礎(chǔ)上考慮時間窗約束，對節(jié)約算法進(jìn)行深化求解時間窗與載重同時約束下的配送路徑優(yōu)化方案與所需配送車數(shù)量。

在求解三種情況下的配送路徑優(yōu)化方案后進(jìn)行對比，總結(jié)各自的優(yōu)缺點，進(jìn)而說明優(yōu)化方案的可行性。

2 案例分析

2.1 案例介紹

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

表2 各點之間的行駛時間

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

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

2.2 問題解析

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

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

3 優(yōu)化方法

3.1 TSP問題路徑優(yōu)化法

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

由于本文所解決的問題相對來說較為簡單，所涉及到的顧客點較少，因此可以直接通過混合整數(shù)線性規(guī)劃算法求解，用EXCEL構(gòu)建規(guī)劃求解模型配以適當(dāng)?shù)募s束條件即可。

3.2 節(jié)約算法

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

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

圖1 節(jié)約算法思路圖

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

4 優(yōu)化方案

4.1 單配送車輛不考慮載重優(yōu)化方案

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

根據(jù)案例背景建立模型如下：

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

圖3 EXCEL求解結(jié)果

4.2 多配送車輛考慮載重優(yōu)化方案

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

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

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

表4 各需求點連線節(jié)約值

表5 節(jié)約值排序

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

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

圖4 多車輛考慮載重情況下的配送路徑優(yōu)化圖

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

表6 多車輛考慮載重情況下配送路徑優(yōu)化結(jié)果

4.3 多配送車輛考慮載重與時間窗的優(yōu)化方案

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

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

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

在該表的基礎(chǔ)上通過節(jié)約算法進(jìn)行計算，計算過程以及結(jié)果如下所示。

圖5 節(jié)約算法計算流程圖

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

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

表8 多配送車輛考慮載重與時間窗的配送路徑優(yōu)化結(jié)果

4.4 方案對比

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

表9 方案對比表

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

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

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

5 結(jié)語

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