陳卿詩 CHEN Qing-shi；邱文倩 QIU Wen-qian；莫立佳 MO Li-jia

（湖南科技大學(xué)，湘潭 411201）

0 引言

在互聯(lián)網(wǎng)的帶動下，農(nóng)產(chǎn)品冷鏈物流需求越來越大，而成本一直是制約冷鏈牧流發(fā)展的關(guān)鍵因素，如何有效降低冷鏈物流成本成為國家、企業(yè)和消費者共同關(guān)注的熱點話題。與此同時，冷鏈物流市場的擴大以及消費者對服務(wù)品質(zhì)的要求提升促使企業(yè)不得不提升自身服務(wù)質(zhì)量，食品安全和衛(wèi)生問題越來越受到關(guān)注，提高滿意度來增加顧客黏性，在競爭激烈的場中占據(jù)一席之地[1]。作為食品安全的重要組成部分，蔬菜的新鮮度和衛(wèi)生質(zhì)量是人們關(guān)注的重點。而蔬菜的運輸路線直接影響到其新鮮度和衛(wèi)生質(zhì)量，因此，研究食堂蔬菜運輸路線具有重要的現(xiàn)實意義和社會價值。通過深入探究當(dāng)前蔬菜運輸路線的現(xiàn)狀和問題，可以幫助我們更好地了解食堂的需求和挑戰(zhàn)，為制定相應(yīng)的政策和措施提供科學(xué)依據(jù)和參考。同時，也有助于提高人們的食品安全和衛(wèi)生意識，促進社會的可持續(xù)發(fā)展。

蔬菜等生鮮的配送優(yōu)化屬于典型的車輛路徑規(guī)劃問題，已有學(xué)者對該應(yīng)用場景展開了論述。張洪瑤等[2]基于灰色神經(jīng)網(wǎng)絡(luò)預(yù)測生鮮物流需求；冉昊杰等[3]將遺傳算法與模擬退火算法融合，實現(xiàn)選址過程的整體優(yōu)化；趙佳豪等[4]基于大數(shù)據(jù)技術(shù)應(yīng)用分析，提出優(yōu)化供應(yīng)鏈的對策。上述學(xué)者多考慮生鮮配送的需求以及選址等的優(yōu)化對策。

鑒于此，本文針對社區(qū)某市22 所高校蔬菜生鮮配送的實際場景，考慮多車輛類別以及不同容量的約束情況，提出運用基于OR-Tools 的路徑優(yōu)化方法；其次運用matplotlib 繪制路徑圖像；最后導(dǎo)出各車輛移動路線、移動距離以及載重量，直觀反映優(yōu)化效果。

1 問題及模型

1.1 問題描述

物流中心每日需要為學(xué)校提供蔬菜的配送服務(wù)，每個學(xué)校的蔬菜配送量一定。物流中心擁有一定數(shù)量不同規(guī)格的配送車，各個學(xué)校均設(shè)有一個配送接收點，各校之間通有大道。一個物流中心向多個學(xué)校配送蔬菜，配送車輛統(tǒng)一從物流中心出發(fā)按照一定的配送順序，配送到需求點，最后返回到物流中心。應(yīng)用點為基于需求量約束的調(diào)度配送車輛、安排配送線路與次序，使配送總成本最小。

基于現(xiàn)實情況，為簡化問題處理但不失一般性，假設(shè)如下：

①配送中心具有一定數(shù)量不同型號的配送車。

②配送車需要從物流中心出發(fā)，當(dāng)完成所有配送任務(wù)后，需要返回配送中心。忽略特殊情況下配送量激增所導(dǎo)致的往返配送中心裝貨。

③各客戶節(jié)點（買方）只能接受1 輛配送車為其進行配送，且需求量不能超過配送車的最大載荷。

圖1 蔬菜物流配送流程

④各客戶節(jié)點的地理坐標(biāo)、產(chǎn)品需求量等均已知。

⑤學(xué)?？爝f點和物流中心的個數(shù)均唯一。

⑥物流中心至學(xué)?？爝f點、學(xué)?？爝f點之間路徑唯一，且距離已知。

⑦物流中心的成本只考慮運輸成本，裝卸成本忽略不計。

⑧每輛車的行駛距離不超過預(yù)定的該車的最大行駛距離。

1.2 參數(shù)及變量定義

