隨機需求連鎖餐廳聯(lián)合配送規(guī)劃仿真研究

蔣 磊， 李曉明

（1 南京開放大學(xué) 裝備與信息技術(shù)處， 南京 210000； 2 三江學(xué)院 計算機科學(xué)與工程學(xué)院， 南京 210012）

0 引 言

隨著“互聯(lián)網(wǎng)+電子商務(wù)”模式的不斷發(fā)展，網(wǎng)上購物、網(wǎng)上訂餐逐漸成為一種趨勢，餐飲外賣行業(yè)為人們的日常飲食提供便利。 餐飲外賣商家的線上訂單分配與處理、物流派送是快餐配送網(wǎng)絡(luò)的核心環(huán)節(jié)，屬于NP-hard 問題。 餐飲外賣企業(yè)訂單處理與派送的主要特點在于：訂單是隨機產(chǎn)生的；訂單數(shù)量在一定時間段內(nèi)較為密集；訂單的空間分布呈輻射狀規(guī)律；連鎖餐廳之間存在訂單和派送員的相互調(diào)度問題；物流成本和履約率約束；訂單合并問題等。 這些問題使得連鎖快餐訂單分配和派送員調(diào)度規(guī)劃十分復(fù)雜［1］。 訂單信息的整理與分配、派送員派送路徑規(guī)劃是快餐業(yè)務(wù)網(wǎng)絡(luò)中的2 個重要環(huán)節(jié)，是一個有機整體。 通常一個快餐店的派送員數(shù)量是恒定的，訂單量大、分布復(fù)雜時，派送員的需求量增加。 而派送員均處于派送途中且回程時間均不能滿足顧客需求時間時，快餐店不得不停止接單。 所以訂單的分配與派送規(guī)劃是相互制約的，這種矛盾性就要求快餐店研究隨機需求下，派送員聯(lián)合配送模式，實時地進行訂單分配與物流派送優(yōu)化，并研究訂單合并、增加派送員、停單等問題。

靜態(tài)單配送中心最短路徑配送問題的基本模型為VRP（Vehicle Routing Problem），增加時間要求的VRP 問題稱為混合問題，另外一種描述稱為時間窗VRP 問 題， 增 加 隨 機 需 求 的 VRP 問 題 稱 為SDVRPSDP 問題［2-3］。 在電子商務(wù)規(guī)劃中，這一類問題的研究主要分為3 個方面：訂單分配優(yōu)化、物流配送調(diào)度、訂單分配與物流調(diào)度聯(lián)合優(yōu)化（Location Routing Problem， LRP）［1］。 關(guān)于LRP 的研究又可以分為多級LRP、不確定性LRP、隨機需求分解LRP、開放LRP 這四類問題。 這些數(shù)學(xué)模型歸納一般定義為：有一個或多個配送中心和若干個已知的需求點，規(guī)劃行車路線通過每一個需求點，最終回到配送中心，并在車容量、行駛里程、時間等約束條件下，達到總路線最短、費用最低、時間最短等目標。擴展到連鎖快餐訂單配送問題中，需求點的快餐需求量、需求時間、要求送達時間、需求點分布是隨機的，連鎖餐廳之間存在派送員相互調(diào)度而中途不一定回到配送中心、多個配送員動態(tài)規(guī)劃路線來保證訂單系統(tǒng)不關(guān)閉等情況。 從目前的研究現(xiàn)狀來看，現(xiàn)有研究成果可以滿足定量的訂單分配（包括靜態(tài)和動態(tài)），并可以實現(xiàn)物流倉儲設(shè)施點的選擇和物流路徑。 但是這一類解決方案只能解決一定規(guī)模的訂單配送問題，對于餐飲外賣這樣一種特殊的電子商務(wù)模式，這些解決方案不能滿足隨機需求的動態(tài)分配、需求點隨機分布、訂單的合并與停止接單等要求。 文獻［4］建立了隨機需求環(huán)境下三級供應(yīng)鏈任務(wù)分配的雙層規(guī)劃模型，研究了隨機環(huán)境下客戶滿意度和利潤的關(guān)系，但是沒有考慮多個配送周期的任務(wù)動態(tài)分配問題。 文獻［5］提出了基于客戶滿意度的需求預(yù)測模型，為提高快速響應(yīng)客戶需求做出預(yù)測機制，但是模型受到以往數(shù)據(jù)和主觀因素影響，存在缺陷。 部分研究者提出閉環(huán)物流網(wǎng)絡(luò)模型，旨在縮小配送系統(tǒng)成本，增強對于需求的反應(yīng)能力。

