1、地面搜索問題的優(yōu)化模型摘 要 本文針對地面搜索過程中人員安排和路線選擇問題，建立了優(yōu)化模型，并給出了相應算法，用LINGO軟件編程，在確保所有地點都不遺漏且不重復的情況下，合理安排人員和線路，使得搜索用時最短。 問題一的求解中，把20個搜索隊員排成一行，向前搜索。從局部和總體兩個方面對人員行進和路線選擇。在局部方面，考慮到人員行進中90度和180度轉彎的情況，給出了兩種轉彎策略，并計算出這兩種轉彎的情況需要多耗費的時間；在總體方面，把需要進行搜索的區(qū)域分割成的126個方格，利用一筆畫原理，判斷出這些方格可以用一條不重復的線路走完。考慮到轉彎需要多耗費時間，建立了以轉彎次數(shù)最少，并且從起始點開始

2、不重復行走到達集結點的模型，利用LINGO軟件進行編程求解，得到了最少轉彎的模型。考慮到具體情況，對上述模型得到的路線進行適當調整，得到最終的搜索線路安排圖。根據(jù)圖表，計算出20個隊員進行搜索需要50.117小時，無法在48內完成搜索任務。 考慮到隊員和組長距離不超過1000米，設計一種讓20名搜索隊員組成的隊伍和新增人員組成的隊伍進行交替行進的模型，以確保讓整個搜索過程控制在48小時以內。最后給出了該行進模型的相應算法，通過計算，得出增加2個隊員可以確保搜索在48小時內完成。 問題二的求解中，首先對50名人員分3組進行分析，由于矩形區(qū)域被分割后形成的小區(qū)域恰好能被20人組成的一個隊列一次搜索

3、覆蓋，以及10人組成的一個隊列一個來回的搜索覆蓋，于是3組可分為：2個隊伍為20人，1個隊伍為10人。隨后進行隊伍搜索區(qū)域的劃分，根據(jù)各個隊伍人數(shù)確定該組分配到的方格的數(shù)量，劃分出各個隊伍的搜索區(qū)域。然后對三個區(qū)域進行搜索路徑的優(yōu)化求解，改進問題一的模型，求出三個區(qū)域的搜索路徑。再根據(jù)實際情況，對路徑進行適當修改，得出20人的2個隊伍，需要19.816小時，10人的隊伍需要20.294小時。根據(jù)先完成搜索任務的隊伍能否有足夠的時間來幫助未完成搜索任務的隊伍提早完成任務的時間要求，判斷出該解是可以接受的。于是得到50人進行搜救的時間為20.294小時。最后，對文中的模型進行了優(yōu)缺點的分析。關鍵詞

4、：搜索模型；最優(yōu)路徑；一筆畫；遍歷網(wǎng)格；轉彎策略一、問題重述有一個平地矩形目標區(qū)域，大小為11200米×7200米，需要進行全境搜索。假設：出發(fā)點在區(qū)域中心；搜索完成后需要進行集結，集結點（結束點）在左側短邊中點；每個人搜索時的可探測半徑為20米，搜索時平均行進速度為0.6米/秒；不需搜索而只是行進時,平均速度為1.2米/秒。每個人帶有GPS定位儀、步話機，步話機通訊半徑為1000米。搜索隊伍若干人為一組,有一個組長，組長還擁有衛(wèi)星電話。每個人搜索到目標，需要用步話機及時向組長報告，組長用衛(wèi)星電話向指揮部報告搜索的最新結果。現(xiàn)在有如下問題需要解決：1假定有一支20人一組的搜索隊伍,

5、擁有1臺衛(wèi)星電話。請設計一種你認為耗時最短的搜索方式。按照你的方式，搜索完整個區(qū)域的時間是多少? 能否在48小時內完成搜索任務? 如果不能完成，需要增加到多少人才可以完成。2為了加快速度，搜索隊伍有50人，擁有3臺衛(wèi)星電話，分成3組進行搜索。每組可獨立將搜索情況報告給指揮部門。請設計一種你認為耗時最短的搜索方式。按照你的搜索方式, 搜索完整個區(qū)域的時間是多少?二、模型假設1. 假設搜索必須完全，不存在遺漏情況。2. 假設如果發(fā)現(xiàn)需要救助的人員，只需報告組長，不影響其搜索速度。3. 假設救援人員進食休息的時間不計。4. 隊員間不能間接向組長報告情況。5. 假設每組隊員只能向本組組長報告。6. 假

