1、2012年“深圳杯”全國大學(xué)生數(shù)學(xué)建模夏令營承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： D 我們的參賽報(bào)名號(hào)為（如果賽

2、區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?天津農(nóng)學(xué)院 參賽隊(duì)員 (打印并簽名) ：1. 王柔玉 2. 張潤芳 3. 劉東洋 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 年 月 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2012年“深圳杯”全國大學(xué)生數(shù)學(xué)建模夏令營編 號(hào) 專 用 頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：全國評(píng)閱編號(hào)（由全國組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：打孔機(jī)生產(chǎn)效能的提高摘 要過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，過孔的加工費(fèi)用通常占制板費(fèi)用的

3、30%到40%，打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)。因此提高打孔機(jī)的生產(chǎn)效能是降低印刷線路板成本的最主要途徑。本文通過實(shí)現(xiàn)刀具轉(zhuǎn)換最優(yōu)順序的前提下，運(yùn)用蟻群算法找到最優(yōu)線路，及最短距離。使行進(jìn)成本和刀具轉(zhuǎn)換成本均達(dá)到最低，以此減少打孔機(jī)總打孔成本。問題一：單鉆頭進(jìn)行作業(yè)時(shí)，首先根據(jù)鉆頭上各個(gè)刀具的分布，結(jié)合各孔型對(duì)刀具的具體要求，經(jīng)過分析找到了刀具轉(zhuǎn)換次數(shù)最少并能完成各孔型對(duì)刀具加工次序特殊要求的換刀順序：d-c-b-a-h-g-f-e-c。然后運(yùn)用蟻群算法，在整個(gè)區(qū)域內(nèi)分別計(jì)算出十種孔型的最優(yōu)路線和最短路徑，再分別計(jì)算行進(jìn)時(shí)間，及作業(yè)成本。然后與刀具轉(zhuǎn)換時(shí)間和成本及兩孔型之間鉆頭

4、移動(dòng)時(shí)間和成本進(jìn)行匯總分析，所得最后數(shù)值則為所求。其具體對(duì)過孔加工順序按蟻群算法得出的加工順序進(jìn)行。問題二：雙鉆頭作業(yè)時(shí)，由于兩個(gè)鉆頭獨(dú)立工作，兩個(gè)鉆頭可以同時(shí)進(jìn)行打孔，也可以一個(gè)鉆頭打孔，另一個(gè)鉆頭行進(jìn)或轉(zhuǎn)換刀具。但為了避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm，為保證這一要求本文將整個(gè)電路板按過孔分布的密集程度劃分為四個(gè)區(qū)域，首先讓兩個(gè)鉆頭在一、四兩個(gè)對(duì)角線區(qū)域內(nèi)單獨(dú)工作，加工完畢后在分別轉(zhuǎn)向三、二兩個(gè)區(qū)域。換刀方案保持不變，仍然利用蟻群算法找出各個(gè)區(qū)域內(nèi)的最優(yōu)路徑和最短路線，再分別計(jì)算出行進(jìn)時(shí)間，行進(jìn)成本。最后將四個(gè)區(qū)域的總時(shí)間、總成本進(jìn)行匯總得出結(jié)果即為

5、問題二的結(jié)果。其具體對(duì)過孔加工順序一就按蟻群算法對(duì)個(gè)區(qū)域所得出的加工順序進(jìn)行。將問題一的結(jié)果與問題二的行進(jìn)成本、換刀成本、行進(jìn)時(shí)間、換刀總時(shí)間進(jìn)行比較分析，計(jì)算出生產(chǎn)效能不同。同時(shí)結(jié)合問題一、問題二的結(jié)果分析打孔機(jī)的兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。最后根據(jù)遺傳算法對(duì)整個(gè)計(jì)算進(jìn)行檢驗(yàn)、分析及總結(jié)。關(guān)鍵字： 最優(yōu)刀具轉(zhuǎn)換 蟻群算法 遺傳算法 生產(chǎn)效能提高一、問題的提出及研究意義 1.1 問題背景過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，過孔的加工費(fèi)用通常占制板費(fèi)用的30%到40%，打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)。一般打孔機(jī)上有8種刀具，a，b，c，d，e

