考慮時間窗與道路狀況的快餐配送路徑優(yōu)化

PathOptimizationforFastFoodDistributionConsideringTimeWindowandRoadConditions

FUWenhan1，GONGYuxin1，XUXinyi1，DUANChuke1，JINGSheng2

（1.上海理工大學管理學院，上海200093；2.康奈爾大學，美國伊薩卡14853）

（1.SchoolofManagement，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China;2.CornellUniversity，Ithaca14853，UnitedStates）

摘要：隨著現(xiàn)代社會經(jīng)濟的發(fā)展，人們生活節(jié)奏加快，快餐憑其方便快捷的優(yōu)勢成為越來越多人的飲食選擇。如何縮短快餐配送的時間和成本，提高配送的效率成為企業(yè)與客戶關(guān)注的焦點。快餐配送由于其配送品質(zhì)量的易損失性，有著嚴格的配送時間窗限制，道路狀況包括單行道和通行狀態(tài)也極大影響其配送路徑選擇和最終配送效率。文章構(gòu)建了考慮時間窗和道路狀況的快餐配送路徑優(yōu)化模型，基于Dijkstra算法進行求解，并通過S市Y區(qū)K公司的案例驗證了模型的有效性，為品牌快餐企業(yè)配送服務提高效率提供決策支持。

關(guān)鍵詞：快餐配送；時間窗；道路通行狀態(tài)；Dijkstra算法；路徑優(yōu)化

中圖分類號：F253文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2023.19.002

Abstract：Withtherapiddevelopmentofmodernsocietyandpeople'spaceoflife，moreandmorepeoplechoosefastfoodbecauseofitsconvenienceandtimeliness.Howtoshortenthetimeandcostoffastfoodsdistributionandimprovetheefficiencyofdistributionaregoingtobethefocusofbothenterprisesandcustomers.Fastfooddistributionhasstrictdistributiontimewindowrestrictionsduetothevulnerabilityofthequalityoftheproducts，andtheroadconditionsincludingone-waystreetandtrafficstatusmakegreatimpactontheselectionofdistributionpathandfinaldistributionefficiency.ThispaperconstructsafastfoodsdistributionpathoptimizationmodelconsideringthetimewindowandroadconditionsandsolvesitbasedonDijkstraalgorithm.ThevalidityofthemodelisverifiedthroughthecaseofKCompanyinYDistrictofSCity，whichprovidesdecisionsupportforbrandfastfoodenterprisestoimprovetheefficiencyofdistributionservices.

Keywords：fastfooddistribution;timewindow;roadconditions;Dijkstraalgorithm;pathoptimization

0引言

隨著現(xiàn)代社會經(jīng)濟的發(fā)展，人們生活節(jié)奏的加快，快餐憑其方便快捷的優(yōu)勢成為越來越多人的飲食選擇，與此同時，物流行業(yè)的快速發(fā)展，物流方式的不斷創(chuàng)新，這使得如何縮短快餐配送的時間和成本，提高配送的效率成為了企業(yè)關(guān)注的焦點?？觳偷呐渌陀捎谛袠I(yè)的特殊性以及配送物品的特殊性，使其具有一般配送的特點的同時，又具有其自身的特點，包括更具時間性，要求在規(guī)定時間內(nèi)準確快速地送達，以及配送受地區(qū)、交通、天氣、配送工具容量等多重因素的影響，這對配送設施和配送技術(shù)有了更多的要求。而在某些特殊地區(qū)，路況的特殊就導致對配送路線的要求更為苛刻。