6、設隊員的身體和心理狀態(tài)不影響進度。7. 假設搜索區(qū)域地面狀況不影響搜索速度。8. 假設設備在搜索過程中都正常工作。三、 符號說明 20人排成隊列的長度 增加的人數(shù) 不搜索時候行進的速度 搜索時候行進的速度 搜索需要花費的時間 搜索時間的各個組成部分 表示矩形分割后的區(qū)域的標號 表示標號為的區(qū)域的各個方向的連接數(shù) 表示1個180度轉彎需要多耗費的時間 表示1個90度轉彎需要多耗費的時間四、問題分析 本題針對一塊矩形區(qū)域進行全境搜索問題,在保證全部搜索到的情況下，使搜索時間最短，我們將20人看成排成一排的整體,并將大的矩形區(qū)域劃分為126個以800米為邊長的正方形小區(qū)域，根據(jù)圖論中的一筆畫問題,以

7、轉彎最少為約束條件進行LINGO編程，計算出搜索路徑.當隊伍增加為3時，先根據(jù)人數(shù)比例進行大體的區(qū)域劃分，然后在根據(jù)問題1的求解方法，計算出三個隊的最優(yōu)路徑。五、模型的建立與求解5.1 求解問題一建立隊伍前進和轉彎模型： 由于每個搜索隊員的搜索半徑為20米，為了簡化模型，把20名搜索隊員排成一條直線，其中隊長處于中間，這樣就更好的保證了隊員與隊長的通訊： 總長為800米共20個 圖(1-1) 搜索時候可以把20人組成的隊列看作一條長800米的直線，搜索方向是沿著直線的垂線的方向，直線行進的速度為搜索的速度。如下圖所示，直線向其垂線方向進行時，會形成一個矩形軌跡，見圖(1-2)。 800米移動方

8、向 圖(1-2) 但需要進行轉彎時，分為2種情況，180度轉彎和90度轉彎：1、180度轉彎：圖(1-3) 如圖(1-3)所示，原直線沿著AB 邊向右移動，當?shù)竭_CD邊時，整體向上移動，使得原CD邊與EC邊重合，然后EC邊繼續(xù)向左邊運動，搜索遇難人員。由 得， 即過180度的彎需要多耗費的時間2、90度轉彎CDoAB圖(1-4)如圖(1-4)所示，原直線沿著AB 邊向右移動，當?shù)竭_CD邊時，直線上處于C點的人向O點運動，D點上的人向C點運動，點，直線中間的人員依然可以找到合適的路徑向OC邊移動，使得CD與CO重合，然后CO邊繼續(xù)向上邊運動，搜索遇難人員。容易得出，該調整過程也需要的時間，即由以

9、上2個轉彎模型，可以得出，轉彎的時間為建立搜索路線模型：如表(1-1)所示，把矩形區(qū)域劃分為如下小塊，并且標號為：表(1-1)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115

10、116117118119120121122123124125126 根據(jù)圖論中關于奇頂點個數(shù)為偶數(shù)就能一次走完全程而不重復行走的原理，判斷出這些方格可以用一條不重復的線路走完。 由于出發(fā)點在矩形區(qū)域中央，即和交線的中點處，設定搜索隊首先進入?yún)^(qū)域，然后在搜索完全部區(qū)域后，最后回到，過程是一筆畫成的，沒有重復，由于在轉彎時，需要額外花費時間來進行調整，所以，當轉彎數(shù)為最少時，是該題目的最優(yōu)解答。 如表(1-1)可以看出：矩形中的各個小區(qū)域在前后左右有另外的小區(qū)域與其相鄰（邊界的區(qū)域較特殊，可能某個方向沒有相鄰的區(qū)域）。把各個小區(qū)域看成一個點，如果要進行一筆畫，則除了開始點只有一個出口和結束點只有一

