政府補(bǔ)償約束下蔬菜配送路徑優(yōu)化分析
——以A市為例

程紀(jì)揚(yáng)

（安徽財(cái)經(jīng)大學(xué)，安徽 蚌埠 233030）

一、引言

蔬菜與其他商品相比，品種多、流通渠道較短、配送環(huán)節(jié)復(fù)雜。因此，配送過程的優(yōu)劣直接影響蔬菜產(chǎn)業(yè)服務(wù)質(zhì)量、物流效率和蔬菜產(chǎn)業(yè)收益的高低[1]。蔬菜配送是將新鮮的蔬菜從種植基地運(yùn)送到銷售點(diǎn)的過程，該過程中需要綜合考慮各銷售點(diǎn)的蔬菜需求量及蔬菜到達(dá)各銷售點(diǎn)的路程遠(yuǎn)近、運(yùn)輸費(fèi)用及產(chǎn)品耗損等要素，最終對蔬菜產(chǎn)業(yè)進(jìn)行合理種植、揀選分裝、配貨運(yùn)輸?shù)确矫娴膬?yōu)化，使蔬菜產(chǎn)業(yè)帶來的經(jīng)濟(jì)利益達(dá)到最大[2]。對于一些中小城市，蔬菜種植采取以郊區(qū)和農(nóng)區(qū)種植為主，為了保障城區(qū)蔬菜的供應(yīng)，當(dāng)?shù)卣畬κ卟伺渌铜h(huán)節(jié)實(shí)施一定補(bǔ)貼政策[3]。然而，政府補(bǔ)償是有限的，在既定約束下如何優(yōu)化配送路徑，不僅有效提高城區(qū)蔬菜供應(yīng)的數(shù)量和質(zhì)量，還能帶動(dòng)農(nóng)區(qū)菜農(nóng)種植蔬菜的積極性。本文以A市為例，利用Floyd算法求出A市各蔬菜種植基地到各銷售點(diǎn)的最短距離，并利用Lingo軟件進(jìn)行線性規(guī)劃操作，求出政府補(bǔ)償約束下的蔬菜配送最優(yōu)路徑，以期為我國中小城市在政府補(bǔ)償約束下蔬菜配送路徑的優(yōu)化提供一套行之有效的方法。

二、A市蔬菜配送問題提出

（一）問題描述

A市的人口近90萬，該市在郊區(qū)和農(nóng)區(qū)建立了8個(gè)蔬菜種植基地 （記為Ai，i=1,2,3，...,8），承擔(dān)全市居民的蔬菜供應(yīng)任務(wù)，每天將蔬菜運(yùn)送到市區(qū)的35個(gè)蔬菜銷售點(diǎn)（記為Bj，j=1,2,3，...,35）。 市區(qū)有 15 個(gè)主要交通路口（記為 Lm，m=1,2,3，...,15），在蔬菜運(yùn)送的過程中從蔬菜種植基地可以途徑這些交通路口再到達(dá)蔬菜銷售點(diǎn)。如果蔬菜銷售點(diǎn)的需求量不能滿足，則市政府要給予一定的短缺補(bǔ)償。同時(shí)市政府還按照蔬菜種植基地供應(yīng)蔬菜的數(shù)量以及路程，發(fā)放相應(yīng)的運(yùn)費(fèi)補(bǔ)貼，以此提高菜農(nóng)種植蔬菜的積極性，對蔬菜產(chǎn)業(yè)起到宏觀調(diào)控的作用。其中，運(yùn)費(fèi)補(bǔ)貼標(biāo)準(zhǔn)為0.04元/（噸·公里）。本文根據(jù)A市蔬菜配送相關(guān)數(shù)據(jù)（如表1、表2及表3所示），在政府所付的短缺補(bǔ)償和運(yùn)費(fèi)補(bǔ)貼最少的條件下，為A市設(shè)計(jì)從蔬菜種植基地至各蔬菜銷售點(diǎn)的蔬菜運(yùn)送方案。