在算法設(shè)計上，研究者為了對所建立的模型進行處理，提出了一系列求解算法。 主要包括分支定界法、啟發(fā)式算法、遺傳算法、模擬退火法、禁忌表搜索法、蟻群算法等［6］。 葛顯龍等人［6］提出了動態(tài)需求下多車型調(diào)度優(yōu)化的云遺傳算法，利用云滴的隨機性和穩(wěn)定傾向性改進了自適應(yīng)遺傳算法中的交叉變異率，提高了全局搜索能力。 文獻［7］提出了隨機合理化禁忌法，解決了隨機需求同時取送貨路徑問題。 這些算法在求解優(yōu)化問題時具有一定的時效性和穩(wěn)定性，但仍需要根據(jù)具體問題做出改進。

基于以上分析，本文提出三維時間軸的概念來表示3 家連鎖餐廳訂餐服務(wù)時間，并可根據(jù)連鎖餐廳數(shù)量進行多維度擴展。 采用隨機模擬的思想模擬出隨機訂單，以總配送成本最小為目標函數(shù)建立連鎖訂單分配與派送員調(diào)度模型，對配送里程、派送員單程承載量、客戶需求時間進行約束。 設(shè)計基于緊密程度的訂單聚類算法，利用改進C-W 節(jié)約法混合蟻群算法求解最優(yōu)派送方案。 本文算法為連鎖餐飲企業(yè)訂單分配與物流派送提供參考。

1 隨機需求連鎖快餐店配送建模

1.1 問題描述

某連鎖餐飲企業(yè)有多家餐廳對外提供外賣送餐服務(wù)。 顧客通過企業(yè)提供的訂餐方式向訂餐中心提出訂餐要求，訂單信息包括：下單時間、送餐地址、需要的餐點、送貨時間、聯(lián)系方式等信息。 訂餐中心對顧客訂單進行分配，由餐廳完成餐點制備和送餐服務(wù)。 每個餐廳有固定人數(shù)的派送員，并且派送包的大小確定。 在訂單分配的過程中可以進行并單、訂單延遲、停單等處理，現(xiàn)要求探究隨機訂單的分配和派送路線，以及訂單數(shù)量對于連鎖餐廳運營狀態(tài)的影響。

1.2 問題分析

快餐店開啟訂餐服務(wù)的時間為［Te，Ts］，建立三維時間軸，3 家連鎖餐廳分別在ΔTi（i ＝1，2，3）時間內(nèi)產(chǎn)生隨機訂單。 以一家餐廳為例，ΔT時間內(nèi)產(chǎn)生訂單為K0，考慮外賣餐飲的實際情況，訂單數(shù)量在時間維上滿足正態(tài)分布，而在ΔT內(nèi)滿足泊松分布，即：

其中，λ為隨機訂單參數(shù)。 需求點的分布服從二維正態(tài)分布。 根據(jù)訂單信息建立需求點描述向量DM ＝｛T1j，T2j，Sj，Lij｝，i，j∈V，V為節(jié)點集合，DM描述了下單時間、需求時間、需求量和節(jié)點距離。 現(xiàn)根據(jù)時間和派送容積限制討論訂單合并的條件。 記tij，i∈｛0｝∪V，j∈V表示節(jié)點i到節(jié)點j的派送時間，v0表示派送員平均行駛速度，則tij ＝Lij／ v0，送達需求點的總時間為t0j ＝t01+t12+…+tj -1，j。 同樣建立派送員的描述向量DP ＝｛tg，tb｝，tg為出發(fā)時刻，tb為回到快餐店的時刻。 建立三維時間軸如圖1 所示。

圖1 三維時間軸示意圖Fig.1 3D timeline diagram

在ΔTi（i ＝1，2，3） 時間內(nèi)，快餐店可以進行派送的人員為n11，n21，n31，已經(jīng)分配出去的派送員數(shù)量為n1 11，n1 21，n1 31，剩余數(shù)量為n2 11，n2 21，n2 31，規(guī)劃好的派送員k回程時間tk db ＝tk d0j+Lk dj0／v0，d ＝1，2，3 表示3 家餐廳，j為節(jié)點。 派送員能否加入到下一輪的調(diào)度就需要比較回程時間和三維時間軸的坐標。 結(jié)合圖1 分析，第一次派送之后，如果tk db ＜2ΔTd，n2d2＝n2d1+1，在第m個派送區(qū)間，如果（m-1）ΔTd ＜tk db ＜mΔTd，n2dm ＝n2d，m -1+1。 每產(chǎn)生一個隨機訂單即加入到路徑規(guī)劃中，不斷比較區(qū)間上派送員數(shù)量和規(guī)劃路徑，從而為餐廳提供派送參考。 3 個快餐店配送中心的動態(tài)路徑規(guī)劃示意圖如圖2 所示。

圖2 配送中心動態(tài)路徑規(guī)劃示意圖Fig.2 Schematic diagram of dynamic path planning of distribution center

