貨物配送問題

1、題目貨物配送問題摘要本文研究某公司豬肉銷售問題，構(gòu)建數(shù)學(xué)模型，設(shè)計生產(chǎn)與配送方案和增設(shè)銷售連 鎖店方案，使得銷售量最大。問題一要求設(shè)計生產(chǎn)與配送方案，使運輸成本最低。將最低成本問題轉(zhuǎn)化為最短路 徑問題，采用Dijkstra算法：D v Min D v , D w l w,v利用Matlab編程，得到生產(chǎn)基地到所有連鎖店的最短路線：生產(chǎn)基地63為提供3、467、8、12、4、16、7、8、20、23這幾家連鎖店提供鮮豬肉，所耗費的成本約為 4559元，生 產(chǎn)基地120為1、2、5、9、1011、315、19、21、22這幾家連鎖店提供鮮豬肉，所耗費的成本為 6175元，最低總成本為10734元。

2、問題二要求分析各城鎮(zhèn)需求特征并預(yù)測需求達(dá)到峰值的時間及到峰值時需求達(dá)到 前5位和后5位的城鎮(zhèn)。對于需求通過特征分析，通過 SPSS乍出城鎮(zhèn)需求量與時間的折 線圖，可知全省的鮮豬肉的需求量從 2008 2012年雖上下波動，但總體上升趨勢明顯， 每年對鮮豬肉的需求量明顯升高。對于對未來幾年的預(yù)測，通過作出的散點圖利用Matlab進(jìn)行擬合，根據(jù)擬合曲線得 出2014年需求量會達(dá)到峰值為1437802，前五名分別為120號，63號，31號，106號, 104號城鎮(zhèn)，后五名分別為30號，94號，84號，109號，129號城鎮(zhèn)。問題三要求為公司設(shè)計增設(shè)銷售連鎖店方案，使全省銷售量最大。采用0 1規(guī)劃算法

3、，構(gòu)建數(shù)學(xué)模型：154Max 輸 yi 1通過 Lin go 求得優(yōu)化方案：所求城鎮(zhèn) 6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增設(shè)連鎖店，其中城鎮(zhèn)120,31,6410123分別含有連鎖店 的個數(shù)是3,2,2,2,2。關(guān)鍵詞銷售方案 Dijkstra算法擬合曲線 0 1規(guī)劃模型、問題背景與重述1.1 問題背景某公司是一家肉類食品加工與銷售公司，主營：鮮豬肉。該公司在全省縣級及以上 城鎮(zhèn)設(shè)立銷售連鎖店。全省縣級及以上城鎮(zhèn)地理位置及道路連接見數(shù)據(jù)文件：全省交通 網(wǎng)絡(luò)數(shù)據(jù) . xlsx 。目

4、前該公司現(xiàn)有 2個生產(chǎn)基地、 23家銷售連鎖店，生產(chǎn)基地設(shè)在 120號 和 63 號城鎮(zhèn)，為 23 家連鎖店提供鮮豬肉，連鎖店的日銷售量見附錄 I 。通過廣告宣傳等手段，未來幾年公司在全省的市場占有率可增至3 成左右（各城鎮(zhèn)對公司產(chǎn)品每日需求預(yù)測數(shù)據(jù)見文件： 公司未來各城鎮(zhèn)每日需求預(yù)測數(shù)據(jù) .txt ），調(diào)查還 發(fā)現(xiàn)，公司產(chǎn)品的需求量與銷售量并不完全一致，若在當(dāng)?shù)兀ㄍ怀擎?zhèn)）購買，則這一 部分需求量與銷售量相同， 若在不足 10 公里的其他城鎮(zhèn)的銷售連鎖店購買， 則這一部分 需求量只能實現(xiàn)一半（成為公司產(chǎn)品銷售量，由于距離的原因，另一半需求轉(zhuǎn)向購買其 他公司或個體工商戶的產(chǎn)品） ，而在超過 1

