數學建模垃圾運輸問題論文

1、垃圾運輸問題 垃圾運輸問題摘要本文對于垃圾運輸問題的優(yōu)化，通過運用目標規(guī)劃的有關知識對題目給出的坐標數據進行了處理，根據從最遠點開始運載垃圾運輸費用最低的原則，以及不走回路的前提，采用規(guī)劃的理論建立了運輸車和鏟車的調度優(yōu)化模型，運用MATLAB軟件得到了全局最優(yōu)解，對此類問題的求解提供了一種較優(yōu)的方案，以達到最少運輸費用。問題（1）包含著垃圾量和運輸費用的累積計算問題，因此，文中以運輸車所花費用最少為目標函數，以運輸車載重量的大小、當天必須將所有垃圾清理完等為約束條件，以運輸車是否從一個垃圾站點到達另一個垃圾站點為決策變量，建立了使得運輸費用最小的單目標的非線性規(guī)劃模型。運用MATLAB求解，

2、得出了最優(yōu)的運輸路線為10條，此時運輸所花費用為2335.05元。通過分析，發(fā)現只需6輛運輸車（載重量為6噸）即可完成所有任務，且每輛運輸車的工作時間均在4個小時左右。具體結果見文中表3。問題（2），建立了以運行路徑最短為目標的單目標非線性規(guī)劃模型。從而求出了使鏟車費用最少的3條運行路線，且各條路線的工作時間較均衡。因此，處理站需投入3臺鏟車才能完成所有裝載任務，且求得鏟車所花費用為142.8元，三輛鏟車的具體運行路線見文中表4。文中，我們假定垃圾處理站的運輸工作從凌晨0：00開始，根據各鏟車的運輸路線和所花時間的大小，將鏟車和運輸車相互配合進行工作的時間做出了詳細的安排見表5。問題（3），要

3、求給出當有載重量為6噸、10噸兩種運輸車時的最優(yōu)的調度方案?；诘冢?）問中的模型，修改載重量的約束條件，用分別求解，得出兩種調度方案，但總的運輸費用不變，均為2508.63元；對于方案一，有9條路徑，分別需要6噸的運輸車2輛；10噸的運輸車5輛，各運輸車具體的運輸線路見文中表8。對于方案二，有10條路徑，分別需要6噸的運輸車1輛；10噸的運輸車4輛，各運輸車具體的運輸線路見文中表10。問題（4），基于問題（1）、問題（2）、問題（3），修改每個站點的垃圾量，用MATLAB分別求解，得到最優(yōu)的調整方案最后，對模型的優(yōu)缺點進行了分析，并給出了模型的改進意見，對解決實際問題具有一定的指導意義。關鍵

4、詞：目標規(guī)劃；最優(yōu)解； MATLAB；調度優(yōu)化模型一問題的重述某城區(qū)有36個垃圾站，每天都要從垃圾處理廠（第37號節(jié)點）出發(fā)將垃圾運回。現有一種載重6噸的運輸車。每個垃圾點需要用10分鐘的時間裝車，運輸車平均速度為40公里/小時（夜里運輸，不考慮堵車現象）；每臺車每日平均工作4小時（0:00-4:00,5:00前必須結束）。運輸車重載運費1.8元/噸公里；運輸車和裝垃圾用的鏟車空載費用0.4元/公里；并且假定街道方向均平行于坐標軸，請你給出滿意的運輸調度方案以及計算程序。問題：1）運輸車應如何調度（需要投入多少臺運輸車，每臺車的調度方案，運營費用）2）鏟車應如何調度（需要多少臺鏟車，每臺鏟車的

5、行走路線，運營費用）3）如果有載重量為6噸、10噸兩種運輸車，又如何調度？（垃圾點地理坐標數據表見附錄一）4）如果每個垃圾站點的垃圾量是隨機數，標準差為該站點平均垃圾量的10%，該如何調整？二問題的分析這是圖論中的一個遍歷問題，此問題的困難之處在于確定鏟車的行走路線，并使得運輸車工作時盡量不要等待鏟車，才能使得運輸車的工作時間滿足題目的要求每日平均工作四小時，為此，應該使鏟車跟著運輸車跑完一條線路，也就是說，應該使鏟車鏟完一條線路后再接著鏟下一條線路。第（1）問，對于運輸車調度方案的設計，不能僅僅考慮使運輸車的行走路線最短，因為此處還存在著垃圾的累積運輸的花費問題，因此，我們的目標函數應該是使