表1 蔬菜種植基地日供應(yīng)量（噸/天）

表2 蔬菜銷售點(diǎn)日需求量（噸/天）及短缺補(bǔ)償（元/噸·天）

表3 各基地、銷售點(diǎn)及路口之間的距離（km）

（二）算法的選擇

本文旨在解決在政府補(bǔ)償約束下的最短路徑問題。最短路徑問題是指用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑[4]，主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。解決這一類問題的方法有很多，包括Floyd算法、Dijkstra算法、SPFA算法等，其中最為常用的是Floyd算法。

Floyd算法是用于尋找給定加權(quán)圖中頂點(diǎn)間路徑最短的算法[5]，適用于 APSP（All Pairs Shortest Paths，多源最短路徑），是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。由于Floyd算法簡單有效，三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，其效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行|V|次SPFA算法。并且，F(xiàn)loyd算法容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡單。因此，本文采用Floyd算法解決問題。

Floyd算法基本思想為：首先設(shè)置一個(gè)矩陣A（k），其中對角線元素全為0，其他ak[i][j]表示頂點(diǎn)i到j(luò)的路徑值，k代表運(yùn)算步驟，當(dāng)k=0時(shí)：

A（0）[i][j]=arcs[i][j]

得出的矩陣稱為臨接矩陣，以后逐步的嘗試在原路徑的兩頂點(diǎn)上增加其他頂點(diǎn)作為中心頂點(diǎn)，如果增加中間頂點(diǎn)后，新的路徑比原來路徑減小了，則用新的路徑代替舊路徑，并修改矩陣元素，否則不變。

（三）配送路徑情況分析

根據(jù)A市蔬菜配送相關(guān)數(shù)據(jù)，利用Matlab編程繪制出蔬菜種植基地、交通路口、銷售點(diǎn)之間的散點(diǎn)路線圖，如圖1所示。圖中一共有58個(gè)節(jié)點(diǎn)（其中包括8個(gè)蔬菜種植基地，15個(gè)路口以及35個(gè)銷售基地），通過Matlab軟件繪圖使得各基地、銷售點(diǎn)、路口之間的距離一目了然。對圖中的8個(gè)蔬菜種植基地的編號(hào)為 V1—V8；35個(gè)銷售點(diǎn)的編號(hào)為 V9—V43；15個(gè)路口的編號(hào)為 V44—V58。

三、模型構(gòu)建與求解

（一）利用 Floyd算法求出各蔬菜種植基地到各銷售點(diǎn)的最短距離

在不含負(fù)回路的網(wǎng)絡(luò)中，有節(jié)點(diǎn) V1，V2，…，Vn，用 Wij表示節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vj之間的連線長，用dij表示從節(jié)點(diǎn)Vi出發(fā)到節(jié)點(diǎn)Vj時(shí)的路長[6]。

改進(jìn)算法步驟如下：

步驟1：作初始權(quán)矩陣D（0）

步驟 2：在 D（k）中，若 i=j，則 dij（k+1）=0；否則轉(zhuǎn)至步驟 3。

步驟 3：若 dij（k）=∞ 或 dij（k）=∞（l=1,2,…,n），且 dij（k）≠∞,則 dij（k+1）=dij（k），否則轉(zhuǎn)至步驟 4。

步 驟 4： 若 dij（k）≥dij（k）或 dij（k）≥dij（k）（l=1,2,… ,n 且 l≠i,j），則 dij（k+1）=dij（k），否則轉(zhuǎn)至步驟 5。

步驟 5:若 i＜j，則

dij（k+1）=min{dij（k），{dij（k+1）dij（k+1）}，{dij（k+1）dij（k）}，{dij（k）dij（k）}}；

圖1 路線圖

否則

