帶硬時間窗的外賣配送車輛路徑問題

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

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

0 引言

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

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

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

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

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

1 問題及模型

1.1 問題定義

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

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

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

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

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

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

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

1.2 模型構(gòu)建

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

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

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

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

3)約束條件：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

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

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

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

具體算法步驟如下：

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

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

3 實例驗證

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

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

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

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

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

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

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

8)在N中找到離L1最近的需求點10，若將該點插入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步，此時N中離L1回路最近的點為2，插入弧(7,8)和(9,7)，使回路增加均為最小值3 200 m，按先下單先配送的規(guī)則，將點2插入(9,7)間；

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

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

配送線路如圖2所示。

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

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

4 結(jié)論

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