11、個入口，每個點均有兩個接口與其他區(qū)域連接。 （1）一個點有上下左右四個方向，用字母表示這個點在方向上是否與其它點連接，1為連接，0為不連接，分別表示上下左右四個方向。以2個特殊的點為例，如： 點：由于在頂角，則其上邊和左邊必定沒有連接，所以，。 點：由于在下邊沿，則其下邊必定沒有連接，所以 全面的表示出這些點的特征，表達式為：（2）由于每個點的連接個數(shù)只能為2個（除外）， 所以，（3）如果有2個點，一個點的左邊與另一個點連接，則另一個點的右端必定與該點連接。基于這個原則，得到如下表達式： （4）為了判定在一個點處是否轉彎，只要判定該點的2個接口是否為上和下，或者左和右，當一個為上，一個為下，可

12、以說明該點處不轉彎；當一個為左，一個為右，也可以說明該點處不轉彎。用表達式來表示如下： 當時，為不轉彎。 根據(jù)以上（1）（2）（3）（4）四點，可以轉化為一個優(yōu)化問題的求解。目標函數(shù)：約束條件：，用LINGO編寫程序（見附錄），可以得到對應的上下左右四個方向是否有連接的數(shù)據(jù)，根據(jù)數(shù)據(jù)可以表示出其路線圖。為了方便觀看，用線路圖表示路線如圖(1-5):圖(1-5) 如圖(1-5)可知，通過LINGO軟件解決了不重復和彎角最小的問題，可是其沒有解決一筆畫問題，在圖中出現(xiàn)了一個閉合的路徑，不和其他路徑進行相連接，由于程序為我們解決了不重復和彎角最小的問題，我們如果進行適當?shù)奈⒄{，對最優(yōu)結果的影響是很微

13、小的。觀察圖形，對那個閉合路徑進行修改，使得他和其他路徑相連接。 對圖像的調整結果如下：圖（1-6） 如圖(1-6)所示該路線經過了所有的區(qū)域，一共需要轉彎17個，則轉彎所需的時間為 除轉彎外的時間外，其余時間設都為搜索前進，為 得， 由于在開始搜索時，所有隊員都處在矩形區(qū)域中央，即左邊沿的中點處，為了讓隊員排列成一條直線，則所有隊員向兩邊散開，使其均勻分布在左邊沿，這一過程需要耗費的時間為得， 在搜索結束時候，所有隊員都均勻分布在的下邊沿，為了讓他們到達集合地點（的左邊沿的中點），需要耗費的時間為得，則所以搜索完整個區(qū)域的時間是50.117小時，不能在48小時內完成搜索。建立增加人數(shù)的模型

14、為了滿足能夠在48小時內搜索完成搜索任務，決定增加人數(shù)為，這個人的作用就是為了幫助原20個人的隊伍分擔部分搜索區(qū)域，來達到原20人的隊伍能在48小時內完成搜索任務的目的。隊伍搜索區(qū)域的時間包括，其中是最有可能進行優(yōu)化的數(shù)據(jù)，也是可以減少幅度最大的時間因素。讓增加的個人在這段時間里發(fā)揮作用，來減少。建立模型：只考慮隊員搜索所有路線的時間，由于不轉彎所以隊員行進路線可視為一條直線。把原20人和新增加的個人分為2個隊伍，只要個人的隊伍離原20人的隊伍距離不超過1000米，就可以和組長保持連續(xù)，但兩隊伍的搜索是獨立完成的。ABCDE 圖（1-7） 如圖(1-7)，可以把行進路線分割為一大一小交替的段落

15、。其中A為原20人隊伍搜索的區(qū)域，B為增加的個人隊伍趁著原20人隊伍在搜索A區(qū)域時，以速度移動過去搜索的路線。當原20人隊伍搜索完A時，要繼續(xù)搜索C區(qū)域，可以速度經過B區(qū)域，此時個人的隊伍又以速度移動到D，如此交替。可以發(fā)現(xiàn)，總共搜索節(jié)約的時間，就是20 人隊伍以速度穿過B，D所節(jié)省的時間，且節(jié)約的時間為原來大部隊經過B，D時間的一半。得到方程： 解得 因此，如果想在48小時內完成搜索應該增加2個搜索隊員。5.2 求解問題二 由問題一的選擇路徑模型可知，需要搜索的矩形區(qū)域長和寬可以被20人組成的直線的長度整除，也可以被10人組成的直線的長度整除，為了便于計算和工作安排，我們做如下設定：1. 把

16、50人分為三組，人數(shù)分別為20、20、10人；2. 為了使搜索所用時間最短，則三組所用時間相等；3. 在不考慮轉彎時間的條件下，如問題一所示，把矩形區(qū)域分為126個區(qū)域由于最終所有隊伍必須回到一點，所以除去該點所在的區(qū)域，三隊分得的區(qū)域個數(shù)為為50，50，25時時間最短。 如圖(2-1)，分出了區(qū)域，上下兩個圖形塊為20人搜索的面積，中間區(qū)域10個人隊伍搜索的區(qū)域。 以上理論是理想化的圖形，實際上要考慮轉彎等因素，所以時間可能會不相同。 圖(2-1) 如圖(2-1)可知，上下兩個區(qū)域是對稱的，他們的搜索路徑時相同的。而中間區(qū)域必須把每個小區(qū)域的邊長變?yōu)?00，才能利用問題一種的方法進行10人搜