6、，f，g，h，依次排列呈圓環(huán)狀，如圖1所示： bcdefgha圖1：某種鉆頭上8種刀具的分布情況而且8種刀具的順序固定，不能調(diào)換。在加工作業(yè)時(shí)，一種刀具使用完畢后，可以轉(zhuǎn)換使用另一種刀具。相鄰兩刀具的轉(zhuǎn)換時(shí)間是18 s，例如，由刀具a轉(zhuǎn)換到刀具b所用的時(shí)間是18s，其他情況以此類推。作業(yè)時(shí)，可以采用順時(shí)針旋轉(zhuǎn)的方式轉(zhuǎn)換刀具，例如，從刀具a轉(zhuǎn)換到刀具b；也可以采用逆時(shí)針的方式轉(zhuǎn)換刀具，例如，從刀具a轉(zhuǎn)換到刀具h(yuǎn)。將任一刀具轉(zhuǎn)換至其它刀具處，所需時(shí)間是相應(yīng)轉(zhuǎn)換時(shí)間的累加，例如，從刀具a轉(zhuǎn)換到刀具c，所需的時(shí)間是36s（采用順時(shí)針方式）。為了簡化問題，假定鉆頭的行進(jìn)速度是相同的，為180 mm/s，

7、行進(jìn)成本為0.06元/mm，刀具轉(zhuǎn)換的時(shí)間成本為7元/min。刀具在行進(jìn)過程中可以同時(shí)進(jìn)行刀具轉(zhuǎn)換，但相應(yīng)費(fèi)用不減。而孔的類型對(duì)刀具具有一定的要求，不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，有的孔型需要多種刀具及規(guī)定的加工次序來完成，如孔型C需要刀具a和刀具c，且加工次序?yàn)閍，c。表1列出了10種孔型所需加工刀具及加工次序（標(biāo)*者表示該孔型對(duì)刀具加工次序沒有限制）。表1：10種孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一塊線路板上的過孔全部加工完成后，再制作另一線路板。但在同一線路板上的過孔不要

8、求加工完畢一個(gè)孔，再加工另一個(gè)孔，即對(duì)于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可為提高打孔機(jī)效能，現(xiàn)在設(shè)計(jì)一種雙鉆頭的打孔機(jī)（每個(gè)鉆頭的形狀與單鉆頭相同），兩鉆頭可以同時(shí)作業(yè)，且作業(yè)是獨(dú)立的，即可以兩個(gè)鉆頭同時(shí)進(jìn)行打孔，也可以一個(gè)鉆頭打孔，另一個(gè)鉆頭行進(jìn)或轉(zhuǎn)換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm（稱為兩鉆頭合作間距）。為使問題簡化，可以將鉆頭看作質(zhì)點(diǎn)。1.2 需要解決的問題1.2.1 單鉆頭作業(yè)給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進(jìn)時(shí)間和作業(yè)成本。1.2.2針對(duì)附件1的數(shù)據(jù)，給出雙鉆頭作業(yè)時(shí)的最優(yōu)作業(yè)線路、

9、行進(jìn)時(shí)間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機(jī)進(jìn)行比較，其生產(chǎn)效能提高多少。1.2.3研究打孔機(jī)的兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。1.3研究意義過孔的加工費(fèi)用通常占制板費(fèi)用的30%到40%。提高打孔機(jī)的生產(chǎn)效能對(duì)降低印刷線路板成本起著至關(guān)重要的作用。二、問題分析打孔機(jī)的生產(chǎn)效能主要取決于以下幾方面：（1）單個(gè)過孔的鉆孔作業(yè)時(shí)間，這是由生產(chǎn)工藝決定，為了簡化問題，這里假定對(duì)于同一孔型鉆孔作業(yè)時(shí)間都是相同的。（2）打孔機(jī)在加工作業(yè)時(shí)，鉆頭的行進(jìn)時(shí)間。（3）針對(duì)不同孔型加工作業(yè)時(shí)，刀具的轉(zhuǎn)換時(shí)間。問題一分析：本題要求提高打孔機(jī)在傳統(tǒng)單鉆頭作業(yè)時(shí)的工作效能，即降低刀具轉(zhuǎn)換成本和鉆頭行進(jìn)成本。由