6、得所有運輸的花費最少。在建模過程中，我們無需考慮投入的運輸車臺數，只需對各條路徑所花費的時間進行和各運輸車載重量約束即可，至于投入的車輛數，在各條路徑確定后，計算出各路徑運輸所花費的時間，再根據題目中要求的每輛車平均工作時間為4小時左右進行計算即可。第（2）問，對于鏟車的調度方案，因其無累積計算問題，因此只需要在已確定的各運輸路徑的基礎上，使得鏟車的行駛路徑為最短。在此方案中，我們將已確定的各條路徑看作為節(jié)點，建立使鏟車運費最少（亦即路徑最短）的非線性規(guī)劃模型，在此需注意的是，由于垃圾運輸為夜間運輸，所以每輛鏟車的工作時間也受到一定的限制，文中，我們假定鏟車的工作時間為從（零晨0：00早4：0

7、0），因此每輛鏟車的工作時間最多為5個小時，再由所有運輸車完成任務所需的總時間判定所需鏟車的臺數，之后可以根據具體情況進行調整。同時應注意，由于運輸車有工作時間的限制，而鏟車沒有嚴格的限制（除工作時間不能超過9小時以外），所以，在確定鏟車出行的時間時，應保證只可讓鏟車等待運輸車，而不能讓運輸車等待鏟車。第（3）問，是在第一問的基礎上將對運輸車載重的約束條件從不大于6噸改為不大于10噸，在求得各條路線中，對于垃圾量不大于6噸的路線，調用6噸的運輸車；對于垃圾量在（610噸）之間的路線，調用10噸的運輸車。 第（4）問，是在前三問的基礎上將對每個站點的垃圾量進行隨機調整，使得其標準差為該點平均垃圾

8、量的10%。三模型的假設與符號說明1模型假設（1）假設各站點每天的垃圾量基本相同；（2）假設各站點的垃圾都必須在當天清理完,不允許滯留；（3）不考慮運輸車和鏟車在行駛過程中出現的堵車、拋錨等耽誤時間的情況；（4）不允許運輸車有超載現象；（5）每個垃圾站點均位于街道路口，便于垃圾的集中、運輸；（6）垃圾只在晚上運輸，基本保證運完后，當天不會再有新的垃圾產生；（7）假設卸垃圾及倒車均在10分鐘內完成；（8）車在裝的足夠多的情況下應該直接返回原點2 符號說明 第個垃圾站點向第個垃圾站點運輸的垃圾量； 運輸車是否從第個垃圾站點向第個垃圾站點運輸的0-1變量；第輛鏟車是否從第條路徑向第條路徑運輸的0-1

9、變量； 假設所需要的鏟車的臺數 ：垃圾運輸路線總條數；：第條路線上垃圾集中點的個數，；：第條路線上的第個垃圾集中點的橫坐標，；：條路線上的第個垃圾集中點的縱坐標：第條路線上的第個垃圾集中點的垃圾量，；:第條路線所需要的總時間；：第輛車的運輸總時間；：運輸車空載的總費用；：運輸車重載的總費用；：運輸車的總費用；：鏟車空載的總費用四模型的建立與求解模型的建立41 運輸車調度方案的模型由于最遠的垃圾集中點的運輸時間不超過運輸車每天平均工作時間，所以可以先不考慮時間的約束。從而建立如下算法：1) 確定重載起點 由于每個垃圾集中點的垃圾量及其坐標是不變，重載運輸的費用是不變的，所以為了使總運輸費用最少，

10、只要使空載的費用最少，即盡量安排較遠的垃圾集中點在同一路線上，從而確定重載起點.2）確定運輸車路線走向要求運輸時走最短的路線，以及運輸費用最低，而且由于運輸車的重載費用1.8元/噸是空載費用0.4元/噸的4.5倍，為了使運輸總費用最少,那只能從最遠的點（）開始運載垃圾，下一個點編號為，走一條路線，向垃圾處理站（坐標原點）方向運回。順次經過的點遵循滿足條件：即其橫坐標以及縱坐標均不超過前一點的橫、縱坐標，并且各點橫、縱坐標遞減進行搭配，由若干個點組成一條路線。3）確定運輸車路線垃圾集中點數根據每個垃圾集中點的垃圾量，每條路線上的垃圾總量不超過運輸車的最大運輸量：根據上面算法,建立運輸車費用優(yōu)化模

