基于狄杰斯特拉算法的蔬菜種植和配送最優(yōu)化

姜思源，曹春玲，孟超，浦東，王凱琪

（吉林大學(xué) 數(shù)學(xué)學(xué)院，長(zhǎng)春 130022）

基于狄杰斯特拉算法的蔬菜種植和配送最優(yōu)化

姜思源，曹春玲，孟超，浦東，王凱琪

（吉林大學(xué) 數(shù)學(xué)學(xué)院，長(zhǎng)春 130022）

采用狄杰斯特拉（Dijkstra）最優(yōu)化理論，對(duì)城市周邊的蔬菜種植和配送建立數(shù)學(xué)模型，在考慮增加蔬菜種植量同時(shí)各蔬菜銷售點(diǎn)的短缺量一律不超過(guò)需求量的30%的情況下，實(shí)現(xiàn)了總短缺補(bǔ)償和運(yùn)費(fèi)補(bǔ)貼最少。對(duì)“菜籃子工程”具有一定的指導(dǎo)意義和應(yīng)用價(jià)值。

狄杰斯特拉算法；菜籃子工程；蔬菜配送方案

為緩解我國(guó)副食品供不應(yīng)求的矛盾，農(nóng)業(yè)部于1988年提出建設(shè)“菜籃子工程”，以保證居民一年四季都有新鮮的副食品供應(yīng)。對(duì)于一些中小城市，蔬菜種植采取以郊區(qū)和農(nóng)區(qū)種植為主，結(jié)合政府補(bǔ)貼的方式來(lái)保障城區(qū)蔬菜的供應(yīng)。這樣不僅提高了城區(qū)蔬菜供應(yīng)的數(shù)量和質(zhì)量，還帶動(dòng)了郊區(qū)和農(nóng)區(qū)菜農(nóng)種植蔬菜的積極性。但由于地區(qū)差異，蔬菜產(chǎn)區(qū)過(guò)于分散使其在種植區(qū)域和運(yùn)輸路徑、配送成本上存在很多問(wèn)題。因此采用最優(yōu)算法對(duì)蔬菜配送路徑進(jìn)行優(yōu)化就顯得尤為重要。

最優(yōu)路徑算法是路徑分析中最常用的算法之一。在很多領(lǐng)域都應(yīng)用非常廣泛，例如車載導(dǎo)航系統(tǒng)、智慧交通系統(tǒng)等都離不開(kāi)最優(yōu)路徑算法的應(yīng)用。本文在詳細(xì)分析了某市蔬菜基地與銷售點(diǎn)交通路線情況的基礎(chǔ)上，應(yīng)用最優(yōu)算法中經(jīng)典的狄杰斯特拉（Dijkstra）最短路徑法分析得出從蔬菜基地到不同銷售點(diǎn)的最佳運(yùn)送路線，并從減少政府補(bǔ)貼的角度出發(fā)，建立目標(biāo)函數(shù)和相應(yīng)的約束條件，進(jìn)行參數(shù)優(yōu)化，得出不同要求下的最佳運(yùn)送方案和補(bǔ)貼金額。從而為企業(yè)提供實(shí)時(shí)蔬菜配送最優(yōu)路徑和管理手段，提高企業(yè)和社會(huì)效益。

1 狄杰斯特拉最優(yōu)化算法研究

狄杰斯特拉算法［1］（Dijkstra）是由荷蘭計(jì)算機(jī)科學(xué)家狄杰斯特拉于1959年提出，應(yīng)用貪心算法模式，是目前公認(rèn)的最好的求解最短路徑的方法。算法解決的是圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問(wèn)題，其主要特點(diǎn)是每次迭代時(shí)選擇的下一個(gè)頂點(diǎn)是標(biāo)記點(diǎn)之外距離源點(diǎn)最近的頂點(diǎn)。狄杰斯特拉算法屬于圖論中關(guān)于最優(yōu)路徑的算法。

表1 蔬菜運(yùn)送距離

狄杰斯特拉算法的基本思想是按距離u0從近到遠(yuǎn)的順序，以此求得u0到G的各項(xiàng)頂點(diǎn)的最短路徑和距離，直到v0（或直到G的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用標(biāo)號(hào)算法。算法實(shí)現(xiàn)如下

（1）令l(u0)=0，對(duì)v≠u0，令l(v)=∞ ，S0={u0}，i=0。

（3）若i=|v|-1，停止；若i＜|v|-1，用i+1替代i，轉(zhuǎn)第2步。

