數(shù)學(xué)建模垃圾運(yùn)輸問(wèn)題論文

1、垃圾運(yùn)輸問(wèn)題姓名： 學(xué)號(hào)：班級(jí)：指導(dǎo)老師： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院垃圾運(yùn)輸問(wèn)題摘 要我們就生活中垃圾運(yùn)輸?shù)膯?wèn)題的調(diào)度方案予以研究。本文通過(guò)對(duì)問(wèn)題的分析和合理的假設(shè)，采用規(guī)劃的理論建立了單目標(biāo)的非線性規(guī)劃的數(shù)學(xué)模型。，運(yùn)用軟件得到了全局最優(yōu)解，對(duì)此類(lèi)問(wèn)題的求解提供了一種較優(yōu)的方案。題中的問(wèn)題（1）包含著垃圾量和運(yùn)輸費(fèi)用的累積計(jì)算問(wèn)題，因此，文中以運(yùn)輸車(chē)所花費(fèi)用最少為目標(biāo)函數(shù)，以運(yùn)輸車(chē)載重量的大小、當(dāng)天必須將所有垃圾清理完等為約束條件，以運(yùn)輸車(chē)是否從一個(gè)垃圾站點(diǎn)到達(dá)另一個(gè)垃圾站點(diǎn)為決策變量，建立了使得運(yùn)輸費(fèi)用最小的單目標(biāo)的非線性規(guī)劃模型。運(yùn)用求解，得出了最優(yōu)的運(yùn)輸路線為10條，此時(shí)運(yùn)輸所花費(fèi)用為

2、2335.77元。通過(guò)分析，發(fā)現(xiàn)只需6輛運(yùn)輸車(chē)（載重量為6噸）即可完成所有任務(wù)，且每輛運(yùn)輸車(chē)的工作時(shí)間均在4個(gè)小時(shí)左右。具體結(jié)果見(jiàn)文中表3。問(wèn)題（2），建立了以運(yùn)行路徑最短為目標(biāo)的單目標(biāo)非線性規(guī)劃模型。從而求出了使鏟車(chē)費(fèi)用最少的3條運(yùn)行路線，且各條路線的工作時(shí)間較均衡。因此，處理站需投入3臺(tái)鏟車(chē)才能完成所有裝載任務(wù)，且求得鏟車(chē)所花費(fèi)用為202.0元，三輛鏟車(chē)的具體運(yùn)行路線見(jiàn)文中表4。文中，我們假定垃圾處理站的運(yùn)輸工作從晚21：00開(kāi)始，根據(jù)各鏟車(chē)的運(yùn)輸路線和所花時(shí)間的大小，將鏟車(chē)和運(yùn)輸車(chē)相互配合進(jìn)行工作的時(shí)間做出了詳細(xì)的安排見(jiàn)表5。問(wèn)題（3），要求給出當(dāng)有載重量為4噸、6噸、8噸三種運(yùn)輸車(chē)時(shí)的

3、最優(yōu)的調(diào)度方案?；诘冢?）問(wèn)中的模型，修改載重量的約束條件，用和分別求解，得出兩種調(diào)度方案，但總的運(yùn)輸費(fèi)用不變，均為2326.17元；對(duì)于方案一，有9條路徑，分別需要4噸的運(yùn)輸車(chē)1輛；6噸的運(yùn)輸車(chē)2輛；8噸的運(yùn)輸車(chē)5輛，各運(yùn)輸車(chē)具體的運(yùn)輸線路見(jiàn)文中表8。對(duì)于方案二，有10條路徑，分別需要4噸的運(yùn)輸車(chē)1輛；6噸的運(yùn)輸車(chē)1輛；8噸的運(yùn)輸車(chē)4輛，各運(yùn)輸車(chē)具體的運(yùn)輸線路見(jiàn)文中表10。最后，對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了分析，并給出了模型的改進(jìn)意見(jiàn)，對(duì)解決實(shí)際問(wèn)題具有一定的指導(dǎo)意義。關(guān)鍵字： 垃圾運(yùn)輸?shù)恼{(diào)度；線性規(guī)劃；最優(yōu)解問(wèn)題的分析 這是一個(gè)便利問(wèn)題，此問(wèn)題的困難之處在于確定鏟車(chē)的行走路線，并使得運(yùn)輸車(chē)工作時(shí)

4、盡量不要等待鏟車(chē)，才能使得運(yùn)輸車(chē)的工作時(shí)間滿足題目的要求每日平均工作四小時(shí)，為此，應(yīng)該使鏟車(chē)跟著運(yùn)輸車(chē)跑完一條線路，也就是說(shuō)，應(yīng)該使鏟車(chē)鏟完一條線路后再接著鏟下一條線路。第（1）問(wèn)，對(duì)于運(yùn)輸車(chē)調(diào)度方案的設(shè)計(jì)，不能僅僅考慮使運(yùn)輸車(chē)的行走路線最短，因?yàn)榇颂庍€存在著垃圾的累積運(yùn)輸?shù)幕ㄙM(fèi)問(wèn)題，因此，我們的目標(biāo)函數(shù)應(yīng)該是使得所有運(yùn)輸?shù)幕ㄙM(fèi)最少。在建模過(guò)程中，我們無(wú)需考慮投入的運(yùn)輸車(chē)臺(tái)數(shù)，只需對(duì)各條路徑所花費(fèi)的時(shí)間進(jìn)行和各運(yùn)輸車(chē)載重量約束即可，至于投入的車(chē)輛數(shù)，在各條路徑確定后，計(jì)算出各路徑運(yùn)輸所花費(fèi)的時(shí)間，再根據(jù)題目中要求的每輛車(chē)平均工作時(shí)間為4小時(shí)左右進(jìn)行計(jì)算即可。第（2）問(wèn)中，對(duì)于鏟車(chē)的調(diào)度方案，因