5、0 公里的其他城鎮(zhèn)的銷售連鎖店購買，銷售量 只能達(dá)到需求量的三成。于是，公司決定在各城鎮(zhèn)增設(shè)銷售連鎖店，基于現(xiàn)有條件、成 本等的考慮，原有的 23家銷售連鎖店銷售能力可在現(xiàn)有銷售量的基礎(chǔ)上上浮 20% ，增 設(shè)的銷售連鎖店銷售能力控制在每日 20噸至 40噸內(nèi)，并且要求增設(shè)的銷售連鎖店的銷 售量必須達(dá)到銷售能力的下限。同一城鎮(zhèn)可設(shè)立多個銷售連鎖店。1.2 問題重述分析數(shù)據(jù)，并通過數(shù)學(xué)建模知識回答下述問題：1、若運輸成本為 0.45元/ 噸公里 ，為公司設(shè)計生產(chǎn)與配送方案，使運輸成本最低。2、根據(jù)公司收集的近 5 年全省各城鎮(zhèn)的鮮豬肉月度需求數(shù)據(jù)， 分析各城鎮(zhèn)需求特征， 并 預(yù)測未來何時全省鮮豬

6、肉需求達(dá)到峰值和達(dá)到峰值時需求達(dá)到前5位和后 5 位的城鎮(zhèn)。3、為公司設(shè)計增設(shè)銷售連鎖店方案，使全省銷售量達(dá)到最大。問題分析2.1 問題一的分析要設(shè)計生產(chǎn)與配送方案使運輸成本最低， 即可將最低成本問題轉(zhuǎn)化為最短路徑問題， 進(jìn)而得到最優(yōu)化生產(chǎn)和配送方案。Dijkstra 算法 2是最具代表性的最短路徑的算法，它以起點為中心向外層層拓展直至結(jié)點，因此可將連鎖店和生產(chǎn)基地看成質(zhì)點，路基最短即兩點之間距離最短, 可通過軟件畫出城鎮(zhèn)網(wǎng)絡(luò)圖，并利用 Matlab 結(jié)合 Dijkstra 算法，得到生產(chǎn)基地到所有連鎖店的 最短路線，從而得到最優(yōu)分配方案。2.2 問題二的分析要分析各城鎮(zhèn)需求特征，首先要明白數(shù)

7、據(jù)的的變化情況，通常對這種題目要求，可 以對所給數(shù)據(jù)進(jìn)行均值和標(biāo)準(zhǔn)差運算來了解數(shù)據(jù)的波動情況和離散程度，并通過 SPSS 作出各城鎮(zhèn)需求量與時間的折線圖。為準(zhǔn)確得知公司發(fā)展?fàn)顩r，并采取相對應(yīng)的措施，要求對未來峰值的預(yù)測，可通過畫出散點圖了解總需求量的變化，并利用最小二乘法對散點圖進(jìn)行曲線擬合3，預(yù)測出未來走勢，利用擬合出的兩個函數(shù)式估測出出現(xiàn)峰值時的年份，對于需求排名前五和后 五情況確定，則可以對2008年至2012年這五年間的需求量進(jìn)行統(tǒng)計并通過排名情況總 結(jié)。2.3問題三的分析問題三要求設(shè)計增設(shè)銷售連鎖店方案，使全省銷售量達(dá)到最大，要考慮連鎖店的銷 售量、需求量與距離變化的關(guān)系以及增設(shè)的銷

8、售連鎖店銷售能力控制在每日20噸至40噸內(nèi)，并且要求增設(shè)的銷售量必須達(dá)到銷售能力的下限，且同一城鎮(zhèn)可設(shè)立多個銷售連 鎖店。根據(jù)題意擬采用0-1規(guī)劃算法，對新增連鎖店進(jìn)行規(guī)劃，建立目標(biāo)函數(shù)。同一城鎮(zhèn) 可設(shè)立多個銷售連鎖店，以及連鎖店對于每個城鎮(zhèn)的供給量的實現(xiàn)，（在10公里以內(nèi)，需求量等于銷售量的一半，10公里以外，需求量等于銷售量的三分之一，且每個店最低 銷量為20噸），由此建立線性約束條件，并利用 Lin go軟件建立優(yōu)化模型，則可以得出 優(yōu)化方案。三、模型假設(shè)結(jié)合本題的實際，為了確保模型求解的準(zhǔn)確性與合理性，本文排除一些干擾因素, 提出以下幾點假設(shè)：1、假設(shè)材料中信息來源可靠真實；2、假設(shè)各

