餐飲企業配送車輛路徑優化研究

張 潭，蒲 忠,2，魏 卓 ZHANG Tan,PU Zhong,2,WEI Zhuo

（1.西南石油大學 經濟管理學院，四川 成都 610500；2.西南石油大學 大數據管理研究所，四川 成都 610500；3.中國石油吉林油田分公司 物資供應處，吉林 松原 138000）

(1.School of Economics and Management,Southwest Petroleum University,Chengdu 610500,China;2.Big Data Management Institute,Southwest Petroleum University,Chengdu 610500,China;3.CNPC Jilin Oilfield Material Supply Department,Songyuan 138000,China)

0 引言

安全性和時效性是餐飲物流的重點，如何高效安全地把食品由物流中心配送到門店是國內外學者一直關注的問題。付秋睿[1]等對超市冷鏈物流的車輛路徑做出優化，設計多目標函數，降低了配送成本。趙娜[2]研究了鄭州町上壽司配送路線，在車輛路徑優化的基礎上加入時間窗約束，建立起VRPTW問題模型，并且設計遺傳算法進行求解；吳暢[3]重點考慮到環境安全問題，在VRP問題基礎上加入碳排放約束，建立起帶時間窗和送取貨一體化的VRPSPDTW模型；潘立軍[4]等針對帶時間窗和取送貨問題設計出一種基于時差的插入法的改進遺傳算法，該算法與基本遺傳算法相比，搜索速度快，能夠避免早熟，求解質量更高。為了保證食品的安全，降低在途損耗，文章通過分析某餐飲企業配送車輛的成本，考慮時間窗約束等條件，建立數學優化模型，并且設計遺傳算法進行求解，希望能夠為餐飲企業提供車輛成本優化思路。

1 餐飲企業配送車輛路徑優化模型

1.1 問題描述

文章選取某餐飲企業作為研究對象，該企業在某區域范圍內擁有47家門店，分布不均，不同的地理位置和經營狀況的門店對送貨時間和送貨量有著不同的要求，所有門店的需求量和時間窗都是已知。在該區域內有一家企業自有的配送中心為門店提供配送服務，當天18點前門店會將第二天的需求計劃發送到配送中心，配送中心開始生產備貨，在第二天3點前完成配送任務，車輛在配送時也需要完成取貨任務，并且帶回配送中心。

1.2 模型建立

1.2.1 基本假設

（1）一個配送中心完成所有門店的配送任務；

（2）車輛車型相同，取送貨物規格相同；

（3）一個門店只允許被一輛車服務；

（4）所有車輛完成配送任務后需要返回配送中心；

（5）不考慮取送貨順序，取送貨的重量不超過車輛載重量；

1.2.2 參數設計

配送中心編號為0，有n個客戶點 （1,2,3,…,n ），第i個客戶點的取貨和送貨量分別為pi和qi（i=1,2,3,…,n），車輛集合為V，汽車載重量為M。

1.2.3 成本分析

在車輛路徑優化問題中，成本主要來源兩個方面：直接成本和間接成本。直接成本包括：固定成本、行駛成本、燃油成本、輪胎損耗等。間接成本包括：管理費用、業務費用等。本文結合實際問題，選取成本占比最大的固定成本，燃油成本等進行研究。

（1） 固定成本

u1表示車輛單位固定成本（萬元）。

（2） 燃油成本

文章借鑒了韓國慶[5]的燃油計算成本公式，結合本文研究對象的實際情況，去除了道路、氣溫、海拔和其他因素的修正系數。

u2表示燃油的單位價格（元）；

Qa表示車輛的基本燃油消耗量；

Qb表示車輛質量變化附加燃油消耗量；

dij表示客戶i到j的行駛距離；

yijk表示車輛k從客戶i到j的載重量。

（3） 懲罰函數

u3為表示懲罰單位成本（元）；

d為表示早到的懲罰系數；

e為表示晚到的懲罰系數；

ai為表示客戶i最早的服務時間；

bi為表示客戶i最晚的服務時間；

1.2.4 目標函數

約束函數：

公式（5）表示目標函數，價格最低，成本最小；公式（6）表示每個客戶點僅由一輛車服務；公式（7）表示所有車輛在完成送取貨任務之后都要返回到配送中心；公式（8）表示一條配送路徑上總的客戶需求量不超過車輛的最大載重量；公式（9） 表示懲罰函數。

2 算法分析

2.1 遺傳算法的概念

遺傳算法是仿照遺傳生物學演化發展而來，它模仿了自然選擇和遺傳過程中的復制、交叉、變異等步驟，從初始種群出發，通過遺傳編碼、單點交叉或者多點交叉、變異算子等，由此產生一個更加適應當前環境的個體，使得整個種群進化到最優解的空間范圍內，如此循環進化，直至收斂到一群最適合當前環境的群體個體，得出最優解。

2.2 遺傳算法的基本求解流程