5、其無(wú)累積計(jì)算問(wèn)題，因此只需要在已確定的各運(yùn)輸路徑的基礎(chǔ)上，使得鏟車(chē)的行駛路徑為最短。在此方案中，我們將已確定的各條路徑看作為節(jié)點(diǎn)，建立使鏟車(chē)運(yùn)費(fèi)最少（亦即路徑最短）的非線性規(guī)劃模型，在此需注意的是，由于垃圾運(yùn)輸為夜間運(yùn)輸，所以每輛鏟車(chē)的工作時(shí)間也受到一定的限制，文中，我們假定鏟車(chē)的工作時(shí)間為從（晚21：00早6：00），因此每輛鏟車(chē)的工作時(shí)間最多為9個(gè)小時(shí)，再由所有運(yùn)輸車(chē)完成任務(wù)所需的總時(shí)間判定所需鏟車(chē)的臺(tái)數(shù)，之后可以根據(jù)具體情況進(jìn)行調(diào)整。同時(shí)應(yīng)注意，由于運(yùn)輸車(chē)有工作時(shí)間的限制，而鏟車(chē)沒(méi)有嚴(yán)格的限制（除工作時(shí)間不能超過(guò)9小時(shí)以外），所以，在確定鏟車(chē)出行的時(shí)間時(shí)，應(yīng)保證只可讓鏟車(chē)等待運(yùn)輸車(chē)，而不

6、能讓運(yùn)輸車(chē)等待鏟車(chē)。對(duì)于第（3）問(wèn)，是在第一問(wèn)的基礎(chǔ)上將對(duì)運(yùn)輸車(chē)載重的約束條件從不大于6噸改為不大于8噸，在求得各條路線中，對(duì)于垃圾量不大于4噸的路線，調(diào)用4噸的運(yùn)輸車(chē)；對(duì)于垃圾量在（46噸）之間的路線，調(diào)用6噸的運(yùn)輸車(chē)；對(duì)于垃圾量在（68噸）之間的路線，調(diào)用8噸的運(yùn)輸車(chē)。一 模型假設(shè)（1）假設(shè)各站點(diǎn)每天的垃圾量是不變的；（2）假設(shè)各站點(diǎn)的垃圾都必須在當(dāng)天清理完畢；（3）不考慮運(yùn)輸車(chē)和鏟車(chē)在行駛過(guò)程中出現(xiàn)的塞車(chē)、拋錨等耽誤時(shí)間的情況；（4）不允許運(yùn)輸車(chē)有超載現(xiàn)象；（5）每個(gè)垃圾站點(diǎn)均位于街道旁，保證運(yùn)輸車(chē)和鏟車(chē)行駛順暢；二 模型的建立及求解1 符號(hào)說(shuō)明 每天運(yùn)輸前第個(gè)垃圾站點(diǎn)的垃圾量； 第個(gè)垃

7、圾站點(diǎn)向第個(gè)垃圾站點(diǎn)運(yùn)輸?shù)睦浚?運(yùn)輸車(chē)是否從第個(gè)垃圾站點(diǎn)向第個(gè)垃圾站點(diǎn)運(yùn)輸?shù)?-1變量；第輛鏟車(chē)是否從第條路徑向第條路徑運(yùn)輸?shù)?-1變量； 第個(gè)垃圾站點(diǎn)和第個(gè)垃圾站點(diǎn)之間的距離； 第條路徑到第條路徑的有向距離； 垃圾運(yùn)輸車(chē)的單位量貨物每公里的運(yùn)輸費(fèi)用； 垃圾運(yùn)輸車(chē)和鏟車(chē)每公里的空載費(fèi)用； 鏟車(chē)通過(guò)第條路徑所需要的時(shí)間（包括在各垃圾站點(diǎn)裝車(chē)的時(shí)間） 假設(shè)所需要的鏟車(chē)的臺(tái)數(shù) 2 模型的建立21 運(yùn)輸車(chē)調(diào)度方案的模型對(duì)于運(yùn)輸車(chē)的調(diào)度方案，我們建立單目標(biāo)規(guī)劃的非線性模型使得運(yùn)輸費(fèi)用最小，模型如下。目標(biāo)函數(shù)的建立考慮使運(yùn)輸費(fèi)用最小時(shí)，目標(biāo)函數(shù)包括兩個(gè)方面的費(fèi)用：空載費(fèi)用和重載費(fèi)用。其中，空載費(fèi)用為第