10、于不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，有的孔型需要多種刀具及規(guī)定的加工次序來完成，本題中有8種刀具，相比較于孔的兩千多坐標(biāo)來說，確定刀具的轉(zhuǎn)換順序比較簡單，所以應(yīng)先確定刀具的最短轉(zhuǎn)換順序，再運(yùn)用模型計(jì)算出最有路徑和最短路線。打孔機(jī)是打完一個(gè)電板之后再按照原來的最優(yōu)線路進(jìn)行下一個(gè)電板，所以在打完一個(gè)電板的最后一個(gè)點(diǎn)之后，鉆頭應(yīng)回到起始點(diǎn)，對(duì)于每種刀具而言，每個(gè)孔型的每個(gè)坐標(biāo)只需加工一次，然后返回到出發(fā)點(diǎn)即可。根據(jù)以上分析，該問題與旅行商問題相似，可以采用蟻群算法、遺傳算法和模擬退火算法進(jìn)行求解。由于本題的數(shù)據(jù)比較小，而蟻群算法又具有局部搜索速度快、收斂性良好的優(yōu)點(diǎn)，所以本文采用

11、蟻群算法對(duì)本問題的最優(yōu)線路和最短路徑進(jìn)行求解，用遺傳算法對(duì)蟻群算法進(jìn)行優(yōu)化和檢驗(yàn)。問題二分析：在雙鉆頭作業(yè)時(shí)，兩個(gè)鉆頭獨(dú)立工作，且為避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm，所以考慮將一塊電路板根據(jù)孔的密集程度劃分出四個(gè)不同的區(qū)域：一區(qū)（x<0,y>4x105），二區(qū)（x>0,y>4x105），三區(qū)（x<0,y<4x105），四區(qū)（x>0,y<4x105）(單位：1/100mil)。如圖四。第一個(gè)鉆頭工作路線為先打一區(qū)再換到三區(qū)工作，第二個(gè)鉆頭先打四區(qū)再打二區(qū)，使兩個(gè)鉆頭的距離始終保持大于等于3cm。每個(gè)區(qū)域的刀

12、具轉(zhuǎn)換順序與問題一相同，一就運(yùn)用蟻群算法分別計(jì)算出各個(gè)區(qū)域的最短路線和最優(yōu)路徑，再根據(jù)已知的鉆頭行進(jìn)速度180mm/s和換刀時(shí)間計(jì)算出總的時(shí)間及成本。三、模型的基本假設(shè)1、單個(gè)過孔的鉆孔作業(yè)時(shí)間，這是由生產(chǎn)工藝決定，為了簡化問題，這里假設(shè)對(duì)于同一孔型鉆孔作業(yè)時(shí)間都是相同的。2、在計(jì)算兩孔之間距離時(shí)，為了簡化問題，這里假設(shè)打孔機(jī)的鉆頭看作一個(gè)質(zhì)點(diǎn)。3、為了計(jì)算行進(jìn)費(fèi)用，需要計(jì)算行進(jìn)時(shí)間，為了簡化問題，這里假設(shè)打孔機(jī)的行進(jìn)是一個(gè)勻速運(yùn)動(dòng)。四、符號(hào)定義和說明五、模型建立與求解根據(jù)以上對(duì)問題的分析，打孔機(jī)的生產(chǎn)效能主要取決于鉆頭的行進(jìn)時(shí)間和刀具轉(zhuǎn)換時(shí)間，加工總費(fèi)用=刀具行進(jìn)費(fèi)用+刀具轉(zhuǎn)換費(fèi)用。對(duì)此，我

13、們建立優(yōu)化模型單鉆頭工作時(shí)刀具轉(zhuǎn)換順序?yàn)椋篸-c-b-a-h-g-f-e-c，成本為： 鉆頭運(yùn)行成本的計(jì)算運(yùn)用基于蟻群算法。5.1問題一模型的建立與求解5.1.1.模型原理 研究表明,螞蟻具有找到蟻巢與食物之間最短路徑的能力。這種能力是靠其在所經(jīng)過的路徑上留下一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失)來實(shí)現(xiàn)的。螞蟻在一條路上前進(jìn)時(shí)，會(huì)留下?lián)]發(fā)性信息素，后來的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上該物質(zhì)的強(qiáng)度成正比.。對(duì)于一條路徑,選擇它的螞蟻越多，則在該路徑上螞蟻所留下的信息素的強(qiáng)度就越大，而強(qiáng)度大的信息素會(huì)吸引更多的螞蟻，從而形成一種正反饋。通過這種