外賣配送問題是帶時間窗的車輛路徑問題（VehicleRoutingProblem，VRP），在VRP基礎上添加配送時間約束條件，給定車輛到達目的地的最早時間和最晚時間，要求在規(guī)定的時間窗內(nèi)到達。余海燕等人針對生鮮農(nóng)產(chǎn)品新鮮度要求高、時效性強等特點，考慮訂單的動態(tài)性、硬時間窗等因素，以配送路徑最短為優(yōu)化目標，建立帶硬時間窗的即時配送模型，并設計滾動時域延遲配送算法求解[1]。徐倩等人針對外賣需求產(chǎn)生時間集中、配送時間要求嚴格的特點，設定顧客期望送餐時間窗以及時間懲罰成本，建立物流配送平臺總成本最低為目標的數(shù)學模型，運用自適應大鄰域搜索算法對不同規(guī)模算例進行求解[2]。陳濤等人針對社區(qū)團購生鮮產(chǎn)品配送的效率低、損耗高等特點，提出了考慮時間窗與新鮮度損耗的社區(qū)團購生鮮產(chǎn)品配送路徑優(yōu)化模型[3]。然而，現(xiàn)有配送優(yōu)化研究大多假設配送時間和費用與配送路程相關(guān)，忽視不同道路狀況對行駛速度和配送成本的影響[4]。蘭輝等人根據(jù)各時間段內(nèi)各路段的通行情況，統(tǒng)計配送路段通行狀況矩陣，并將路段距離矩陣轉(zhuǎn)化為運輸時間矩陣，建立考慮道路通行狀況下的冷鏈物流配送路徑優(yōu)化模型[5]。郭琪在考慮實時路況的情況下，以時間最短為目標建立商砼配送路徑優(yōu)化模型并采用Dijkstra算法求解[6]。

綜上所述，現(xiàn)有文獻對帶時間窗的車輛路徑問題進行了充分研究，但同時考慮到道路狀況的配送路徑優(yōu)化研究還不足，同時所應用領域大多集中在生鮮農(nóng)產(chǎn)品，較少針對熟食快餐這一對于時間窗要求甚至更高的領域。因此，本文針對快餐外賣配送路徑優(yōu)化問題，同時考慮時間窗和道路狀態(tài)建立模型并基于Dijkstra算法進行求解，并通過S市Y區(qū)的K快餐公司配送問題作為案例，驗證所提出方法的實證有效性。

1問題描述與分析

1.1問題描述

現(xiàn)代社會的飛速發(fā)展導致人們對快餐的需求不斷增長，如何找到最佳路徑縮短配送時間以及減少配送成本成為快餐配送急需解決的問題。本文所研究的快餐配送路徑優(yōu)化問題，可以具體描述為：某快餐企業(yè)門店對其所負責區(qū)域內(nèi)的居民社區(qū)和企事業(yè)單位進行其店內(nèi)所銷售的快餐配送服務。快餐門店根據(jù)各社區(qū)和單位的需求，同時兼顧對顧客承諾的時間窗條件和配送當下道路通行狀況，合理制定配送方案以完成配送?？觳烷T店和訂餐顧客的地理坐標，由于客戶對餐品送達時間與食物新鮮度有較高要求，在顧客期望的時間外到達將產(chǎn)生高額懲罰。因此本文以時間最短為目標，建立快餐配送路徑優(yōu)化模型。

本文以某K快餐公司為案例，以S市Y區(qū)的門店為研究對象，通過考慮地區(qū)、交通、距離等因素，特別是單行道單向通行、貨運火車通過封閉道路等復雜道路通行情況下，研究快餐配送的最短路徑問題并找出最優(yōu)方案。研究范圍內(nèi)的公司門店和配送服務范圍如圖1所示。圖中紫色三角形為K快餐公司所在位置，可以發(fā)現(xiàn)該區(qū)域內(nèi)道路較多，居民區(qū)較密，存在單行道等較復雜路況。此外包含了一段貨運鐵路，當火車經(jīng)過時需要封閉道路，從而導致交通堵塞。將比較密集的居民區(qū)合并為一個居民區(qū)然后圖中的紅色點代表的是各個點餐的客戶所在的位置。

1.2問題分析

