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

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

2、1）經(jīng)過(guò) D 的每一個(gè)頂點(diǎn)正好一次的圈，稱為 D 的生成圈；（2）含生成圈的圖稱為哈密頓圖或日?qǐng)D.定義 3? 設(shè) G 是完全（有向或無(wú)向 ）賦權(quán)圖， 在 C 中尋找權(quán)最小閉跡的問(wèn)題稱 為 TSP 問(wèn)題（即 TraveIingSaIesman ProbIem.） 若此閉跡是日圈，則稱此閉跡為最佳日圈.容易證明：在滿足條件t （ ）+t （，）下，TSP問(wèn)題可轉(zhuǎn)化為尋找最佳H 圈的問(wèn)題，這可通過(guò)構(gòu)造一個(gè)完全圖來(lái)實(shí)現(xiàn).2 垃圾運(yùn)輸問(wèn)題例 I 某城區(qū)有若干個(gè)垃圾集中點(diǎn)，每天都要從垃圾處理廠 （第 37 號(hào)節(jié)點(diǎn)）出 發(fā)將垃圾運(yùn)回.假定運(yùn)輸圖 1 運(yùn)輸車(chē)線路圖車(chē)的線路已確定下來(lái)共 IO 條（如圖 1 所示

3、）.為了節(jié)省費(fèi)用，運(yùn)輸車(chē)在每條線路上總是先從遠(yuǎn)離處 理廠的垃圾集中點(diǎn)開(kāi)始運(yùn)送垃圾現(xiàn)有 6輛載重 6 噸的運(yùn)輸車(chē)及裝垃圾用的鏟車(chē)，它們的平均速度 為40 kin/h（夜里運(yùn)輸，不考慮塞車(chē)現(xiàn)象），每個(gè)垃 圾點(diǎn)需要用 10 rain 的時(shí)間裝車(chē)，每臺(tái)運(yùn)輸車(chē)每日 平均工作4 h.運(yùn)輸車(chē)重載運(yùn)費(fèi)1. 8元/噸km;運(yùn) 輸車(chē)和裝垃圾用的鏟車(chē)空載費(fèi)用 0. 4 km.并 且假定街道方向均平行于坐標(biāo)軸.請(qǐng)你給出滿意 的運(yùn)輸調(diào)度方案 （每臺(tái)運(yùn)輸車(chē)的調(diào)度方案，每臺(tái)鏟 車(chē)的行走路線及總運(yùn)營(yíng)費(fèi)用 ）.鼉收稿日期： 2005一 l1 一 O8作者簡(jiǎn)介：劉育興 （1968 一），男，江西吉安人，贛南師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)

4、科學(xué)學(xué)院講師，主要從事圖論研究.維普資訊 第 3 期 劉育興，鐘劍垃圾運(yùn)輸問(wèn)題的模型及其求解 53 表 l 垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表問(wèn)題分析：這是一個(gè)遍歷問(wèn)題， 此問(wèn)題的困難之處在于確定鏟車(chē)的行走路線， 并使得運(yùn)輸車(chē)工作時(shí)盡量不要等待鏟車(chē)，才能使得運(yùn)輸車(chē)的工作時(shí)間滿足題目的要求每日平均工 作4 h.為此，應(yīng)使鏟車(chē)跟著運(yùn)輸車(chē)跑完一條線路，也就是說(shuō)，應(yīng)使鏟車(chē)鏟完一條線路后再接著鏟下一條線路. 問(wèn)題解答：為敘述方便，每條路線上開(kāi)始的垃圾集中點(diǎn)稱為這條路線的始點(diǎn)， 最后的垃圾集中點(diǎn)稱為這條路線的終點(diǎn). 每條線路上運(yùn)輸車(chē)行走的路程與花費(fèi)的時(shí)間列表如表2： 莽表 2 運(yùn)輸路程與時(shí)問(wèn)根據(jù)表 2中各路線上運(yùn)輸車(chē)花

5、費(fèi)的時(shí)間， 各運(yùn)輸車(chē)運(yùn)輸路線安排如表 3所示： 表3運(yùn)輸線路時(shí)間安排 為了尋找鏟車(chē)合理的行走路線，構(gòu)造一有向圖D如 下：將各條線路看成一個(gè)點(diǎn)，路線 、？、分別看成點(diǎn)1、2、？、10 點(diǎn)i到點(diǎn)j的弧上的權(quán)等于鏟車(chē)由路i的終點(diǎn)到路j的始 點(diǎn)的空載費(fèi)用，而由點(diǎn) 4、5、?、l0 分別到點(diǎn) 1、2、3的弧上的權(quán)等于；其次，將原點(diǎn)0用3階完全有向圖來(lái)代替，三點(diǎn)分別為01、02、03,弧上的權(quán)均為, 0i（i_1 , 2, 3）與其他各點(diǎn) 之間的弧上權(quán)如下確定： 0i 分別到點(diǎn) 1， 2， 3的弧上的權(quán)等于鏟車(chē)由點(diǎn)0分別到路， 的起點(diǎn)的空載費(fèi)用，點(diǎn)4, 5,?,10分別到點(diǎn)0i的弧上的權(quán)分別等于鏟車(chē)由路

6、4, 5, ?。10的終點(diǎn)分別到點(diǎn)0的空載費(fèi)用，其余各弧上的權(quán)均等于.于是，D是一個(gè)完全賦權(quán)有向圖，問(wèn)題轉(zhuǎn)化成在D中尋找最小哈密頓有向圈,可采用對(duì)調(diào)調(diào)優(yōu)算法,通過(guò)編程計(jì)算,得到 近似最優(yōu)哈密頓有向圈 （把 0i（i=1 ， 2， 3）收縮為點(diǎn) 0）：0一十 1-+ 一十 7 H 6-+0 一十 3-+I0-+8 9-+0，因此，3 輛鏟車(chē)維普資訊 贛南師范學(xué)院學(xué)報(bào) 2006年 的行走路線分別為：鏟車(chē) 1: 0 I 一 5 一 0;鏟車(chē)2: 0 一 27 6 一 0;鏟車(chē) 3： 0一 3一 I089 一 0.由于各鏟車(chē)的行走路線已確定且它們花在各條路線上的時(shí)間可精確計(jì)算出來(lái)，因 此，根據(jù)鏟車(chē)的情況和各運(yùn)輸車(chē)的行走路線，可安排出如表 4 所示的較為滿意的調(diào)度方案：表 4 行走路線與時(shí)間安排運(yùn)輸車(chē)輛 行走路線及時(shí)問(wèn)安排1 10: 00從點(diǎn)0發(fā)車(chē)一 I1 : 06到達(dá)路線 的起點(diǎn)一 1: 02返回點(diǎn)02 10: 58從點(diǎn)0發(fā)車(chē)一+o: 07到達(dá)路線的起點(diǎn)一 1: 46返回點(diǎn)010: 00從點(diǎn)0發(fā)車(chē)一 I1 : 03到達(dá)路線 的起點(diǎn)一加：46