建模機(jī)器人避路障問(wèn)題

1、建模機(jī)器人避路障問(wèn)題機(jī)器人避障問(wèn)題摘要：本文根據(jù)題目要求，主要研究了在一個(gè)區(qū)域內(nèi)有障礙物的最短路徑問(wèn)題 依題意我們可以認(rèn)為最短路徑一定是由線和最小圓弧組成，圓心在障礙物的頂 點(diǎn)。對(duì)于問(wèn)題一首先討論由O到A的距離，為了到達(dá)目標(biāo)點(diǎn)，我們建立了圓線模型。將路線 分為兩部分：一部分是平面上的自然最短路徑(即直線段)，另一部分是限定區(qū)域的部分邊界的半徑至少十個(gè)單位以外的圓弧，得到其路徑長(zhǎng)度為L(zhǎng)r yjc r r ,并用MATLA程序解得最短路徑471.0372對(duì)于O到B的距離問(wèn)題，為了到達(dá)目標(biāo)點(diǎn)，我們需要建立圓與點(diǎn)圓模型，其 中由于圓與圓之間的不同的位置關(guān)系，又可以分為同向相切與異向相切，同向相切時(shí)LJ

2、br2Jc2r21r 2 qq，異向相切時(shí)LJbr2Jc2r2r 1r 2彳(罟)2r2。由MATLA程序解得最短路徑869.8523。對(duì)于O到C,與前者的區(qū)別是障礙物大圓視為半徑較大的轉(zhuǎn)折弧，為了到達(dá) 目標(biāo)點(diǎn)，依舊建立圓圓結(jié)構(gòu)與線圓結(jié)構(gòu)模型，經(jīng)MATLA程序解得最短路徑為1011.3。對(duì)于OABC的路徑問(wèn)題，除了用了上述提到的圓圓，線圓結(jié)構(gòu)外，還建立了圓心偏移的模型(即點(diǎn)ABC在相對(duì)應(yīng)的弧上)，A點(diǎn)偏以后的坐標(biāo)為(290.9,304.1)，B點(diǎn)偏以后的坐標(biāo)為(108.23,694.32)，C點(diǎn)偏以后的坐標(biāo)為(707.26,633.12)，將 OABC分為兩部分，一部分為 OABCN 730,

3、520 )的距離,另一部分為由N回到O的距離，兩部分結(jié)果之和即為所求路徑。OABC的距離1.7691e+003,N 到C為880.7744，總長(zhǎng)為 2649,6744對(duì)于問(wèn)題二，我們將路線問(wèn)題轉(zhuǎn)化為規(guī)劃問(wèn)題，求的最短時(shí)間，目標(biāo)函數(shù) 為T AC BD rVow由 LINGOt最短時(shí)間為 94.22822，切點(diǎn)坐標(biāo)(69.80,211.98 )(77.75,220.14) 圓心(82.14,207.92 )。關(guān)鍵詞：最短路徑最優(yōu)化模型避障路徑規(guī)劃問(wèn)題線圓結(jié)構(gòu)一問(wèn)題重述機(jī)器人從原點(diǎn)C出發(fā)且他只能在圖中所給出的800*800正方平面場(chǎng)景范圍內(nèi) 活動(dòng)。且平面場(chǎng)景范圍內(nèi)的12個(gè)不同形狀的區(qū)域是機(jī)器人不能與

4、之發(fā)生碰撞的 障礙物。在平面場(chǎng)景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)(要求目標(biāo)點(diǎn) 與障礙物的距離至少超過(guò)10個(gè)單位)。規(guī)定機(jī)器人的行走路徑由直線段和圓弧 組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線 路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè) 圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走 線路與障礙物間的最近距離為10個(gè)單位，否則機(jī)器人將無(wú)法完成行走。機(jī)器人直線行走的最大速度為V。5個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎 速度為v v( )V，其中 是轉(zhuǎn)彎半徑。1 e請(qǐng)建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和

