基于OR-Tools 的某市高校蔬菜配送路徑優(yōu)化

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

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

0 引言

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

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

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

1 問(wèn)題及模型

1.1 問(wèn)題描述

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

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

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

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

③各客戶(hù)節(jié)點(diǎn)（買(mǎi)方）只能接受1 輛配送車(chē)為其進(jìn)行配送，且需求量不能超過(guò)配送車(chē)的最大載荷。

圖1 蔬菜物流配送流程

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

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

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

⑦物流中心的成本只考慮運(yùn)輸成本，裝卸成本忽略不計(jì)。

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

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

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

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

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

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

Q：每輛車(chē)的容量限制；

di：客戶(hù)點(diǎn)的需求量；

ci，j：客戶(hù)點(diǎn)i 到客戶(hù)點(diǎn)j 的距離；

1.3 模型構(gòu)建

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

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

2 求解方法

2.1 求解思路

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

2.2 代碼框架

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

圖2 求解思路

3 問(wèn)題分析

3.1 配送現(xiàn)狀

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

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

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

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

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

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

3.2.2 配送時(shí)間不合理

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

3.2.3 配送路線不合理

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

3.3 路徑改進(jìn)

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

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

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

圖4 車(chē)輛運(yùn)輸路線圖

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

4 結(jié)論與建議

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

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

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