垃圾運輸問題的模型及其求解

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

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

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

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

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

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