程紀揚

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

一、引言

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

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

（一）問題描述

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

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

表2 蔬菜銷售點日需求量（噸/天）及短缺補償（元/噸·天）

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

（二）算法的選擇

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

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

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

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

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

（三）配送路徑情況分析

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

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

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

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

改進算法步驟如下：

步驟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é)點Vi與節(jié)點Vj之間的最短路徑經(jīng)過節(jié)點Vi，并且路長 的 值 dij（k+1）。

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

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

（二）建立模型

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

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

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

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

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

（三）模型的求解

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

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

表4 蔬菜基地與銷售點的最短距離表

綜上，可以得到：

短缺補償費用：=42658.00

調(diào)運費用：=178.28

政府花費:=42836.28元。

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

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

四、結(jié)束語

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

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

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

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