11、型:4.1.1 運輸車調度方案在運輸過程中假設沒有運輸車等待的情況,在四個小時的工作時間里,根據垃圾運輸費用優(yōu)化模型，得到垃圾集中點分配的路線及其時間,為了達到安排運輸車最少，把所有的路線分成()類，每類配置一輛運輸車，每輛運輸車的工作時間：4.2 鏟車調度方案的模型此模型的建立基于上問模型的結果，從以上運輸車的調度方案得出共有10條路徑，在此模型中，我們將10條路徑分別看作10個節(jié)點，而把垃圾處理站看作為第11個節(jié)點（以下將各路徑均稱作節(jié)點），建立了使鏟車行駛所需費用最小的模型。在此需要說明的是，由于運輸車的路徑已經確定，我們只能讓鏟車跟隨著運輸車，而不能讓運輸車在垃圾站點等待鏟車。由此可以

12、確定,鏟車必須跟隨著運輸車行走完一條路徑，才能轉到其他路徑繼續(xù)工作。而對于各路徑，其行走方案已定，所以各路徑內的費用已經確定。因此，我們需要做的是，找出一種調度方案使鏟車在各路徑之間的行走所需的費用為最小。4.2.1目標函數的建立各路徑內的費用已定，因此我們建立以下使鏟車在各路徑之間行走所需費用最小的目標函數如下：2.2.2 約束條件的確立：（1）對于1到10號的每個節(jié)點，只允許一輛鏟車通過，且只通過一次：（2）所有的鏟車必須從第11號節(jié)點（垃圾處理站）出發(fā)，并最終回到11號節(jié)點，即從11號節(jié)點發(fā)出的鏟車數和最終返回11號節(jié)點的鏟車數均為N：（3）為保證每輛鏟車均從11號節(jié)點出發(fā)最終回到11號

13、節(jié)點，且不重復已走的路徑，則需控制鏟車所走路徑均為一個環(huán)，即對于每個節(jié)點，只要有鏟車進入則必有鏟車出，不進則無出，進與出的狀態(tài)保持一致： （4）對于每個節(jié)點，不允許出現鏟車向自己節(jié)點運行的路徑：（5）不允許出現鏟車的路徑為，除11號節(jié)點以外，在其他節(jié)點相互運行的路徑：（6）由于垃圾的運輸均在夜間進行，則每輛鏟車的工作時間不能大于5個小時（即假定工作時間為（凌晨0：00早4：00），另外，由于題目中給定鏟車的運行速度，均速度與運輸車的平均速度相同，為40公里/小時，的約束條件為：4.2.3鏟車規(guī)劃模型在給出了目標函數和約束條件后，即可得到一個使得鏟車運行費用最小的單目標規(guī)劃模型如下：4.3 載重

14、量不同的運輸車調度方案模型此問在第一問的基礎上，通過改變垃圾運輸車載重量的大小，從而得到垃圾處理廠在擁有不同載重量的運輸車時，采用怎樣的運輸方案使得所花運輸費用最少。此模型的目標函數與第一問中的運輸車調度方案模型相同，只是在約束條件上將第（6）個約束條件中的載重最多為6噸變成最多為10噸，： 從而可求出在擁有不同載重量運輸車的情況下，各運輸車的調度方案。模型的求解運輸車調度方案模型的求解在不考慮鏟車的情況下，利用SPSS，首先據題畫出散點圖：利用MATLAB編程（見附錄二），對運輸車調度方案的模型（1）進行求解,求得各垃圾站點的運輸方案如表2所示，此時，求得將所有垃圾運回到37號站點運輸車所需

15、費用為2335.05元。表2：各運輸路徑所包含的垃圾站點、運輸量及所需時間路徑包含的站點運輸垃圾總量每條線路所需時間 15.3噸3小時46分鐘25.7噸3小時02分鐘35.5噸2小時46分鐘45.2噸2小時22分鐘55.0噸2小時7分鐘65.6噸2小時4分鐘75.85噸1小時46分鐘83.3噸1小時23分鐘95.55噸1小時30分鐘104.0噸1小時30分鐘 從上表可以看出，對于這10條路徑上的垃圾總量，有8條都超過了5噸，另兩條也超過了載重量的一半，運輸車得到了充分地利用，結果非常好。各運輸路徑以圖示表示如下：由題目可知，每臺運輸車的平均工作時間為4小時，根據此條件對以上10條路徑進行規(guī)劃，