9、基地足夠地供給鮮豬肉，不出現(xiàn)斷貨缺貨的情況；3、假設(shè)運輸成本中只考慮距離問題，其他損失忽略不計；4、假設(shè)在近期內(nèi)連鎖店不會出現(xiàn)食品安全問題，保證正常運營。四、符號說明為了便于問題的求解，本文給出以下符號說明:符號說明S第i個數(shù)據(jù)值S所有數(shù)據(jù)的平均值ai新增的銷售能力bi不足10公里的其他城鎮(zhèn)的連鎖店銷售能力Ci超過10公里的其他城鎮(zhèn)連鎖店的銷售能力di未來第i個城鎮(zhèn)的需求量x原有的連鎖店在增設(shè)之前的銷售能力y原有的連鎖店在增設(shè)后的銷售能力五、模型的建立與求解5.1問題一的模型建立與求解模型建立Dijkstra算法是很具有代表性的最短路徑的算法，它是以起點為中心向外層層拓展 直至結(jié)點。在本題中，

10、采用軟件求得貨物配送的最短路徑，進(jìn)而得到最優(yōu)生產(chǎn)和配送方 案。由于需要解決的問題轉(zhuǎn)化成了最短路徑問題，所以解決任意兩點間的最短距離問題 采用Dijkstra算法。因此建立模型，將每個連鎖店和生產(chǎn)基地看成一個質(zhì)點，按照城鎮(zhèn)編號命名為 點,2,3,，54，其中點63和點120是貨物運輸?shù)钠瘘c。設(shè)源始點v到某一結(jié)點u的距離為 D u，結(jié)點v到結(jié)點u的距離為I v,u，則以點63為始點時，D u l 63,u表示兩者之 間有直通車，D u表示兩者之間沒有直通車。同理，點120。比較點63和點120到相同點的之間的距離，取最小的那一種情況，來滿足最短距離配送問題要求，其中重要步 驟如下：D vMinDv

11、,Dw I w,v ，w是除了 63的其他始點，由此將最低成本問題轉(zhuǎn)化為最短路徑問題。模型求解1JI1訂丹祜和直井（1）利用軟件根據(jù)全省交通網(wǎng)絡(luò)數(shù)據(jù)表和高速公路連接表中的數(shù)據(jù)繪制出城鎮(zhèn)網(wǎng) 絡(luò)圖，如下圖：200第7300350iDO圖1城鎮(zhèn)網(wǎng)絡(luò)圖如圖所示，我們可以清晰地看出各城鎮(zhèn)之間的相對位置，也較為直觀地看出貨物運 輸路線。（2）利用Matlab軟件結(jié)合Dijkstra算法，編寫程序，很快地得出生產(chǎn)基地到所有 連鎖店的最短路線，得到最優(yōu)分配方案表（具體見附錄II）根據(jù)表中數(shù)據(jù)可知，生產(chǎn)基地63為提供3、4、6、7、812、141617、8、20、23這幾家連鎖店 提供鮮豬肉，所耗費的成本約為

12、4559元，生產(chǎn)基地120為1、2、5、9、0、1、31519、21、22這 幾家連鎖店提供鮮豬肉，所耗費的成本為 6175，由此得到運輸最低成本約為10734元。5.2問題二的模型建立與求解要求分析各城鎮(zhèn)的需求特征，首先，我們分別求出每年每個月所有城鎮(zhèn)需求量的平 均值，結(jié)果如表2：表2城鎮(zhèn)需求量平均值12345678910111220086956897006947087097067017077197177172009714712719728724729731736P 741738730P 7362010740744745745739745748751752759744759201175475