14、正反饋，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短路徑。5.1.2蟻群系統(tǒng)模型為模擬蟻群系統(tǒng)的尋徑方法,我們定義如下參數(shù):蟻群中螞蟻的數(shù)量；:路徑的能見度；:時(shí)刻在路徑上的信息量；為:螞蟻在本次循環(huán)中留在路徑上的信息量；:螞蟻在時(shí)刻由位置轉(zhuǎn)移到位置的概率；:軌跡的相對(duì)重要性；:能見度的相對(duì)重要性；:信息素的持久性,表示信息素的衰減度. 初始時(shí)刻,設(shè)所有路徑上的信息素都相等，(是一個(gè)常數(shù)) . 螞蟻在運(yùn)動(dòng)過程中, 根據(jù)各條路徑上的信息素的大小以一定的概率決定轉(zhuǎn)移方向, 表示為:其中是常數(shù),表示螞蟻循環(huán)一周所釋放的總信息量.表示第只螞蟻在本次循環(huán)中所走路徑的長度,它體現(xiàn)了全局范圍內(nèi)的最短路徑,能夠提高系統(tǒng)搜索的收斂速度

15、. 參數(shù)、可以用實(shí)驗(yàn)方法確定其最優(yōu)組合.停止條件可以用固定循環(huán)次數(shù)或者當(dāng)進(jìn)化趨勢(shì)不明顯時(shí)便停止計(jì)算. . 5.1.2模型的建立對(duì)于鉆頭的行進(jìn)費(fèi)用：其中，當(dāng)表示在得到的最優(yōu)路徑上；當(dāng)表示不在得到的最優(yōu)路徑上。問題一中確定刀具轉(zhuǎn)換順序?yàn)閐-c-b-a-h-g-f-e-c,然后每個(gè)刀具將需要打的點(diǎn)操作完畢后再轉(zhuǎn)換到下一個(gè)刀具，如d刀具，需要打D、G兩類孔型，將這兩類的點(diǎn)的坐標(biāo)集合在一起，然后放入蟻群算法中的城市坐標(biāo)，在matlab中運(yùn)行得出最優(yōu)路徑和最短路線，然后轉(zhuǎn)換到c刀具進(jìn)行相同的操作，然后依次按刀具運(yùn)行。對(duì)于轉(zhuǎn)換刀具時(shí)從一類刀具打出的最后一個(gè)點(diǎn)與下一個(gè)刀具的第一個(gè)點(diǎn)的距離，同樣利用運(yùn)用公式進(jìn)行

16、計(jì)算。5.1.3 模型的求解由于需要打的孔的數(shù)量相對(duì)較多，不能想像點(diǎn)的整個(gè)分布情況，所以先運(yùn)用matlab軟件做出散點(diǎn)圖分析點(diǎn)的分布，如圖2將各種刀具所需坐標(biāo)點(diǎn)集合后導(dǎo)入到蟻群算法代碼中，計(jì)算出最優(yōu)路線和最短路徑。運(yùn)行后的結(jié)果為（由于數(shù)據(jù)較多，故以b、c刀具為例）。 圖2 b刀具最短路徑優(yōu)化結(jié)果 圖3 b刀具平均路徑與最短路徑圖4 c刀具最短路徑優(yōu)化結(jié)果 圖5 b刀具平均路徑與最短路徑表1：最終最短路徑運(yùn)行結(jié)果（單位：1/100mil）刀具dcbah最短路線6.0092e+0063.8716e+0061.1399e+0071.2039e+0073.1221e+006刀具gfec最短路線3.25

17、45e+0066.8748e+0066.0012e+0068.9880e+006 表2：c刀具打孔順序（表中數(shù)字為代碼中打孔的點(diǎn)坐標(biāo)的順序號(hào)碼）677068366367374303254253252251250249248247239240241242243244245246201316242963034018419319619039419939620020419823838816916316415313714914711111511912312712813213614214414615215114514314113513112412011611214815013815411411812212

