1、垃圾運(yùn)輸問題* 信息工程學(xué)院 計(jì)算機(jī)應(yīng)用專業(yè) *摘要：本文通過對(duì)垃圾站點(diǎn)之間分布位置的分析，構(gòu)造出解決垃圾運(yùn)輸問題的模型。首先，我們對(duì)所給數(shù)據(jù)繪制其xy散點(diǎn)圖，根據(jù)題設(shè)提出自己假設(shè)的條件，。其次，結(jié)合已有的模型，對(duì)垃圾點(diǎn)之間的位置分布關(guān)系進(jìn)行討論及證明，從而確定最基本的行車路線原則。然后，編寫c語(yǔ)言程序，利用計(jì)算機(jī)進(jìn)行算法的模擬，從而搜索出各運(yùn)輸車輛的數(shù)量以及最佳的分配方案，使得(1)在不考慮鏟車的情況下運(yùn)輸費(fèi)用最少、(2)考慮在有鏟車的模型中的最佳解、(3)對(duì)不同運(yùn)輸量的運(yùn)輸車進(jìn)行合理分配調(diào)度，使得總費(fèi)用最少。根據(jù)我們確定的解題思路，最終我們得到了一組可行解，如下：第一問，求得全部的運(yùn)輸費(fèi)用

2、是2340.97元，花費(fèi)的總時(shí)間是21.95小時(shí)；第二問：求得需要3輛鏟車；第三問：求得總的運(yùn)輸費(fèi)用是2323.77 元。其中8噸的車4輛，6噸的車3輛，4噸的車3輛。具體的路線分配圖，車輛調(diào)度圖見正文部分。本文討論的解題方法模型簡(jiǎn)單，得出的結(jié)果只是一個(gè)近似最優(yōu)解的可行解，所以還有很大的改進(jìn)空間，比如我們可以采用更加智能的算法等。 關(guān)鍵詞：計(jì)算機(jī)算法模擬 優(yōu)化1問題的重述某城區(qū)有 37 個(gè)垃圾集中點(diǎn)，每天都要從垃圾處理廠（第 38號(hào)節(jié)點(diǎn)）出發(fā)將垃圾運(yùn)回。現(xiàn)有一種載重 6 噸的運(yùn)輸車。每個(gè)垃圾點(diǎn)需要用 10 分鐘的時(shí)間裝車，運(yùn)輸車平均速度為 40 公里小時(shí)（夜里運(yùn)輸，不考慮塞車現(xiàn)象）；每臺(tái)車每日

3、平均工作 4 小時(shí)。運(yùn)輸車重載運(yùn)費(fèi) 2 元 / 噸公里；運(yùn)輸車和裝垃圾用的鏟車空載費(fèi)用 0.5 元 / 公里；并且假定街道方向均平行于坐標(biāo)軸。請(qǐng)你給出滿意的運(yùn)輸調(diào)度方案以及計(jì)算程序。問題：1.運(yùn)輸車應(yīng)如何調(diào)度（需要投入多少臺(tái)運(yùn)輸車，每臺(tái)車的調(diào)度方案，運(yùn)營(yíng)費(fèi)用）2.鏟車應(yīng)如何調(diào)度（需要多少臺(tái)鏟車，每臺(tái)鏟車的行走路線，運(yùn)營(yíng)費(fèi)用）3.如果有載重量為 4 噸、 6 噸、 8 噸三種運(yùn)輸車，又如何調(diào)度？2模型的基本假設(shè)與符號(hào)說明（一）基本假設(shè)1車輛在拐彎時(shí)的時(shí)間損耗忽略。2車輛在任意兩站點(diǎn)中途不停車，保持穩(wěn)定的速率。3只要平行于坐標(biāo)軸即有街道存在。4無(wú)論垃圾量多少，都能在十分鐘內(nèi)裝上運(yùn)輸車。5 每個(gè)垃圾