13、875776276175576676576577476017752012764767771763781783769769777770780768由表格數(shù)據(jù)可得，每年每月所有城鎮(zhèn)的需求量的平均值都普遍在呈上升趨勢，我們 畫出該表格的折線統(tǒng)計圖：圖2城鎮(zhèn)月需求量平均圖由圖得，城鎮(zhèn)每年每月的需求量的平均值呈上升趨勢，但趨勢趨于平緩，下面我們 做出所有月份城鎮(zhèn)平均值的的折線圖：圖3城市月需求量平均總圖由圖3可得，全省的鮮豬肉的需求量從 2008-2012年雖上下波動，但總體上升趨勢明顯，每年對鮮豬肉的需求量明顯升高。對于未來幾年的預(yù)測，首先我們求出 2008-2012年每年全省鮮豬肉的總需求量，如 下

14、：(1304076 1346541 1382772 1410444 1427072)根據(jù)前五年全省鮮豬肉的總需求量，我們可以做出散點圖如圖4：1 441411鮎1.341.321 I 522 53354*5 S圖4散點圖對散點圖分析可得2008-2012年的總需求量呈拋物線形式，所以運用最小二乘法對 散點圖進(jìn)行曲線擬合。上述過程以求得2008-2012年全省鮮豬肉的需求量，以年份ti(t 1,2,3L)為自變量， 總需求量y為因變量，所以假設(shè)曲線為二次多項式 y a2 a?x a3，利用Matlab進(jìn)行 擬合求得系數(shù)：所以函數(shù)方程式為：y 4302x2 5680x 1251000得出擬合圖后發(fā)

15、現(xiàn)這五年間大致上呈增長的趨勢發(fā)展，接著我們對未來幾年的鮮豬 肉的總需求量做出預(yù)測，如圖 6：對圖6進(jìn)行分析得，同時將i 6、7、89代入函數(shù)關(guān)系式得第七年全省對鮮豬肉的需 求量會達(dá)到峰值，即2014年需求量會達(dá)到峰值為。在對2014年達(dá)到峰值時，對前五名與后五名排名時，我們求出2008 2012年每個城鎮(zhèn)對鮮豬肉的年度總需求量（見附錄III），其次對每年的每個城鎮(zhèn)鮮豬肉的總需求量 分別作出折線統(tǒng)計圖（其中 2008年的折線圖見圖7，2009 2012年的折線統(tǒng)計圖見附錄 IV ）。圖7 2008年每個城鎮(zhèn)鮮豬肉總需求量折線圖通過對五張折線圖的分析，我們發(fā)現(xiàn)每年各城鎮(zhèn)對鮮豬肉總需求的排名幾乎沒有

16、變動，所以推測2014年各城鎮(zhèn)對鮮豬肉需求量排名與幾乎前幾年相同，前五名分別為120號，63號，31號，106號，104號城鎮(zhèn)，后五名分別為 30號，94號，84號，109號， 129號城鎮(zhèn)。5.3問題三的模型建立與求解模型建立題目要求設(shè)計增設(shè)銷售連鎖店方案，使全省銷售量達(dá)到最大。而經(jīng)調(diào)查發(fā)現(xiàn)，公司 產(chǎn)品的需求量與銷售量并不完全一致，若在當(dāng)?shù)兀ㄍ怀擎?zhèn)）購買，則這一部分需求量 與銷售量相同，若在不足10公里的其他城鎮(zhèn)的銷售連鎖店購買，則這一部分需求量只能 實現(xiàn)一半，而在超過10公里的其他城鎮(zhèn)的銷售連鎖店購買，銷售量只能達(dá)到需求量的三 成。所以建立0 1規(guī)劃模型，首先建立線性目標(biāo)函數(shù)，其中ti

