劉旺盛，吳球軍，嚴(yán)浩洲，敬添俊

(1.集美大學(xué)現(xiàn)代物流研究中心，福建 廈門 361021；2.荊門職業(yè)學(xué)院機(jī)電與信息工程學(xué)院，湖北 荊門 448000)

0 引言

快餐外賣在生活中扮演著越來越重要的角色，已成為餐飲行業(yè)發(fā)展的新生力量。經(jīng)歷過萌芽期、發(fā)展期、擴(kuò)張期之后，快餐行業(yè)正在邁入一個(gè)較為穩(wěn)定的階段，即成熟階段，各企業(yè)間的競爭已開始向提高服務(wù)質(zhì)量，以及降低配送成本方向轉(zhuǎn)變，越來越多的外賣行業(yè)開始著眼于配送服務(wù)與客戶滿意方面的優(yōu)化[1]。顧客除了關(guān)注與外賣產(chǎn)品本身品質(zhì)與口味以外，更加注重時(shí)效問題，也就是配送時(shí)效，很多企業(yè)為了搶占市場，提出了一定時(shí)間范圍內(nèi)送達(dá)的服務(wù)承諾。時(shí)效通常是依據(jù)顧客的預(yù)定時(shí)間與顧客心理預(yù)期綜合設(shè)定的。送達(dá)的時(shí)間延遲越嚴(yán)重，該次配送服務(wù)的顧客滿意度就會(huì)越低。因此，商家希望能尋找到較優(yōu)的配送路線，實(shí)現(xiàn)總耗時(shí)或路程最短。由此可見，外賣配送中的車輛路徑問題(vehicle routing problem,VRP)屬于帶時(shí)間窗的車輛路徑問題。

車輛路徑問題(vehicle routing problem,VRP)由Dantzig和Ramser[2]首次提出，在實(shí)際中應(yīng)用廣泛，關(guān)鍵參數(shù)不確定和需求有服務(wù)時(shí)間窗這兩種情況研究得最多。

不確定參數(shù)下的VRP,研究方向主要集中于兩類：一類是僅概率分布已知或關(guān)鍵參數(shù)未知的隨機(jī)VRP，最常見的是顧客需求是隨機(jī)的，Tillman等[3-6]對此類問題進(jìn)行了研究，提出了一些模型和求解算法。另一類是關(guān)鍵參數(shù)與時(shí)間相關(guān)的動(dòng)態(tài)車輛路徑問題(dynamic vehicle routing problem,DVRP)，最常見的是顧客需求是隨時(shí)間動(dòng)態(tài)變化的，Hvattum[7]等吸收了隨機(jī)信息，發(fā)現(xiàn)可以改進(jìn)求解質(zhì)量；李兵等[8]對于集貨過程中隨時(shí)有客戶提出服務(wù)請求，或客戶地址發(fā)生變化的DVRP，通過引入虛擬任務(wù)點(diǎn)將其轉(zhuǎn)化為靜態(tài)VRP求解；張景玲等[9]提出了2-OPT量子進(jìn)化算法求解車輛實(shí)時(shí)配送過程中又有新客戶加入的問題；Azi等[10]著重探討了多路徑DVRP下新客戶的服務(wù)請求接受規(guī)則，以是否盈利作為判斷準(zhǔn)則。