16、發(fā)現用6臺運輸車即可按要求行走完10條路徑，所以，處理站只需投入6臺垃圾運輸車即可完成任務。各運輸車行走的路徑分別表示如下：表3：各運輸車的行走路徑、具體路線及所需時間運輸車編號路徑編號行走路線所需時間第一輛23小時02分鐘第二輛13小時46分鐘第三輛84小時9分鐘3第四輛93小時37分鐘5第五輛43小時52分鐘10第六輛63小時50分鐘7由上表可發(fā)現，每輛運輸車的運輸時間均在4個小時左右，相差很少，很好地達到了時間上的要求，且結果很理想。3.1鏟車調度方案模型的求解利用LINGO10編程，對鏟車調度方案模型（2）進行求解，得到了使鏟車運費最少的行走路線。此時，需要投入的鏟車數為3臺，且所有鏟

17、車完成任務所需費用為202.0元，各鏟車的具體行駛路線及所花費的時間如下表.表4：各鏟車的具體行駛路線及所花費的時間鏟車行走路徑具體路線所需時間第一臺 8，9，6，54小時22分第二臺1，3，104小時30分第三臺2，4，74小時26分由上表可以看出3臺鏟車的工作時間均為4個多小時，相差不大，工作分配地非常合理。鏟車及運輸車調度方案的具體時間安排在問題的分析中，我們知道，運輸車及鏟車的工作時間從凌晨0：00早4：00，對于運輸車調度方案，由于第三輛第六輛都要運輸兩條路徑上的垃圾，因此，需要確定這4輛運輸車具體先行駛哪條路徑，而此方案的確定依賴于鏟車的行走方案。根據以上求得的各鏟車和運輸車工作所

18、需時間的多少及鏟車應配合運輸車進行工作的原則，對他們的工作時間進行安排如下表所示。表5：鏟車及運輸車相互配合的具體時間安排鏟車1：運輸路線8965包含站點時間及車號到達時間車輛編號到達時間車輛編號到達時間車輛編號到達時間車輛編號鏟車0:3111:1112:2613:581運輸車0:3141:1132:2663:584鏟車2：運輸路線1310包含站點時間到達時間車輛編號到達時間車輛編號到達時間車輛編號鏟車1:0922:1224:302運輸車1:0923:2034:505鏟車3：運輸路線247包含站點時間到達時間車輛編號到達時間車輛編號到達時間車輛編號鏟車1:0632:4233:493運輸車1:0

19、612:4254:236以上時間安排均是基于工作時間從凌晨0：00開始，從上表3和表4可以看出，每輛運輸車和每臺鏟車的工作時間都不超過5個小時，因此，垃圾處理站可根據實際情況將工作開始的時間向前或向后推相應的時間即可。由表5的時間安排可以確定出各運輸車的具體行駛路線及出發(fā)、返回時間如表6所示.表6:運輸車的行走路線運輸車編號從37號站點出發(fā)時間行走路線返回37號站點時間第一輛 0:00 3:02第二輛0:00 3:46第三輛 0:11 1:41 1:47 4:33第四輛0:201:232:154:22第五輛0:513:133:154:45第六輛0:442:482:504:363.3 載重量不同

20、的運輸車的調度方案3.3.1 方案一運用LINGO對模型（3）進行求解可以得到以下7條運輸路徑，以問題分析中運輸車選擇的原則即：對于垃圾量不大于6噸的路線，調用6噸的運輸車；對于垃圾量在（610噸）之間的路線，調用10噸的運輸車；，具體數據如表7所示。此情況下求得的運輸費用為2326.17元。表7：方案一的各運輸各路徑、運輸的總垃圾量及運輸所需時間運輸路徑包含的垃圾站點運輸總垃圾量運輸所需時間112，10 95.6 噸1.33小時213，8 19，285.6 噸1.38小時318，14，31，5，67.35 噸2.23小時424，17，3，1，265.45噸2.37小時530，29，27，15

21、，11，168.7噸3.13小時634，35，20，7，4，2,218.4 噸2.45小時736，23，33，32，22,259.9 噸2.93小時由以上各條路徑上的垃圾總量的大小來對運輸車輛進行選擇，根據各路徑運輸所需時間的大小，對各輛運輸車的行駛方案進行規(guī)劃，得到結果如下表。根據以上數據可得，當有載重量為6噸、10噸二種運輸車時，需要各類載重的運輸車輛分別為：對于6噸的運輸車，需要3輛；對于10噸的運輸車，需要4輛。3.3.2方案二運用MATLAB編程對模型（3）求解（見附錄三），可以得到另外一種調度方案，共有8條運輸路徑，所花費用為2326.17元。各路徑的垃圾總量、運輸所需時間分別表示