17、1表示第i個城鎮(zhèn)增加連鎖店， ti 0表示第 i 個不增設(shè)連鎖店則有目標(biāo)函數(shù)：154Maxtiai yii1 約束條件：s.t.2000tibiai4000t id ixi2000ticiyi 1.2xi5.3.2 模型求解利用軟件 Lingo 結(jié)合 0-1線性規(guī)劃，求得結(jié)果如下： 所求城鎮(zhèn) 6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增設(shè)連鎖店，其中城鎮(zhèn) 120， 31， 64，10，123 分別含有連鎖店的個數(shù)是 3，2，2，2，2 個。使得全省銷售量最大，最大 值為 919414 公

18、斤六、模型的評價與改進(jìn)6.1 模型的評價6.1.1 模型的優(yōu)點1、擬合曲線可以得到近似函數(shù)方程，比便預(yù)測未來數(shù)據(jù)；2、規(guī)劃模型與實際緊密聯(lián)系，將問題簡單化，具有很好的通透性和推廣性；3、模型的計算采用專業(yè)的數(shù)學(xué)軟件，可信度高。模型的缺點1、 0-1規(guī)劃模型約束條件有點簡單；2、 Dijkstra 算法只能解決正權(quán)值圖，雖是較為成熟、最易接受的一種算法，但始終存在 局限。6.2 模型的改進(jìn)對于問題一的改進(jìn) 最短路徑是圖論研究中一個重要課題，傳統(tǒng)公認(rèn)的求得最短路徑的最好算法是Dijketra 算法，然而存在時間和空間復(fù)雜度，現(xiàn)對此算法進(jìn)行改進(jìn)，采用鄰接表和堆排 序的優(yōu)化方法。首先，將數(shù)組 T 通過

19、堆排序調(diào)整為小頂堆，取數(shù)組首元即堆頂節(jié)點為中 間節(jié)點，并將該節(jié)點加入到已標(biāo)記集合 S 中，再比較更新節(jié)點的鄰接點集合與已標(biāo)記集 合的差集中任一節(jié)點Vi的當(dāng)前最短路徑值，然后查找S集合所有節(jié)點的鄰接點的并集和 S集合的差集，同時將這些節(jié)點順次存入數(shù)組 T中，覆蓋原數(shù)組中的節(jié)點，并設(shè)置一個 計數(shù)器 i 記錄節(jié)點個數(shù)，最后將數(shù)組中的前 i 個元素按它們當(dāng)前的最短路徑值調(diào)整成小 頂堆，取堆頂節(jié)點為下一個最短路徑節(jié)點將其個歸并到集合 S 中，如此反復(fù)得出理想的 最短路徑值 。對于問題三的改進(jìn)基于本文的問題，可把0-1非線性規(guī)劃問題轉(zhuǎn)化為約束優(yōu)化問題，采用動態(tài)雙目標(biāo) 的約束處理方法，即粒子群混合算法。首先

20、設(shè)置當(dāng)前迭代代數(shù)t=1,確定種群的大小N , 搜索空間的維度D，在0，1空間內(nèi)產(chǎn)生N個粒子的初始位置和速度。第二步將第個粒 子的最好位置pbest設(shè)置為該粒子的當(dāng)前位置，如果A=x|?(x)工?,則全局最優(yōu)位置, 第三步根據(jù)Sigmoid函數(shù)公式、改進(jìn)式和粒子優(yōu)化等式更新每個粒子的速度與當(dāng)前位置， 第四步根據(jù)前面轉(zhuǎn)化出來的無約束雙目標(biāo)問題得出的公式：mi nF(x) = min ?(x),f(x)更新每個粒子的個體優(yōu)化位置和全局最優(yōu)值，按照一定的概率對當(dāng)前粒子在0，1空間進(jìn)行隨機(jī)賦值，最后讓t=t+1返回到步驟三，直到獲得一個預(yù)期的適應(yīng)值。七、模型的檢驗將雜亂無序，無相關(guān)關(guān)系的散點擬合成曲線，