4、站點(diǎn)的垃圾只能由一輛運(yùn)輸車運(yùn)載。6. 假設(shè)運(yùn)輸車、鏟車從A垃圾站到B垃圾站總走最短路線。7. 任意兩垃圾站間的最短路線為以兩垃圾站連線為斜邊的直角三角形的兩直角邊之和。8. 建設(shè)在運(yùn)輸垃圾過程中沒有新垃圾入站。9. 假設(shè)鏟車、運(yùn)輸車載工作途中不發(fā)生意外也不遇到意外；10. 各垃圾站每天的垃圾量相對(duì)穩(wěn)定。（二）符號(hào)說明|A| 表示A點(diǎn)到原點(diǎn)的距離，恒正|B| 表示B點(diǎn)到原點(diǎn)的距離，恒正|A-B| 表示A,B兩點(diǎn)之間的距離,恒正Ta 表示A點(diǎn)所在地的垃圾量cost：運(yùn)費(fèi)；time：時(shí)間消耗；裝的足夠多 運(yùn)輸車當(dāng)前的載重離限載不大于0.55噸(垃圾點(diǎn)的最小垃圾量)序數(shù)號(hào) 所在點(diǎn)的編號(hào)3模型的建立垃圾

5、運(yùn)輸問題最終可以歸結(jié)為最優(yōu)路徑搜索問題，但注意到此圖為森林而不是樹，不能直接套用Krusal，Prim等現(xiàn)成算法，于是根據(jù)具體問題設(shè)計(jì)出隨機(jī)下山法，用計(jì)算模擬搜索，可以搜尋到令人滿意的可行解。先注意到兩點(diǎn)的情況，設(shè)兩點(diǎn)分別為A(x1,y1),B(x2,y2)。主要有以下兩種情況：一A,B明顯有先后次序。-遞減狀態(tài)（如圖1） 不妨設(shè)x1>x2, y1>y2,不難看出A在B的后方,即A比B遠(yuǎn)。對(duì)于前方參考點(diǎn)O,要將A,B對(duì)應(yīng)垃圾點(diǎn)的垃圾全部取回再返回O,一共有三種方式：1O->A->O, O->B->O單獨(dú)運(yùn)輸。這種情況下，總的路程消費(fèi)等于空載運(yùn)行費(fèi)用(0.4元

6、/公里)與裝載時(shí)運(yùn)行費(fèi)用（1.8元/公里噸）的總和。所需的總時(shí)間等于車輛所走過的總路程與速度（40公里/小時(shí)）的比值再加上在A,B兩點(diǎn)停留的時(shí)間(每個(gè)垃圾點(diǎn)上停留了10分鐘，1/6小時(shí))，于是有：Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*TbTime = (2*|A| + 2*|B|)/40 + 1/6*22. O->A->B->O 先遠(yuǎn)點(diǎn)再近點(diǎn)，即先空載至最遠(yuǎn)處，裝完A點(diǎn)垃圾后再返回至B,再回O點(diǎn)，有： Cost = 0.4*|A| + 1.8*|A-B|*Ta +1.8*|B|*(Ta+Tb) = 0.4*|A| +

7、1.8*|A|*Ta + 1.8*|B|*Tb Time = 2*|A|/40 + 1/6*23. O->B->A->O 先近點(diǎn)在遠(yuǎn)點(diǎn)，即先裝B點(diǎn)垃圾，然后載著B點(diǎn)的垃圾奔至A點(diǎn)，再回O點(diǎn)，有： Cost= 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb) = 0.4*|B| + 1.8*|A|*Ta + 1.8*|B|*Tb + 1.8*|A-B|*2*Tb Time = 2*|A|/40 + 1/6*2比較以上三種情況，遠(yuǎn)近點(diǎn)的遍歷順序，可以看出，“先遠(yuǎn)后近”絕對(duì)比“先近后遠(yuǎn)”在花費(fèi)錢的數(shù)量上要少的多，省出1.8*|A-B|*2*Tb這部分