（1）編碼：將當前的可行解編碼成遺傳算法的基因型串結構數據；

（2） 初始種群生成：隨機生成M個個體作為初始群體P（0 ），設置進化代數t＜0；

（3）適應度值評價檢測：計算P（t）中個體的適應度；

（4）選擇、交叉和變異；

（5） 終止條件判斷：若t≤T，則t+1→t，轉到步驟（2），若t＞T，則輸出最優解

遺傳算法的流程圖如圖1所示：

圖1 遺傳算法基本流程圖

2.3 車輛路徑優化模型的遺傳算法設計

2.3.1 編碼和解碼

序列編碼是遺傳算法編碼方式的一種，采用自然數代表目標客戶，0代表車輛的出發點和回歸點，用目標客戶的自然數代表車輛的訪問路徑，用帶箭頭的線代表車輛行進方向，自然數的前后排列順序就是客戶的服務順序。例如有N個門店的TSP問題，門店編號依次為 ｛1,2 ,…,N ｝，則編碼的位串為：這就表示對門店采用由小到大的方法訪問行走路線。如果編碼位串為：

表示對門店采用由大到小的方式訪問行走路線。如果編碼位串為：

表示車輛從配送中心出發，首先訪問1門店，然后訪問2門店，接著訪問4門店后返回配送中心。對于門店編號集合內的自然數，需要路線包括所有集合內的自然數整個編碼過程才算完成，否則就要重復編碼行為。

2.3.2 遺傳算子的設計

（1）文章通過輪盤賭選擇確定選擇算子。輪盤賭選擇中所有個體都有概率被選擇，但是在實際操作中那些適應度較大的個體更容易被選中，就像旋轉的輪盤一樣，指針更容易落在那些面積較大的區域。假設種群大小為M，個體g的適應度值為Fg，則個體g被選中的概率Pg為：

（2）本文選擇均勻交叉的方式進行交叉算子操作，均勻交叉相較于單點交叉和多點交叉更具有廣義性，每一個點都是潛在交叉點。

（3）文章結合模型特征和算法特點，選擇基本位變異進行變異操作。實例如下：

種群1：4 3 1 8 9 0 2 5 6。隨機產生兩個變異“1”和“2”，在種群中顯示為種群1：4 3丨1 8 9 0 2丨5 6，然后進行變異操作轉換為種群1:4 3 2 8 9 0 1 5 6。

3 算例分析

3.1 樣本選擇

該企業經過數十年的發展，目前在國內市場已經擁有數百家門店，經過前期的市場調研，本文選取某地區的47家門店進行研究，以驗證模型和算法的有效性。

3.2 數據選取

配送車輛由該地區的配送中心出發，向分散在區域內的47家自營門店提供配送服務，配送產品為火鍋食品。各車輛的車型、規格、行駛速度等相同，車輛載重為5.2噸，行駛速度為70km/h。

3.3 物流中心和門店信息

由于火鍋食材易腐蝕等特征，物流中心需要每天完成一次配送和取貨任務，配送出發時間為當天21:00至第二天03:00，車輛出發時間與倉庫配貨速度和門店距離遠近有關，完成配送任務之后再將取回的貨物帶回物流中心。各門店的需求量和取貨量以及時間窗要求如表1所示：

表1 門店基本信息

4 結果分析

根據遺傳算法設計思路，本文采用Matlab2018a軟件進行遺傳算法的編程求解，在Inter（R） Core（TM） i5-3230M CPU@2.60GHz，內存8G，操作系統為Win10的電腦上進行運算。所得優化路徑如表2所示：

表2 優化后的配送路徑

通過與優化前的數據對比分析可以得到，優化后的路線車輛數由14輛降低為12輛，固定成本降低1 100元，行駛里程降低280.7公里，在途時間降低8.41小時，運輸成本降低364.91元，時間懲罰成本降低205.2元，平均載重率提高20.15%，大大提高了客戶滿意度。在市區范圍的車輛路徑優化中，這個結果是很有意義的。

5 研究結論和未來展望

5.1 研究結論

冷鏈運輸注重時效和客戶滿意度，本次優化結果大大降低車輛的在途時間、行駛里程和時間懲罰成本，這給門店以及消費者帶來的體驗價值遠遠高于它的經濟價值。本文建立的企業車輛路徑優化模型和遺傳算法，能夠發揮優化作用，實現了企業和消費者共贏的局面，物流成本得到有效控制，在滿足消費者需求的基礎上減少了服務車輛數和在途時間，提升了餐飲企業的核心競爭力。

5.2 未來展望

本文圍繞VRP基礎問題進行研究，結合企業實際問題建立起帶時間窗和同時取送貨條件的冷鏈配送車輛路徑優化模型。雖然已經考慮比較全面，但本文的研究還存在一些不足之處：首先本文研究的是單目標問題，實際上多配送中心相比較單配送中心更具有研究價值和更符合實際情況；其次需求是固定的，實際上動態優化更具有實際意義。