18、111711312512613013414013913312933733927427528528429329529829930230137821339921421621037938292969338382877773696132031931831731632232332432532646363328271718165384234158344155343309297300332338217400201218231109106101315255257259261262264263265267269270268266260258256868833614972353851561661571593861

19、602361673463473493483503523543563583603623643653633613593573553533513911721771811782902802892912942762731613871621682372772822923695763626066566559368757678919094837980858481645455523732505158717274899598212398211215209171175390176180342105278287288279711174389170173179341345232931494842454140393822

20、440422723022837037122540322322622927210310499321286283220401232219202333334328331281271304100102105327329335330221402203222233183189195393188475320539720820720637737619439218218718619239519119718525222115941263811101071082192630830730630531031131231338138037537343443534372314表3：b刀具打孔順序66366212027066

21、467667969670878077078677178277276078378476176278577377476376477575475575675775877327237287397437296896906846826726738182612792937767167065912312212112451324224321767467568673673774473824321141151161171191121961901951941931924124454845045095275595605114964764744854875245254934864714584604654664594534

22、164104304283863853843834074234054084094064545355344724634804734905294424364384374754895283963973983993803813603533263223052782772452302712813153253483173062722692802392192181991861851841871281291301311321261271891884328454423221776768765745727692678677685740741769591622002202212102092052042012032612

23、792822623383373354224214515415965315325304704694684674414404474463883763753873743573473162752462242472252482262492272502282512292522763002942992982973023563553543523513502021481189080463697777796543217151312141654535556578485831521531591511581571561551541491651911401341361461601671641701611471381131

24、331049186141150166197211212273274311310309222223175171174182145144181172178101941029596979899696058212519117817667677357347136976806607872271271070670570370069372641427611144841940437837035936636738237740342441743347747850651451651555456658359057956756256356456559359250548850150250359559451751851948

25、248146451250850739237936228434636539041342542642740039137236434937338939341443545037126023725923623525823425523323223128318317617717918017323866726571626864706374343531103848308751742730888913710010512513511010614214310710810910373678775313932340240143944445651049949850057055252152049455855758158058

26、661258454958557657758252352249541843442046147949753353653753853952655356157236835833631932132046269869966943232775653701198411555474577255402630473179328431667668665666681702688683492442562402572412532642662672902962912922892932681691682953343443333433323423313413303403293392852652632862872883454525

27、566016166176145985885976066136156086035895715876216266396466576546556436306256276336286346296356316246206106006025995745755455465515505445434494294153953943613693634554436456446476526616406236196096426416486506516586566386326226186116045915785693183243123032542132062142072152082163013083133073145239

28、3318748747749750746778203751504075975268757356848354260749149260572470970469569171178778873363663754754816370764969429720721714717718719716715根據(jù)以上運(yùn)行結(jié)果，又知，計(jì)算得：運(yùn)行成本為元總成本元行進(jìn)時(shí)間=996.2255/0.06/180=86.43197,換刀時(shí)間為18*9=162s,總時(shí)間=86.43197+162=248.432s5.2 問題二模型的建立與求解5.2.1 模型的建立 設(shè)計(jì)雙鉆頭打孔機(jī)，兩鉆頭可以同時(shí)作業(yè)并且兩鉆頭作業(yè)相互獨(dú)立，要使印

29、刷線路板的過孔的總費(fèi)用最小，與第一個(gè)問題模型相同，只要使兩個(gè)鉆頭行進(jìn)費(fèi)用、作業(yè)費(fèi)用之和最小，則為最優(yōu)作業(yè)方案。若鉆頭1打孔時(shí)鉆頭2打孔，記孔與孔之間的距離為5.2.1 模型的求解由于兩個(gè)鉆頭工作是相互獨(dú)立的，且合作間距不小于3cm。因此在解決雙鉆頭最優(yōu)作業(yè)方案時(shí)，我們?cè)趩毋@頭作業(yè)的基礎(chǔ)上，根據(jù)點(diǎn)的密集程度將整個(gè)電板劃分為四個(gè)區(qū)域 ，如圖6圖6 電路板四個(gè)區(qū)域 根據(jù)圖四可知過孔沒有分布在分界線上，并且一區(qū)到三區(qū)最近的點(diǎn)和四區(qū)到二區(qū)的最近的點(diǎn)的距離大于3cm，所以，人工控制鉆頭1在一區(qū)工作的同時(shí)，鉆頭2在其對(duì)角區(qū)域四區(qū)進(jìn)行打孔，以保證兩個(gè)鉆頭的距離不小于3cm。當(dāng)鉆頭1在一區(qū)工作完畢開始進(jìn)入三區(qū)，