帶時(shí)間窗的VRP研究分為軟時(shí)間窗和硬時(shí)間窗兩種。在軟時(shí)間窗情形下，早到或者晚到是允許的，不過有懲罰成本[11-21]；但硬時(shí)間窗條件下，早到或晚到是不允許的[13]。牛群[14]針對硬時(shí)間窗條件，設(shè)計(jì)了改進(jìn)型煙花算法求解；Larsen[15]首次將時(shí)間窗與車輛路徑問題相結(jié)合；Ahmmed[16]等提出多重蟻群優(yōu)化算法求解DVRPTW(dynamic vehicle routing problem with time window)；王萬全[17]等構(gòu)建了軟時(shí)間窗多配送中心VRP問題的數(shù)學(xué)模型，設(shè)計(jì)了混合3-OPT量子進(jìn)化算法進(jìn)行求解；Hong[18]等將時(shí)間劃分成長度相等的時(shí)間片，采用事件驅(qū)動(dòng)機(jī)制將動(dòng)態(tài)問題轉(zhuǎn)化為靜態(tài)問題；張文博[19]等也將動(dòng)態(tài)問題轉(zhuǎn)化為多個(gè)瞬時(shí)靜態(tài)問題，以提升服務(wù)準(zhǔn)時(shí)性和最小配送成本為目標(biāo)，采用模擬退火算法求解；翟勁松等[20]也采用時(shí)間切片原則，將時(shí)間均勻劃分，以配送時(shí)間最短為目標(biāo)，運(yùn)用遺傳算法得出最優(yōu)配送路徑；李桃迎等[21]基于同時(shí)送取貨VRP問題的求解策略,引入時(shí)間懲罰成本，衡量外賣配送超出時(shí)間窗的情況,引入k-means，對“商家-客戶”進(jìn)行聚類,同一類設(shè)計(jì)“商家-客戶”遺傳算法求解；李常敏等[22]基于每個(gè)顧客對服務(wù)時(shí)間感知度不同，建立了基于顧客時(shí)間滿意度的車輛配送模型，并利用模擬退火算法編程求解。

從現(xiàn)有文獻(xiàn)看，目前帶時(shí)間窗的VRP基本是采用懲罰成本的方式，研究硬時(shí)間窗的少，且現(xiàn)有DVRPTW研究多是采用對時(shí)間進(jìn)行均勻切片的方法轉(zhuǎn)化為靜態(tài)VRP求解，現(xiàn)實(shí)中也是采用固定時(shí)間截單的做法，這種簡單以固定時(shí)長切片的方法實(shí)際上損失了很多優(yōu)化機(jī)會(huì)。本文擬杜絕固定時(shí)間截單這種將動(dòng)態(tài)問題簡化為靜態(tài)問題求解的方法，盡可能等待更多訂單進(jìn)來，直到有訂單采用直接配送才可能滿足硬時(shí)間窗要求才出發(fā)，該訂單作為第一個(gè)服務(wù)客戶，回程再配送其他滿足硬時(shí)間窗要求的訂單，避免陷入局部最優(yōu)，且方案隨時(shí)間推移滾動(dòng)執(zhí)行，實(shí)現(xiàn)真正意義上的“動(dòng)態(tài)”求解。

1 問題及模型

1.1 問題定義

該問題可定義為：一家提供外賣配送服務(wù)的餐飲店，不斷有客戶下單，并要求在一定的時(shí)間范圍內(nèi)送達(dá)，每筆訂單有一定的訂購量，那么店家該如何實(shí)施配送，使所有訂單在顧客要求的時(shí)間范圍內(nèi)送達(dá)，又使配送成本最小。

為方便問題求解，做以下簡化與假設(shè)。

1)車輛行駛速度。參照實(shí)際情況，配送車輛通常為電動(dòng)車或者摩托車，在模型中將行駛速度統(tǒng)一設(shè)置為定值，即不考慮路況等外界因素干擾。

2)外賣加工時(shí)間。外賣為主的餐飲店在實(shí)際的運(yùn)營中，通常會(huì)提前備餐，加工時(shí)間較短；另一方面，當(dāng)顧客訂購的餐品加工需時(shí)較長時(shí)，店家會(huì)向顧客提前申明，服務(wù)時(shí)間窗會(huì)自動(dòng)延長，故在此模型中不考慮備餐時(shí)間，即假設(shè)下單時(shí)餐品已加工完成。

3)配送人員充足。假設(shè)有足夠的配送人員，只要系統(tǒng)發(fā)出配送指令，就有配送員前去執(zhí)行。