經(jīng)過實地考察和訪談，快餐公司的送餐流程主要包括如下步驟：（1）等待餐飲制作；（2）將店員打包好的餐飲裝進箱子；（3）背上箱子；（4）出門店；（5）騎上專用的送餐車；（6）配送餐點；（7）到地方聯(lián)系客戶；（8）確認送達；（9）繼續(xù)配送下一單；（10）重復前面（7）至（9）步，直至全部訂單送達；（11）返回店內(nèi)；（12）等待下一次配送。

利用5M1E分析法分析快餐配送流程中的人（Man）、機器（Machine）、材料（Material）、方法（Method）、測量（Measurement）和環(huán)境（Environment），可以畫出快餐配送流程的魚骨圖如圖2所示。

從中可以發(fā)現(xiàn)影響快餐配送效率的主要限制因素如下：

（1）時間窗限制：用戶點較多、較雜，而且K快餐公司規(guī)定餐飲必須在30分鐘內(nèi)送達。但此區(qū)域路況較復雜，行程較不易規(guī)劃，容易造成時間的浪費，從而導致送餐效率低下。

（2）道路通向限制：該區(qū)域道路狀況復雜，存在單行道；送餐路況較為復雜，送餐時間難以把握；很難控制在30分鐘以內(nèi)，難以保證送餐效率。

（3）道路通行限制：特別是與其他地區(qū)所不同，該區(qū)域內(nèi)還存在著一條火車線，并有運貨的火車經(jīng)常通行，導致火車所經(jīng)過的兩條道路在通過的情況下會導致送餐時間的大大延長，直接導致送餐的延誤。

2基于Dijkstra算法的路徑優(yōu)化規(guī)劃

2.1Dijkstra算法建模

Dijkstra算法使用類似廣度優(yōu)先搜索的方法解決賦權(quán)圖的單源最短路徑問題。Dijkstra算法在解決直送式配送運輸問題中具有獨特的優(yōu)勢[7]，也被利用在物流配送路徑優(yōu)化中，通過對物流配送路徑及節(jié)點的選擇進行建模分析，求解出配送節(jié)點至各需求點的最短路徑及所經(jīng)節(jié)點[8]。

將圖1中K快餐公司門店的位置和各個顧客所在位置數(shù)字化后得到快餐門店配送范圍節(jié)點圖如圖3所示。其中節(jié)點7至節(jié)點2為單行道，只能單向通行，而其余線路都可以雙向通行實現(xiàn)餐品的配送。運用Dijkstra算法固定了快餐門店節(jié)點0作為源節(jié)點，然后找到該點到圖中所有其它節(jié)點的最短路徑，就可以產(chǎn)生最短路徑樹，每次取出未訪問節(jié)點中距離最小的，用該節(jié)點更新其他節(jié)點的距離。

2.2情景分析

由于該區(qū)域內(nèi)存在貨運鐵路，當有火車經(jīng)過時需要封閉道路，從而導致交通堵塞。通過調(diào)查分析鐵軌上經(jīng)行的火車時間表，可以將整體送餐狀況分為兩種情景：無火車經(jīng)過的時刻范圍配送路徑和有火車經(jīng)過的時刻范圍配送路徑。

（1）無火車通過時配送路徑

道路無阻礙的情況下，計算每條道路通行所用的時間（單位：分）并繪制無火車通過配送路徑如圖4所示，并用Python編寫程序運行

Dijkstra算法計算求解最短路徑。對快餐配送最短路徑進行模擬求解，分別求出門店配送節(jié)點0至其他各需求節(jié)點的最短路徑，直至最終節(jié)點9結(jié)束如表1所示。可以得到，當不屬于火車經(jīng)過的時刻范圍內(nèi)時，送餐員優(yōu)先選擇0→1→3→7→9的路線來送餐，配送路徑時間最少，耗時19.5分鐘。

（2）有火車通過時配送路徑