1.3 跨區(qū)域聯(lián)合調(diào)度模型

1.3.1 模型假設(shè)

（1）不考慮訂單制作時間和派送員在客戶節(jié)點處的逗留時間。

（2）每個客戶只被一個派送員服務(wù)，一個客戶的訂單只需要一個派送員就能夠滿足。

（3）單個配送中心情況下，派送員必須回到原來餐廳，而多個配送中心情況下，派送員不是必須回到原來餐廳。

（4）需求點隨機產(chǎn)生，需求向量也隨機產(chǎn)生，均服從一定的概率分布。

1.3.2 符號與決策變量

除在1.2 節(jié)問題分析部分外的符號定義如下：C1為單位里程派送費用；C2為增加一個派送員的成本；Lij為節(jié)點i與節(jié)點j之間的距離；tij為節(jié)點i與節(jié)點j之間的行駛時間；nΔT為時間軸上n段時間；一個快餐占據(jù)空間為V0，派送包容積為Q；V為節(jié)點集合；M為派送員集合；m0為總的派送員數(shù)量；Md為增加派送員數(shù)量集合；xijk為0-1 變量，如果派送員k從節(jié)點i送到節(jié)點j，則xijk ＝1，否則xijk ＝0；yik為0-1 變量，如果節(jié)點i是由派送員k配送的，則yik ＝1，否則yik ＝0；zi為0-1 變量，如果需要增加第i個派送員，則zi ＝1，否則，zi ＝0。

1.3.3 配送模型

其中，式（3）表示配送系統(tǒng)的總成本最小，主要包括配送路程成本和增加派送員成本；式（4）為派送包容量約束，表示規(guī)劃的路線上總的快餐體積不大于派送包體積；式（5）為配送時間約束，表示派送員送達時間不超過客戶需求時間；式（6）表示一次派送中，一個需求點只能被派送員送一次；式（7）和式（8）表示從快餐店出發(fā)和回到快餐店的派送員數(shù)量不超過派送員總數(shù)量與增加的派送員數(shù)量之和。

2 算法設(shè)計

2.1 聚類分配算法

將隨機產(chǎn)生的訂單按照距離和訂單承受能力進行聚類，分配到3 家餐廳分別進行配送規(guī)劃，每當產(chǎn)生一批新訂單就加入到聚類樣本中進行動態(tài)分類。ΔT時間內(nèi)產(chǎn)生需求點集合C ＝｛c1，c2，…，cp｝，D為餐廳集合。 定義需求節(jié)點到餐廳的緊密程度Rid為：

其中，F(xiàn)id為需求點i到餐廳d的親和力，定義為：

其中，λ1和λ2為正的加權(quán)系數(shù)；Iid為0-1 變量，如果i需求點已經(jīng)分配給d餐廳，則Iid ＝1，否則Iid ＝0；Bd為當前d餐廳的訂單承載能力，具體為：

其中，qi為0-1 變量，如果派送員i已經(jīng)分配到d餐廳，qi ＝1，否則，qi ＝0。 式（11）一個主要缺點在于假設(shè)了派送員滿載派送而實際情況不一定滿載，但是滿載體現(xiàn)了承載能力的最大化，這只是訂單分配的條件，實際路徑規(guī)劃中是否滿載是約束條件（3） 判斷的。

上述分析可知，緊密程度Rid最大，需求點i就被分配到d餐廳。

2.2 C-W 節(jié)約法混合蟻群算法

Clarke-Wright 節(jié)約算法是一種隨機合理化動態(tài)衍生方法，首先生成初始方案，利用隨機合理化動態(tài)衍生方法構(gòu)造備選方案集，計算出備選方案集中的送貨代價，在此基礎(chǔ)上進行禁忌選優(yōu)，確定優(yōu)化方案，提高了搜索效率。 在本文多配送中心隨機需求的問題中，隨機計算過程復(fù)雜，在需求分配初期仍然采用CW 節(jié)約法生產(chǎn)初始方案，這里從載重限制、時間窗限制等方面改進C-W 節(jié)約法。 但是利用改進C-W 節(jié)約法生成的線路受到起始需求點影響較大，相同的需求點下雖然滿足了載重和時間限制，但是行駛路徑存在可能交叉現(xiàn)象，并不最優(yōu)。 所以引進蟻群算法，通過蟻群的全局搜索能力，在需求點之間形成最短路徑，C-W 混合蟻群算法同時縮短了求解時間，提高系統(tǒng)效率。 時間上，在一段時間內(nèi)產(chǎn)生的訂單加入需求點集合中進行分配；空間上，繁忙程度高的餐廳（ndm＜0） 產(chǎn)生訂單加入到其它餐廳分配。

