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

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

2、 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10 25 16 11 11 1.10 17 3 30 30 1.20 28

3、 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 0.00 0 0 19 19 0.80 15 12 表1-1 垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表 2.模型的基本假設(shè)與符號(hào)說(shuō)明 2.2 基本假設(shè) 1車輛在拐彎時(shí)的時(shí)間損耗

4、忽略。 2車輛在任意兩站點(diǎn)中途不停車，保持穩(wěn)定的速率。 3只要平行于坐標(biāo)軸即有街道存在。 4無(wú)論垃圾量多少，都不計(jì)裝車時(shí)間。 5 每個(gè)垃圾站點(diǎn)的垃圾只能由一輛運(yùn)輸車運(yùn)載。 6. 假設(shè)運(yùn)輸車從A垃圾站到B垃圾站總走最短路線。 7. 任意兩垃圾站間的最短路線為以兩垃圾站連線為斜邊的直角三角形的兩直角邊之和。 實(shí)用文檔 文案大全 8. 每輛垃圾運(yùn)輸車每次運(yùn)的足夠多，且不允許運(yùn)輸車有超載現(xiàn)象； 9. 假設(shè)在運(yùn)輸垃圾過(guò)程中沒(méi)有新垃圾入站。 10. 假設(shè)運(yùn)輸車和鏟車在行駛過(guò)程中不出現(xiàn)的塞車、拋錨等耽誤時(shí)間的情況； 11. 各垃圾站每天的垃圾量相對(duì)穩(wěn)定。 2.2 符號(hào)說(shuō)明 kT：第k個(gè)垃圾集中點(diǎn)的垃圾量,3

5、6,2,1?k； kX：第k個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，36,2,1?k； kY：第k個(gè)垃圾集中點(diǎn)的縱坐標(biāo)，36,2,1?k； L：垃圾運(yùn)輸路線總條數(shù)； iC：第i條路線上垃圾集中點(diǎn)的個(gè)數(shù)，Li,2,1?； N:安排運(yùn)輸車的總數(shù)量； ijX：第i條路線上的第j個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，iCjLi,2,1,2,1?； ijY：第i條路線上的第j個(gè)垃圾集中點(diǎn)的縱坐標(biāo)，iCjLi,2,1,2,1? ijT：第i條路線上的第j個(gè)垃圾集中點(diǎn)的垃圾量，iCjLi,2,1,2,1?； ih:第i條路線所需要的總時(shí)間； nH：第n輛車的運(yùn)輸總時(shí)間； 1W：運(yùn)輸車空載的總費(fèi)用； 2W：運(yùn)輸車重載的總費(fèi)用； W：運(yùn)輸車的總

6、費(fèi)用； 3模型的建立 3.1 確定運(yùn)輸車路線算法 由于最遠(yuǎn)的垃圾集中點(diǎn)的運(yùn)輸時(shí)間不超過(guò)運(yùn)輸車每天平均工作時(shí)間，所以可以先不考慮時(shí)間的約束。從而建立如下算法： 1) 確定重載起點(diǎn) 由于每個(gè)垃圾集中點(diǎn)的垃圾量及其坐標(biāo)是不變，重載運(yùn)輸?shù)馁M(fèi)用是不變的，所以為了使總運(yùn)輸費(fèi)用W最少，只要使空載的費(fèi)用最少，即盡量安排較遠(yuǎn)的垃圾集中點(diǎn)在同一路線上，從而確定重載起點(diǎn)1iX. 2）確定運(yùn)輸車路線走向 要求運(yùn)輸時(shí)走最短的路線，以及運(yùn)輸費(fèi)用最低，而且由于運(yùn)輸車的重載費(fèi)用1.8元/噸是空載費(fèi)用0.4元/噸的4.5倍，為了使運(yùn)輸總費(fèi)用W最少,那只能從最遠(yuǎn)的點(diǎn)（1?j）開(kāi)始運(yùn)載垃圾，下一個(gè)點(diǎn)編號(hào)為1?j，走一條路線，向垃圾

7、處理站（坐標(biāo)原點(diǎn)）方向運(yùn)回。順次經(jīng)過(guò)的點(diǎn)遵循滿足條件： ?11ijijijijYYXX 即其橫坐標(biāo)以及縱坐標(biāo)均不超過(guò)前一點(diǎn)的橫、縱坐標(biāo)，并且各點(diǎn)橫、縱坐標(biāo)遞減進(jìn)行搭配，由若干個(gè)點(diǎn)組成一條路線。 3）確定運(yùn)輸車路線垃圾集中點(diǎn)數(shù) 實(shí)用文檔 文案大全 根據(jù)每個(gè)垃圾集中點(diǎn)的垃圾量，每條路線上的垃圾總量不超過(guò)運(yùn)輸車的最大運(yùn)輸量：LiTiCjij,2,1,61? 根據(jù)上面算法,建立運(yùn)輸車費(fèi)用優(yōu)化模型: LiTYYXXtsXWiCjijijijijijLii,2,1,6.*4.0min111111? 3.2 運(yùn)輸車調(diào)度方案 在運(yùn)輸過(guò)程中假設(shè)沒(méi)有運(yùn)輸車等待的情況,在四個(gè)小時(shí)的工作時(shí)間里,根據(jù)垃圾運(yùn)輸費(fèi)用優(yōu)化模

