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

（吉林大學 數(shù)學學院，長春 130022）

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

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

（吉林大學 數(shù)學學院，長春 130022）

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

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

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

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

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

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

表1 蔬菜運送距離

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

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

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

算法結束時，從u0到各頂點v的距離由v的最后一次的標號l(v)給出。在v進入Si之前的標號l(v)叫T標號，v進入Si時的標號l(v)叫P標號。算法就是不斷修改各頂點的T標號，直至獲得P標號。若在算法運行過程中，將每一頂點獲得P標號所由來的邊在圖上標明，則算法結束時，u0至各項點的最短路徑即可在圖上標示出來。

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

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

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

設i表示基地編號，j表示銷售點編號，yij表示基地i對銷售點j運送量；pj表示銷售點的需求量，dij表示運送總路程，Mj表示短缺補償；C表示政府的補貼總額，則補貼總額的目標函數(shù)如下：

根據(jù)調研給出8個基地的產量和35個銷售點的需求量見表2和表3，建立8個基地的產量、35個銷售點的需求量與運送量約束關系，其中Gi表示基地產量。

表2 蔬菜種植基地日供應量（噸/天）

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

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

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

圖1 蔬菜基地、路口和銷售點的位置圖

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

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

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

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

表5 基地產量與增產量

3 結論

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

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

［2］ 王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題［J］.計算機科學，2014，41（6）：217-224.

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

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

［5］ 陳華友，周禮剛，劉金培.數(shù)學模型與數(shù)學建模［M］.北京：科學出版社，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

自然科學基金資助（J1310022）

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

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