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

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

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

1 背景介紹

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

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

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

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

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

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

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

1.3 研究?jī)?nèi)容

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

本文主要解決三大問題：

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

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

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

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

2 案例分析

2.1 案例介紹

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

表2 各點(diǎn)之間的行駛時(shí)間

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

表3 各點(diǎn)的需求量和時(shí)間窗

2.2 問題解析

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

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

3 優(yōu)化方法

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

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

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

3.2 節(jié)約算法

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

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

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

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

4 優(yōu)化方案

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

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

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

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

圖3 EXCEL求解結(jié)果

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

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

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

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

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

表5 節(jié)約值排序

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

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

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

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

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

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

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

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

表7 各配送點(diǎn)的特征與要求

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

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

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

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

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

4.4 方案對(duì)比

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

表9 方案對(duì)比表

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

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

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

5 結(jié)語

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