21、用來預(yù)測未來情況，但意義不大，因 此為了模型的高精確度和曲線的高切合度，有必要對回歸方程進(jìn)行顯著性檢驗。一般設(shè)$ b° b b?X2 L bmXm是已求得的回歸方程。yi是第i個試驗點代入回歸方程所求的回歸值。這里稱實驗值 yi與其平均值y的離差平方和為總離差平方和，記為S、，以此推測出S回與S剩: 已知公式及關(guān)系式如下：s回1 S總總、s總總、n2S總yii 1y定義R21 S剩/&為復(fù)相關(guān)系數(shù)，顯然-1 ny二Yini 1n2i 1y屮0 R 1,R越接近1,回歸效果就越好。我們對問題二擬合出的方程：y4302x2 56800x 1251000進(jìn)行顯著性檢驗得R 0.99

22、98,明顯接近于1,所以該方程的擬合程度較高，預(yù)測比較 準(zhǔn)確。八、模型推廣Dijkstra算法是計算最短路徑的經(jīng)典算法，是許多工程解決最短路徑冋題的理論基 礎(chǔ)。最短路徑問題又可以引申為最快路徑問題、最低費用問題等，但他們的核心算法都 是最短路徑算法經(jīng)典的最短路徑算法一一Dijkstra算法是目前多數(shù)系統(tǒng)解決最短路徑問題采用的理論基礎(chǔ)，只是不同系統(tǒng)對Dijkstra算法采用了不同的實現(xiàn)方法。0 1規(guī)劃模型能夠很好的解決本文中的增設(shè)銷售連鎖店問題。也可以將其推廣到大面積區(qū)域的規(guī)劃，比如從一個區(qū)域推廣到多個區(qū)域或是一個市、一個省的情形。另外也 可以推廣到其他服務(wù)性行業(yè)的選址中的方案的確定。比如物流中

23、心的選址就可以用0 1規(guī)劃模型來解決，知識此時需要考慮的因素，需要列出的約束條件和目標(biāo)函數(shù)都有所不 同。九、參考文獻(xiàn) 1 姜啟源 謝金星 葉?。ǖ谌妫瑪?shù)學(xué)模型，北京：高等教育出版社， 2003； 2 陳益富 盧瀟 丁豪杰，對 Dijkstra 算法的優(yōu)化策略研究 J ，計算機(jī)技術(shù)與發(fā)展 , 2006， 09:73-75+78；3徐海霞 任紅松 袁繼勇 楊德松 馬智群，用EXCEL及其“規(guī)劃求解”功能擬合曲線 方程J，農(nóng)業(yè)網(wǎng)絡(luò)信息，2004, 02:37-39; 4 程郁昕 陶金萍 蔡治華 ,擬合曲線的顯著性檢驗 J, 安徽農(nóng)業(yè)技術(shù)師范學(xué)院學(xué)報， 2001， 02:46-48; 5 高更君

24、黃衛(wèi)，現(xiàn)代物流中心的貨物配送問題 J ，東南大學(xué)學(xué)報 （自然科學(xué)版 ）, 2001， 06:30-33。附錄I表1連鎖店的日銷售量連鎖店編號12345678所在城鎮(zhèn)編號1201066331141106579日銷售量（公斤）:287333822321733239479258 :84811557038759連鎖店編號910111213141516所在城鎮(zhèn)編號1120362734429411日銷售量（公斤）：14744 32517115039265451948912773r 6103連鎖店編號P 17181920212223所在城鎮(zhèn)編號2463145221612364日銷售量（公斤）32512829539653637514783180811840附錄II利用Matlab軟件結(jié)合Dijkstra算法，得到最優(yōu)分配方案表:表2最優(yōu)分配方案連鎖店編號所在城鎮(zhèn)編號最短距離日銷量（公斤）r運輸成本（兀）基地1201120028733021066338223109551416192582579113414744891101200325170113615111503P782133411945124159419012