


下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、垃圾運(yùn)輸問題的模型及其求解劉育興 ,鐘劍(贛南師范學(xué)院a.數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院;b.網(wǎng)絡(luò)中心,江西贛州341000)摘要:本文通過垃圾運(yùn)輸問題的模型建立與求解, 總結(jié)出這類問題的一般性 解法,即根據(jù)實(shí)際問題構(gòu)造恰當(dāng)?shù)挠邢蚧驘o向賦權(quán)圖,把問題轉(zhuǎn)化成mecq的TSP問題,通過解決這類TSP 問題,從而使原問題獲得滿意的解答關(guān)1有關(guān)概念定義I【11設(shè)G=(,E)是連通無向圖,(1)經(jīng)過 G 的每一個頂點(diǎn)正好一次的路,稱為G 的一條哈密頓路或日路;(2)經(jīng)過 G 的每一個頂點(diǎn)正好一次的圈,稱為G 的一條哈密頓圈或日圈;(3)含日圈的圖稱為哈密頓圖或日圖. .定義2【i1設(shè)D =(,A)是連通有向圖,(
2、1)經(jīng)過 D 的每一個頂點(diǎn)正好一次的圈,稱為 D 的生成圈;(2)含生成圈的圖稱為哈密頓圖或日圖.定義 3? 設(shè) G 是完全(有向或無向 )賦權(quán)圖, 在 C 中尋找權(quán)最小閉跡的問題稱 為 TSP 問題(即 TraveIingSaIesman ProbIem.) 若此閉跡是日圈,則稱此閉跡為最佳日圈.容易證明:在滿足條件t ( )+t (,)下,TSP問題可轉(zhuǎn)化為尋找最佳H 圈的問題,這可通過構(gòu)造一個完全圖來實(shí)現(xiàn).2 垃圾運(yùn)輸問題例 I 某城區(qū)有若干個垃圾集中點(diǎn),每天都要從垃圾處理廠 (第 37 號節(jié)點(diǎn))出 發(fā)將垃圾運(yùn)回.假定運(yùn)輸圖 1 運(yùn)輸車線路圖車的線路已確定下來共 IO 條(如圖 1 所示
3、).為了節(jié)省費(fèi)用,運(yùn)輸車在每條線路上總是先從遠(yuǎn)離處 理廠的垃圾集中點(diǎn)開始運(yùn)送垃圾現(xiàn)有 6輛載重 6 噸的運(yùn)輸車及裝垃圾用的鏟車,它們的平均速度 為40 kin/h(夜里運(yùn)輸,不考慮塞車現(xiàn)象),每個垃 圾點(diǎn)需要用 10 rain 的時間裝車,每臺運(yùn)輸車每日 平均工作4 h.運(yùn)輸車重載運(yùn)費(fèi)1. 8元/噸km;運(yùn) 輸車和裝垃圾用的鏟車空載費(fèi)用 0. 4 km.并 且假定街道方向均平行于坐標(biāo)軸.請你給出滿意 的運(yùn)輸調(diào)度方案 (每臺運(yùn)輸車的調(diào)度方案,每臺鏟 車的行走路線及總運(yùn)營費(fèi)用 ).鼉收稿日期: 2005一 l1 一 O8作者簡介:劉育興 (1968 一),男,江西吉安人,贛南師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)
4、科學(xué)學(xué)院講師,主要從事圖論研究.維普資訊 第 3 期 劉育興,鐘劍垃圾運(yùn)輸問題的模型及其求解 53 表 l 垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表問題分析:這是一個遍歷問題, 此問題的困難之處在于確定鏟車的行走路線, 并使得運(yùn)輸車工作時盡量不要等待鏟車,才能使得運(yùn)輸車的工作時間滿足題目的要求每日平均工 作4 h.為此,應(yīng)使鏟車跟著運(yùn)輸車跑完一條線路,也就是說,應(yīng)使鏟車鏟完一條線路后再接著鏟下一條線路. 問題解答:為敘述方便,每條路線上開始的垃圾集中點(diǎn)稱為這條路線的始點(diǎn), 最后的垃圾集中點(diǎn)稱為這條路線的終點(diǎn). 每條線路上運(yùn)輸車行走的路程與花費(fèi)的時間列表如表2: 莽表 2 運(yùn)輸路程與時問根據(jù)表 2中各路線上運(yùn)輸車花
5、費(fèi)的時間, 各運(yùn)輸車運(yùn)輸路線安排如表 3所示: 表3運(yùn)輸線路時間安排 為了尋找鏟車合理的行走路線,構(gòu)造一有向圖D如 下:將各條線路看成一個點(diǎn),路線 、?、分別看成點(diǎn)1、2、?、10 點(diǎn)i到點(diǎn)j的弧上的權(quán)等于鏟車由路i的終點(diǎn)到路j的始 點(diǎn)的空載費(fèi)用,而由點(diǎn) 4、5、?、l0 分別到點(diǎn) 1、2、3的弧上的權(quán)等于;其次,將原點(diǎn)0用3階完全有向圖來代替,三點(diǎn)分別為01、02、03,弧上的權(quán)均為, 0i(i_1 , 2, 3)與其他各點(diǎn) 之間的弧上權(quán)如下確定: 0i 分別到點(diǎn) 1, 2, 3的弧上的權(quán)等于鏟車由點(diǎn)0分別到路, 的起點(diǎn)的空載費(fèi)用,點(diǎn)4, 5,?,10分別到點(diǎn)0i的弧上的權(quán)分別等于鏟車由路
6、4, 5, ?。10的終點(diǎn)分別到點(diǎn)0的空載費(fèi)用,其余各弧上的權(quán)均等于.于是,D是一個完全賦權(quán)有向圖,問題轉(zhuǎn)化成在D中尋找最小哈密頓有向圈,可采用對調(diào)調(diào)優(yōu)算法,通過編程計(jì)算,得到 近似最優(yōu)哈密頓有向圈 (把 0i(i=1 , 2, 3)收縮為點(diǎn) 0):0一十 1-+ 一十 7 H 6-+0 一十 3-+I0-+8 9-+0,因此,3 輛鏟車維普資訊 贛南師范學(xué)院學(xué)報(bào) 2006年 的行走路線分別為:鏟車 1: 0 I 一 5 一 0;鏟車2: 0 一 27 6 一 0;鏟車 3: 0一 3一 I089 一 0.由于各鏟車的行走路線已確定且它們花在各條路線上的時間可精確計(jì)算出來,因 此,根據(jù)鏟車的情況和各運(yùn)輸車的行走路線,可安排出如表 4 所示的較為滿意的調(diào)度方案:表 4 行走路線與時間安排運(yùn)輸車輛 行走路線及時問安排1 10: 00從點(diǎn)0發(fā)車一 I1 : 06到達(dá)路線 的起點(diǎn)一 1: 02返回點(diǎn)02 10: 58從點(diǎn)0發(fā)車一+o: 07到達(dá)路線的起點(diǎn)一 1: 46返回點(diǎn)010: 00從點(diǎn)0發(fā)車一 I1 : 03到達(dá)路線 的起點(diǎn)一加:46
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 全身性水腫的健康教育
- 會厭囊腫的護(hù)理查房
- 骨盆骨髓炎個案護(hù)理
- 輪胎非線性特性對主動四輪轉(zhuǎn)向控制的影響研究及優(yōu)化策略
- 先天性肛瘺的健康宣教
- 軍團(tuán)病的治療及護(hù)理
- 腎動靜脈瘺的健康宣教
- 下丘腦膿腫的健康宣教
- 壞疽性紫癜的健康宣教
- 開放性牙槽骨骨折查房
- 過盈配合壓入力計(jì)算公式
- 第八章-材料工程-倫理問題-全
- 婚前協(xié)議(保護(hù)女方利益)
- 奉賢區(qū)教育系統(tǒng)師德師風(fēng)建設(shè)學(xué)習(xí)測試附有答案
- 扶貧農(nóng)產(chǎn)品購銷合同協(xié)議(農(nóng)產(chǎn)品購銷合同模板)
- 汽車維修高級工考試試題及參考答案
- 檢驗(yàn)科安全管理制度匯總
- GB/T 5782-2016六角頭螺栓
- GB/T 23445-2009聚合物水泥防水涂料
- GB/T 13451.2-1992著色顏料相對著色力和白色顏料相對散射力的測定光度計(jì)法
- GB/T 11264-2012熱軋輕軌
評論
0/150
提交評論