數(shù)學(xué)模型垃圾車調(diào)度問題

1、作業(yè)題之一垃圾運(yùn)輸調(diào)度問題1 .問題重述某城區(qū)有36個(gè)垃圾集中點(diǎn)，每天都要從垃圾處理廠（第37號(hào)節(jié)點(diǎn)）出發(fā)將垃圾運(yùn)回。不考慮垃圾的裝車時(shí)間。現(xiàn)有一種載重6噸的運(yùn)輸車，運(yùn)輸車平均速度為40公里/小時(shí)（夜里運(yùn)輸，不考慮塞車現(xiàn)象）；每臺(tái)車每日平均工作4小時(shí)。運(yùn)輸車重載運(yùn)費(fèi)元/噸公里；運(yùn)輸車空載費(fèi)用元/公里；并且假定街道方向均平行于坐標(biāo)軸。運(yùn)輸車應(yīng)如何調(diào)度（需要投入多少臺(tái)運(yùn)輸車，每臺(tái)車的調(diào)度方案，運(yùn)營費(fèi)用）？表1-1?垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表?序號(hào)站點(diǎn)編R垃圾量T坐標(biāo)（km）序號(hào)站點(diǎn)編R垃圾量T坐標(biāo)（km）xyxy1132201519922152132225335422222104447232327956

2、0824241519653112525151477792626201788962727211399102282824201010140292925161111173303028181212146313151213131293221171614141012333325715207143434920161621635359151717618363630121818111737370019191512?2 .模型的基本假設(shè)與符號(hào)說明基本假設(shè)1 .車輛在拐彎時(shí)的時(shí)間損耗忽略。2 .車輛在任意兩站點(diǎn)中途不停車，保持穩(wěn)定的速率。3 .只要平行于坐標(biāo)軸即有街道存在。4 .無論垃圾量多少，都不計(jì)裝車時(shí)間。5

3、.每個(gè)垃圾站點(diǎn)的垃圾只能由一輛運(yùn)輸車運(yùn)載。6 .假設(shè)運(yùn)卒&車從A垃圾站到B垃圾站總走最短路線。7 .任意兩垃圾站間的最短路線為以兩垃圾站連線為斜邊的直角三角形的兩直角邊之和。8 .每輛垃圾運(yùn)輸車每次運(yùn)的足夠多，且不允許運(yùn)輸車有超載現(xiàn)象；9 .假設(shè)在運(yùn)輸垃圾過程中沒有新垃圾入站。10 .假設(shè)運(yùn)輸車和鏟車在行駛過程中不出現(xiàn)的塞車、拋錨等耽誤時(shí)間的情況；11 .各垃圾站每天的垃圾量相對(duì)穩(wěn)定。符號(hào)說明Tk:第k個(gè)垃圾集中點(diǎn)的垃圾量，k1,2,36;Xk:第k個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，k1,2,36;Yk:第k個(gè)垃圾集中點(diǎn)的縱坐標(biāo)，k1,2,36;L：垃圾運(yùn)輸路線總條數(shù)；G:第i條路線上垃圾集中點(diǎn)的

4、個(gè)數(shù)，i1,2,L;N:安排運(yùn)輸車的總數(shù)量；Xj:第i條路線上的第j個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，i1,2,L,j1,2,Ci;Yj：第i條路線上的第j個(gè)垃圾集中點(diǎn)的縱坐標(biāo)，i1,2,L,j1,2,CiTj:第i條路線上的第j個(gè)垃圾集中點(diǎn)的垃圾量，i1,2,L,j1,2,Ci；hi:第i條路線所需要的總時(shí)間；Hn：第n輛車的運(yùn)輸總時(shí)間；W1：運(yùn)輸車空載的總費(fèi)用；W2：運(yùn)輸車重載的總費(fèi)用；W：運(yùn)輸車的總費(fèi)用；3模型的建立確定運(yùn)輸車路線算法由于最遠(yuǎn)的垃圾集中點(diǎn)的運(yùn)輸時(shí)間不超過運(yùn)輸車每天平均工作時(shí)間，所以可以先不考慮時(shí)間的約束。從而建立如下算法：1）確定重載起點(diǎn)由于每個(gè)垃圾集中點(diǎn)的垃圾量及其坐標(biāo)是不變，重載

5、運(yùn)輸?shù)馁M(fèi)用是不變的，所以為了使總運(yùn)輸費(fèi)用W最少，只要使空載的費(fèi)用最少，即盡量安排較遠(yuǎn)的垃圾集中點(diǎn)在同一路線上，從而確定重載起點(diǎn)Xi1.2）確定運(yùn)輸車路線走向要求運(yùn)輸時(shí)走最短的路線，以及運(yùn)輸費(fèi)用最低，而且由于運(yùn)輸車的重載費(fèi)用元/噸是空載費(fèi)用元/噸的倍，為了使運(yùn)輸總費(fèi)用W最少,那只能從最遠(yuǎn)的點(diǎn)（j1）開始運(yùn)載垃圾，下一個(gè)點(diǎn)編號(hào)為j1，走一條路線，向垃圾處理站（坐標(biāo)原點(diǎn)）方向運(yùn)回。順次經(jīng)過的點(diǎn)遵循滿足條件：XijXij1YijYij1即其橫坐標(biāo)以及縱坐標(biāo)均不超過前一點(diǎn)的橫、縱坐標(biāo)，并且各點(diǎn)橫、縱坐標(biāo)遞減進(jìn)行搭配，由若干個(gè)點(diǎn)組成一條路線。3）確定運(yùn)輸車路線垃圾集中點(diǎn)數(shù)根據(jù)每個(gè)垃圾集中點(diǎn)的垃圾量，每條路