8、37號(hào)站點(diǎn)直接到達(dá)的其他各點(diǎn)所花的費(fèi)用；而重載費(fèi)用為上一個(gè)點(diǎn)（除37號(hào)站點(diǎn)）到下一個(gè)點(diǎn)（包括37號(hào)站點(diǎn)）所花的費(fèi)用，表示如下： ： 約束條件的確立（1）對(duì)于各個(gè)垃圾站點(diǎn)，只有一輛運(yùn)輸車(chē)經(jīng)過(guò)，即每個(gè)站點(diǎn)的運(yùn)進(jìn)點(diǎn)和運(yùn)出點(diǎn)均是有且只有一個(gè)，即：其中，（2）運(yùn)輸車(chē)到達(dá)某個(gè)站點(diǎn)后，必須將此站點(diǎn)的所有垃圾帶走：（3）不允許出現(xiàn)自己往自己站點(diǎn)運(yùn)輸垃圾的現(xiàn)象,即當(dāng)時(shí)有：（4）不允許從第37號(hào)站點(diǎn)（垃圾處理站）運(yùn)出垃圾，即：（5）各點(diǎn)的垃圾都必須在當(dāng)天清理完畢，不允許有滯留：（6）各垃圾運(yùn)輸車(chē)不允許有超載現(xiàn)象，即每輛車(chē)的載重最多為6噸：21.3單目標(biāo)規(guī)劃模型在給出了目標(biāo)函數(shù)和約束條件后，即可得到一個(gè)使得運(yùn)輸費(fèi)用

9、最小的單目標(biāo)規(guī)劃模型如下： （1）2.2 鏟車(chē)調(diào)度方案的模型此模型的建立基于上問(wèn)模型的結(jié)果，從以上運(yùn)輸車(chē)的調(diào)度方案得出共有10條路徑，在此模型中，我們將10條路徑分別看作10個(gè)節(jié)點(diǎn)，而把垃圾處理站看作為第11個(gè)節(jié)點(diǎn)（以下將各路徑均稱作節(jié)點(diǎn)），建立了使鏟車(chē)行駛所需費(fèi)用最小的模型。在此需要說(shuō)明的是，由于運(yùn)輸車(chē)的路徑已經(jīng)確定，我們只能讓鏟車(chē)跟隨著運(yùn)輸車(chē)，而不能讓運(yùn)輸車(chē)在垃圾站點(diǎn)等待鏟車(chē)。由此可以確定,鏟車(chē)必須跟隨著運(yùn)輸車(chē)行走完一條路徑，才能轉(zhuǎn)到其他路徑繼續(xù)工作。而對(duì)于各路徑，其行走方案已定，所以各路徑內(nèi)的費(fèi)用已經(jīng)確定。因此，我們需要做的是，找出一種調(diào)度方案使鏟車(chē)在各路徑之間的行走所需的費(fèi)用為最小。目

10、標(biāo)函數(shù)的建立各路徑內(nèi)的費(fèi)用已定，因此我們建立以下使鏟車(chē)在各路徑之間行走所需費(fèi)用最小的目標(biāo)函數(shù)如下： 約束條件的確立：（1）對(duì)于1到10號(hào)的每個(gè)節(jié)點(diǎn)，只允許一輛鏟車(chē)通過(guò)，且只通過(guò)一次：（2）所有的鏟車(chē)必須從第11號(hào)節(jié)點(diǎn)（垃圾處理站）出發(fā)，并最終回到11號(hào)節(jié)點(diǎn)，即從11號(hào)節(jié)點(diǎn)發(fā)出的鏟車(chē)數(shù)和最終返回11號(hào)節(jié)點(diǎn)的鏟車(chē)數(shù)均為N：（3）為保證每輛鏟車(chē)均從11號(hào)節(jié)點(diǎn)出發(fā)最終回到11號(hào)節(jié)點(diǎn)，且不重復(fù)已走的路徑，則需控制鏟車(chē)所走路徑均為一個(gè)環(huán)，即對(duì)于每個(gè)節(jié)點(diǎn)，只要有鏟車(chē)進(jìn)入則必有鏟車(chē)出，不進(jìn)則無(wú)出，進(jìn)與出的狀態(tài)保持一致： （4）對(duì)于每個(gè)節(jié)點(diǎn)，不允許出現(xiàn)鏟車(chē)向自己節(jié)點(diǎn)運(yùn)行的路徑：（5）不允許出現(xiàn)鏟車(chē)的路徑為，除1