算法結(jié)束時(shí)，從u0到各頂點(diǎn)v的距離由v的最后一次的標(biāo)號(hào)l(v)給出。在v進(jìn)入Si之前的標(biāo)號(hào)l(v)叫T標(biāo)號(hào)，v進(jìn)入Si時(shí)的標(biāo)號(hào)l(v)叫P標(biāo)號(hào)。算法就是不斷修改各頂點(diǎn)的T標(biāo)號(hào)，直至獲得P標(biāo)號(hào)。若在算法運(yùn)行過(guò)程中，將每一頂點(diǎn)獲得P標(biāo)號(hào)所由來(lái)的邊在圖上標(biāo)明，則算法結(jié)束時(shí)，u0至各項(xiàng)點(diǎn)的最短路徑即可在圖上標(biāo)示出來(lái)。

2 蔬菜最優(yōu)化種植和配送

本文主要研究某市蔬菜種植和配送的最優(yōu)方案，通過(guò)調(diào)研蔬菜基地、蔬菜銷售點(diǎn)及相互位置關(guān)系和交通狀況，得出某市蔬菜基地、路口和銷售點(diǎn)三者之間的位置關(guān)系，如圖1所示。結(jié)合圖論相關(guān)理論，建立各個(gè)蔬菜基地、路口和銷售點(diǎn)的鄰接矩陣，應(yīng)用狄杰斯特拉算法，利用Matlab軟件實(shí)現(xiàn)算法，得出從蔬菜基地到各個(gè)銷售點(diǎn)的最短運(yùn)輸路線，如表1所示。運(yùn)輸補(bǔ)貼正比于運(yùn)輸量和運(yùn)輸距離，因此每個(gè)種植基地運(yùn)往每個(gè)銷售點(diǎn)的蔬菜可以單獨(dú)運(yùn)輸，所以選擇兩地之間最短路線運(yùn)送蔬菜即可使總運(yùn)費(fèi)補(bǔ)貼最少。

本模型中假設(shè)運(yùn)送蔬菜的汽車數(shù)量足夠多，當(dāng)選擇最短的運(yùn)送路線時(shí)可以使政府的運(yùn)費(fèi)補(bǔ)貼最少，從而使政府的補(bǔ)貼總額達(dá)到最低，因而在本模型中蔬菜運(yùn)送路線選擇表1所述的最短路線。

設(shè)i表示基地編號(hào)，j表示銷售點(diǎn)編號(hào)，yij表示基地i對(duì)銷售點(diǎn)j運(yùn)送量；pj表示銷售點(diǎn)的需求量，dij表示運(yùn)送總路程，Mj表示短缺補(bǔ)償；C表示政府的補(bǔ)貼總額，則補(bǔ)貼總額的目標(biāo)函數(shù)如下：

根據(jù)調(diào)研給出8個(gè)基地的產(chǎn)量和35個(gè)銷售點(diǎn)的需求量見(jiàn)表2和表3，建立8個(gè)基地的產(chǎn)量、35個(gè)銷售點(diǎn)的需求量與運(yùn)送量約束關(guān)系，其中Gi表示基地產(chǎn)量。

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

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

利用Lingo軟件，編程可以得到最優(yōu)條件下的蔬菜配送方案和配送量，利用公式1可以計(jì)算出最優(yōu)配送方案下對(duì)應(yīng)的補(bǔ)貼值C=42821.66元。當(dāng)存在短缺量上線限制時(shí)，在原有約束條件中加入短缺上限條件，使短缺量上限小于需求量的30%。

利用Lingo軟件，編程可以得到使短缺量上限小于需求量的30%時(shí)最優(yōu)條件下的蔬菜配送方案和配送量，見(jiàn)表4。根據(jù)公式1得到存在短缺上限時(shí)的最優(yōu)政府補(bǔ)貼總額C=50469.61元

圖1 蔬菜基地、路口和銷售點(diǎn)的位置圖

表4 短缺量上限小于需求量的30%條件下的最優(yōu)蔬菜配送方案和配送量

