垃圾運(yùn)輸問題的模型及其求解

1、垃圾運(yùn)輸問題的模型及其求解劉育興 ，鐘劍（贛南師范學(xué)院a.數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院；b.網(wǎng)絡(luò)中心，江西贛州341000）摘要：本文通過垃圾運(yùn)輸問題的模型建立與求解， 總結(jié)出這類問題的一般性 解法，即根據(jù)實際問題構(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)造一個完全圖來實現(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ī)

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)算法,通過編程計算,得到 近似最優(yōu)哈密頓有向圈 （把 0i（i=1 ， 2， 3）收縮為點(diǎn) 0）：0一十 1-+ 一十 7 H 6-+0 一十 3-+I0-+8 9-+0，因此，3 輛鏟車維普資訊 贛南師范學(xué)院學(xué)報 2006年 的行走路線分別為：鏟車 1: 0 I 一 5 一 0;鏟車2: 0 一 27 6 一 0;鏟車 3： 0一 3一 I089 一 0.由于各鏟車的行走路線已確定且它們花在各條路線上的時間可精確計算出來，因 此，根據(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