5、最短時(shí)間路徑的 數(shù)學(xué)模型。對(duì) 4個(gè)點(diǎn) 0(0, 0)，A(300, 300) ，B(100, 700)，C(700, 640)，具體 計(jì)算：(1)機(jī)器人從0(0, 0)出發(fā)，OA、OB、OC和OA B-C-O勺最短路 徑。 機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑平面場(chǎng)景圖二問(wèn)題分析1、問(wèn)題一中要求定點(diǎn)機(jī)器人按照一定的行走規(guī)則繞過(guò)障礙物到達(dá)目標(biāo)點(diǎn)的 最短路徑，由于機(jī)器人不能折線拐彎，所以拐彎處必然是一圓弧，我們采用線 圓結(jié)構(gòu)的方法建立模型，用這種方法尋找可能的最短路徑，然后采用窮舉法列 出0到目標(biāo)點(diǎn)的最短路徑。這其中我們不能僅僅考慮是經(jīng)過(guò)障礙物拐點(diǎn)的問(wèn)題（例如由OABCO路徑的計(jì)算）

6、，也應(yīng)該考慮經(jīng)過(guò)路徑中的目標(biāo)點(diǎn)處轉(zhuǎn)彎的問(wèn)題， 這是簡(jiǎn)單的線圓結(jié)構(gòu)就不能解決這種問(wèn)題，我們?cè)诠拯c(diǎn)及途中目標(biāo)點(diǎn)處采用最 小轉(zhuǎn)彎半徑的形式，使機(jī)器人能夠沿直線通過(guò)途中的目標(biāo)點(diǎn)，然后建立優(yōu)化模 型對(duì)此問(wèn)題進(jìn)行優(yōu)化，最終求得最短路徑。2、問(wèn)題二中涉及到機(jī)器人的速度問(wèn)題， 這樣就不能以最短路徑來(lái)進(jìn)行計(jì)算, 因?yàn)楣諒澦俣扰c直線速度不相同，這時(shí)就需要在加入速度因素，來(lái)求得最佳結(jié) 果。三模型假設(shè)1假設(shè)機(jī)器人能夠抽象成點(diǎn)來(lái)處理。2假設(shè)機(jī)器人在直線上或弧上均勻速行走四符號(hào)說(shuō)明付號(hào)符號(hào)含義L出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑長(zhǎng)度r轉(zhuǎn)彎半徑R經(jīng)過(guò)障礙物圓2處的轉(zhuǎn)彎半徑五模型的建立與求解我們?nèi)菀椎弥?，起點(diǎn)到目標(biāo)點(diǎn)無(wú)論中間障礙物有多少，

7、最短路徑都應(yīng)該是 若干個(gè)線圓結(jié)構(gòu)組成。在本題中存在障礙物的狀況，我們易知，在求兩點(diǎn)之間 的最短路徑中的拐彎半徑我們應(yīng)該按照最小的轉(zhuǎn)彎半徑來(lái)計(jì)算才能達(dá)到最優(yōu)， 所以我們理解為在拐點(diǎn)處的危險(xiǎn)區(qū)域是一個(gè)半徑為10的圓弧。以下圖為例,1）點(diǎn)圓模型如上圖，設(shè)A （錯(cuò)誤！未找到引用源。為起點(diǎn)，B （錯(cuò)誤！未找到引用源。為 目標(biāo)點(diǎn)，C （錯(cuò)誤！未找到引用源。和 D （錯(cuò)誤！未找到引用源。分別為機(jī)器人 經(jīng)過(guò)拐點(diǎn)分別于隔離危險(xiǎn)線拐角小圓弧的切點(diǎn)，圓心為（錯(cuò)誤！未找到引用源。， 圓的半徑為r，AB的長(zhǎng)度為a，AO的長(zhǎng)度為b，B0的長(zhǎng)度為c,角度 AOB=g 誤！未找到引用源。, AOC二錯(cuò)誤！未找到引用源。,BO