11、1號(hào)節(jié)點(diǎn)以外，在其他節(jié)點(diǎn)相互運(yùn)行的路徑：（6）由于垃圾的運(yùn)輸均在夜間進(jìn)行，則每輛鏟車(chē)的工作時(shí)間不能大于9個(gè)小時(shí)（即假定工作時(shí)間為從晚21：00早6：00），另外，由于題目中沒(méi)有給定鏟車(chē)的運(yùn)行速度，不妨假定其平均速度與運(yùn)輸車(chē)的平均速度相同，為40公里/小時(shí)，的約束條件為：鏟車(chē)規(guī)劃模型在給出了目標(biāo)函數(shù)和約束條件后，即可得到一個(gè)使得鏟車(chē)運(yùn)行費(fèi)用最小的單目標(biāo)規(guī)劃模型如下：（2）2.3 載重量不同的運(yùn)輸車(chē)調(diào)度方案模型此問(wèn)在第一問(wèn)的基礎(chǔ)上，通過(guò)改變垃圾運(yùn)輸車(chē)載重量的大小，從而得到垃圾處理廠在擁有不同載重量的運(yùn)輸車(chē)時(shí)，采用怎樣的運(yùn)輸方案使得所花運(yùn)輸費(fèi)用最少。此模型的目標(biāo)函數(shù)與第一問(wèn)中的運(yùn)輸車(chē)調(diào)度方案模型相同

12、，只是在約束條件上將第（6）個(gè)約束條件中的載重最多為6噸變成最多為8噸，： （3）從而可求出在擁有不同載重量運(yùn)輸車(chē)的情況下，各運(yùn)輸車(chē)的調(diào)度方案。模型的求解3 運(yùn)輸車(chē)調(diào)度方案模型的求解利用LINGO10編程，對(duì)運(yùn)輸車(chē)調(diào)度方案的模型（1）進(jìn)行求解,求得各垃圾站點(diǎn)的運(yùn)輸方案如表2所示，此時(shí)，求得將所有垃圾運(yùn)回到37號(hào)站點(diǎn)運(yùn)輸車(chē)所需費(fèi)用為2335.77元。表2：各運(yùn)輸路徑所包含的垃圾站點(diǎn)、運(yùn)輸量及所需時(shí)間路徑包含的站點(diǎn)運(yùn)輸垃圾總量每條線路所需時(shí)間 15.3噸3小時(shí)46分鐘25.7噸3小時(shí)02分鐘35.5噸2小時(shí)46分鐘45.2噸2小時(shí)22分鐘55.0噸2小時(shí)7分鐘65.6噸2小時(shí)4分鐘75.85噸1小

13、時(shí)46分鐘83.3噸1小時(shí)23分鐘95.55噸1小時(shí)30分鐘104.0噸1小時(shí)30分鐘 從上表可以看出，對(duì)于這10條路徑上的垃圾總量，有8條都超過(guò)了5噸，另兩條也超過(guò)了載重量的一半，運(yùn)輸車(chē)得到了充分地利用，結(jié)果非常好。各運(yùn)輸路徑以圖示表示如下：圖1：運(yùn)輸車(chē)行走路線圖由圖1可以看出，10條路徑中只有2條路徑有交叉點(diǎn)，其他路徑各自互不干擾，結(jié)果很理想。由題目可知，每臺(tái)運(yùn)輸車(chē)的平均工作時(shí)間為4小時(shí)，根據(jù)此條件對(duì)以上10條路徑進(jìn)行規(guī)劃，發(fā)現(xiàn)用6臺(tái)運(yùn)輸車(chē)即可按要求行走完10條路徑，所以，處理站只需投入6臺(tái)垃圾運(yùn)輸車(chē)即可完成任務(wù)。各運(yùn)輸車(chē)行走的路徑分別表示如下：表3：各運(yùn)輸車(chē)的行走路徑、具體路線及所需時(shí)間

14、運(yùn)輸車(chē)編號(hào)路徑編號(hào)行走路線所需時(shí)間第一輛23小時(shí)02分鐘第二輛13小時(shí)46分鐘第三輛84小時(shí)9分鐘3第四輛93小時(shí)37分鐘5第五輛43小時(shí)52分鐘10第六輛63小時(shí)50分鐘7 由上表可發(fā)現(xiàn)，每輛運(yùn)輸車(chē)的運(yùn)輸時(shí)間均在4個(gè)小時(shí)左右，相差很少，很好地達(dá)到了時(shí)間上的要求，且結(jié)果很理想。3.1鏟車(chē)調(diào)度方案模型的求解利用LINGO10編程，對(duì)鏟車(chē)調(diào)度方案模型（2）進(jìn)行求解，得到了使鏟車(chē)運(yùn)費(fèi)最少的行走路線。此時(shí)，需要投入的鏟車(chē)數(shù)為3臺(tái)，且所有鏟車(chē)完成任務(wù)所需費(fèi)用為202.0元，各鏟車(chē)的具體行駛路線及所花費(fèi)的時(shí)間如下表.表4：各鏟車(chē)的具體行駛路線及所花費(fèi)的時(shí)間鏟車(chē)行走路徑具體路線所需時(shí)間第一臺(tái) 8，9，6，5