17、索。 取出上邊區(qū)域單獨考慮，對方格標號如表(2-1)：表(2-1)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950對問題一中的模型進行修改：目標函數(shù)：約束條件：，通過LINGO編程(見附件：程序2)，在進行適當?shù)穆窂秸{整后，得到 圖(2-2)由于中間區(qū)域的搜索隊員的人數(shù)為10人,展開的長度為400米，于是把區(qū)域再劃分為4個區(qū)域，得到如下區(qū)域表： 表(2-2)對問題一中的模型進行修改得：目標函數(shù)： 約束條件： ，通過LINGO編程(見附件：程序3)，在進行適當?shù)穆?/p>

18、徑調整后，得到： 圖(2-3) 由于在求中間區(qū)域時候，不可避 免的進行了較多的轉彎，所以圖(2-3)中“X”點處為沒有進行分配的區(qū)域應該平均分給20人的2個隊伍。依然使用來表示搜索某一區(qū)域的時間，其中分別表示，轉彎時間，搜索時間，開始搜索時候人員調配的時間，結束時候人員集合的時間。 由上述結果可以得出，20人的隊伍在比10人的隊伍早完成任務。設定搜索上邊區(qū)域和下邊區(qū)域的隊伍分別為第一、二隊，搜索中間區(qū)域的為第三隊。如果第一隊和第二隊有必要幫助第三隊完成搜索任務以縮短搜索時間，那么第一二兩隊和第三隊完成任務相差時間必須大于已經結束搜索任務第一二隊走出集結點所在的區(qū)域時剛好碰到中間的隊伍完成搜索一起到集結點的時間，通過計算這段時間為，如果第一二隊比第三隊至少早完成搜索任務，才能幫助第三隊減少任務時間。由于第三隊比第一二隊晚完成搜索，小于小時，則沒有必要再減少第三隊的搜索時間，所以我們的方案是合理的。所以50個人分三組最少搜索時間是。六、優(yōu)缺點分析 優(yōu)點：劃分為網(wǎng)格，確定了隊員的大體移動方向，避免了無規(guī)則的移動，簡化了問題的求解。利用圖論的判斷了對搜索路線可以一筆畫，在編寫程序中避免了搜索過程中的重復搜索，節(jié)省了時間， 缺點：用LINGO程序求出的搜索路徑不一定是最優(yōu)解，只是一個較好的可行解。在考慮增加人數(shù)問題的處理上，沒有考慮轉彎時間的變化，導致求出的人數(shù)相對變小。七、參考文獻1