8、D=錯(cuò)誤！未找到 引用源。，COD.求A錯(cuò)誤！未找到引用源。B的長(zhǎng)度，設(shè)為L(zhǎng).解法如下：如上圖可得有以下關(guān)系：a,(X2X1)2(y2Yi)2b、(X5X1)2(YsYi)2c.(X5X2)2(ysY2)2在AOB中：,2 2 2 arccos(-c )2bc在 Rt AOC : 在Rt AOC中:所以：從而可得：r=arccos-barccos cLr我們就可以這樣認(rèn)為，起點(diǎn)到目標(biāo)點(diǎn)無(wú)論中間障礙物有多少，最短路徑都應(yīng)該 是若干個(gè)點(diǎn)圓結(jié)構(gòu)所組成。在本題中存在障礙物的狀況，且障礙物在拐點(diǎn)處的 危險(xiǎn)區(qū)域是一個(gè)半徑為10的圓弧，所以結(jié)合上述結(jié)論，我們易知，求兩點(diǎn)之間 的最短路徑中的轉(zhuǎn)彎半徑我們應(yīng)該按

9、照最小的轉(zhuǎn)彎半徑來(lái)算才能達(dá)到最優(yōu)。2）線圓模型而對(duì)于下圖兩種情況我們不能直接采用線圓的結(jié)構(gòu)來(lái)解決，需要做簡(jiǎn)單的變 換。情況一（同向）：這里我們依然設(shè)圓心坐標(biāo)分別為 0（洛,力）和O（X2, y2）,半徑均為r，這樣我們可以得到：此段路徑就是由兩段狐與兩段直線的組合加圓心距的總長(zhǎng)。這樣我們 就可以利用1）中的方法，先求A到E,再求D到B,最后減去DE的長(zhǎng)度，這樣 分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，我們同樣可以按照此種方法分解。情況二（反向）：我們假設(shè)兩圓心坐標(biāo)分別為O（xi, yi）和0 （X2, y2）,半徑均為r， M點(diǎn)坐標(biāo)為 （X3, y3），那么我們很容易可以求得：M點(diǎn)坐標(biāo)X3X

10、X22y % y2y3 V利用M將圖上分解成兩個(gè)線圓結(jié)構(gòu)，利用上述方法進(jìn)行計(jì)算，易得出結(jié)果。3）圓心偏移模型在處理OAEC路徑中，由于需要使ABC處在路徑上，所以尋找所對(duì)應(yīng)弧的 圓心，建立模型R如圖所示，E為0102的中點(diǎn)，圖中的E為題中的ABC 01為各點(diǎn)所在弧的圓心， 利用LINGO找出使點(diǎn)落在最短路徑上所對(duì)應(yīng)的圓心，利用此圓心為拐點(diǎn)，用上 述的方法進(jìn)行計(jì)算。問(wèn)題一一、以下給出了機(jī)器人到個(gè)目標(biāo)點(diǎn)的可能路徑的最短路徑：如下圖就是機(jī)器人由0到目標(biāo)點(diǎn)的最短路線1) 0到目標(biāo)點(diǎn)A的最短路徑求解，通過(guò)計(jì)算，機(jī)器人從障礙物 5的上方走的 最短路徑大于機(jī)器人從障礙物 5下方走的最優(yōu)路徑，機(jī)器人行走的最優(yōu)

11、路線的 可能性已經(jīng)列出，附錄中給出兩種方案的求解結(jié)果。最小結(jié)果對(duì)應(yīng)的行走路路線乃是黑線所示，就是0到A的最短路徑471.0372。8009B86002400632005200600S(M)6A2005200600S(M)11:4004002 ） O到目標(biāo)點(diǎn)B的最短路徑求解，我們?cè)诟戒浿薪o出三種路徑的求解過(guò)程, 分別為：（1）由0路過(guò)障礙物5,8到達(dá)B,如圖中虛線所示（2）由0路過(guò)障礙物6的上端，至V 7,8最后到達(dá)B點(diǎn)，如圖中黑實(shí)線所示（3）由0路過(guò)障礙物6的下端，至V 7,8最后到達(dá)B點(diǎn)，圖中間隔線所示。 附錄中給出三種方案的結(jié)果，最終比較得到最短路徑為路徑（2）即圖中黑實(shí)線所示路徑長(zhǎng)度為