當火車經(jīng)過，需要封閉道路，從而導致交通堵塞，部分道路通行時間變長。將該情況下道路的用時進行更改并繪制有火車通過配送路徑如圖5所示，用Python編寫程序運行Dijkstra算法計算求解最短路徑優(yōu)化。對快餐配送最短路徑進行模擬求解，分別求出門店配送節(jié)點0至其他各需求節(jié)點的最短路徑，直至最終節(jié)點9結(jié)束如表2所示?？梢缘玫剑瑢τ诠?jié)點9，當在火車經(jīng)過的時刻范圍內(nèi)時，送餐員按照0→1→2→5→9的路線來送餐，配送路徑時間耗時22.5分鐘，相較于原路線0→1→3→7→9耗時29.5分鐘，節(jié)省了7分鐘。

2.3方案評估

由以上分析可知無火車經(jīng)過的時刻范圍內(nèi)時，送餐員按照0→1→3→7→9的路線來送餐，有火車經(jīng)過的時刻范圍內(nèi)時，送餐員則優(yōu)先選擇0→1→2→5→9的路線來送餐。通過所提出的分類討論最短最優(yōu)路徑方案，在有火車經(jīng)過時，平均單次節(jié)省送餐員7分鐘的送餐時間，在訂單多或者客戶位置相距較遠時有顯著作用，同時大幅提高送餐員的工作效率。

3結(jié)論與展望

本文構(gòu)建了考慮時間窗和道路狀態(tài)的快餐配送路徑優(yōu)化模型，先通過魚骨圖考慮分析地區(qū)、交通、距離等問題限制因素，再對道路通行和通向狀況進行情景分析，利用Dijkstra算法進行求解找出最短路徑，并通過S市Y區(qū)K公司的案例驗證了模型的有效性，為品牌快餐企業(yè)配送服務提高效率提供決策支持。未來路徑優(yōu)化算法的應用不僅局限在快餐配送的問題上，還可以運用在其他領域?！耙粠б宦贰睉?zhàn)略下我國陸地運輸需求很大，利用最短路徑算法尋找最優(yōu)規(guī)劃方案，可以縮短運輸時間降低運輸成本，促進社會經(jīng)濟發(fā)展。隨著人工智能等信息技術(shù)發(fā)展，對網(wǎng)絡通信流量的要求與日俱增，路徑優(yōu)化算法可以用于尋找流量大、速度快、費用低的傳輸方式，從而提高網(wǎng)絡資源的利用率，降低通信成本，加速信息化社會進程。

參考文獻：

[1] 余海燕，唐婉倩，吳騰宇. 帶硬時間窗的O2O生鮮外賣即時配送路徑優(yōu)化[J]. 系統(tǒng)管理學報，2021，30（3）：584-591.

[2] 徐倩，熊俊，楊珍花，等. 基于自適應大鄰域搜索算法的外賣配送車輛路徑優(yōu)化[J]. 工業(yè)工程與管理，2021，26（3）：115-122.

[3] 陳濤，康世寧. 考慮時間窗與新鮮度損耗的社區(qū)團購生鮮產(chǎn)品配送路徑優(yōu)化研究[J]. 物流科技，2022，45（11）：22-26.

[4] 王恒，徐亞星，王振鋒，等. 基于道路狀況的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化[J]. 系統(tǒng)仿真學報，2019，31（1）：126-135.

[5] 蘭輝，何琴飛，邊展，等. 考慮道路通行狀況的冷鏈物流配送路徑優(yōu)化[J]. 大連海事大學學報，2015，41（4）：67-74.

[6] 郭琪，韋金銀，郭鵬祥，等. 考慮實時路況下的商砼配送路徑優(yōu)化研究[J]. 軟件工程，2019，22（4）：29-32.

[7] 周冰，盧貝. 基于Dijkstra算法的地下物流配送路徑優(yōu)化研究[J]. 現(xiàn)代信息科技，2021，5（6）：91-95.

[8] 劉臣宇，孫偉奇，李衛(wèi)靈. Dijkstra標號法在直送式配送運輸問題中的應用[J]. 物流科技，2021，44（7）：90-91.