4)訂單交接時(shí)間。實(shí)際配送中，外賣送達(dá)客戶要求的地點(diǎn)后，一般交接時(shí)間很短，但有時(shí)需要等待一定時(shí)間，即送達(dá)后交付時(shí)間有波動(dòng)，本文采用比較低的行駛速度將這些波動(dòng)考慮進(jìn)來，不考慮等待時(shí)間。

5)時(shí)間精度。下單時(shí)間、要求送達(dá)時(shí)間、實(shí)際送達(dá)時(shí)間都采用向下取整，如某訂單的送達(dá)時(shí)間為11點(diǎn)55分11秒，取11點(diǎn)55分；行駛時(shí)間采用向上取整，如兩相鄰配送客戶距離相差700 m，當(dāng)車速為500 m/min時(shí)，則需行駛1.4 min，此時(shí)向上取整為2 min。

1.2 模型構(gòu)建

外賣店所在地和訂單需求點(diǎn)構(gòu)成一個(gè)有向圖G=(V，A)，其中：V是點(diǎn)集，V={V0，V1，…，Vn}，V0為外賣店所在地，即配送點(diǎn)，其他各點(diǎn)均為需求點(diǎn)；A是各點(diǎn)間路線的集合，A=(i，j)i,j∈V且i≠j，線路(i，j)的距離記為dij。

每趟配送最大裝載量均為q(gi≤q)，需要的總配送次數(shù)為M，配送速度為定值v，S為集合N的任意子集，|S|表示S中的元素個(gè)數(shù)。

數(shù)學(xué)模型構(gòu)建如下：

2)目標(biāo)函數(shù) 該模型的目的是尋找配送成本最小的配送方案，在配送過程中，成本的主要影響因素為行駛路程，所以目標(biāo)函數(shù)為總的行駛路程最短

3)約束條件：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 不定時(shí)間截單求解算法設(shè)計(jì)

算法的目的在于尋求成本最小的配送方案，需要做出的決策包括：哪些訂單安排同一趟配送；每趟的發(fā)車時(shí)間以及配送員執(zhí)行配送任務(wù)的具體行走路徑。

算法分兩步：第一步為訂單信息確認(rèn)；第二步為路徑規(guī)劃。首先將配送時(shí)間盡量后移，直至待配送訂單中有訂單需要直送才不超出時(shí)間窗要求時(shí)開始規(guī)劃路線，以求盡可能多地確認(rèn)需求信息，避免陷入局部最優(yōu)，然后采用最近插入法進(jìn)行路徑規(guī)劃。

相關(guān)符號(hào)定義如下：

具體算法步驟如下：

5)在N中找一個(gè)離新加入配送線路Lk最近的點(diǎn)j，然后在Lk的配送回路中找一個(gè)弧rp(rp≠0i，因?yàn)榫€路Lk是在i最晚出發(fā)時(shí)間發(fā)車，若插入其他點(diǎn)，i的送達(dá)時(shí)間將達(dá)不到要求)，使弧的兩端節(jié)點(diǎn)到點(diǎn)j的距離之和減去弧長的值，即Δ=drj+djp-drp最小，若存在這樣的多個(gè)點(diǎn)和多條弧，則按“先下單先配送”的原則選擇；

8)重復(fù)第5至第7步，直至N中所有的點(diǎn)均已加入Lk或確認(rèn)無法加入Lk中，配送發(fā)車。

3 實(shí)例驗(yàn)證

采用一外賣店中午11:00—12:00的實(shí)際訂單,訂單數(shù)據(jù)如表1所示。

表1 某外賣店11:00—12:00時(shí)間段內(nèi)訂單數(shù)據(jù)

外賣點(diǎn)及各需求點(diǎn)位置分布如圖1所示。其中：點(diǎn)0表示外賣店所在地址；1～13為客戶需求點(diǎn)，客戶1和6位置重合。

在訂餐平臺(tái)下單的“顧客預(yù)計(jì)等待時(shí)間”一般為30～60 min，此例取40 min，那么要求送達(dá)時(shí)間均在下單時(shí)間上往后推40 min。