15、5小時(shí)22分第二臺(tái)1，3，105小時(shí)50分第三臺(tái)2，4，75小時(shí)36分 由上表可以看出3臺(tái)鏟車(chē)的工作時(shí)間均為5個(gè)多小時(shí)，相差不大，工作分配地非常合理。各鏟車(chē)的行駛路線表示在圖上如圖2所示：圖2：各鏟車(chē)的具體行駛路線圖3.2鏟車(chē)及運(yùn)輸車(chē)調(diào)度方案的具體時(shí)間安排在問(wèn)題的分析中，我們提到，由于垃圾運(yùn)輸是在夜間進(jìn)行，因此，我們假定運(yùn)輸車(chē)及鏟車(chē)的工作時(shí)間從晚21：00早6：00，對(duì)于運(yùn)輸車(chē)調(diào)度方案，由于第三輛第六輛都要運(yùn)輸兩條路徑上的垃圾，因此，需要確定這4輛運(yùn)輸車(chē)具體先行駛哪條路徑，而此方案的確定依賴于鏟車(chē)的行走方案。根據(jù)以上求得的各鏟車(chē)和運(yùn)輸車(chē)工作所需時(shí)間的多少及鏟車(chē)應(yīng)配合運(yùn)輸車(chē)進(jìn)行工作的原則，對(duì)他們

16、的工作時(shí)間進(jìn)行安排如下表所示。表5：鏟車(chē)及運(yùn)輸車(chē)相互配合的具體時(shí)間安排鏟車(chē)1：運(yùn)輸路線8965包含站點(diǎn)時(shí)間及車(chē)號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)鏟車(chē)21:31122:11123:2610:581運(yùn)輸車(chē)21:31422:11323:2660:584鏟車(chē)2：運(yùn)輸路線1310包含站點(diǎn)時(shí)間到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)鏟車(chē)22:09223:1221:302運(yùn)輸車(chē)22:0920:2031:505鏟車(chē)3：運(yùn)輸路線247包含站點(diǎn)時(shí)間到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)鏟車(chē)22:06323:4230:493運(yùn)輸車(chē)22:06123:4251:236以

17、上時(shí)間安排均是基于工作時(shí)間從晚21：00開(kāi)始，從上表3和表4可以看出，每輛運(yùn)輸車(chē)和每臺(tái)鏟車(chē)的工作時(shí)間都不超過(guò)6個(gè)小時(shí)，因此，垃圾處理站可根據(jù)實(shí)際情況將工作開(kāi)始的時(shí)間向前或向后推相應(yīng)的時(shí)間即可。由表5的時(shí)間安排可以確定出各運(yùn)輸車(chē)的具體行駛路線及出發(fā)、返回時(shí)間如表6所示.表6:運(yùn)輸車(chē)的行走路線運(yùn)輸車(chē)編號(hào)從37號(hào)站點(diǎn)出發(fā)時(shí)間行走路線返回37號(hào)站點(diǎn)時(shí)間第一輛 21:00 00:02第二輛21:00 00:46第三輛 21:11 22:41 22:47 01:33第四輛21:0022:230:1502:22第五輛22:5101:1301:1502:45第六輛22:440:480:5002:363.3 載

18、重量不同的運(yùn)輸車(chē)的調(diào)度方案 方案一運(yùn)用LINGO對(duì)模型（3）進(jìn)行求解可以得到以下9條運(yùn)輸路徑，以問(wèn)題分析中運(yùn)輸車(chē)選擇的原則即：對(duì)于垃圾量不大于4噸的路線，調(diào)用4噸的運(yùn)輸車(chē)；對(duì)于垃圾量在（46噸）之間的路線，調(diào)用6噸的運(yùn)輸車(chē)；對(duì)于垃圾量在（68噸）之間的路線，調(diào)用8噸的運(yùn)輸車(chē)來(lái)為各路徑選擇運(yùn)輸車(chē)，具體數(shù)據(jù)如表7所示。此情況下求得的運(yùn)輸費(fèi)用為2326.17元。表7：方案一的各運(yùn)輸各路徑、運(yùn)輸?shù)目偫考斑\(yùn)輸所需時(shí)間運(yùn)輸路徑包含的垃圾站點(diǎn)運(yùn)輸總垃圾量運(yùn)輸所需時(shí)間112，104.2 噸1.33小時(shí)213，84.1 噸1.38小時(shí)3161.5 噸1.07小時(shí)418，14，31，5，67.35 噸2.23

19、小時(shí)524，17，3，14.45 噸2.37小時(shí)628，26，21，25，19，97.1 噸3.20小時(shí)730，29，27，15，117.8 噸3.13小時(shí)834，35，20，7，4，27.2 噸2.45小時(shí)936，23，33，32，227.3 噸2.93小時(shí)由以上各條路徑上的垃圾總量的大小來(lái)對(duì)運(yùn)輸車(chē)輛進(jìn)行選擇，根據(jù)各路徑運(yùn)輸所需時(shí)間的大小，對(duì)各輛運(yùn)輸車(chē)的行駛方案進(jìn)行規(guī)劃，得到結(jié)果如下表。表8：不同載重量的運(yùn)輸車(chē)對(duì)應(yīng)的方案一的線路安排車(chē)輛編號(hào)車(chē)輛選擇經(jīng)過(guò)路徑經(jīng)過(guò)的節(jié)點(diǎn)運(yùn)輸總時(shí)間第一輛4噸31.07小時(shí)第二輛6噸1，22.72小時(shí)第三輛6噸52.37小時(shí)第四輛8噸42.23小時(shí)第五輛8噸63.2