dij（k+1）=min{dij（k），{dij（k+1）dij（k+1）}，{dij（k）dij（k+1）}，{dij（k）dij（k）}}

若 dij（k+1）=dij（k）+dij（k）， 且 dij（k+1）＜dij（k），則 將 l 標(biāo) 注 在 權(quán) 矩陣 D（k+1）中的元素 dij（k+1）的右下角，表明經(jīng)過本次迭代后，節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj之間的最短路徑經(jīng)過節(jié)點(diǎn)Vi，并且路長 的 值 dij（k+1）。

步驟 6:若 D（k+1）=D（k），結(jié)束；否則 k=k+1，轉(zhuǎn)至步驟 2。

利用MATLAB實(shí)現(xiàn)算法程序化，求得各蔬菜基地到各個(gè)銷售點(diǎn)的最短距離如表4所示。

（二）建立模型

由表1及表2中的數(shù)據(jù)可知，市場的總需求量為360噸，而8個(gè)蔬菜生產(chǎn)基地的總產(chǎn)量僅為270噸，蔬菜的供給量小于需求量，市場處于供不應(yīng)求的狀態(tài)，此時(shí)利用Lingo軟件進(jìn)行線性規(guī)劃操作，求出最優(yōu)解。

設(shè)政府付出的費(fèi)用為F,則F=F1+F2,F1為市場的短缺補(bǔ)償費(fèi)用，即各銷售點(diǎn)對蔬菜的需求得不到滿足時(shí)所獲得的補(bǔ)償，F(xiàn)2為調(diào)運(yùn)費(fèi)用。 則可知：F1=Pj×（bj-xij）

其中，i=1,2,…,8；j=1,2,3,…,35；Pj為第 j個(gè)銷售點(diǎn)的蔬菜供給量達(dá)不到需求量時(shí)的單位補(bǔ)貼；bj為第j個(gè)銷售點(diǎn)對蔬菜的需求；xij為第i個(gè)蔬菜生產(chǎn)基地運(yùn)往第j個(gè)銷售點(diǎn)的蔬菜量。

其中 i=1,2,…,8；j=1,2,3,…,35；c 為運(yùn)輸每單位蔬菜的單位距離花費(fèi)；xij為第i個(gè)蔬菜生產(chǎn)基地運(yùn)往第j個(gè)銷售點(diǎn)的蔬菜量。sij為第i個(gè)蔬菜生產(chǎn)基地到第j個(gè)銷售點(diǎn)的距離。所以目標(biāo)函數(shù)最小費(fèi)用為：

又因?yàn)槭袌鎏幱诠┎粦?yīng)求的狀態(tài)，每個(gè)蔬菜基地的供應(yīng)量應(yīng)全部運(yùn)輸?shù)礁鱾€(gè)銷售點(diǎn)，即：xij=ai同時(shí)各個(gè)基地運(yùn)送到銷售點(diǎn)的蔬菜量應(yīng)小于其需求量，即：xij≤bj，其中ai為每一個(gè)蔬菜基地每天能夠提供的蔬菜量，bj為每一個(gè)銷售點(diǎn)每天需要的蔬菜量。所以，可規(guī)劃函數(shù)為：

（三）模型的求解

利用Lingo程序求解模型，求得運(yùn)送分配方案結(jié)果，具體內(nèi)容如表5所示。

通過表2與表5的對比參照，得出各銷售點(diǎn)的需要量的滿足情況。如果未滿足銷售點(diǎn)需求量，使用短缺量乘以單位短缺補(bǔ)償，進(jìn)行簡單的數(shù)學(xué)計(jì)算可以得出短缺補(bǔ)償費(fèi)用；再通過表2、表4與表5的對比參照，得出蔬菜配送過程中的運(yùn)輸路程與重量，得到的數(shù)值乘以運(yùn)費(fèi)補(bǔ)貼標(biāo)準(zhǔn)便得出調(diào)運(yùn)費(fèi)用。其中，運(yùn)費(fèi)補(bǔ)貼為0.04元/（噸·公里）。