配送員騎電動(dòng)車，設(shè)配送速度v為500 m/min。據(jù)調(diào)查，每趟能攜帶的餐盒數(shù)最大為50盒，在需要滿足硬時(shí)間窗的前提下，基本上很難出現(xiàn)達(dá)到裝載上限的情況，因此本例將各點(diǎn)需求量忽略。

按照算法流程，該例具體求解步驟如下：

5)在N中找到離L1回路最近的需求點(diǎn)6，根據(jù)最近插入法尋找最近的弧插入，即(1,0)和(0,1)兩段弧，兩段弧插入點(diǎn)6后增加值均為0，按下單先后規(guī)則，訂單1應(yīng)先于訂單6配送，故考慮插入弧(1,0)；

8)在N中找到離L1最近的需求點(diǎn)10，若將該點(diǎn)插入L1中的弧(6,0)，弧長增加值最小，為600 m；

11)多次重復(fù)算法第5-7步，L1更新為{0,1,6,5,4,10,3,9,7,8,0}，N更新為{2,11}；

12)重復(fù)執(zhí)行第5步，此時(shí)N中離L1回路最近的點(diǎn)為2，插入弧(7,8)和(9,7)，使回路增加均為最小值3 200 m，按先下單先配送的規(guī)則，將點(diǎn)2插入(9,7)間；

13)判斷點(diǎn)2和之后的點(diǎn)預(yù)計(jì)到達(dá)時(shí)間是否符合要求，若將點(diǎn)2插入弧(9,7)，回路變?yōu)閧0,1,6,5,4,10,3,9,2,7,8,0}，點(diǎn)2預(yù)計(jì)到達(dá)時(shí)間為12:18，不符合要求，不能將點(diǎn)2加入L1；

14)接下來考慮點(diǎn)11，同理將點(diǎn)11插入L1，使回路增加值最小的位置也是弧(9,7)，若將點(diǎn)11插入此位置，點(diǎn)11和其后的所有需求點(diǎn)的預(yù)計(jì)送達(dá)時(shí)間都能滿足服務(wù)時(shí)間窗要求，因此點(diǎn)11能插入L1，至此N中所有的點(diǎn)均已考慮，開始配送發(fā)車，最終子回路L1為{0,1,6,5,4,10,3,9,11,7,8,0}，最晚發(fā)車時(shí)間為11:50，當(dāng)前N為{2}；

配送線路如圖2所示。

表2 不定時(shí)間截單和固定時(shí)間截單結(jié)果對比

由表2看出，本文設(shè)計(jì)的不定時(shí)間截單算法遠(yuǎn)遠(yuǎn)優(yōu)于實(shí)際中采用的固定時(shí)間截單算法，可以節(jié)省一趟配送人力成本，行使的總距離也遠(yuǎn)遠(yuǎn)小于固定時(shí)間截單算法。不過為了滿足硬時(shí)間窗要求，配送行走總距離相對無時(shí)間窗要求下會(huì)大很多。

4 結(jié)論

本文基于硬時(shí)間窗的約束條件，對待配送訂單的分配問題、配送順序問題進(jìn)行研究，建立了數(shù)學(xué)模型，并設(shè)計(jì)了不固定時(shí)間截單算法。通過與實(shí)際固定時(shí)間截單做法的比較，證明不固定時(shí)間截單可以有效降低配送人力和成本。此外，需要說明的是：首先算例數(shù)量、訂單容量不夠龐大，一定程度上對算法效果的驗(yàn)證存在一定的影響；其次，對問題做了簡化處理，如假定配送員人數(shù)充足、配送速度為平均行駛速度、餐品加工時(shí)間不計(jì)等。在實(shí)際中，會(huì)出現(xiàn)配送人員不夠的情形，每種餐品加工時(shí)間不同，不同路段和時(shí)段、不同配送員行駛速度也存在差異等情況，將來可以考慮這些實(shí)際情況和因素，進(jìn)行更為深入地研究和分析。