20、0小時(shí)第六輛8噸73.13小時(shí)第七輛8噸82.45小時(shí)第八輛8噸92.93小時(shí)根據(jù)以上數(shù)據(jù)可得，當(dāng)有載重量為4噸、6噸、8噸三種運(yùn)輸車(chē)時(shí)，需要各類(lèi)載重的運(yùn)輸車(chē)輛分別為：對(duì)于4噸的運(yùn)輸車(chē)，需要1輛；對(duì)于6噸的運(yùn)輸車(chē)，需要3輛；對(duì)于8噸的運(yùn)輸車(chē)，需要5輛。畫(huà)出此時(shí)各運(yùn)輸車(chē)的行走路線圖如圖3所示。圖3：方案一中不同載重量情況下各運(yùn)輸車(chē)行走的路線圖方案二運(yùn)用MATLAB編程對(duì)模型（3）求解，可以得到另外一種調(diào)度方案，共有10條運(yùn)輸路徑，所花費(fèi)用與LINGO求解相同，為2326.17元。各路徑的垃圾總量、運(yùn)輸所需時(shí)間分別表示如下：表9：方案二的各路徑包含的垃圾站點(diǎn)、垃圾總量及運(yùn)輸所需時(shí)間運(yùn)輸路徑包含的垃

21、圾站點(diǎn)運(yùn)輸?shù)目偫窟\(yùn)輸所需時(shí)間130，29，27，156.72.97小時(shí)228，26，21，25，19，147.53.2小時(shí)336，23，33，32，227.32.93小時(shí)424，18，35，20，317.12.53小時(shí)534，17，16，6，4.352.12小時(shí)613，7，4，25.71.72小時(shí)712，8，3，17.051.67小時(shí)811，102.61.33小時(shí)951.30.87小時(shí)1091.40.77小時(shí)同方案一，可根據(jù)各路徑的垃圾總量選擇運(yùn)輸車(chē)輛，根據(jù)各路徑運(yùn)輸所花時(shí)間對(duì)運(yùn)輸車(chē)的行走路徑進(jìn)行安排。得到具體的結(jié)果如下表10所示：表10：方案二各運(yùn)輸車(chē)的線路安排車(chē)輛編號(hào)車(chē)輛選擇經(jīng)過(guò)線路經(jīng)

22、過(guò)節(jié)點(diǎn)運(yùn)輸所需時(shí)間第一輛4噸83.02小時(shí)第二輛6噸5，63.84小時(shí)第三輛8噸12.97小時(shí)第四輛8噸23.2小時(shí)第五輛8噸32.93小時(shí)第六輛8噸4，74.2小時(shí)對(duì)于方案二，由以上數(shù)據(jù)可得：當(dāng)有載重量為4噸、6噸、8噸三種運(yùn)輸車(chē)時(shí)，需要各類(lèi)載重的運(yùn)輸車(chē)輛分別為：對(duì)于4噸的運(yùn)輸車(chē)，需要2輛；對(duì)于6噸的運(yùn)輸車(chē)，需要1輛；對(duì)于8噸的運(yùn)輸車(chē)，需要4輛。相比較來(lái)說(shuō)，對(duì)于兩種方案，方案二的結(jié)果較好，雖然運(yùn)輸路徑較方案一多一條，但是需要的車(chē)輛數(shù)卻比方案一要少一輛，且運(yùn)輸車(chē)的利用率較高。相應(yīng)的各輛運(yùn)輸車(chē)的行走路線圖如下：圖4：方案二中不同載重量情況下各運(yùn)輸車(chē)行走的路線圖四 結(jié)果分析由于題目中沒(méi)有給出司機(jī)的

23、工資額，因此文中只考慮了垃圾的運(yùn)輸費(fèi)用。但實(shí)際生活中，對(duì)于垃圾處理站來(lái)說(shuō)，垃圾的運(yùn)輸所需花費(fèi)不僅包括運(yùn)輸費(fèi)用還包括付給司機(jī)的工資。運(yùn)輸路徑越長(zhǎng)，運(yùn)輸所需要的時(shí)間就越長(zhǎng)，所需要的運(yùn)輸車(chē)輛越多，從而需要更多的司機(jī)，因而花費(fèi)更大。因此，在給出了司機(jī)工資額的情況下，目標(biāo)函數(shù)中還包括付給司機(jī)的工資。另外，此時(shí)目標(biāo)函數(shù)不再是單目標(biāo)函數(shù)，而是雙目標(biāo)函數(shù)。第二個(gè)目標(biāo)函數(shù)是使得運(yùn)輸車(chē)行駛的路徑最短。五 模型評(píng)價(jià)模型的優(yōu)點(diǎn)（1）此問(wèn)題為典型的NP難問(wèn)題，規(guī)劃模型的規(guī)模較大，共有2000多個(gè)變量，直接求解比較困難。由于在設(shè)計(jì)算法時(shí)采用了一些技巧，將變量減少到800多個(gè)，從而求出了最優(yōu)的結(jié)果。（2）模型中將各約束條件