30、鉆頭2在四區(qū)工作完畢后進(jìn)入二區(qū)，使兩鉆頭依舊在對(duì)角進(jìn)行工作。將附件1中的點(diǎn)通過matlab進(jìn)行編程篩選，將每個(gè)區(qū)域的點(diǎn)單獨(dú)存放，同樣運(yùn)用和問題一相同的蟻群算法分別運(yùn)行出各個(gè)區(qū)域的最優(yōu)路線，最短路徑，最后計(jì)算出鉆頭1和鉆頭2總的運(yùn)行成本，并求出各自的時(shí)間，較大的那個(gè)即為最終的運(yùn)行時(shí)間。運(yùn)行結(jié)如下：表4：一區(qū)運(yùn)行最短路線刀具dcbah最短路線961270125350021691001988100643380刀具gfec最短路線017039009426402084600表5：二區(qū)運(yùn)行最短路線刀具dcbah最短路線1839200111440020758002765600873430刀具gfec最短路線

31、78808021344022550002677600表6：三區(qū)運(yùn)行最短路線刀具dcbah最短路線169420088388045123003727100887980刀具gfec最短路線374820146160014170001932600表7：四區(qū)運(yùn)行最短路線刀具dcbah最短路線1480500127350027444003933400708650刀具gfec最短路線392010189500015097002121900運(yùn)用excel進(jìn)行成本的運(yùn)算，結(jié)果如下表（除去換區(qū)所用的刀具轉(zhuǎn)換時(shí)間、成本及換區(qū)行進(jìn)成本、時(shí)間）。區(qū)域行進(jìn)成本換刀成本行進(jìn)時(shí)間換刀時(shí)間成本合計(jì)時(shí)間合計(jì)三區(qū)280.007818.9

32、25.92665162305.9344187.9266一區(qū)213.46718.919.76547162232.367181.7655鉆頭1493.474837.845.69211324538.3014369.6921二區(qū)255.647918.923.6711162274.5479185.6711四區(qū)262.615918.924.31629162281.5159186.3163鉆頭2518.263837.847.98739324556.0638371.9874合計(jì)1011.73975.693.67956481094.365371.9874換區(qū)距離：類型距離類型距離一區(qū)到二區(qū)336442.2三區(qū)到

33、一區(qū)121285.8一區(qū)到三區(qū)419054.3三區(qū)到二區(qū)895228.7一區(qū)到四區(qū)431537.7三區(qū)到四區(qū)338306.9二區(qū)到一區(qū)665767.5四區(qū)到一區(qū)385366.5二區(qū)到三區(qū)620286.4四區(qū)到二區(qū)611092.5二區(qū)到四區(qū)468398.7四區(qū)到三區(qū)396803.2由上表可以看出，鉆頭1從三區(qū)到一區(qū)進(jìn)行轉(zhuǎn)換，鉆頭2從二區(qū)到四區(qū)進(jìn)行轉(zhuǎn)換的路線最短，距離為589684.5（1/100mil）成本為589684.5x0.00025x0.06=8.986792元，換區(qū)時(shí)刀具轉(zhuǎn)換成本為2x18/60x7=4.2元所以總成本=1094.365+8.986792+4.2=1107.551792

34、 元。換區(qū)行進(jìn)時(shí)間：0.660963 s，換刀時(shí)間：36s總時(shí)間=371.9874+36+0.660963=408.6484s5.2.3兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響通過計(jì)算結(jié)果顯示打孔機(jī)的兩鉆頭為避免鉆頭間的觸碰和干擾，在過孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm，這一距離對(duì)打孔機(jī)的作業(yè)路線和生產(chǎn)效能起到一點(diǎn)的制約作用。不利于打孔機(jī)的最短線路優(yōu)化，制約鉆頭走刀路線，增大作業(yè)路線行程 ，不能對(duì)提高打孔機(jī)的生產(chǎn)效能起到一個(gè)很好的輔助作用。經(jīng)過研究及生產(chǎn)實(shí)際經(jīng)驗(yàn)表明，兩鉆頭的最短間距如能小于3cm，將極大優(yōu)化打孔機(jī)的作業(yè)線路，提高生產(chǎn)效能。具體數(shù)值將結(jié)合具體刀具類型做特殊分析，

