[建筑]垃圾運輸問題的模型及其求解

《[建筑]垃圾運輸問題的模型及其求解》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、垃圾運輸問題的模型及其求解’劉育興，鐘劍(贛南師范學院a．數(shù)學與計算機科學學院；b．網(wǎng)絡中心，江西贛州341000)摘要：本文通過垃圾運輸問題的模型建立與求解，總結出這類問題的一般性解法，即根據(jù)實際問題構造恰當?shù)挠邢蚧驘o向賦權圖，把問題轉化成mecq,的TSP問題，通過解決這類TSP問題，從而使原問題獲得滿意的解答．關1有關概念定義l【I1設G=(，E)是連通無向圖，(1)經(jīng)過G的每一個頂點正好一次的路，稱為G的一條哈密頓路或日路；(2)經(jīng)過G的每一個頂點正好一次的圈，稱為G的一條哈密頓圈或日圈；(3)含日圈的圖稱為哈密頓圖或日圖．．定義2【

2、i1設D=(，A)是連通有向圖，(1)經(jīng)過D的每一個頂點正好一次的圈，稱為D的生成圈；(2)含生成圈的圖稱為哈密頓圖或日圖．定義3?設G是完全(有向或無向)賦權圖，在C中尋找權最小閉跡的問題稱為TSP問題(即TravelingSalesmanProblem)．若此閉跡是日圈，則稱此閉跡為最佳日圈．容易證明：在滿足條件t‘}()+t‘}(，)下，TSP問題可轉化為尋找最佳H圈的問題，這可通過構造一個完全圖來實現(xiàn)．2垃圾運輸問題例l某城區(qū)有若干個垃圾集中點，每天都要從垃圾處理廠(第37號節(jié)點)出發(fā)將垃圾運回．假定運輸圖1運輸車線路圖車的線路已確定

3、下來共lO條(如圖1所示)．為了節(jié)省費用，運輸車在每條線路上總是先從遠離處理廠的垃圾集中點開始運送垃圾．現(xiàn)有6輛載重6噸的運輸車及裝垃圾用的鏟車，它們的平均速度為40kin／h(夜里運輸，不考慮塞車現(xiàn)象)，每個垃圾點需要用10rain的時間裝車，每臺運輸車每日平均工作4h．運輸車重載運費1．8元／噸km；運輸車和裝垃圾用的鏟車空載費用0．4km．并且假定街道方向均平行于坐標軸．請你給出滿意的運輸調度方案(每臺運輸車的調度方案，每臺鏟車的行走路線及總運營費用)．鼉收稿日期：2005一l1一O8作者簡介：劉育興(1968一)，男，江西吉安人，贛南

4、師范學院數(shù)學與計算機科學學院講師，主要從事圖論研究．維普資訊http://www.cqvip.com第3期劉育興，鐘劍垃圾運輸問題的模型及其求解53表l垃圾點地理坐標數(shù)據(jù)表問題分析：這是一個遍歷問題，此問題的困難之處在于確定鏟車的行走路線，并使得運輸車工作時盡量不要等待鏟車，才能使得運輸車的工作時間滿足題目的要求——每日平均工作4h．為此，應使鏟車跟著運輸車跑完一條線路，也就是說，應使鏟車鏟完一條線路后再接著鏟下一條線路．問題解答：為敘述方便，每條路線上開始的垃圾集中點稱為這條路線的始點，最后的垃圾集中點稱為這條路線的終點．每條線路上運輸車行

5、走的路程與花費的時間列表如表2：莽表2運輸路程與時問根據(jù)表2中各路線上運輸車花費的時間，各運輸車運輸路線安排如表3所示：表3運輸線路時間安排為了尋找鏟車合理的行走路線，構造一有向圖D如下：將各條線路看成一個點，路線①、②、?、⑩分別看成點1、2、?、lO．點i到點j的弧上的權等于鏟車由路i的終點到路j的始點的空載費用，而由點4、5、?、l0分別到點1、2、3的弧上的權等于∞；其次，將原點0用3階完全有向圖來代替，三點分別為Ol、o2、O3，弧上的權均為∞，Oi(i_1，2，3)與其他各點之間的弧上權如下確定：Oi分別到點1，2，3的弧上的權等

6、于鏟車由點0分別到路①，②，③的起點的空載費用，點4，5，?，lO分別到點Oi的弧上的權分別等于鏟車由路4，5，?。lO的終點分別到點0的空載費用，其余各弧上的權均等于∞．于是，D是一個完全賦權有向圖，問題轉化成在D中尋找最小哈密頓有向圈，可采用對調調優(yōu)算法，通過編程計算，得到近似最優(yōu)哈密頓有向圈(把Oi(i=1，2，3)收縮為點0)：O一十1—-+一十7—÷6-+O一十3-+lO-+89-+O，因此，3輛鏟車維普資訊http://www.cqvip.com贛南師范學院學報2006年的行走路線分別為：鏟車1：O—l一5一O；鏟車2：O一2—7

7、-÷6一O；鏟車3：O一3一l0—8—9一O．由于各鏟車的行走路線已確定且它們花在各條路線上的時間可精確計算出來，因此，根據(jù)鏟車的情況和各運輸車的行走路線，可安排出如表4所示的較為滿意的調度方案：表4行走路線與時間安排運輸車輛行走路線及時問安排110：00從點O發(fā)車一l1：06到達路線①的起點一l：02返回點O210：58從點O發(fā)車—+o：07到達路線②的起點一l：46返回點O1O：00從點O發(fā)車一l1：03到達路線③的起點—加：46返回點O，再次從點O發(fā)車一l：l6到達路線⑧的起點—：O6返回點O．11：43從點O發(fā)車—加：14．5到達路線

8、⑩的起點一l：06返回點O，再次從點O發(fā)車一l：43．5。到達路線④的起點—：l3返回點O11：41從點O發(fā)車—加：32到達路線⑤的起點一2：達路線⑨的起點—：33