8、的錢主要是車載著B點(diǎn)的垃圾奔到A點(diǎn)再返回B點(diǎn)。而又注意到兩者的時(shí)間花費(fèi)是相等的。所以在其余同等的情況下選擇“先遠(yuǎn)后近”。考慮到時(shí)間上單獨(dú)運(yùn)輸比其余的兩種運(yùn)輸要大的多，多一一倍，而且花費(fèi)的錢仍不比“先遠(yuǎn)后近”省，還多了0.4*|B|，所以一般情況下，不采用單獨(dú)運(yùn)輸。二A，B兩點(diǎn)沒有明顯先后順序。 -并鄰狀態(tài)（如圖2）還是一共有三種情況： 1O->A->O, O->B->O單獨(dú)運(yùn)輸。這種情況下，跟A,B兩點(diǎn)有先后順序中的情況完全相同，即有：Cost = 0.4*|A| + 1.8*|A|*Ta + 0.4*|B| + 1.8*|B|*Tbtime = (2*|A| + 2*

9、|B|)/40 + 1/6*22O->A->B->OCost = 0.4*|A| + 1.8*|A-B|*Ta + 1.8*|B|*(Ta+Tb) -1Time = (|A| + |A-B| + |B|)/40 + 1/6*23.O->B->A->OCost = 0.4*|B| + 1.8*|A-B|*Tb + 1.8*|A|*(Ta+Tb) -2Time = (|A| + |A-B| + |B|)/40 +1/6*2相比之下，清晰可見并鄰狀態(tài)下的單獨(dú)運(yùn)輸所花的費(fèi)用最少，所以在不要求時(shí)間的情況下對(duì)于并鄰兩點(diǎn)，采用單獨(dú)運(yùn)輸?shù)姆绞阶罟?jié)約錢。用<1>式

10、與<2>式相減除以1.8， 得到如下判斷式：|A-B|*(Ta-Tb) + (Ta+Tb)*(|B|-|A|) -<3>上式 < 0時(shí)， 選 0->A->B->O;上式 > 0時(shí)， 選 O->B->A->O;上式 = 0時(shí)， 任意選上述兩路線。三兩點(diǎn)選擇趨勢(shì)的討論。 （如圖3）由圖中看到B,C兩點(diǎn)沒有明顯的先后順序，屬于并鄰點(diǎn)。因?yàn)楫?dāng)運(yùn)輸車載重行駛時(shí)費(fèi)用會(huì)成倍的增長(zhǎng)，比其空載時(shí)所花費(fèi)用要大的多，所以排除A->B->C或A->C->B這樣的一次經(jīng)過3點(diǎn)的往返路線，僅選擇B,C中的某一點(diǎn)與A完成此次運(yùn)輸

11、，將另一點(diǎn)留到下次。那么A點(diǎn)選擇B還是C呢？不妨假設(shè)|B|>|C|,即B點(diǎn)離原點(diǎn)的距離比C點(diǎn)的更遠(yuǎn)，因?yàn)锳在B,C之后，所以也就是B點(diǎn)離A點(diǎn)更近。這樣，此次的運(yùn)輸我們更趨向于選擇A->B,因?yàn)榫瓦@三點(diǎn)而論，A無(wú)論是選B還是C，三點(diǎn)的垃圾總要運(yùn)完，所以花費(fèi)的錢是一樣的。但選擇A->B后，下次運(yùn)輸車運(yùn)C點(diǎn)垃圾時(shí)就無(wú)需跑的更遠(yuǎn)。四關(guān)于垃圾點(diǎn)的垃圾是否一次清除的討論（以6噸車?yán)┯杉僭O(shè)2知，每天的垃圾必須清除完畢，全部運(yùn)往37點(diǎn)。這里說的一次清除問題不是指一天，而是指當(dāng)一輛運(yùn)輸車已經(jīng)裝載了足夠多的垃圾，不能完全清理下一個(gè)垃圾點(diǎn)的時(shí)候，車在下一個(gè)站點(diǎn)“停還是不停”的問題。例如，一輛運(yùn)輸