根據(jù)前面最優(yōu)化分析得到最優(yōu)條件下的蔬菜配送方案和配送量。但在實(shí)際配送過(guò)程中，要考慮不同銷售點(diǎn)的實(shí)際需求量。因此需在此基礎(chǔ)上對(duì)模型進(jìn)行調(diào)整，利用前面分析中得到的最佳運(yùn)輸路線。以滿足各個(gè)銷售點(diǎn)的需求量為原則，采用逆向分配的方法，由銷售點(diǎn)向種植基地分配供應(yīng)量。建立約束條件，結(jié)合目標(biāo)函數(shù)，從而得出各個(gè)基地的增產(chǎn)和蔬菜運(yùn)輸方案，獲得最佳的政府補(bǔ)貼方案。得出增產(chǎn)后的配送方案和補(bǔ)貼金額，由增產(chǎn)前后蔬菜基地的產(chǎn)量得到各個(gè)基地所需增加的種植量。在分析中對(duì)部分基地的蔬菜種植面積進(jìn)行擴(kuò)大。通過(guò)分析發(fā)現(xiàn)相對(duì)于短缺補(bǔ)貼，運(yùn)費(fèi)補(bǔ)貼對(duì)政府總補(bǔ)貼額度的影響相對(duì)較小，因而在盡可能滿足供應(yīng)的條件下建立約束條件，在部分基地?zé)o產(chǎn)量上限的約束下使運(yùn)費(fèi)達(dá)到最少。目標(biāo)函數(shù)和約束條件如下：

利用Lingo軟件計(jì)算，可以得到最低補(bǔ)貼的運(yùn)送方案，根據(jù)目標(biāo)函數(shù)，得到最優(yōu)政府補(bǔ)貼總額為C=182.204元，補(bǔ)貼數(shù)額極小，實(shí)現(xiàn)了最優(yōu)化結(jié)果。

根據(jù)Lingo的運(yùn)算結(jié)果，可以得到增產(chǎn)狀態(tài)下各基地的種植數(shù)量，通過(guò)與表2中給出的每個(gè)基地的產(chǎn)量進(jìn)行對(duì)比，得出增產(chǎn)方案，如表5所示。

表5 基地產(chǎn)量與增產(chǎn)量

3 結(jié)論

本文研究了某市蔬菜生產(chǎn)基地與各個(gè)路口和蔬菜銷售基地的位置關(guān)系和交通狀況，應(yīng)用狄杰斯特拉算法，得出從蔬菜基地到各個(gè)銷售點(diǎn)的最短運(yùn)輸路線，即總運(yùn)費(fèi)補(bǔ)貼最少?？紤]供應(yīng)量和需求量，以滿足各個(gè)銷售點(diǎn)的需求量為原則，采用逆向分配的方法，由銷售點(diǎn)向種植基地分配供應(yīng)量。建立約束條件，結(jié)合目標(biāo)函數(shù)，從而得出各個(gè)基地的增產(chǎn)和蔬菜運(yùn)輸方案，獲得最佳的政府補(bǔ)貼方案。模型的復(fù)雜性和運(yùn)算量低，實(shí)用性好，具有很強(qiáng)的現(xiàn)實(shí)應(yīng)用指導(dǎo)意義。

［1］ 樊月珍，江發(fā)潮，毛恩榮.車輛行駛最優(yōu)路徑優(yōu)化算法設(shè)計(jì)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（23）：5758-5761.

［2］ 王樹(shù)西，李安渝.Dijkstra算法中的多鄰接點(diǎn)與多條最短路徑問(wèn)題［J］.計(jì)算機(jī)科學(xué)，2014，41（6）：217-224.

［3］ 張錦明，洪剛，文銳，等.Dijkstra最短路徑算法優(yōu)化策略［J］.測(cè)繪科學(xué)，2009，34（5）：105-106.

［4］ 周畢文，黃潔萍，李春華.線性規(guī)劃最優(yōu)解的探討及在生產(chǎn)與運(yùn)作管理中的應(yīng)用［J］.北京理工大學(xué)學(xué)報(bào)，2001，3（4）：47-49.

［5］ 陳華友，周禮剛，劉金培.數(shù)學(xué)模型與數(shù)學(xué)建模［M］.北京：科學(xué)出版社，2014：116-118.

Vegetables Planting and Distribution Optimization Based on the Dijkstra Optimization Algorithm

JIANG Siyuan，CAO Chunling，MENG Chao，PU Dong WANG Kaiqi
（Institute of Mathematics，Jilin University，Changchun 130022）

The paper establish a mathematical model to the peri-urban vegetables planting and distribution base on the DiJie Stel?la（Dijkstra）optimization theory，considering the increase in the vegetables planting and all the shortage of vegetables point-ofsale amount shall not exceed 30%of the demand，realize the shortage of total compensation and minimumfreightsubsidies.thepaper hasacertainguidingsignificanceandapplicationvaluetothe“vegetablebasketproject”.

DiJie stella（Dijkstra）optimization theory；vegetable basket project；vegetable distribution scheme

TP301.6 1

A

1672-9870（2017）03-0130-04

2017-03-05

自然科學(xué)基金資助（J1310022）

姜思源（1996-），男，本科，E-mail：873879194@qq.com

曹春玲（1971-），女，副教授，E-mail：caocl@jlu.edu.cn