基于OR-Tools 的某市高校蔬菜配送路徑優化

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

（湖南科技大學，湘潭 411201）

0 引言

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

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

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

1 問題及模型

1.1 問題描述

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

基于現實情況，為簡化問題處理但不失一般性，假設如下：

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

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

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

圖1 蔬菜物流配送流程

④各客戶節點的地理坐標、產品需求量等均已知。

⑤學校快遞點和物流中心的個數均唯一。

⑥物流中心至學校快遞點、學校快遞點之間路徑唯一，且距離已知。

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

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

1.2 參數及變量定義

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

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

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

m：車輛的總數量；

Q：每輛車的容量限制；

di：客戶點的需求量；

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

1.3 模型構建

基于上述問題與假設，以某物流中心的蔬菜配送服務為應用對象，構建規劃模型如下：

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

2 求解方法

2.1 求解思路

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

2.2 代碼框架

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

圖2 求解思路

3 問題分析

3.1 配送現狀

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

圖3 高校坐標相對位置

3.2 配送現狀存在的問題

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

3.2.1 配送規劃不合理

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

3.2.2 配送時間不合理

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

3.2.3 配送路線不合理

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

3.3 路徑改進

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

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

表1 優化結果數據表

圖4 車輛運輸路線圖

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

4 結論與建議

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

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

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