12、車選擇了30->26->18->35->20的路線（即先將空車開往30，清理裝載30點(diǎn)的垃圾，然后依次到26，18，35，20），它從20返回時(shí)車已經(jīng)裝載了5.8噸垃圾，仍可以裝0.2噸(小于垃圾點(diǎn)垃圾量的最小值0.5，稱這種情況為“裝的足夠多”)。在20點(diǎn)下方仍有不少的點(diǎn)，但肯定不能將下面的任意點(diǎn)的垃圾裝完，那么此車是直接返回37點(diǎn)呢，還是繼續(xù)裝直至車裝滿為止呢？我們判斷前者更好，就是車在裝的足夠多的情況下應(yīng)該直接返回原點(diǎn)（37點(diǎn)）。這是因?yàn)閷?duì)于下一垃圾點(diǎn)(假設(shè)為A點(diǎn))內(nèi)的垃圾而言，無(wú)論是一次裝完還是分兩次裝完，將它們運(yùn)回所花費(fèi)用是恒定的，等于1.8*Ta*|A|。整

13、體而言，兩者花費(fèi)的錢是相等的，但分兩次裝要多花10分鐘的裝車時(shí)間，所以選擇前者。綜上所述，得出搜索的基本原則：1在兩點(diǎn)遞減的情況下，不采用單獨(dú)運(yùn)輸；2在其余同等的情況下選擇“先遠(yuǎn)后近”；3不要求時(shí)間的情況下對(duì)于并鄰兩點(diǎn)，采用單獨(dú)運(yùn)輸?shù)姆绞阶罟?jié)約錢；一般情況下用式<3作判斷；4車在裝的足夠多的情況下應(yīng)該直接返回原點(diǎn)（37點(diǎn)）；5每一次布局和每條線路的搜索不妨由剩下未搜點(diǎn)中的最大值開始。4模型的求解問題一在不考慮鏟車的情況下。首先根據(jù)題所給的數(shù)據(jù)畫出散點(diǎn)圖求得總運(yùn)營(yíng)費(fèi)用為2345.4元,總時(shí)間為22.5小時(shí)，求解程序如附錄二，運(yùn)輸車的最優(yōu)路線如下圖所示：表一:線路的費(fèi)用和所用時(shí)間站點(diǎn)序號(hào)空載

14、費(fèi)用所花時(shí)間一號(hào)線0-30-29-27-3-018.42.3+2/3二號(hào)線0-28-26-32-25-5-017.62.2+5/6三號(hào)線0-36-23-33-21-016.82.1+2/3四號(hào)線0-24-18-35-15-013.61.7+2/3五號(hào)線0-34-17-16-2-0121.45+2/3六號(hào)線0-20-11-10-011.21.4+1/2七號(hào)線0-19-13-8-010.81.35+1/2八號(hào)線0-14-7-4-1-08.81.1+1/2九號(hào)線0-22-08.41.05+1/6十號(hào)線0-12-9-081+1/3十一號(hào)線0-31-6-06.80.85+1/3問題二.鏟車加入后的討論

15、當(dāng)加入鏟車后,我們應(yīng)該讓鏟車將就運(yùn)輸車,因?yàn)殓P車的空載費(fèi)用為0.4元/小時(shí).鏟車加入垃圾后為1.8元/公里小時(shí).若改變一條線,則會(huì)造成幾公里的誤差,甚至十幾公里的誤差,這一項(xiàng)的數(shù)目就很大.若是鏟車將就運(yùn)輸車,則即使路線誤差大一點(diǎn),但所需費(fèi)用也不會(huì)變得很大.故我們以第一個(gè)方案的路線為準(zhǔn).這時(shí)我們只要保證前一條線路的末節(jié)點(diǎn),與后一條線路的首節(jié)點(diǎn)的路程差分別相加之和最小即可.根據(jù)這一思路.我們?cè)O(shè)一個(gè)結(jié)構(gòu)數(shù)組變量,他有11個(gè)元素(代表11條元素).其中每個(gè)元素里面有兩個(gè)結(jié)構(gòu)成員,這樣一個(gè)元素就代表一條線路.對(duì)這11個(gè)元素進(jìn)行排列,這樣每一個(gè)排列就是一個(gè)線路方案.這樣便能通過排列,遍歷每種方案.就求出最