35、本文暫不做討論。六、模型的評(píng)價(jià)與改進(jìn) 結(jié)合本題實(shí)際情況，對(duì)蟻群模型進(jìn)行評(píng)價(jià)并作出改進(jìn)： 6.1優(yōu)點(diǎn) 1.根據(jù)最優(yōu)的刀具轉(zhuǎn)換順序，蟻群算法不僅能夠智能的搜索出打孔的最優(yōu)線路，還能計(jì)算出每個(gè)刀具運(yùn)行的最短路徑。 2.蟻群算法是一種基于種群的進(jìn)化算法, 具有本質(zhì)并行性, 易于并行實(shí)現(xiàn)。如在第二問中，雙鉆頭的打孔機(jī)兩鉆頭可以同時(shí)作業(yè)，且作業(yè)是獨(dú)立的。以此來進(jìn)一步提高打孔機(jī)的生產(chǎn)效能。3. 蟻群算法很容易與多種啟發(fā)式算法結(jié)合, 以改善算法的性能。雖然蟻群算法具有很強(qiáng)的全局尋優(yōu)能力, 在很多領(lǐng)域獲得了廣泛的應(yīng)用.6.2缺陷( 1) 與其他的尋優(yōu)算法相比教, 蟻群算法的搜索時(shí)間過長。( 2) 算法開始時(shí),

36、信息素的作用不明顯, 需要經(jīng)過較長的一段時(shí)間才會(huì)顯現(xiàn)出較好路徑上的信息素優(yōu)勢(shì)。( 3) 蟻群算法的執(zhí)行過程中容易出現(xiàn)停滯現(xiàn)象,不利于發(fā)現(xiàn)更好的解。6.3改進(jìn) 從本題來看，蟻群算法從在的最大缺點(diǎn)就是在搜索空間和時(shí)間性能上的矛盾, 易出現(xiàn)過早收斂于非全局最優(yōu)解以及計(jì)算時(shí)間過長，因此，該模型的改進(jìn)主要是要從其自身算法、遺傳算法與聚類思想相結(jié)合, 以克服其需要較長的計(jì)算時(shí)間、收斂速度慢等缺陷。參考文獻(xiàn)1 姜啟源，邢文訓(xùn)，謝金星，楊頂輝.大學(xué)數(shù)學(xué)實(shí)驗(yàn)，北京：清華大學(xué)出版社，2005.2楊啟帆，何勇，談之奕. 數(shù)學(xué)建模競(jìng)賽，杭州：浙江大學(xué)出版社，2005.3朱道元.數(shù)學(xué)建模案例精選，北京：科學(xué)出版社，20

37、03.4韓中庚.數(shù)學(xué)建模方法及其應(yīng)用，北京：高等教育出版社，2005.5肖人彬，陶振武.孔群加工路徑規(guī)劃問題的進(jìn)化求解 J計(jì)算機(jī)集成制造系統(tǒng),2005,11(5)：682689 6王霄PCB 數(shù)控鉆孔最佳走刀路線的建模與求解J計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2001,13(7)：590593 7姜昌華,胡幼華一種求解旅行商問題的高效混合遺傳算法J計(jì)算機(jī)工程與應(yīng)用，2004。40(22)：6770 8丁建立, 陳增強(qiáng), 袁著祉. 基于自適應(yīng)螞蟻算法的動(dòng)態(tài)最優(yōu)路由選擇J. 控制與決策, 2003, 18(6): 7512-753 9田貴超，黎明，韋雪潔.旅行商問題（TSP）的幾種求解方法J.計(jì)算機(jī)仿真

