姜思源,曹春玲,孟超,浦東,王凱琪
(吉林大學(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](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)。
本文主要研究某市蔬菜種植和配送的最優(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)量
本文研究了某市蔬菜生產(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