16、優(yōu)解.再考慮了最短路徑的情況下，由于要考慮和各車在時(shí)間地銜接，以及盡量要在規(guī)定的時(shí)間內(nèi)作完，我們進(jìn)行相應(yīng)的調(diào)整。這部分由于考慮到計(jì)算復(fù)雜性，我們用手工調(diào)整，由于前面有最短路徑的保證，我們調(diào)整的結(jié)果接近最優(yōu)解。程序代碼如附錄三【源碼】程序運(yùn)行結(jié)果見附錄三【結(jié)果】 表二:行走線路和所用時(shí)間線路時(shí)間0-30-29-27-3-0 2.3+4/60-28-26-32-25-5-02.2+5/60-36-23-33-21-02.1+4/60-24-18-35-15-0 1.7+4/60-34-17-16-2-01.45+2/30-19-13-8-01.35+1/20-20-12-9-01.0+1/20-1

17、1-10-0 0.7+1/30-31-6-00.7+1/30-14-7-4-1-00.55+4/613.5小時(shí)根據(jù)總時(shí)間和個(gè)線路的耗時(shí)，依平均工作6小時(shí)為條件得出需要三量鏟車，三輛鏟車的起始點(diǎn)分別為36 ，31 ，28；因?yàn)檫\(yùn)輸車時(shí)速為40km/h,則鏟車速度無(wú)須大于40km/h.若速度小于40km/h,則至少要多買一輛鏟車,這樣造成重復(fù),故最好多花點(diǎn)錢買大功率的鏟車.為了保證能在晚上干完，我們可以多條路同時(shí)干，但考慮到新加鏟車費(fèi)用，我們只讓三輛鏟車同時(shí)工作，就能在規(guī)定時(shí)間干完。總費(fèi)用為81.6元。問題三： 存在4噸，6噸，8噸三種運(yùn)輸車時(shí)的調(diào)度 若存在4噸,6噸,8噸三種,我們應(yīng)把握的原則是

18、:盡量讓8噸的車,拉遠(yuǎn)處的垃圾,遠(yuǎn)處垃圾拉得越多,以后車的空載路程就越少,而不考慮空載費(fèi)用,只把垃圾運(yùn)回垃圾處理廠,它的這部分費(fèi)用不變.同時(shí)，我們考慮到8噸,6噸,4噸的運(yùn)輸車費(fèi)用問題,故8噸的車不宜太多.我們?cè)诜治鲞^程中,發(fā)現(xiàn)主要是第15點(diǎn)比較難處理,因此8噸的車應(yīng)將這一點(diǎn)在30那條線上一并處理.而象第2點(diǎn),用6噸車單獨(dú)拉一次太浪費(fèi),應(yīng)用4噸車還有11,22這兩條線也可改用4噸車.運(yùn)營(yíng)總費(fèi)用為：2325.8 其中運(yùn)輸費(fèi)用是2213.4 空載費(fèi)用為112.4求解程序如附錄四： 表三:線路所用時(shí)間和承載垃圾量線路時(shí)間垃圾量30-29-27-20-11-0 2.3+5/67.828-26-32-2