設(shè)蔬菜配送配送中心車場有m 輛車，每輛配送車的最大載重量Q，需要對n 個客戶（節(jié)點）進行運輸配送，每輛車從中心車場出發(fā)給若干個客戶送貨，最終回到中心車場，客戶點i 的貨物需求量是di（i=1，2，…，n），且di＜Q。記配送中心編號為0，各客戶編號為i（i=1，2，…，n），ci，j表示客戶i 到客戶j 的距離。求滿足車輛數(shù)最小，車輛行駛總路程最短的運送方案。

模型涉及的參數(shù)與變量作以下界定：

n：客戶點的數(shù)量（不包括起始點）；

m：車輛的總數(shù)量；

Q：每輛車的容量限制；

di：客戶點的需求量；

ci，j：客戶點i 到客戶點j 的距離；

1.3 模型構(gòu)建

基于上述問題與假設(shè)，以某物流中心的蔬菜配送服務(wù)為應(yīng)用對象，構(gòu)建規(guī)劃模型如下：

其中，式（1）表示目標(biāo)函數(shù)為最小化總行駛距離，式（2）確保每個客戶點必須被訪問且僅被訪問一次，式（3）和式（4）確保每輛車的路徑必須從起始點開始，并在終點結(jié)束，式（5）為車輛容量限制，式（6）為0～1 決策變量約束。

2 求解方法

2.1 求解思路

上述模型是一個NP-hard 問題，且隨著問題規(guī)模的增大，傳統(tǒng)算法很難快速、智能地去求解這個問題。不少學(xué)者基于退火算法進行處理。區(qū)別于此，本研究從實際應(yīng)用角度出發(fā)，首先對其某市22 所高校高校進行了實地考察和數(shù)據(jù)收集。其次，查閱相關(guān)文獻，了解國內(nèi)外在VRP 方面的研究進展、方法和技術(shù)，總結(jié)本文研究某市高校蔬菜車輛配送中存在的問題。隨后，建立一個實際的物流網(wǎng)絡(luò)模型并對在OR-Tools 工具包的基礎(chǔ)上編碼進行該模型求解。通過對比不同參數(shù)設(shè)置下的優(yōu)化的求解結(jié)果，分析其優(yōu)缺點，結(jié)合VRP 問題的解決方案，為社區(qū)某市蔬菜配送運輸提供一種有效的路徑優(yōu)化方案。原因有如下幾點，OR-Tools 提供了使用多種算法和工具，且能高效地求解計算出最優(yōu)車輛行駛路徑結(jié)果。同時，支持多種編程語言,本文使用Python 編程語言構(gòu)建模型框架能自由修改源代碼，符合本文模型的實際問題求解需要。

2.2 代碼框架

求解的代碼框架如圖2 所示。其中，OR-Tools 的核心原理是建立數(shù)學(xué)模型和求解器，且主要用于解決車輛路徑、流程、整數(shù)和線性規(guī)劃以及約束等問題，可用ORTools 中的RoutingModel 分析求解，以此尋找方案的相對最優(yōu)求解結(jié)果。在此基礎(chǔ)上，代碼基于Python3.8 編寫，首先引入OR-Tools 以及matplotlib 工具包，其次，記錄和設(shè)置本文模型中各參數(shù)，如物流中心與各高校的坐標(biāo)位置、車輛數(shù)量、物流中心為出發(fā)點與起始點，以矩陣和數(shù)組表示。隨后，利用OR-Tools 的函數(shù)求解，求解思路是使用路由模型以及距離回調(diào)、確定采用距離矩陣，進而通過計算重量和每輛車的載重以及對應(yīng)距離長度計算獲取路線來尋找每輛車的最佳路徑。最后，繪制圖像將最優(yōu)車輛行駛路徑結(jié)果可視化。

圖2 求解思路

3 問題分析

3.1 配送現(xiàn)狀

目前，物流中心配送車輛有12 臺，其中承載量為4 噸的貨車有4 臺，配送路況較差的線路，承載量為6 噸的貨車有4 臺，承載量為8 噸的貨車有4 臺，配送道路路況較好的線路，訂單量激增時會租借其他車隊的車?，F(xiàn)在的配送是由物流中心分別向各個學(xué)校之間的單獨配送，每次只配送一個學(xué)校的蔬菜，配送完成后需重新返回物流中心進行下一個學(xué)校蔬菜的配送。物流中心以及高校分布圖如圖3 所示。

圖3 高校坐標(biāo)相對位置

3.2 配送現(xiàn)狀存在的問題

配送貨運車輛運力不足且性能與承載量無法滿足目前的需求，相比其他城市，物流中心的配送路線的問題也有很多不合理的地方。

3.2.1 配送規(guī)劃不合理

