垃圾運(yùn)輸問(wèn)題模型

《垃圾運(yùn)輸問(wèn)題模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、關(guān)于垃圾運(yùn)輸問(wèn)題的數(shù)學(xué)模型摘要本文對(duì)于垃圾運(yùn)輸問(wèn)題的優(yōu)化，通過(guò)運(yùn)用圖論的TSP問(wèn)題的有關(guān)知識(shí)對(duì)題目給出的坐標(biāo)數(shù)據(jù)進(jìn)行了處理，根據(jù)從最遠(yuǎn)點(diǎn)開(kāi)始運(yùn)載垃圾運(yùn)輸費(fèi)用最低的原則，以及不走回路的前提，在條件時(shí)間約束下，建立了運(yùn)輸車(chē)和鏟車(chē)的調(diào)度優(yōu)化模型，得到運(yùn)輸車(chē)和鏟車(chē)的安排路線和時(shí)間，在垃圾運(yùn)輸問(wèn)題上，安排了六輛運(yùn)輸車(chē)，三輛鏟車(chē)的最少調(diào)動(dòng)車(chē)輛數(shù)目，達(dá)到最少運(yùn)輸費(fèi)用。關(guān)鍵詞：哈密頓圖；TSP問(wèn)題；垃圾集中點(diǎn)；重載起點(diǎn)；運(yùn)輸路線1問(wèn)題重述某城區(qū)有36個(gè)垃圾集中點(diǎn)，每天都要從垃圾處理廠（第37號(hào)節(jié)點(diǎn)）出發(fā)將垃圾運(yùn)回?，F(xiàn)用一種載重6噸的運(yùn)輸車(chē)到期每個(gè)垃圾點(diǎn)載運(yùn)垃圾,并需要用10分鐘的時(shí)間

2、裝車(chē)，運(yùn)輸車(chē)平均速度為40公里／小時(shí)（夜里運(yùn)輸，不考慮塞車(chē)現(xiàn)象）；每臺(tái)車(chē)每日平均工作4小時(shí)。運(yùn)輸車(chē)重載運(yùn)費(fèi)1.8元/噸公里；運(yùn)輸車(chē)和裝垃圾用的鏟車(chē)空載費(fèi)用0.4元/公里；并且假定街道方向均平行于坐標(biāo)軸。要求給出滿意的運(yùn)輸調(diào)度方案，使總運(yùn)費(fèi)最少。問(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)用）垃圾集中點(diǎn)坐標(biāo)數(shù)據(jù)表如下表1：表1:垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表序號(hào)站點(diǎn)編號(hào)垃圾量T坐標(biāo)(km)序號(hào)站點(diǎn)編號(hào)垃圾量T坐標(biāo)(km)xyxy111.503220151.40199221.501521

3、321.20225330.555422221.80210441.204723231.40279560.850824241.601519651.3031125251.601514771.207926261.002017882.309627272.002113991.4010228281.00242010101.5014029292.10251611111.1017330301.20281812122.7014631311.9051213131.8012932211.30171614141.80101233331.6025715200.6071434341.2092016

4、161.5021635351.5091517170.8061836361.30301218181.50111737370.000019190.8015122模型假設(shè)2.1假設(shè)運(yùn)輸車(chē)重載與空載行走時(shí)間相同；2.2假設(shè)運(yùn)輸車(chē)在工作過(guò)程中沒(méi)有任何耽誤；2.3假設(shè)鏟車(chē)的速度與運(yùn)輸車(chē)的速度一樣；2.4只要在滿足每輛運(yùn)輸車(chē)在每天平均工作四小時(shí)的前提下,假設(shè)運(yùn)輸車(chē)工作時(shí)間允許超過(guò)四小時(shí)；2.5假設(shè)運(yùn)輸車(chē)每天安排所走的路線不是固定不變的，有一個(gè)值班制度,使每輛運(yùn)輸車(chē)每天平均工作大約四小時(shí)。3符號(hào)說(shuō)明：第個(gè)垃圾集中點(diǎn)的垃圾量,；：第個(gè)垃圾集中點(diǎn)的橫坐標(biāo)，；：第個(gè)垃圾集中點(diǎn)的縱坐標(biāo)，；：

5、垃圾運(yùn)輸路線總條數(shù)；：第條路線上垃圾集中點(diǎn)的個(gè)數(shù)，；:安排運(yùn)輸車(chē)的總數(shù)量；：第條路線上的第個(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ē)1的空載費(fèi)用；：鏟車(chē)2的空載費(fèi)用；：鏟車(chē)3的空載費(fèi)用；：全部鏟車(chē)空載的總費(fèi)用。4運(yùn)輸車(chē)調(diào)度優(yōu)化模型4.1確定運(yùn)輸車(chē)路線算法由于最遠(yuǎn)的垃圾集中點(diǎn)的運(yùn)輸時(shí)間不超過(guò)運(yùn)輸車(chē)每天平均工作時(shí)間，所以可以先不考慮時(shí)間的約束。從而建立如下算法：1)確定重載起點(diǎn)由于每個(gè)垃圾集中點(diǎn)的垃圾量及其坐標(biāo)是不變，重載運(yùn)輸?shù)馁M(fèi)用是不

6、變的，所以為了使總運(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)遵循滿足條件：即其橫坐標(biāo)以及縱坐標(biāo)均不超過(guò)前一點(diǎn)的橫、縱坐標(biāo)，并且各點(diǎn)橫、縱坐標(biāo)遞減進(jìn)行搭配，由若干個(gè)點(diǎn)組成一條路線。3）確定運(yùn)輸車(chē)路線垃圾集中點(diǎn)數(shù)根據(jù)每個(gè)垃圾集中點(diǎn)的垃圾量，每條路線上的垃圾總量不

7、超過(guò)運(yùn)輸車(chē)的最大運(yùn)輸量：根據(jù)上面算法,建立運(yùn)輸車(chē)費(fèi)用優(yōu)化模型:4.2運(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í)間：5鏟車(chē)調(diào)度優(yōu)化模型這是一個(gè)遍歷問(wèn)題，要確定鏟車(chē)的行走路線，并使得運(yùn)輸車(chē)工作時(shí)盡量不要等待鏟車(chē)，為此，應(yīng)使鏟車(chē)跟著運(yùn)輸車(chē)跑完一條線路，也就是說(shuō)，應(yīng)使鏟車(chē)跟著運(yùn)輸車(chē)鏟完一條線路后再接著鏟下一條線路。再跑下一條路線?？墒沁\(yùn)輸車(chē)的工作時(shí)間有限制，都不能超過(guò)每日平均工作4