24、均考慮在內(nèi)，對(duì)問(wèn)題的理解較全面，因此求出的結(jié)果為最優(yōu)。（3）克服了NP難問(wèn)題中很難得到最優(yōu)解的問(wèn)題，通過(guò)對(duì)算法的技巧性設(shè)計(jì)，使得此問(wèn)題得以圓滿的解決模型的缺點(diǎn)此問(wèn)題在建模中存在很多難點(diǎn)，因此模型中只考慮了，對(duì)于一個(gè)垃圾站點(diǎn)，一旦有運(yùn)輸車(chē)到此運(yùn)輸，則必須將所有垃圾帶走，而不能分批次運(yùn)輸，從而導(dǎo)致第8和第10條路徑的總垃圾量分別為3.3和4噸，運(yùn)輸量太少的情況，運(yùn)輸車(chē)不能得到充分地利用。六 參考文獻(xiàn)韓中庚.數(shù)學(xué)建模競(jìng)賽獲獎(jiǎng)?wù)撐木x與點(diǎn)評(píng).北京：科學(xué)出版社，2007.謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件.北京：清華大學(xué)出版社.2006.應(yīng)用范例與解法.北京：清華大學(xué)出版社.2006.9

25、.附錄附件1：運(yùn)輸車(chē)調(diào)度方案的程序sets:jiedian/1.37/:s,m;link1(jiedian,jiedian):x,u,d;endsetsdata:a=0.4;b=1.8;s=?;d=?;enddatamin=F;!運(yùn)輸費(fèi)用;F=sum(jiedian(t)|t#le#36:a*d(37,t)*u(37,t)+sum(link1(i,j):b*x(i,j)*d(i,j);!運(yùn)輸時(shí)間;!T=sum(link1(i,j):d(i,j)*u(i,j)/40)+1/6*sum(link1(t,k)|t#le#36:u(t,k)+sum(jiedian(t)|t#le#36:d(37,t)

26、*sum(jiedian(i):u(t,i)-u(i,t)/40;!37號(hào)節(jié)點(diǎn)沒(méi)有垃圾運(yùn)出;for(jiedian(j):x(37,j)=0);!最終垃圾全部被運(yùn)到37號(hào)節(jié)點(diǎn);sum(jiedian(i)|i#le#36:x(i,37)=51;!定義0-1變量;for(link1:bin(u);!不允許各節(jié)點(diǎn)自己往自己運(yùn)輸垃圾;for(jiedian(i)|i#le#36:x(i,i)=0);!每個(gè)站點(diǎn)只允許一輛車(chē)在此處運(yùn)出垃圾;for(jiedian(i)|i#le#36:sum(jiedian(j):u(i,j)=1);!每個(gè)站點(diǎn)只允許一輛車(chē)在此處運(yùn)進(jìn)垃圾;for(jiedian(i)|i

27、#le#36:sum(jiedian(j):u(j,i)=1);!運(yùn)出量等于運(yùn)進(jìn)來(lái)的加上該站點(diǎn)原有的垃圾量;for(link1(t,i)|t#le#36:x(t,i)=u(t,i)*(sum(jiedian(j):x(j,t)+s(t);!每輛車(chē)的載重不超過(guò)6噸;for(link1(i,j)|i#le#36:x(i,j)=6);for(jiedian(i)|i#le#36:u(1,i)=0);for(jiedian(i)|i#le#36:x(1,i)=0);for(jiedian(i)|i#le#36:u(2,i)=0);for(jiedian(i)|i#le#36:x(2,i)=0);for

28、(jiedian(i)|i#le#36#and#i#ne#1:u(3,i)=0);for(jiedian(i)|i#le#36#and#i#ne#1:x(3,i)=0);for(jiedian(i)|i#le#36#and#i#ge#3:u(4,i)=0);for(jiedian(i)|i#le#36#and#i#ge#3:x(4,i)=0);for(jiedian(i)|i#le#36#and#i#ge#3#and#i#ne#6:u(5,i)=0);for(jiedian(i)|i#le#36#and#i#ge#3#and#i#ne#6:x(5,i)=0);for(jiedian(i)|i#

29、le#36:u(6,i)=0);for(jiedian(i)|i#le#36:x(6,i)=0);for(jiedian(i)|i#le#36#and#i#ge#5#and#i#ne#6:u(7,i)=0);for(jiedian(i)|i#le#36#and#i#ge#5#and#i#ne#6:x(7,i)=0);for(jiedian(i)|i#le#36#and#i#ge#4:u(8,i)=0);for(jiedian(i)|i#le#36#and#i#ge#4:x(8,i)=0);for(jiedian(i)|i#le#36#and#i#ge#2:u(9,i)=0);for(jiedi

30、an(i)|i#le#36#and#i#ge#2:x(9,i)=0);for(jiedian(i)|i#le#36:u(10,i)=0);for(jiedian(i)|i#le#36:x(10,i)=0);for(jiedian(i)|i#le#36#and#i#ge#2#and#i#ne#9#and#i#ne#10:u(11,i)=0);for(jiedian(i)|i#le#36#and#i#ge#2#and#i#ne#9#and#i#ne#10:x(11,i)=0);for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#

31、i#ne#8:u(12,i)=0);u(13,5)=0;x(13,5)=0;for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#8:x(12,i)=0);for(jiedian(i)|i#le#36#and#i#ge#10:u(13,i)=0);for(jiedian(i)|i#le#36#and#i#ge#10:x(13,i)=0);for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#31:u(14,i)=0);for(jiedian(i)|i#le#36#and#i#ge#1

32、0#and#i#ne#31:x(14,i)=0);for(jiedian(i)|i#le#36#and#i#ge#14:u(15,i)=0);u(15,5)=0;x(15,5)=0;for(jiedian(i)|i#le#36#and#i#ge#14:x(15,i)=0);for(jiedian(i)|i#le#36#and#i#ge#7:u(16,i)=0);for(jiedian(i)|i#le#36#and#i#ge#7:x(16,i)=0);for(jiedian(i)|i#le#5#and#i#ne#2:u(16,i)=0);for(jiedian(i)|i#le#5#and#i#n

33、e#2:x(16,i)=0);for(jiedian(i)|i#le#36#and#i#ge#7:u(17,i)=0);for(jiedian(i)|i#le#36#and#i#ge#7:x(17,i)=0);for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#14#and#i#ne#16#and#i#ne#20#and#i#ne#31:u(18,i)=0);for(jiedian(i)|i#le#36#and#i#ge#10#and#i#ne#14#and#i#ne#16#and#i#ne#20#and#i#ne#31:x(18,i)=0);for(jie

34、dian(i)|i#le#36#and#i#ge#8:u(20,i)=0);for(jiedian(i)|i#le#36#and#i#ge#8:x(20,i)=0);for(jiedian(i)|i#le#36#and#i#ne#10:u(22,i)=0);for(jiedian(i)|i#le#36#and#i#ne#10:x(22,i)=0);!;for(jiedian(i)|i#le#36#and#i#ge#11:u(19,i)=0);u(19,11)=0;for(jiedian(i)|i#le#36#and#i#ge#11:x(19,i)=0);x(19,11)=0;for(jiedi

35、an(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#35:u(21,i)=0);u(21,15)=0;u(21,17)=0;u(21,18)=0;for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#35:x(21,i)=0);x(21,15)=0;x(21,17)=0;x(21,18)=0;for(jiedian(i)|i#le#36#and#i#ge#14#and#i#ne#15#and#i#ne#22#and#i#ne#32#and#i#ne#33:u(23,i)=0);u(23,5)=0

36、; for(jiedian(i)|i#le#36#and#i#ge#14#and#i#ne#15#and#i#ne#22#and#i#ne#32#and#i#ne#33:x(23,i)=0);x(23,5)=0;for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#31#and#i#ne#35:u(24,i)=0);u(24,15)=0;u(24,11)=0; for(jiedian(i)|i#le#36#and#i#ge#21#and#i#ne#25#and#i#ne#31#and#i#ne#35:x(24,i)=0);x(24,15

37、)=0;x(24,11)=0;for(jiedian(i)|i#le#36#and#i#ge#15#and#i#ne#19#and#i#ne#20#and#i#ne#31:u(25,i)=0);u(25,11)=0; for(jiedian(i)|i#le#36#and#i#ge#15#and#i#ne#19#and#i#ne#20#and#i#ne#31:x(25,i)=0);x(25,11)=0;for(jiedian(i)|i#le#36#and#i#ge#22#and#i#ne#25#and#i#ne#31#and#i#ne#35:u(26,i)=0);u(23,17)=0; for(

38、jiedian(i)|i#le#36#and#i#ge#22#and#i#ne#25#and#i#ne#31#and#i#ne#35:x(26,i)=0);x(23,17)=0;for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#31:u(27,i)=0);for(jiedian(i)|i#le#36#and#i#ge#16#and#i#ne#19#and#i#ne#22#and#i#ne#31:x(27,i)=0);u(28,29)=0;u(28,23)=0;u(28,30)=0;u(28,33)=0;u(2

39、8,36)=0;u(29,17)=0;u(29,18)=0;u(29,23)=0;u(29,24)=0;u(29,26)=0;u(29,28)=0;u(29,30)=0;u(29,34)=0;u(29,36)=0;u(30,24)=0;u(30,28)=0;u(30,34)=0;u(30,36)=0;for(jiedian(i)|i#le#36#and#i#ge#7:u(31,i)=0);for(jiedian(i)|i#le#36#and#i#ge#7:x(31,i)=0);for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#an

40、d#i#ne#11#and#i#ne#22:u(32,i)=0); for(jiedian(i)|i#le#36#and#i#ge#4#and#i#ne#9#and#i#ne#10#and#i#ne#11#and#i#ne#22:x(32,i)=0);for(jiedian(i)|i#le#36#and#i#ge#13#and#i#ne#22#and#i#ne#32:u(33,i)=0);for(jiedian(i)|i#le#7#and#i#ge#5:u(33,i)=0); for(jiedian(i)|i#le#36#and#i#ge#13#and#i#ne#22#and#i#ne#32:x(33,i)=0);for(jiedian(i)|i#le#7#and#i#ge#5:x(33,i)=0);for(jiedian(i)|i#le#36#and#i#ge#9#and#i#ne#16#and#i#ne#17#and#i#ne#20#and#i#ne#31#and#i#ne#35:u(34,i)=0);for(jiedian(i)|i#le#3