現(xiàn)在的配送是由物流中心分別向各個學(xué)校之間的單獨配送，每次只配送一個學(xué)校的蔬菜，配送完成后需重新返回物流中心進行下一個學(xué)校蔬菜的配送，因而需要在物流中心和各學(xué)校網(wǎng)點之間來回，配送路線出現(xiàn)重復(fù)。從而導(dǎo)致物流中心的配送次數(shù)增多、配送效率降低，并且運輸成本增加，造成不必要的運輸資源浪費。

3.2.2 配送時間不合理

配送時間的錯亂，現(xiàn)在配送的順序是按大學(xué)、中學(xué)來進行區(qū)分配送的，單輛配送車負責(zé)的配送區(qū)域跨度較大，配送時間過長。因而常常導(dǎo)致無法按時送達貨物，或使各網(wǎng)點延遲收貨時間，對一些急需蔬菜的客戶群體造成收貨延遲，顧客滿意度下降，損失大部分客戶。

3.2.3 配送路線不合理

配送線路單一，目前物流中心采用的配送線路是由多年前道路路況狀況及貨物運輸量來設(shè)計的，經(jīng)過的重復(fù)路徑過多。對于如今的發(fā)展，此配送線路已無法滿足目前的需求，同時也降低了物流中心對某市高效蔬菜配送的作業(yè)效率。

3.3 路徑改進

每輛車需要在不同的地點提取貨物并在其他地點交付貨物，要求是為車輛分配路線以提取和交付所有貨物，同時最小化所有訪問路線的總長度?？紤]使用OR-Tools的RoutingModel 等模塊。根據(jù)上述背景數(shù)據(jù)，通過Python實現(xiàn)上述實際問題的蔬菜配送優(yōu)化求解。實驗硬件顯卡為NVIDIA GeForce RTX 2060 內(nèi)存為16GB。

算法運行結(jié)果如表1 與圖4 所示。其中，編號1 至11為大學(xué)A 至K，編號12 至22 為某市第一中學(xué)至第某市第十一中學(xué)。其中車輛總裝載量、車輛路線以及路程距離均得到了體現(xiàn)。

表1 優(yōu)化結(jié)果數(shù)據(jù)表

圖4 車輛運輸路線圖

配送需求量改進，車輛載重量最大效益化，改進前每次只配送一個學(xué)校的蔬菜就回到物流中心。由表1 可見總路程為269531m，運輸車輛從原有的12 臺降低至10 臺，減少了無效車輛2 輛；總路徑降低至27 公里左右，配送效率提高了5%，打破了原有的車輛規(guī)劃與配送路線。表明，本文方法在帶容量多車輛類型的路徑優(yōu)化中優(yōu)勢顯著，可收獲效果理想。每個學(xué)校的蔬菜需求量有大有小，蔬菜需求量可能不滿足車輛裝載量的最大化，本文通過改進后的車輛路徑優(yōu)化，可使車輛完成一個學(xué)校配送后還有盈余量送往另一個配送點，減少了無效車輛的使用，節(jié)約配送成本的同時還能在客戶預(yù)期的時間內(nèi)完成配送，提高用戶滿意程度，優(yōu)化后的結(jié)果具有實際踐行意義。

4 結(jié)論與建議

本文基于python3.8，利用OR-Tools 與matplotlib，針對某市各高校的蔬菜生鮮配送為代表的車輛容量約束的VRP 問題，應(yīng)用本文模型與求解框架進行研究并得到了最優(yōu)配送線路，探討了求解時間、門店空間分布以及裝載約束條件變化對優(yōu)化結(jié)果的影響，驗證了本研究的實踐應(yīng)用價值。與改進前相比，改進后，總車輛數(shù)目與平均路程均得到了改善。但研究仍存在以下不足：

①沒有考慮帶時間窗的VRP 問題。在實際情況中，各高校的食堂會提前制作好菜肴以供師生享用，因此物流中心運輸蔬菜生鮮至各高校時應(yīng)當(dāng)在其食堂預(yù)定時間內(nèi)送達，否則配送不能滿足客戶需求，實際意義降低。因此，將來應(yīng)該考慮帶時間窗的VRP 問題。

②沒有考慮多配送中心運輸問題。在實際情況中，配送中心與各高校協(xié)調(diào)后應(yīng)會調(diào)度多個配送中心的車輛運輸。本文僅考慮了一個配送中心的車輛運輸問題，如若考慮多配送中心，客戶將會覆蓋到湘潭市更多的高校，實際模型才更準(zhǔn)確。因此，將來應(yīng)考慮多配送中心的車輛運輸路徑的優(yōu)化問題。