12、869.8523。3） O到目標(biāo)點(diǎn)C的最短路徑求解，我們?cè)诟戒浿薪o出三種路徑的求解過(guò)程， 分別為：（1）由0路過(guò)障礙物5的上端,3,2,11到達(dá)C,黑線所示；（2）由0路過(guò)障礙物5的下端，至V 3,2,11最后到達(dá)C點(diǎn)，如圖中虛線所示。 由附錄中給出的結(jié)果，最終比較得到最短路徑為路徑（1 ），圖中黑實(shí)線所示，路徑長(zhǎng)度為1.0113e+003。800B94002004) OABC的最短路徑求解，通過(guò)計(jì)算 OA,OC,OB我們?nèi)菀椎贸鯫ABC的最短 路徑如下圖所標(biāo)，求解過(guò)程有兩部分組成，先計(jì)算由 O到N點(diǎn)的距離，再求N到O 點(diǎn)的距離，最終結(jié)果為二者之和，結(jié)果為 2649,6744。10c60011

13、26r31258400200問(wèn)題二設(shè)目標(biāo)函數(shù)為VoViD Xi,yi Cgy ）,O（Xo,y。）0x180;0 y1240;80x2300;210y2300;v05; v1v10 0.1* 2 eBD . X12 y2 ; AC22.300 x2300 y2 ;cBOAOBO AO AB2 a cos a cos a cos;由LINGO可得出所求， 最短時(shí)間為94.22822，切點(diǎn)坐標(biāo) (69.80,211.98 ) (77.75,220.14 )圓心(82.14,207.92 )。六、模型評(píng)價(jià)模型優(yōu)點(diǎn)、模型優(yōu)化后用解析幾何，三角形中各個(gè)之間的關(guān)系進(jìn)行求解，精確度較2、模型簡(jiǎn)單易懂，便于實(shí)

14、際檢驗(yàn)及應(yīng)用。3、模型缺陷、此模型適于全局規(guī)劃，獲得精確解卻失去了效率。2、在障礙物較多時(shí)，且形狀不規(guī)則時(shí)，模型需要進(jìn)一步改進(jìn)。3 、在程序設(shè)計(jì)時(shí)，較復(fù)雜，需要繁瑣的編輯過(guò)程。七、參考文獻(xiàn)【1】韓新社，高等數(shù)學(xué)，合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社2009.7【2】姜啟源，數(shù)學(xué)模型M，北京：高等教育出版社，2003.【3】謝金星 薛毅，優(yōu)化建模與LINGO，北京：清華大學(xué)出版社，2005年【4】劉來(lái)福 曾文藝，數(shù)學(xué)模型與數(shù)學(xué)建模，北京：北京師范大學(xué)出版社2003.八、附錄附錄一：?jiǎn)栴}一中用matlab解一 OA長(zhǎng)度求解1) %求解一次轉(zhuǎn)彎所經(jīng)路線總長(zhǎng)1 %O初始點(diǎn)E:轉(zhuǎn)彎圓弧圓心A:到達(dá)點(diǎn)fun ct