表4 蔬菜基地與銷售點(diǎn)的最短距離表

綜上，可以得到：

短缺補(bǔ)償費(fèi)用：=42658.00

調(diào)運(yùn)費(fèi)用：=178.28

政府花費(fèi):=42836.28元。

表5 蔬菜運(yùn)送數(shù)量分配方案表

通過模型的構(gòu)建與求解，計(jì)算出政府支付的短缺補(bǔ)償和運(yùn)費(fèi)補(bǔ)貼最少的條件下，花費(fèi)為42836.28元。可見，政府在推進(jìn)城市蔬菜供應(yīng)的過程中，運(yùn)用Floyd算法，不僅有效保障了城區(qū)蔬菜供應(yīng)的數(shù)量和質(zhì)量，同時(shí)促進(jìn)農(nóng)區(qū)菜農(nóng)種植蔬菜的積極性，緩解財(cái)政資金補(bǔ)償?shù)牟蛔悖M(jìn)而實(shí)現(xiàn)政府的民生工程目標(biāo)。

四、結(jié)束語

以Floyd算法為核心設(shè)計(jì)并優(yōu)化蔬菜配送系統(tǒng)，能夠在蔬菜運(yùn)送過程中找到一條從產(chǎn)地到市場的最佳運(yùn)輸路線，有效減少蔬菜運(yùn)輸過程中的產(chǎn)品損耗，提高配送效率并且符合蔬菜配送的時(shí)效性特點(diǎn)。在本文中，政府補(bǔ)償約束下的蔬菜配送路徑優(yōu)化可理解為在原有的路徑設(shè)計(jì)上增加政府補(bǔ)償約束這一限制條件，使自然的蔬菜配送系統(tǒng)升級(jí)為政府調(diào)控下的蔬菜配送系統(tǒng)。政府利用補(bǔ)償約束條件在宏觀上對蔬菜配送系統(tǒng)進(jìn)行調(diào)整，使其更加符合市場需求，同時(shí)也能有效預(yù)防系統(tǒng)長期運(yùn)行中可能出現(xiàn)的弊端。與傳統(tǒng)的蔬菜配送相比，路徑優(yōu)化后一方面可以縮短運(yùn)輸時(shí)間，從而保證蔬菜的新鮮程度，提高食材的安全度；另一方面，在經(jīng)過充分計(jì)算后設(shè)計(jì)的方案，政府能夠在支付最少的情況下完成任務(wù)，因此能夠提升財(cái)政資金效用與自身行政效率。誠然，在實(shí)際的運(yùn)輸過程中，時(shí)間、氣溫、交通狀況等各種受限參數(shù)也會(huì)對配送產(chǎn)生影響，這些分析工作有待進(jìn)一步研究。

參考文獻(xiàn)：

[1]王琳,楊莉,楊曉明.蔬菜綠色供應(yīng)鏈配送優(yōu)化研究[J].食品研究與開發(fā),2016,37（22）:187-190.

[2]汪世志,張志清.城市蔬菜業(yè)的物流配送優(yōu)化研究——以武漢為例[J].物流技術(shù),2014,33（7）:110-112.

[3]姜思源,曹春玲,孟超,等.基于狄杰斯特拉算法的蔬菜種植和配送最優(yōu)化[J].長春理工大學(xué)學(xué)報(bào)（自然科學(xué)版）,2017,40（3）:130-133.

[4]左秀峰,沈萬杰.基于Floyd算法的多重最短路問題的改進(jìn)算法[J].計(jì)算機(jī)科學(xué),2017,44（5）:232-234.

[5]劉海洋,木仁.基于Floyd算法的公交專用車道設(shè)置路段分析[J].中國管理科學(xué),2015,23（S1）:257-261.

[6]趙禮峰,梁娟.最短路問題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24（8）:31-34.