8、型，得到垃圾集中點(diǎn)分配的路線及其時(shí)間ih,為了達(dá)到安排運(yùn)輸車最少，把所有的路線分成N(LN?)類，每類配置一輛運(yùn)輸車，每輛運(yùn)輸車的工作時(shí)間nH： 4,2,1,1,00,2,1,1?niLiiinHNnniniELiEhH?類條路線在第類條路線不在第 4.模型的求解 4.1 運(yùn)輸車路線的計(jì)算 首先根據(jù)題所給的數(shù)據(jù)畫(huà)出散點(diǎn)圖 垃圾點(diǎn)地理坐標(biāo) 0 5 10 15 20 25 9 24 6 15 28 2 11 17 20 25 7 9 15 5 10 15 21 30 3 0 7 12 19 27 4 9 14 25 1 5 22 3 10 17 0 0 5 10 14 15 2021 25 30

9、35 求解程序(見(jiàn)附錄1),得到以下運(yùn)行結(jié)果: 實(shí)用文檔 文案大全 30 29 27 3 0 0 0 0 0 0 0 28 26 32 25 5 0 0 0 0 0 0 36 23 33 21 0 0 0 0 0 0 0 24 18 35 15 0 0 0 0 0 0 0 34 17 16 2 0 0 0 0 0 0 運(yùn)輸路線 先后經(jīng)過(guò)的垃圾站點(diǎn)序號(hào) 空載費(fèi)用 (元) 重載費(fèi)用 (元) 運(yùn)輸路程 (km) 運(yùn)輸所需時(shí)間（h） 一號(hào)線 0-22-0 8.4 45.36 42 1.05 二號(hào)線 0-31-6-0 6.8 90.9 34 0.85 三號(hào)線 0-12-9-0 8 127.44 40 1

10、.0 四號(hào)線 0-20-11-10-0 11.2 147.96 56 1.4 五號(hào)線 0-19-13-8-0 10.8 169.02 54 1.35 六號(hào)線 0-14-7-4-1-0 8.8 143.1 44 1.1 0 20 11 10 0 0 0 0 0 0 0 0 19 13 8 0 0 0 0 0 0 0 0 14 7 4 1 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 31 6 0 0 0 0 0 0 0 0 0 運(yùn)輸車的最優(yōu)路線如下圖所示： 表1-2 運(yùn)輸路線安排及其費(fèi)用 實(shí)用文檔 文案大全 七號(hào)線 0-3

11、4-17-16-2-0 11.6 162 58 1.45 八號(hào)線 0-24-18-35-15-0 13.6 261 68 1.7 九號(hào)線 0-36-23-33-21-0 16.8 339.48 84 2.1 十號(hào)線 0-30-29-27-3-0 18.4 385.65 92 2.3 十一號(hào)線 0-28-26-32-25-5-0 17.6 318.78 88 2.2 由此得出，運(yùn)輸車空載的總運(yùn)費(fèi)為各路線總和的一半乘以空載的運(yùn)輸費(fèi)用： ?元132*4.01111?LiiiYXW 運(yùn)輸車重載的總運(yùn)費(fèi)為各路線的最遠(yuǎn)點(diǎn)開(kāi)始至垃圾處理站各自線路上的各個(gè)垃圾集中點(diǎn)將線路劃分的若干部分，各部分運(yùn)輸車上垃圾量乘

12、以該部分的路程，再將各部分所得的積的總和乘以運(yùn)輸車重載的運(yùn)輸費(fèi)用： .4.2213)(*8.13612元?kkkkYXTW 運(yùn)輸車總的運(yùn)輸費(fèi)用為： 元4.234565.22124.12221?WWW。 4.2 運(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小時(shí)21分 2 六、十一 2小時(shí)12分 1小時(shí)06分 3小時(shí)18分 3

13、 二、三、五 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)度方案的程序 clear x=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 9

14、 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 實(shí)用文檔 文案大全 1.20 1.50 1.30 0.00; i=1:37; a=1:37; plot(x,y,'*r') for ii=1:37 k=int2str

15、(ii); k=strcat('P',k); text(x(ii),y(ii),k); end w=i;x;y;t;a; w(5,:)=0; jg=zeros(11,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 end w(5,m)=1; j1=j1+

16、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 實(shí)用文檔 文案大全 end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end end end kcost=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=