22、如下：表9：方案二的各路徑包含的垃圾站點、垃圾總量及運輸所需時間運輸路徑包含的垃圾站點運輸的總垃圾量運輸所需時間1,29，27，155.52.97小時228，26，21，25，19，14,58.83.2小時336，23，33，32，22,98.72.93小時424，18，35，315.72.53小時534，17，16，6，305.592.12小時613，7，4，25.71.72小時712，8，3，5.551.67小時811，10，20，15.51.33小時同方案一，可根據各路徑的垃圾總量選擇運輸車輛，根據各路徑運輸所花時間對運輸車的行走路徑進行安排。對于方案二，由以上數據可得：當有載重量為6噸

23、、10噸三種運輸車時，需要各類載重的運輸車輛分別為：對于6噸的運輸車，需要6輛；對于10噸的運輸車，需要2輛。相比較來說，對于兩種方案，方案二的結果較好。 3.4 每個垃圾站點的垃圾量是隨機數，標準差為該站點平均垃圾量的10%模型五模型結果的分析與檢驗由于題目中沒有給出司機的工資額，因此文中只考慮了垃圾的運輸費用。但實際生活中，對于垃圾處理站來說，垃圾的運輸所需花費不僅包括運輸費用還包括付給司機的工資。運輸路徑越長，運輸所需要的時間就越長，所需要的運輸車輛越多，從而需要更多的司機，因而花費更大。因此，在給出了司機工資額的情況下，目標函數中還包括付給司機的工資。另外，此時目標函數不再是單目標函數

24、，而是雙目標函數。第二個目標函數是使得運輸車行駛的路徑最短。六模型的推廣與改進方向該模型可以應用在很多方面，比如說貨物運輸、車輛分配等。七模型的優(yōu)缺點然而，該問題在站點眾多，運輸路徑較大的前提下，缺點就會顯得尤為突出。首先是運輸車載重的不足，當運輸車的載重不能滿足其中任一點的垃圾量時，模型就可能不能適用了，該模型優(yōu)點是算法簡單容易實現,精度特別是后兩個模型的精度不是很高.前兩問只要進行窮舉就能得出最優(yōu)解.第三問的處理原則不算很精確,有待改進參考文獻 【1】全國大學生數學建模競賽 優(yōu)秀論文匯編。中國物價出版社，2002【2】宋兆基，徐流美等。MATLAB6.5在科學計算中的應用。清華大學出版社，

25、2005【3】耿素云.集合論與圖論(離散數學二分冊)M.北京:北京大學出版社,1997.【4】趙可培.運籌學M.上海:上海財經大學出版社,2000.附錄附錄一：垃圾站地理坐標數據表序號站點編號垃圾量T坐標x(km)坐標y (km)111.5032221.8015332.5554441.2047560.8508651.30311773.2079882.3096991.4010210101.5014011111.1017312122.7014613131.8012914142.80101215200.6071416161.5021617170.8061818181.50111719190.8015

26、12202115321.401.2019229522221.8021023231.4027924241.60151925252.60151426261.00201727272.00211328281.00242029292.10251630301.20281831311.9051232211.30171633333.2025734341.2092035352.5091536361.303012附錄二：codeclearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25

27、9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=

28、1:37;plot(x,y,'*r')for ii=1:37 k=int2str(ii); k=strcat('P',k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(11,11);for i=1:20 sum=0; j1=1; s=0; m=37; i3=37; for j=1:36 if(w(2,j)+w(3,j)>s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end en

29、d w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:36 if(q>w(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(6-sum)>w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3

30、)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=0;for u1=1:11 for u2=1:11 if jg(u1,u2)=0 n=jg(u1,u2); else continue end zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:11;time=i;time(1,:)=0;n1=0;n2=0;n3=0;f

31、or u4=1:11 for u5=1:11 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time 附錄三clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0

32、9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,'*r')for ii=1:37 k=int2str(ii); k=strcat

33、('P',k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(10,10);%´æ·Å11Ìõ·¾¶for i=1:20 sum=0; j1=1; s=0; m=37; i3=37; for j=1:36 if(w(2,j)+w(3,j)>=s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end end w(5,m)=1; j1=j1+1; w