15、i onresult=z on gcha ng(O,E,A,r)0E=sqrt(0(1)-E(1)F2+( O( 2)-E(2)A2);AE=sqrt(A(1)-E(1)A2+(A (2)七(2)八2);0A=sqrt(0(1)-A(1)F2+(0 (2)-A(2)A2);alpha1=acos(OEA2+AEA2-OAA2)/(2*AE*OE);alpha2=acos(r/AE);alpha3=acos(r/OE);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4 為轉(zhuǎn)彎圓心角result=sqrt(AEA2-rA2)+sqrt(OEA2-rA2)+r*alp

16、ha4;將(0,0 ), (80,210 ), (300 , 300 )代入 求得長(zhǎng)度為ans =471.03722 %0初始點(diǎn)F:轉(zhuǎn)彎圓弧圓心A:到達(dá)點(diǎn)fun cti onresult=z on gcha ng(O,E,A,r)0E=sqrt(0(1)-F(1)A2+( 0( 2)-F(2)F2);AF=sqrt(A(1)-F(1)A2+(A (2)-F(2)F2);0A=sqrt(0(1)-A(1)A2+(0 (2)-A(2)A2);alpha仁acos(0FA2+AFA2-0AA2)/(2*AF*0F);alpha2=acos(r/AF);alpha3=acos(r/0F);alpha4

17、=2*pi-alpha1-alpha2-alpha3;%alpha4 為轉(zhuǎn)彎圓心角result=sqrt(AEA2-rA2)+sqrt(0EA2-rA2)+r*alpha4;將(0,0)，( 230,60)，( 300，300 )代入 求得長(zhǎng)度為ans =498.42592) 計(jì)算0B路徑1%0初始點(diǎn) E,F,G,H,D :轉(zhuǎn)彎圓弧圓心M,N:為距離中點(diǎn)B:到達(dá)點(diǎn)fun ctio nresult=zo ngcha ng(0,E,F,G,H,D,M,N,B,r)0E=sqrt(0(1)-E(1)A2+( 0( 2)七(2)八2);0F=sqrt(0(1)-F(1)A2+( 0( 2)-F(2)F

18、2);EF=sqrt(E(1)-F(1)A2+(E (2)-F (2)八2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);ME=sqrt(M(1)-E(1)A2+( M( 2)-E(2)F2);MG=sqrt(M(1)-G(1)A2+( M( 2)-G(2)F2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)A2);GN=sqrt(G(1)-N(1)F2+(G (2)-N(2)F2);MH=sqrt(M(1)-H(1)A2+( M( 2)-H(2)F2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);BN=sqrt(B(1)

19、-N(1)A2+(B (2)-N(2)A2);DN=sqrt(D(1)-N(1)A2+(D (2)-N(2)A2);BD=sqrt(B-D(1)F2+(B (2)-D(2)F2);alpha仁acos(OEA2+EFA2-OFA2)/(2*OE*EF);alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+MFA2-MEA2)/(2*EF*MF);alpha5=acos(r/MF);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(MGA2+GHA2-MHA2)/(2*MG*GH);alpha

20、8=acos(r/MG);alpha9=1.5*pi-alpha7-alpha8;alpha10=acos(N 屮 2+GHA2-GNA2)/(2*NH*GH);alpha11=acos(r/NH);alpha12=1.5*pi-alpha10-alpha11;alpha13=acos(BDA2+DNA2-BNA2)/(2*BD*DN);alpha14=acos(r/BD);alpha15=acos(r/DN);alpha16=2*pi-alpha13-alpha14-alpha15;TS1= sqrt(OEA2-rA2);TS2=EF;TS3=sqrt(MFA2-rA2);TS4=GH;TS

21、5=sqrt(NHA2-rA2);TS6=sqrt(DNA2-rA2);TS7=sqrt(BDA2-rA2);S1S1hu=r*alpha3;S1S2hu=r*alpha6;S1S3hu=r*alpha9;S1S4hu=r*alpha12;S1S5hu=r*alpha16;result=TS1+TS2+2*TS3+TS4+TS5+TS6+TS7+S1S2hu+S1S4hu+S1S3hu+S1S1hu+S1S5hu;將0,0,160,300,150,435,220,470,220,530,150,600,185,452.5,175,565,100,700,10)代入可求得ans =869.852

22、3 2%O初始點(diǎn)E F:轉(zhuǎn)彎圓弧圓心B:到達(dá)點(diǎn)fun cti onresult=z on gcha ng(O,E,F,B,r)OE=sqrt(O(1)-E(1)F2+( O(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+( O( 2)-F(2)F2);FE=sqrt(F(1)-E(1)A2+(F (2)-E (2)八2);FB=sqrt(F(1)-B(1)A2+(F (2)-B(2)A2);BE=sqrt(B(1)-E(1)A2+(B (2)七(2)八2);alpha仁acos(OEA2+FEA2-OFA2)/(2*OE*FE); alpha2=acos(r/OE);alpha

23、3=1.5*pi-alpha1-alpha2;alpha4=acos(FBA2+FEA2-BEA2)/(2*FB*FE); alpha5=acos(r/FB);alpha6=1.5*pi-alpha4-alpha5;TS1= sqrt(OEA2-rA2);S2W=sqrt(FBA2-rA2);S1S2hu=r*alpha3;S3W=FES1S3hu=r*alpha6; result=TS1+S2W+S1S2hu+S3W+S1S3hu;代入將(0,0,230,60,270,680,100,700,10)可求的ans =1.0584e+0033%O初始點(diǎn) E,F,G,H,D : 轉(zhuǎn)彎圓弧圓心M,N

24、:為距離中點(diǎn) B:到達(dá)點(diǎn)fun ctio nresult=zo ngcha ng(O,E,F,G,H,M,N,B,r)OE=sqrt(O(1)-E(1)A2+( O( 2)-E(2)F2);OM=sqrt(O(1)-M(1)A2+(O (2)-M(2)F2);ME=sqrt(M(1)-E(1)A2+( M( 2)-E(2)F2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);FG=sqrt(F(1)-G(1)A2+(F (2)-G(2)A2);NF=sqrt(N(1)-F(1)A2+( N( 2)-F(2)F2);NG=sqrt(N(1)-G(1)A2+(N (2)-

25、G(2)A2);MG=sqrt(M(1)-G(1)A2+( M( 2)-G(2)F2);BN=sqrt(B(1)-N(1)A2+(B (2)-N(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);BH=sqrt(B-H(1)F2+(B (2)-H(2)A2);EF=sqrt(E(1)-F(1)F2+(E (2)-F (2)八2);GH=sqrt(G(1)-H(1)A2+(G (2)-H(2)A2);alpha仁acos(OEA2+MEA2-OMA2)/(2*OE*ME); alpha2=acos(r/OE);alpha3=acos(r/ME);alpha4=2*

26、pi-alpha1-alpha2-alpha3;alpha5=acos(FGA2+MFA2-MGA2)/(2*FG*MF);alpha6=acos(r/MF);alpha7=1.5*pi-alpha5-alpha6;alpha8=acos(FGA2+NGA2-NFA2)/(2*FG*NG);alpha9=acos(r/NG);alpha10=1.5*pi-alpha8-alpha9;alpha11=acos(NHA2+BHA2-BNA2)/(2*NH*BH);alpha12=acos(r/NH);alpha13=acos(r/BH);alpha14=2*pi-alpha11-alpha12-a

27、lpha13;TS1= sqrt(OEA2-rA2);S1W=0.5*EF;S2W=0.5*GH;TS2=sqrt(S1WA2-rA2);TS3=sqrt(S1WA2-rA2);TS4=FG;TS5=sqrt(S2WA2-rA2);TS6=sqrt(BNA2-rA2);S1Shu=r*alpha4;S2Shu=r*alpha7;S3Shu=r*alpha10;S4Shu=r*alpha14;result=TS1+TS2+TS3+TS4+2*TS5+TS6+S1Shu+S2Shu+S3Shu+S4Shu; 將(0,0,230,60,235,600,220,470,220,530,150,600,

28、185,565,100,700,10)代入可求得ans =1.2170e+0033) 計(jì)算OC路徑1%O初始點(diǎn) E,F,G,H,D :轉(zhuǎn)彎圓弧圓心M,N:為距離中點(diǎn) C:到達(dá)點(diǎn)fun ctio nresult=zo ngcha ng(O,E,F,G,H,D,M,N,C,r,R)0E=sqrt(0(1)-E(1)F2+( 0(2)-E(2)A2);0M=sqrt(0(1)-M(1)F2+(0 (2)-M(2)F2);EM=sqrt(E(1)-M(1)A2+(E (2)-M(2)F2);MF=sqrt(M(1)-F(1)A2+( M( 2)-F(2)F2);FN=sqrt(F(1)-N(1)F2+

29、(F (2)-N(2)F2);MN=sqrt(M(1)-N(1)A2+( M( 2)-N(2)F2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)A2+(G (2)-N(2)A2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C-D(1)F2+(C (2)-D(2)F2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁a

30、cos(0EA2+EMA2-0MA2)/(2*0E*EM); alpha2=acos(r/0E);alpha3=acos(r/EM);alpha4=2*pi-alpha1-alpha2-alpha3;alpha5=acos(FNA2+MFA2-MNA2)/(2*FN*MF);alpha6=acos(r/MF);alpha7=acos(r/FN);alpha8=2*pi-alpha5-alpha6-alpha7;alpha9=acos(GNA2+GHA2-NHA2)/(2*GN*GH);alpha10=acos(R/GN);alpha11=acos(R-r)/GH);alpha12=2*pi-a

31、lpha9-alpha10-alpha11;alpha13=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH);alpha14=pi-alpha11;alpha15=1.5*pi-alpha14-alpha13;alpha16=acos(CDA2+DHA2-CHA2)/(2*CD*DH);alpha17=acos(r/CD);alpha18=1.5*pi-alpha16-alpha17;TS1= sqrt(0EA2-rA2);TS2=2*sqrt(EMA2-rA2);TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2)TS4=sqrt(G 屮 2-(R-rF2

32、);TS5=DH;TS6=sqrt(CDA2-rA2);S1S1hu=r*alpha4;S1S2hu=r*alpha8;S1S3hu=r*alpha15;S1S4hu=R*alpha12;S1S5hu=r*alpha18;result=TS1+TS2+TS5+TS6+S1S1hu+S1S2hu+S1S3hu+S1S5hu+TS4+S1S4hu+TS3+TS7;將(0,0,230,60,400,330,550,450,720,520,720,600,代入315,195,416.67,343.33,700,640,10,80)可求得ans =1.1444e+0032%O初始點(diǎn) E,F,G,H,D

33、:轉(zhuǎn)彎圓弧圓心N:為距離中點(diǎn) C:到達(dá)點(diǎn)fun ctio nresult=zo ngcha ng(O,E,F,G,H,D,N,C,r,R)OE=sqrt(O(1)-E(1)A2+( 0(2)-E(2)A2);OF=sqrt(O(1)-F(1)A2+( 0(2)-F(2)F2);EF=sqrt(E(1)-F(1)A2+(E (2)-F (2)八2);EN=sqrt(E(1)-N(1)A2+(E (2)-N(2)F2);FN=sqrt(F(1)-N(1)A2+(F (2)-N(2)A2);GH=sqrt(G(1)-H(1)A2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)A2+

34、(G (2)-N(2)F2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)A2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C(1)-D(1)A2+(C (2)-D(2)A2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁acos(OEA2+EFA2-OFA2)/(2*OE*EF); alpha2=acos(r/OE);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+FNA2-ENA2

35、)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5; alpha7=acos(GNA2+GHA2-NHA2)/(2*GN*GH); alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH); alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12; alpha14=acos(CDA2+DHA2-CHA2)/(2*CD*DH

36、); alpha15=acos(r/CD);alpha16=1.5*pi-alpha14-alpha15;TS1= sqrt(OEA2-rA2);TS2=EF;TS3=sqrt(FNA2-rA2);TS7=sqrt(GNA2-RA2);TS4=sqrt(G 屮 2-(R-rF2);TS5=DH;TS6=sqrt(CDA2-rA2);S1S1hu=r*alpha3;S1S2hu=r*alpha6;S1S3hu=r*alpha13;S1S4hu=R*alpha10;S1S5hu=r*alpha16;result=TS1+TS2+TS5+TS6+S1S1hu+S1S2hu+S1S3hu+S1S5hu

37、+TS4+S1S4hu+TS3將(0,0,80,210,400,330,550,450,720,520,720,600,416.67,343.33,700,640,10,80)代入可求得ans =1.0113e+003所以應(yīng)采取2路線3)計(jì)算OABC路徑將此路線分為兩段進(jìn)行計(jì)算之前 需要找到可以使ABC落于圓上的圓心坐標(biāo) 使用LINGO軟件進(jìn)行最優(yōu)化處理輸入Min=sqrt (x-80)A2+(y-210)A2)+sqrt(x-220)A2+(y-530)A2);(x-300)A2+(y-300)A2=100;可得Local optimal solution found.Objective v

38、alue:467.6803Exte nded solver steps:5Total solver iteratio ns:105VariableValueReducedCostX290.88340.000000Y304.10950.000000Row Slackor Surplus DualPrice1 467.6803 -1.0000002 0.000000 0.6650490E-01再次輸入Min=sqrt(x-150)A2+(y-600)A2)+sqrt(x-370)A2+(y-680)A2);5(x-100)A2+(y-700)A2=100;可得Local optimal solut

39、ion found.Objective value:Exte nded solver steps:Total solver iteratio ns:Variable ValueCostX0.000000Y0.000000Row SlackPrice1-1.00000020.8527221E-01最后輸入min =sqrt (x-670)A2+(y-730F2)+J(x-700)A2+(y-640)A2=100;可得 Local optimal soluti on found.Objective value:Exte nded solver steps:365.31625133Reduced10

40、8.2292694.3184or Surplus Dual365.31620.000000sqrt (x-720)A2+(y-600)A2)139.2839Total solver iteratio ns:91VariableValue ReducedCostX707.26030.000000Y633.12330.000000Row Slackor Surplus DualPrice1 139.2839 -1.0000002 0.000000 0.000000所以取得三個(gè)坐標(biāo)(290.9 , 304.1) ,(108.23694.32)(707.26633.12)第一部分長(zhǎng)度輸入%初始值cle

41、ar allclcA= 0 0 0;80 210 0;290.9 304.1 2;220 530 1;150 600 2;108.23 694.32 1;270 680 1;370 680 2;430 680 1;540 730 2;670 730 1;707.26 633.12 2;720 600 2;720 530 3;%230 60 0;%410 100 1;%500 200 2;%720 520 2;%720 600 1;%700 640 3;r=10;m, n=size(A);i=1;while i=m-2p仁 A(i,1:2);p2=A(i+1,1:2);p3=A(i+2,1:2)

42、;p12=norm(p1-p2);p23=norm(p2-p3);p13=norm(p1-p3);alpha3=acos(p12A2+p23A2-p13A2)/(2*p12*p23); if i=1alpha仁acos(10/p12);L1= p12*si n(al phal);endif A(i+2,3)=1alpha2=pi/2; sita=2*pi-alpha1-alpha2-alpha3;L2=p23+10*sita;%外切圓-同側(cè)elseif A(i+2,3)=2alpha2=acos(2*r/p23);%內(nèi)切圓-兩側(cè)sita=2*pi-alpha1-alpha2-alpha3;L2

43、=r*sita+p23*si n(al pha2);else alpha2=acos(r/p23);%點(diǎn)sita=2*pi-alpha1-alpha2-alpha3;L2=p23*si n(al pha2)+r*sita;endL=L1+L2;L仁L;alpha仁alpha2;i=i+1;endL可得結(jié)果L =1.7691e+003第二部分輸入 functionresult=zongchang(O,E,F,G,H,D,N,C,r,R)0E=sqrt(0(1)-E(1)F2+( 0(2)-E(2)A2);0F=sqrt(0(1)-F(1)F2+( 0(2)-F(2)F2);EF=sqrt(E(1

44、)-F(1)A2+(E (2)-F (2)八2);EN=sqrt(E(1)-N(1)A2+(E (2)-N(2)F2);FN=sqrt(F(1)-N(1)A2+(F (2)-N(2)A2);GH=sqrt(G(1)-H(1)F2+(G (2)-H(2)F2);GN=sqrt(G(1)-N(1)F2+(G (2)-N(2)F2);DH=sqrt(D(1)-H(1)A2+(D (2)-H(2)F2);NH=sqrt(N(1)-H(1)A2+(N (2)-H(2)A2);CD=sqrt(C-D(1)F2+(C (2)-D(2)F2);CH=sqrt(C(1)-H(1)A2+(C (2)-H(2)A2

45、);GD=sqrt(G(1)-D(1)A2+(G (2)-D(2)A2);alpha仁acos(0EA2+EFA2-0FA2)/(2*0E*EF);alpha2=acos(r/0E);alpha3=1.5*pi-alpha1-alpha2;alpha4=acos(EFA2+FNA2-ENA2)/(2*EF*FN);alpha5=acos(r/FN);alpha6=1.5*pi-alpha4-alpha5;alpha7=acos(GNA2+GHA2-NHA2)/(2*GN*GH);alpha8=acos(R/GN);alpha9=acos(R-r)/GH);alpha10=2*pi-alpha9-alpha7-alpha8;alpha11=acos(G 屮 2+DHA2-GDA2)/(2*GH*DH);alpha12=pi-alpha11;alpha13=1.5*pi-alpha11-alpha12;alpha14=acos(CDA2+DHA2-C