隨機需求下多配送中心聯(lián)合調(diào)度算法流程如下：

步驟1采用蒙特卡洛隨機模擬的思想，在第一個ΔT時間內(nèi)，按照式（1） 產(chǎn)生隨機訂單，參數(shù)λ在［Te，Ts］上滿足正態(tài)分布。 同時確定需求點描述向量DM。

步驟2根據(jù)需求點與餐廳之間的緊密程度將需求點聚類。

步驟3在第一個ΔT內(nèi)， 每個餐廳先進行獨立分配。 單配送中心利用C-W 算法思想計算節(jié)約值并進行排序，根據(jù)載重限制（3）和需求時間限制（4）逐層連接需求點，生成初始分配方案。

步驟4利用蟻群算法將初始分配方案優(yōu)化，按照式（2）優(yōu)化路線，同時生成派送員描述向量DP。

步驟5在mΔT內(nèi)產(chǎn)生隨機訂單，計算tk db ＝tk d0j + Lk dj0／v0在時間軸上位置，更新ndm、n1dm與n2dm。 如果n2dm ＞0 則配送工作正常，否則，調(diào)整路徑，將多余需求點加入到其它餐廳。 遍歷d，如果仍不能滿足n2dm ＞0，則采用增加派送員機制。 不斷循環(huán)步驟5，直到m ＞（Ts - Te）／ ΔT。

步驟6改變隨機模擬參數(shù)，探究不同繁忙程度下多配送中心訂單配送情況。 動態(tài)變化過程的路徑規(guī)劃算法圖3 所示。

圖3 動態(tài)變化過程的路徑規(guī)劃算法Fig.3 Path planning algorithm for dynamic change process

3 仿真實驗分析

設(shè)定的外賣餐廳工作時間區(qū)間為10：00 ～13：00，時間間隔均為10 min，在工作時間內(nèi)產(chǎn)生訂單的最大值為8，方差為2，數(shù)據(jù)產(chǎn)生區(qū)域在3 km 以內(nèi)，外賣派送包容積為5 份，每個需求點需求量為1-2，派送員一次行程最遠距離為2.0 km，行駛速度為0.6 km／min，3 家快餐店距離相同。 設(shè)定區(qū)間3 家外賣餐廳位置分別位于邊長6 km 正方形區(qū)域內(nèi)坐標為（0，1 000），（-1 000，-1 000），（1 000，-1 000）位置。 利用本文算法獲得的派送路徑如圖4 所示。

圖4 隨機訂單下派送路徑規(guī)劃Fig.4 Delivery path planning under random orders

10 點開始派送狀態(tài)下的派送路徑情況見表1。

表1 初始狀態(tài)下派送路徑表Tab.1 Delivery path table in initial state

表1 中，-2、-1、0 分別表示3 家餐廳，其余點編號表示訂餐中心在10 點時刻累計的客戶。 選擇各個配送員第三次配送的情況見表2。

表2 第三次配送路徑規(guī)劃情況Tab.2 Third distribution route planning

表2中選取了動態(tài)派送路徑規(guī)劃中每名派送員第3 次的派送路徑，其中派送員P1第3 次派送的起始時間為10：18，派送員P2第3 次派送的起始時間為10：55， 派送員P3第3 次派送的起始時間為10：28。

按運送費用最小為目標得出最優(yōu)路徑的求解結(jié)論有：

（1）訂單派送過程未發(fā)生訂餐中心停單情況。

（2）完成所有訂單累計最少消耗成本為1 002.14 元。

（3）隨機產(chǎn)生的訂單總數(shù)為432 個。

（4）損失的客戶數(shù)為52 名，損失的訂單數(shù)為98個，可得客戶損失率約為24.1%，訂單的損失率約為22.7%。

從模型的求解結(jié)果可以看出，該模型能夠完成訂單的派送任務(wù)，累計最少消耗成本較高，通過計算完成了對模型的檢驗，證明該模型的設(shè)計是合理的。

4 結(jié)束語

本文研究了隨機訂單生成狀態(tài)下，配送員的路徑規(guī)劃問題。 不失一般性，研究了3 家連鎖餐廳隨機訂單生成與配送規(guī)劃。 建立了以總配送成本最小為目標函數(shù)建立連鎖訂單分配與派送員調(diào)度模型，對配送里程、派送員單程承載量、客戶需求時間進行約束。 通過仿真研究驗證了算法有效性。 在實際的餐廳訂單配送過程中，可能會存在更多的約束條件，且各約束條件之間還可能相互沖突，因此需根據(jù)實際情況對模型進行適當?shù)恼{(diào)整。 本文算法對于實際連鎖餐飲店的動態(tài)訂單生成配送問題提供了一定的解決方案。