6、線上的垃圾總量不超過運(yùn)輸車的最大Ci運(yùn)輸量：Tij6,i1,2,Lji根據(jù)上面算法，建立運(yùn)輸車費(fèi)用優(yōu)化模型：LminW0.4*X”i1XijXij1st.YijYij1,i1,2,LCiTij6j1運(yùn)輸車調(diào)度方案在運(yùn)輸過程中假設(shè)沒有運(yùn)輸車等待的情況，在四個(gè)小時(shí)的工作時(shí)間里，根據(jù)垃圾運(yùn)輸費(fèi)用優(yōu)化模型，得到垃圾集中點(diǎn)分配的路線及其時(shí)間hi,為了達(dá)到安排運(yùn)輸車最少，把所有的路線分成N(NL)類，每類配置一輛運(yùn)輸車，每輛運(yùn)輸車的工作時(shí)間Hn：LHnhiEi,i1,2,Li10,第i條路線不在n類日。1,第1條路線在門類,n1,2,NHn44.模型的求解運(yùn)輸車路線的計(jì)算首先根據(jù)題所給的數(shù)據(jù)畫出散點(diǎn)圖垃圾

7、點(diǎn)地理坐標(biāo)252015109I2415161d!81120A21725-9715.,L1-5j015-334,i-7-429二750454-914-4217-3-4j00014-215101520253035求解程序(見附錄1),得到以下運(yùn)行結(jié)果3029273000000028126322550r001000362333210000000241835150000000341716200r0010002011100000000019138000r0000014741000000022000000000012190000r001000316000000000運(yùn)輸車的最優(yōu)路線如下圖所示:表1-2運(yùn)輸

8、路線安排及其費(fèi)用運(yùn)輸路線先后經(jīng)過的垃圾站點(diǎn)序號(hào)空載費(fèi)用（元）重載費(fèi)用（元）運(yùn)輸路程（km）運(yùn)輸所需時(shí)問（h）T線0-22-042二號(hào)線0-31-6-034三號(hào)線0-12-9-0840四號(hào)線0-20-11-10-056五號(hào)線0-19-13-8-054六號(hào)線0-14-7-4-1-044七號(hào)線0-34-17-16-2-016258八號(hào)線0-24-18-35-15-026168九號(hào)線0-36-23-33-21-084左線0-30-29-27-3-092線0-28-26-32-25-5-088由此得出，運(yùn)輸車空載的總運(yùn)費(fèi)為各路線總和的一半乘以空載的運(yùn)輸費(fèi)用：LW10.4*Xi1Yi1132元i1運(yùn)輸車重

9、載的總運(yùn)費(fèi)為各路線的最遠(yuǎn)點(diǎn)開始至垃圾處理站各自線路上的各個(gè)垃圾集中點(diǎn)將線路劃分的若干部分，各部分運(yùn)輸車上垃圾量乘以該部分的路程，冉將各部分所得的積的總和乘以運(yùn)輸車重載的運(yùn)輸費(fèi)用：36W21.8*Tk*(XkYk)2213.4元.k1運(yùn)輸車總的運(yùn)輸費(fèi)用為：WW1W2122.42212.652345.4元。運(yùn)輸車調(diào)度最優(yōu)方案根據(jù)計(jì)算各路線所需時(shí)間的，在運(yùn)輸車每日平均工作四小時(shí)左右的前提下，得出路線的最優(yōu)搭配，從而得出所需最少的卡車數(shù)量。由上表1-2中運(yùn)輸所需時(shí)問，我們得到如下路線搭配，如表1-3:表1-3運(yùn)輸車路線及其時(shí)間安排運(yùn)輸線路車輛安排運(yùn)輸車線路時(shí)間總時(shí)間1一、一十2小時(shí)18分1小時(shí)03分3

10、小時(shí)21分21K、十2小時(shí)12分1小時(shí)06分3小時(shí)18分3二、三、五1小時(shí)21分1小時(shí)51分3小時(shí)12分4七、八1小時(shí)42分1小時(shí)27分3小時(shí)9分5四、九2小時(shí)6分1小時(shí)24分3小時(shí)30分由表1-3得出，最少安排五輛運(yùn)輸車對(duì)垃圾集中點(diǎn)進(jìn)行運(yùn)輸，達(dá)到最優(yōu)運(yùn)輸方案5.附錄附錄1:運(yùn)輸車調(diào)度方案的程序clearx=31540379101417141210726111519222127151520212425285172599300;y=25478119620369121416181712950919141713201618121672015120;t=；i=1:37;a=1:37;plot(x,y,

11、'*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);%?11i?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;

12、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)*(w(2,n)+w(3,n);endn=jg(u1,1);kcost=kcost+*(w(2,n)+w(3,n);end