19、5-14-7-02.2+17.936-23-33-21-22-02.1+5/6724-18-35-15-31-5-0 1.7+17.9534-17-16-2-01.45+2/3519-13-8-3-1-01.35+5/66.9512-9-01.0+1/34.110-0 0.7+1/61.56-00.7+1/61.34-00.55+1/61.2 表四：運(yùn)輸車數(shù)量8噸56噸24噸3鏟車路線：鏟車跟隨運(yùn)輸廠車行駛，先行駛到遠(yuǎn)點(diǎn)、伴隨運(yùn)輸車網(wǎng)回路行駛，鏟完一趟后就尋找該離鏟車最近的另外一條運(yùn)輸線的起始點(diǎn)（運(yùn)輸車遠(yuǎn)端），然后再跟著運(yùn)輸車行駛。5模型優(yōu)缺點(diǎn)分析然而，該問題在站點(diǎn)眾多，運(yùn)輸半徑較大的前提下，

20、缺點(diǎn)就會(huì)顯得尤為突出。首先是運(yùn)輸車載重的不足，當(dāng)運(yùn)輸車的載重不能滿足其中任一點(diǎn)的垃圾量時(shí)，模型就可能不能適用了，該模型優(yōu)點(diǎn)是算法簡(jiǎn)單容易實(shí)現(xiàn),精度特別是后兩個(gè)模型的精度不是很高.前兩問只要進(jìn)行窮舉就能得出最優(yōu)解.第三問的處理原則不算很精確,有待改進(jìn)6模型的推廣和應(yīng)用該模型可以應(yīng)用在很多方面，比如說貨物運(yùn)輸、車輛分配等。7參考文獻(xiàn) 全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽 優(yōu)秀論文匯編。中國(guó)物價(jià)出版社，2002宋兆基，徐流美等。MATLAB6.5在科學(xué)計(jì)算中的應(yīng)用。清華大學(xué)出版社，20058附錄附錄一：垃圾點(diǎn)地理坐標(biāo)數(shù)據(jù)表序號(hào) 站點(diǎn)編號(hào) 垃圾量T 坐標(biāo) (km) 序號(hào) 站點(diǎn)編號(hào) 垃圾量 T 坐標(biāo) (km) x y

21、 x y 1 1 1.50 3 2 20 15 1.40 19 9 2 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10

22、25 16 11 11 1.10 17 3 30 30 1.20 28 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 1.70 810 19 19 0.90 15 12 38380.0000附錄二【源碼】

23、 codeclearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80

24、1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,'*r')for ii=1:37 k=int2str(ii); k=strcat('P',k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(11,11);%´æ·Å11Ìõ·¾¶

25、;for i=1:20 sum=0; j1=1; s=0; m=37; i3=37; for j=1:36 if(w(2,j)+w(3,j)>s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:36 if(q>w(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(6-s

26、um)>w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=0;for u1=1:11 for u2=1:11 if jg(u1,u2)=0 n=jg(u1,u2); else continue en

27、d zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:11;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:11 for u5=1:11 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 ti

28、me 附錄三源碼clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.

29、80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;r=1:37;%plot(x,y,'*r');%for ii=1:37 % k=int2str(ii); % k=strcat('P',k); % text(x(ii),y(ii),k);%endw=r;x;y;t;a=1:11;point=30 28 36 24 34 20 19 14 22 11 31; 3 5 21 15 2 9 8 1 22 10 6;a;point(3,

30、:)=0;s=80;p=80;k=2;j1=0;j2=0;m=1;b=1:11;pai=b;pai(1,:)=0; for j=1:11 if s>=w(2,point(1,j)+w(3,point(1,j)&point(3,j)=0 s=w(2,point(1,j)+w(3,point(1,j); else continue end end j1=j; point(3,j1)=1; pai(1)=point(1,j1); while m<40 for i=1:11 if (p>=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1

31、)-w(3,point(2,j1)&point(3,i)=0 p=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1)-w(3,point(2,j1); else continue end j2=i; point(3,j2)=1; pai(k)=point(1,j2); k=k+1; end j1=j2; m=m+1; end pai 附錄三結(jié)果pai = 31 30 28 36 24 34 20 19 14 22 11 附錄四：clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 2

32、1 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,'*r')for ii=1