38、，2006.23（8）：153-157. 10李擎，張偉，尹怡欣，等.一種用于最優(yōu)路徑規(guī)劃的改進(jìn)遺傳算法J. 信息與控制，2006，35（4）：444-447.附錄一、蟻群算法%蟻群算法求解TSP問題的matlab程序 clear all close all clc %初始化蟻群 m=630;%蟻群中螞蟻的數(shù)量，當(dāng)m接近或等于城市個(gè)數(shù)n時(shí)，本算法可以在最少的迭代次數(shù)內(nèi)找到最優(yōu)解 C=;%城市的坐標(biāo)矩陣 Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動(dòng)的撥數(shù)（每撥螞蟻的數(shù)量當(dāng)然都是m） alpha=1;%螞蟻在運(yùn)動(dòng)過程中所積累信息（即信息素）在螞蟻選擇路徑時(shí)的相對(duì)重要程度，a

39、lpha過大時(shí)，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象 beta=5;%啟發(fā)式因子在螞蟻選擇路徑時(shí)的相對(duì)重要程度 rho=0.5;%0<rho<1,表示路徑上信息素的衰減系數(shù)（亦稱揮發(fā)系數(shù)、蒸發(fā)系數(shù)），1-rho表示信息素的持久性系數(shù) Q=100;%螞蟻釋放的信息素量，對(duì)本算法的性能影響不大 %變量初始化 n=size(C,1);%表示TSP問題的規(guī)模，亦即城市的數(shù)量 D=ones(n,n);%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離 for i=1:n for j=1:n if i<j D(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)

40、2); end D(j,i)=D(i,j); end end eta=1./D;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù) pheromone=ones(n,n);%信息素矩陣,這里假設(shè)任何兩個(gè)城市之間路徑上的初始信息素都為1 tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計(jì)算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過的路徑和路徑的長度 Nc=0;%循環(huán)次數(shù)計(jì)數(shù)器 routh_best=zeros(Nc_max,n);%各次循環(huán)的最短路徑 length_best=ones(Nc_max,1);%各次循環(huán)最短路徑

41、的長度 length_average=ones(Nc_max,1);%各次循環(huán)所有路徑的平均長度 while Nc<Nc_max %將m只螞蟻放在n個(gè)城市上 rand_position=; for i=1:ceil(m/n) rand_position=rand_position,randperm(n); end tabu_list(:,1)=(rand_position(1:m)'%將螞蟻放在城市上之后的禁忌表，第i行表示第i只螞蟻，第i行第一列元素表示第i只螞蟻所在的初始城市 %m只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游 for j=2:n for i=1:

42、m city_visited=tabu_list(i,1:(j-1);%已訪問的城市 city_remained=zeros(1,(n-j+1);%待訪問的城市 probability=city_remained;%待訪問城市的訪問概率 cr=1; for k=1:n%for循環(huán)用于求待訪問的城市。比如如果城市個(gè)數(shù)是5，而已訪問的城市city_visited=2 4,則經(jīng)過此for循環(huán)后city_remanied=1 3 5 if length(find(city_visited=k)=0 city_remained(cr)=k; cr=cr+1; end end %狀態(tài)轉(zhuǎn)移規(guī)則* q0=0.

43、5; if rand>q0 for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; position=find(probability=max(probability); to_visit=city_remained(position(1); end else for k=1:length(city_remained) probability(k)=(pheromo

44、ne(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; end probability=probability/sum(probability); pcum=cumsum(probability); select=find(pcum>=rand); to_visit=city_remained(select(1); end tabu_list(i,j)=to_visit; %* end end if Nc>0 tabu_list(1,:)=routh_best(N

45、c,:);%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來，保證上一代中的最適應(yīng)個(gè)體的信息不會(huì)丟失 end %記錄本次循環(huán)的最佳路線 total_length=zeros(m,1);%m只螞蟻在本次循環(huán)中分別所走過的路徑長度 for i=1:m r=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所走的路徑 for j=1:(n-1) total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只螞蟻本次循環(huán)中從起點(diǎn)城市到終點(diǎn)城市所走過的路徑長度 end total_length(i)=total_length(i)+D(r(1),r(n);%最終得到第i只螞蟻在本次循環(huán)中所走過的路徑長度 end length_best(Nc+1)=min(total_length);%把m只螞蟻在本次循環(huán)中所走路徑長度的最小值作為本次循環(huán)中最短路徑的長度 position=find(total_length=length_best(Nc+1);%找到最短路徑的位置，即最短路徑是第幾只螞蟻或哪幾只