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

垃圾運(yùn)輸問(wèn)題垃圾運(yùn)輸問(wèn)題摘要本文對(duì)于垃圾運(yùn)輸問(wèn)題的優(yōu)化，通過(guò)運(yùn)用目標(biāo)規(guī)劃的有關(guān)知識(shí)對(duì)題目給出的坐標(biāo)數(shù)據(jù)進(jìn)行了處理，根據(jù)從最遠(yuǎn)點(diǎn)開(kāi)始運(yùn)載垃圾運(yùn)輸費(fèi)用最低的原那么，以及不走回路的前提，采用規(guī)劃的理論建立了運(yùn)輸車(chē)和鏟車(chē)的調(diào)度優(yōu)化模型，運(yùn)用MATLAB軟件得到了全局最優(yōu)解，對(duì)此類(lèi)問(wèn)題的求解提供了一種較優(yōu)的方案，以到達(dá)最少運(yùn)輸費(fèi)用。問(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)用MATLAB求解，得出了最優(yōu)的運(yùn)輸路線為10條，此時(shí)運(yùn)輸所花費(fèi)用為2335.05元。通過(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)用為142.8元，三輛鏟車(chē)的具體運(yùn)行路線見(jiàn)文中表4。文中，我們假定垃圾處理站的運(yùn)輸工作從凌晨0：00開(kāi)始，根據(jù)各鏟車(chē)的運(yùn)輸路線和所花時(shí)間的大小，將鏟車(chē)和運(yùn)輸車(chē)相互配合進(jìn)行工作的時(shí)間做出了詳細(xì)的安排見(jiàn)表5。問(wèn)題〔3〕，要求給出當(dāng)有載重量為6噸、10噸兩種運(yùn)輸車(chē)時(shí)的最優(yōu)的調(diào)度方案?；诘凇?〕問(wèn)中的模型，修改載重量的約束條件，用分別求解，得出兩種調(diào)度方案，但總的運(yùn)輸費(fèi)用不變，均為2508.63元；對(duì)于方案一，有9條路徑，分別需要6噸的運(yùn)輸車(chē)2輛；10噸的運(yùn)輸車(chē)5輛，各運(yùn)輸車(chē)具體的運(yùn)輸線路見(jiàn)文中表8。對(duì)于方案二，有10條路徑，分別需要6噸的運(yùn)輸車(chē)1輛；10噸的運(yùn)輸車(chē)4輛，各運(yùn)輸車(chē)具體的運(yùn)輸線路見(jiàn)文中表10。問(wèn)題〔4〕，基于問(wèn)題〔1〕、問(wèn)題〔2〕、問(wèn)題〔3〕，修改每個(gè)站點(diǎn)的垃圾量，用MATLAB分別求解，得到最優(yōu)的調(diào)整方案最后，對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了分析，并給出了模型的改良意見(jiàn)，對(duì)解決實(shí)際問(wèn)題具有一定的指導(dǎo)意義。關(guān)鍵詞：目標(biāo)規(guī)劃；最優(yōu)解；MATLAB；調(diào)度優(yōu)化模型一．問(wèn)題的重述某城區(qū)有36個(gè)垃圾站，每天都要從垃圾處理廠〔第37號(hào)節(jié)點(diǎn)〕出發(fā)將垃圾運(yùn)回。現(xiàn)有一種載重6噸的運(yùn)輸車(chē)。每個(gè)垃圾點(diǎn)需要用10分鐘的時(shí)間裝車(chē)，運(yùn)輸車(chē)平均速度為40公里/小時(shí)〔夜里運(yùn)輸，不考慮堵車(chē)現(xiàn)象〕；每臺(tái)車(chē)每日平均工作4小時(shí)〔0:00-4:00,5:00前必須結(jié)束〕。運(yùn)輸車(chē)重載運(yùn)費(fèi)1.8元/噸公里；運(yùn)輸車(chē)和裝垃圾用的鏟車(chē)空載費(fèi)用0.4元/公里；并且假定街道方向均平行于坐標(biāo)軸，請(qǐng)你給出滿(mǎn)意的運(yùn)輸調(diào)度方案以及計(jì)算程序。問(wèn)題：1〕運(yùn)輸車(chē)應(yīng)如何調(diào)度〔需要投入多少臺(tái)運(yùn)輸車(chē)，每臺(tái)車(chē)的調(diào)度方案，運(yùn)營(yíng)費(fèi)用〕2〕鏟車(chē)應(yīng)如何調(diào)度〔需要多少臺(tái)鏟車(chē)，每臺(tái)鏟車(chē)的行走路線，運(yùn)營(yíng)費(fèi)用〕3〕如果有載重量為6噸、10噸兩種運(yùn)輸車(chē)，又如何調(diào)度？〔垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表見(jiàn)附錄一〕4〕如果每個(gè)垃圾站點(diǎn)的垃圾量是隨機(jī)數(shù)，標(biāo)準(zhǔn)差為該站點(diǎn)平均垃圾量的10%，該如何調(diào)整？二．問(wèn)題的分析這是圖論中的一個(gè)遍歷問(wèn)題，此問(wèn)題的困難之處在于確定鏟車(chē)的行走路線，并使得運(yùn)輸車(chē)工作時(shí)盡量不要等待鏟車(chē)，才能使得運(yùn)輸車(chē)的工作時(shí)間滿(mǎn)足題目的要求——每日平均工作四小時(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)度方案，因其無(wú)累積計(jì)算問(wèn)題，因此只需要在已確定的各運(yùn)輸路徑的根底上，使得鏟車(chē)的行駛路徑為最短。在此方案中，我們將已確定的各條路徑看作為節(jié)點(diǎn)，建立使鏟車(chē)運(yùn)費(fèi)最少〔亦即路徑最短〕的非線性規(guī)劃模型，在此需注意的是，由于垃圾運(yùn)輸為夜間運(yùn)輸，所以每輛鏟車(chē)的工作時(shí)間也受到一定的限制，文中，我們假定鏟車(chē)的工作時(shí)間為從〔零晨0：00～早4：00〕，因此每輛鏟車(chē)的工作時(shí)間最多為5個(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ē)，而不能讓運(yùn)輸車(chē)等待鏟車(chē)。第〔3〕問(wèn)，是在第一問(wèn)的根底上將對(duì)運(yùn)輸車(chē)載重的約束條件從不大于6噸改為不大于10噸，在求得各條路線中，對(duì)于垃圾量不大于6噸的路線，調(diào)用6噸的運(yùn)輸車(chē)；對(duì)于垃圾量在〔6～10噸〕之間的路線，調(diào)用10噸的運(yùn)輸車(chē)。第〔4〕問(wèn)，是在前三問(wèn)的根底上將對(duì)每個(gè)站點(diǎn)的垃圾量進(jìn)行隨機(jī)調(diào)整，使得其標(biāo)準(zhǔn)差為該點(diǎn)平均垃圾量的10%。三．模型的假設(shè)與符號(hào)說(shuō)明1模型假設(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)輸；〔6〕垃圾只在晚上運(yùn)輸，根本保證運(yùn)完后，當(dāng)天不會(huì)再有新的垃圾產(chǎn)生；〔7〕假設(shè)卸垃圾及倒車(chē)均在10分鐘內(nèi)完成；〔8〕車(chē)在裝的足夠多的情況下應(yīng)該直接返回原點(diǎn)2符號(hào)說(shuō)明第個(gè)垃圾站點(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變量；假設(shè)所需要的鏟車(chē)的臺(tái)數(shù)：垃圾運(yùn)輸路線總條數(shù)；：第條路線上垃圾集中點(diǎn)的個(gè)數(shù)，；：第條路線上的第個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，；：條路線上的第個(gè)垃圾集中點(diǎn)的縱坐標(biāo)：第條路線上的第個(gè)垃圾集中點(diǎn)的垃圾量，；:第條路線所需要的總時(shí)間；：第輛車(chē)的運(yùn)輸總時(shí)間；：運(yùn)輸車(chē)空載的總費(fèi)用；：運(yùn)輸車(chē)重載的總費(fèi)用；：運(yùn)輸車(chē)的總費(fèi)用； ：鏟車(chē)空載的總費(fèi)用四．模型的建立與求解模型的建立4．1運(yùn)輸車(chē)調(diào)度方案的模型由于最遠(yuǎn)的垃圾集中點(diǎn)的運(yùn)輸時(shí)間不超過(guò)運(yùn)輸車(chē)每天平均工作時(shí)間，所以可以先不考慮時(shí)間的約束。從而建立如下算法：確定重載起點(diǎn)由于每個(gè)垃圾集中點(diǎn)的垃圾量及其坐標(biāo)是不變，重載運(yùn)輸?shù)馁M(fèi)用是不變的，所以為了使總運(yùn)輸費(fèi)用最少，只要使空載的費(fèi)用最少，即盡量安排較遠(yuǎn)的垃圾集中點(diǎn)在同一路線上，從而確定重載起點(diǎn).2〕確定運(yùn)輸車(chē)路線走向要求運(yùn)輸時(shí)走最短的路線，以及運(yùn)輸費(fèi)用最低，而且由于運(yùn)輸車(chē)的重載費(fèi)用1.8元/噸是空載費(fèi)用0.4元/噸的4.5倍，為了使運(yùn)輸總費(fèi)用最少,那只能從最遠(yuǎn)的點(diǎn)〔〕開(kāi)始運(yùn)載垃圾，下一個(gè)點(diǎn)編號(hào)為，走一條路線，向垃圾處理站〔坐標(biāo)原點(diǎn)〕方向運(yùn)回。順次經(jīng)過(guò)的點(diǎn)遵循滿(mǎn)足條件：即其橫坐標(biāo)以及縱坐標(biāo)均不超過(guò)前一點(diǎn)的橫、縱坐標(biāo)，并且各點(diǎn)橫、縱坐標(biāo)遞減進(jìn)行搭配，由假設(shè)干個(gè)點(diǎn)組成一條路線。3〕確定運(yùn)輸車(chē)路線垃圾集中點(diǎn)數(shù)根據(jù)每個(gè)垃圾集中點(diǎn)的垃圾量，每條路線上的垃圾總量不超過(guò)運(yùn)輸車(chē)的最大運(yùn)輸量：根據(jù)上面算法,建立運(yùn)輸車(chē)費(fèi)用優(yōu)化模型:4.1.1運(yùn)輸車(chē)調(diào)度方案在運(yùn)輸過(guò)程中假設(shè)沒(méi)有運(yùn)輸車(chē)等待的情況,在四個(gè)小時(shí)的工作時(shí)間里,根據(jù)垃圾運(yùn)輸費(fèi)用優(yōu)化模型，得到垃圾集中點(diǎn)分配的路線及其時(shí)間,為了到達(dá)安排運(yùn)輸車(chē)最少，把所有的路線分成()類(lèi)，每類(lèi)配置一輛運(yùn)輸車(chē)，每輛運(yùn)輸車(chē)的工作時(shí)間：4.2鏟車(chē)調(diào)度方案的模型此模型的建立基于上問(wèn)模型的結(jié)果，從以上運(yùn)輸車(chē)的調(diào)度方案得出共有10條路徑，在此模型中，我們將10條路徑分別看作10個(gè)節(jié)點(diǎn)，而把垃圾處理站看作為第11個(gè)節(jié)點(diǎn)〔以下將各路徑均稱(chēng)作節(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)用為最小。4.2.1目標(biāo)函數(shù)的建立各路徑內(nèi)的費(fèi)用已定，因此我們建立以下使鏟車(chē)在各路徑之間行走所需費(fèi)用最小的目標(biāo)函數(shù)如下：2.2.2約束條件確實(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ē)的路徑為，除11號(hào)節(jié)點(diǎn)以外，在其他節(jié)點(diǎn)相互運(yùn)行的路徑：〔6〕由于垃圾的運(yùn)輸均在夜間進(jìn)行，那么每輛鏟車(chē)的工作時(shí)間不能大于5個(gè)小時(shí)〔即假定工作時(shí)間為〔凌晨0：00～早4：00〕，另外，由于題目中給定鏟車(chē)的運(yùn)行速度，均速度與運(yùn)輸車(chē)的平均速度相同，為40公里/小時(shí)，的約束條件為：4.2.3鏟車(chē)規(guī)劃模型在給出了目標(biāo)函數(shù)和約束條件后，即可得到一個(gè)使得鏟車(chē)運(yùn)行費(fèi)用最小的單目標(biāo)規(guī)劃模型如下：4.3載重量不同的運(yùn)輸車(chē)調(diào)度方案模型此問(wèn)在第一問(wèn)的根底上，通過(guò)改變垃圾運(yùn)輸車(chē)載重量的大小，從而得到垃圾處理廠在擁有不同載重量的運(yùn)輸車(chē)時(shí)，采用怎樣的運(yùn)輸方案使得所花運(yùn)輸費(fèi)用最少。此模型的目標(biāo)函數(shù)與第一問(wèn)中的運(yùn)輸車(chē)調(diào)度方案模型相同，只是在約束條件上將第〔6〕個(gè)約束條件中的載重最多為6噸變成最多為10噸，：從而可求出在擁有不同載重量運(yùn)輸車(chē)的情況下，各運(yùn)輸車(chē)的調(diào)度方案。模型的求解運(yùn)輸車(chē)調(diào)度方案模型的求解在不考慮鏟車(chē)的情況下，利用SPSS，首先據(jù)題畫(huà)出散點(diǎn)圖：利用MATLAB編程〔見(jiàn)附錄二〕，對(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.05元。表2：各運(yùn)輸路徑所包含的垃圾站點(diǎn)、運(yùn)輸量及所需時(shí)間路徑包含的站點(diǎn)運(yùn)輸垃圾總量每條線路所需時(shí)間1eq\o\ac(○,37)—eq\o\ac(○,30)—eq\o\ac(○,29)—eq\o\ac(○,27)—eq\o\ac(○,37)5.3噸3小時(shí)46分鐘2eq\o\ac(○,37)—eq\o\ac(○,28)—eq\o\ac(○,26)—eq\o\ac(○,21)—eq\o\ac(○,25)—eq\o\ac(○,19)—eq\o\ac(○,37)5.7噸3小時(shí)02分鐘3eq\o\ac(○,37)—eq\o\ac(○,36)—eq\o\ac(○,23)—eq\o\ac(○,33)—eq\o\ac(○,32)—eq\o\ac(○,37)5.5噸2小時(shí)46分鐘4eq\o\ac(○,37)—eq\o\ac(○,24)—eq\o\ac(○,18)—eq\o\ac(○,35)—eq\o\ac(○,20)—eq\o\ac(○,37)5.2噸2小時(shí)22分鐘5eq\o\ac(○,37)—eq\o\ac(○,34)—eq\o\ac(○,17)—eq\o\ac(○,16)—eq\o\ac(○,2)—eq\o\ac(○,37)5.0噸2小時(shí)7分鐘6eq\o\ac(○,37)—eq\o\ac(○,15)—eq\o\ac(○,13)—eq\o\ac(○,7)—eq\o\ac(○,4)—eq\o\ac(○,37)5.6噸2小時(shí)4分鐘7eq\o\ac(○,37)—eq\o\ac(○,14)—eq\o\ac(○,31)—eq\o\ac(○,5)—eq\o\ac(○,6)—eq\o\ac(○,37)5.85噸1小時(shí)46分鐘8eq\o\ac(○,37)—eq\o\ac(○,22)—eq\o\ac(○,10)—eq\o\ac(○,37)3.3噸1小時(shí)23分鐘9eq\o\ac(○,37)—eq\o\ac(○,12)—eq\o\ac(○,8)—eq\o\ac(○,3)—eq\o\ac(○,37)5.55噸1小時(shí)30分鐘10eq\o\ac(○,37)—eq\o\ac(○,11)—eq\o\ac(○,9)—eq\o\ac(○,1)—eq\o\ac(○,37)4.0噸1小時(shí)30分鐘從上表可以看出，對(duì)于這10條路徑上的垃圾總量，有8條都超過(guò)了5噸，另兩條也超過(guò)了載重量的一半，運(yùn)輸車(chē)得到了充分地利用，結(jié)果非常好。各運(yùn)輸路徑以圖示表示如下：由題目可知，每臺(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í)間運(yùn)輸車(chē)編號(hào)路徑編號(hào)行走路線所需時(shí)間第一輛2eq\o\ac(○,37)—eq\o\ac(○,28)—eq\o\ac(○,26)—eq\o\ac(○,21)—eq\o\ac(○,25)—eq\o\ac(○,19)—eq\o\ac(○,37)3小時(shí)02分鐘第二輛1eq\o\ac(○,37)—eq\o\ac(○,30)—eq\o\ac(○,29)—eq\o\ac(○,27)—eq\o\ac(○,37)3小時(shí)46分鐘第三輛8eq\o\ac(○,37)—eq\o\ac(○,22)—eq\o\ac(○,10)—eq\o\ac(○,37)4小時(shí)9分鐘3eq\o\ac(○,37)—eq\o\ac(○,36)—eq\o\ac(○,23)—eq\o\ac(○,33)—eq\o\ac(○,32)—eq\o\ac(○,37)第四輛9eq\o\ac(○,37)—eq\o\ac(○,12)—eq\o\ac(○,8)—eq\o\ac(○,3)—eq\o\ac(○,37)3小時(shí)37分鐘5eq\o\ac(○,37)—eq\o\ac(○,34)—eq\o\ac(○,17)—eq\o\ac(○,16)—eq\o\ac(○,2)—eq\o\ac(○,37)第五輛4eq\o\ac(○,37)—eq\o\ac(○,24)—eq\o\ac(○,18)—eq\o\ac(○,35)—eq\o\ac(○,20)—eq\o\ac(○,37)3小時(shí)52分鐘10eq\o\ac(○,37)—eq\o\ac(○,11)—eq\o\ac(○,9)—eq\o\ac(○,1)—eq\o\ac(○,37)第六輛6eq\o\ac(○,37)—eq\o\ac(○,15)—eq\o\ac(○,13)—eq\o\ac(○,7)—eq\o\ac(○,4)—eq\o\ac(○,37)3小時(shí)50分鐘7eq\o\ac(○,37)—eq\o\ac(○,14)—eq\o\ac(○,31)—eq\o\ac(○,5)—eq\o\ac(○,6)—eq\o\ac(○,37)由上表可發(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，5eq\o\ac(○,37)—eq\o\ac(○,22)—eq\o\ac(○,10)—eq\o\ac(○,12)—eq\o\ac(○,8)—eq\o\ac(○,3)—eq\o\ac(○,15)—eq\o\ac(○,13)—eq\o\ac(○,7)—eq\o\ac(○,4)—eq\o\ac(○,34)—eq\o\ac(○,17)—eq\o\ac(○,16)—eq\o\ac(○,2)—eq\o\ac(○,37)4小時(shí)22分第二臺(tái)1，3，10eq\o\ac(○,37)—eq\o\ac(○,30)—eq\o\ac(○,29)—eq\o\ac(○,27)—eq\o\ac(○,36)—eq\o\ac(○,23)—eq\o\ac(○,33)—eq\o\ac(○,32)—eq\o\ac(○,11)—eq\o\ac(○,9)—eq\o\ac(○,1)—eq\o\ac(○,37)4小時(shí)30分第三臺(tái)2，4，7eq\o\ac(○,37)—eq\o\ac(○,28)—eq\o\ac(○,26)—eq\o\ac(○,21)—eq\o\ac(○,25)—eq\o\ac(○,19)—eq\o\ac(○,24)—eq\o\ac(○,18)—eq\o\ac(○,35)—eq\o\ac(○,20)—eq\o\ac(○,14)—eq\o\ac(○,31)—eq\o\ac(○,5)—eq\o\ac(○,6)—eq\o\ac(○,37)4小時(shí)26分由上表可以看出3臺(tái)鏟車(chē)的工作時(shí)間均為4個(gè)多小時(shí)，相差不大，工作分配地非常合理。鏟車(chē)及運(yùn)輸車(chē)調(diào)度方案的具體時(shí)間安排在問(wèn)題的分析中，我們知道，運(yùn)輸車(chē)及鏟車(chē)的工作時(shí)間從凌晨0：00～早4：00，對(duì)于運(yùn)輸車(chē)調(diào)度方案，由于第三輛～第六輛都要運(yùn)輸兩條路徑上的垃圾，因此，需要確定這4輛運(yùn)輸車(chē)具體先行駛哪條路徑，而此方案確實(shí)定依賴(lài)于鏟車(chē)的行走方案。根據(jù)以上求得的各鏟車(chē)和運(yùn)輸車(chē)工作所需時(shí)間的多少及鏟車(chē)應(yīng)配合運(yùn)輸車(chē)進(jìn)行工作的原那么，對(duì)他們的工作時(shí)間進(jìn)行安排如下表所示。表5：鏟車(chē)及運(yùn)輸車(chē)相互配合的具體時(shí)間安排鏟車(chē)1：運(yùn)輸路線8965包含站點(diǎn)eq\o\ac(○,22)—eq\o\ac(○,10)eq\o\ac(○,12)—eq\o\ac(○,8)—eq\o\ac(○,3)eq\o\ac(○,15)—eq\o\ac(○,13)—eq\o\ac(○,7)—eq\o\ac(○,4)eq\o\ac(○,34)—eq\o\ac(○,17)—eq\o\ac(○,16)—eq\o\ac(○,2)時(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ē)0:3111:1112:2613:581運(yùn)輸車(chē)0:3141:1132:2663:584鏟車(chē)2：運(yùn)輸路線1310包含站點(diǎn)eq\o\ac(○,30)—eq\o\ac(○,29)—eq\o\ac(○,27)eq\o\ac(○,36)—eq\o\ac(○,23)—eq\o\ac(○,33)—eq\o\ac(○,32)eq\o\ac(○,11)—eq\o\ac(○,9)—eq\o\ac(○,1)時(shí)間到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)鏟車(chē)1:0922:1224:302運(yùn)輸車(chē)1:0923:2034:505鏟車(chē)3：運(yùn)輸路線247包含站點(diǎn)eq\o\ac(○,28)—eq\o\ac(○,26)—eq\o\ac(○,21)—eq\o\ac(○,25)—eq\o\ac(○,19)eq\o\ac(○,24)—eq\o\ac(○,18)—eq\o\ac(○,35)—eq\o\ac(○,20)eq\o\ac(○,14)—eq\o\ac(○,31)—eq\o\ac(○,5)—eq\o\ac(○,6)時(shí)間到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)到達(dá)時(shí)間車(chē)輛編號(hào)鏟車(chē)1:0632:4233:493運(yùn)輸車(chē)1:0612:4254:236以上時(shí)間安排均是基于工作時(shí)間從凌晨0：00開(kāi)始，從上表3和表4可以看出，每輛運(yùn)輸車(chē)和每臺(tái)鏟車(chē)的工作時(shí)間都不超過(guò)5個(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í)間第一輛0:00eq\o\ac(○,37)—eq\o\ac(○,28)—eq\o\ac(○,26)—eq\o\ac(○,21)—eq\o\ac(○,25)—eq\o\ac(○,19)—eq\o\ac(○,37)3:02第二輛0:00eq\o\ac(○,37)—eq\o\ac(○,30)—eq\o\ac(○,29)—eq\o\ac(○,27)—eq\o\ac(○,37)3:46第三輛0:11eq\o\ac(○,37)—eq\o\ac(○,12)—eq\o\ac(○,8)—eq\o\ac(○,3)—eq\o\ac(○,37)1:411:47eq\o\ac(○,37)—eq\o\ac(○,36)—eq\o\ac(○,23)—eq\o\ac(○,33)—eq\o\ac(○,32)—eq\o\ac(○,37)4:33第四輛0:20eq\o\ac(○,37)—eq\o\ac(○,22)—eq\o\ac(○,10)—eq\o\ac(○,37)1:232:15eq\o\ac(○,37)—eq\o\ac(○,34)—eq\o\ac(○,17)—eq\o\ac(○,16)—eq\o\ac(○,2)—eq\o\ac(○,37)4:22第五輛0:51eq\o\ac(○,37)—eq\o\ac(○,24)—eq\o\ac(○,18)—eq\o\ac(○,35)—eq\o\ac(○,20)—eq\o\ac(○,37)3:133:15eq\o\ac(○,37)—eq\o\ac(○,11)—eq\o\ac(○,9)—eq\o\ac(○,1)—eq\o\ac(○,37)4:45第六輛0:44eq\o\ac(○,37)—eq\o\ac(○,15)—eq\o\ac(○,13)—eq\o\ac(○,7)—eq\o\ac(○,4)—eq\o\ac(○,37)2:482:50eq\o\ac(○,37)—eq\o\ac(○,14)—eq\o\ac(○,31)—eq\o\ac(○,5)—eq\o\ac(○,6)—eq\o\ac(○,37)4:363.3載重量不同的運(yùn)輸車(chē)的調(diào)度方案3.3.1方案一運(yùn)用LINGO對(duì)模型〔3〕進(jìn)行求解可以得到以下7條運(yùn)輸路徑，以問(wèn)題分析中運(yùn)輸車(chē)選擇的原那么即：對(duì)于垃圾量不大于6噸的路線，調(diào)用6噸的運(yùn)輸車(chē)；對(duì)于垃圾量在〔6～10噸〕之間的路線，調(diào)用10噸的運(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，1095.6噸1.33小時(shí)213，819，285.6噸1.38小時(shí)318，14，31，5，67.35噸2.23小時(shí)424，17，3，1，265.45噸2.37小時(shí)530，29，27，15，11，168.7噸3.13小時(shí)634，35，20，7，4，2,218.4噸2.45小時(shí)736，23，33，32，22,259.9噸2.93小時(shí)由以上各條路徑上的垃圾總量的大小來(lái)對(duì)運(yùn)輸車(chē)輛進(jìn)行選擇，根據(jù)各路徑運(yùn)輸所需時(shí)間的大小，對(duì)各輛運(yùn)輸車(chē)的行駛方案進(jìn)行規(guī)劃，得到結(jié)果如下表。根據(jù)以上數(shù)據(jù)可得，當(dāng)有載重量為6噸、10噸二種運(yùn)輸車(chē)時(shí)，需要各類(lèi)載重的運(yùn)輸車(chē)輛分別為：對(duì)于6噸的運(yùn)輸車(chē)，需要3輛；對(duì)于10噸的運(yùn)輸車(chē)，需要4輛。3.3.2方案二運(yùn)用MATLAB編程對(duì)模型〔3〕求解〔見(jiàn)附錄三〕，可以得到另外一種調(diào)度方案，共有8條運(yùn)輸路徑，所花費(fèi)用為2326.17元。各路徑的垃圾總量、運(yùn)輸所需時(shí)間分別表示如下：表9：方案二的各路徑包含的垃圾站點(diǎn)、垃圾總量及運(yùn)輸所需時(shí)間運(yùn)輸路徑包含的垃圾站點(diǎn)運(yùn)輸?shù)目偫窟\(yùn)輸所需時(shí)間1,29，27，155.52.97小時(shí)228，26，21，25，19，14,58.83.2小時(shí)336，23，33，32，22,98.72.93小時(shí)424，18，35，315.72.53小時(shí)534，17，16，6，305.592.12小時(shí)613，7，4，25.71.72小時(shí)712，8，3，5.551.67小時(shí)811，10，20，15.51.33小時(shí)同方案一，可根據(jù)各路徑的垃圾總量選擇運(yùn)輸車(chē)輛，根據(jù)各路徑運(yùn)輸所花時(shí)間對(duì)運(yùn)輸車(chē)的行走路徑進(jìn)行安排。對(duì)于方案二，由以上數(shù)據(jù)可得：當(dāng)有載重量為6噸、10噸三種運(yùn)輸車(chē)時(shí)，需要各類(lèi)載重的運(yùn)輸車(chē)輛分別為：對(duì)于6噸的運(yùn)輸車(chē)，需要6輛；對(duì)于10噸的運(yùn)輸車(chē)，需要2輛。相比擬來(lái)說(shuō)，對(duì)于兩種方案，方案二的結(jié)果較好。3.4每個(gè)垃圾站點(diǎn)的垃圾量是隨機(jī)數(shù)，標(biāo)準(zhǔn)差為該站點(diǎn)平均垃圾量的10%模型五．模型結(jié)果的分析與檢驗(yàn)由于題目中沒(méi)有給出司機(jī)的工資額，因此文中只考慮了垃圾的運(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ē)行駛的路徑最短。六．模型的推廣與改良方向該模型可以應(yīng)用在很多方面，比方說(shuō)貨物運(yùn)輸、車(chē)輛分配等。七．模型的優(yōu)缺點(diǎn)然而，該問(wèn)題在站點(diǎn)眾多，運(yùn)輸路徑較大的前提下，缺點(diǎn)就會(huì)顯得尤為突出。首先是運(yùn)輸車(chē)載重的缺乏，當(dāng)運(yùn)輸車(chē)的載重不能滿(mǎn)足其中任一點(diǎn)的垃圾量時(shí)，模型就可能不能適用了，該模型優(yōu)點(diǎn)是算法簡(jiǎn)單容易實(shí)現(xiàn),精度特別是后兩個(gè)模型的精度不是很高.前兩問(wèn)只要進(jìn)行窮舉就能得出最優(yōu)解.第三問(wèn)的處理原那么不算很精確,有待改良參考文獻(xiàn)【1】全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽優(yōu)秀論文匯編。中國(guó)物價(jià)出版社，2002【2】宋兆基，徐流美等。MATLAB6.5在科學(xué)計(jì)算中的應(yīng)用。清華大學(xué)出版社，2005【3】耿素云.集合論與圖論(離散數(shù)學(xué)二分冊(cè))[M].北京:北京大學(xué)出版社,1997.【4】趙可培.運(yùn)籌學(xué)[M].上海:上海財(cái)經(jīng)大學(xué)出版社,2000.附錄附錄一：垃圾站地理坐標(biāo)數(shù)據(jù)表序號(hào)站點(diǎn)編號(hào)垃圾量T坐標(biāo)x(km)坐標(biāo)y(km)111.5032221.8015332.5554441.2047560.8508651.30311773.2079882.3096991.4010210101.5014011111.1017312122.7014613131.8012914142.80101215200.6071416161.5021617170.8061818181.50111719190.801512202115321.401.2019229522221.8021023231.4027924241.60151925252.60151426261.00201727272.00211328281.00242029292.10251630301.20281831311.9051232211.30171633333.2025734341.2092035352.5091536361.303012附錄二：[code]clearx=[31540379101417141210726111519222127151520212425285172599300];y=[25478119620369121416181712950919141713201618121672015120];t=[1.501.500.551.200.851.301.202.301.401.501.102.701.801.800.601.500.801.500.801.401.201.801.401.601.601.002.001.002.101.201.901.301.601.201.501.300.00];i=1:37;a=1:37;plot(x,y,'*r')forii=1:37k=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);fori=1:20sum=0;j1=1;s=0;m=37;i3=37;forj=1:36if(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;elsecontinue;endendw(5,m)=1;j1=j1+1;while1js=0;q=40;fork=1:36if(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)==0q=w(2,m)+w(3,m)-w(2,k)-w(3,k);js=1;jg(i,j1)=w(1,k);i3=k;elsecontinue;endendw(5,i3)=1;sum=sum+w(4,i3);j1=j1+1;m=i3;if(w(2,i3)==0&w(3,i3)==0|js==0)breakendendendkcost=0;zcost=0;allcost=0;n=0;foru1=1:11foru2=1:11ifjg(u1,u2)~=0n=jg(u1,u2);elsecontinueendzcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n));endn=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;foru4=1:11foru5=1:11ifjg(u4,u5)~=0n1=jg(u4,u5);n2=n2+1;elsecontinueendendn3=jg(u4,1);time(1,u4)=((w(2,n3)+w(3,n3))*2)/40;endn2time附錄三clearx=[31540379101417141210726111519222127151520212425285172599300];y=[25478119620369121416181712950919141713201618121672015120];t=[1.501.500.551.200.851.301.202.301.401.501.102.701.801.800.601.500.801.500.801.401.201.801.401.601.601.002.001.002.101.201.901.301.601.201.501.300.00];i=1:37;a=1:37;plot(x,y,'*r')forii=1:37k=int2str(ii);k=strcat('P',k);text(x(ii),y(ii),k);endw=[i;x;y;t;a];w(5,:)=0;jg=zeros(10,10);%′?·?11ì??·??fori=1:20sum=0;j1=1;s=0;m=37;i3=37;forj=1:36if(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