路徑規劃匯總十篇

序論：好文章的創作是一個不斷探索和完善的過程，我們為您推薦十篇路徑規劃范例，希望它們能助您一臂之力，提升您的閱讀品質，帶來更深刻的閱讀感受。

篇（1）

引言

物流與國民經濟及生活的諸多領域密切相關，得到越來越多的重視，甚至被看作是企業“第三利潤的源泉”。因此，作為物流領域中的典型問題，旅行商問題(Traveling Salesman Problem，TSP)的研究具有巨大的經濟意義。

TSP(Traveling Salesman Problem)問題, 是VRP[2]的特例，也稱為巡回旅行商問題,貨擔郎問題。簡稱為TSP問題，已證明TSP問題是NP難題。。TSP問題可描述為:給定一組n個城市和它們兩兩之間的直達距離,尋找一條閉合的旅程,使得每個城市剛好經過一次而且總的旅行路徑最短。TSP問題的描述很簡單,簡言之就是尋找一條最短的遍歷n個城市的路徑,或者說搜索整數子集X={1,2,…,n}(X中的元素表示對n個城市的編號)的一個排列π(X)={v1, v2,…, vn},使取最小值.式中的d(vi,vi+1)表示城市vi到城市vi+1的距離。它是一個典型的、容易描述但卻難以處理的NP完全問題。同時TSP問題也是諸多領域內出現的多種復雜問題的集中概括和簡化形式。所以,有效解決TSP問題在計算理論上和實際應用上都有很高的價值。而且TSP問題由于其典型性已經成為各種啟發式的搜索、優化算法 (如遺傳算法、神經網絡優化法、列表尋優法、模擬退火法等)的間接比較標準。

1 遺傳算法與蟻群算法

1.1 遺傳算法原理

遺傳算法(Genetic Algorithms，GA) 是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法,由美國J.Holland教授提出,其主要內容是種群搜索策略和種群中個體之間的信息交換,搜索不依賴于梯度信息.該算法是一種全局搜索算法,尤其適用于傳統搜索算法難于解決的復雜和非線性問題.。選擇算子、交叉算子和變異算子是遺傳算法的3個主要操作算子.遺傳算法中包含了如下5個基本要素:①對參數進行編碼;②設定初始種群大小;③設計適應度函數;④設計遺傳操作;⑤設定控制參數(包括種群大小、最大進化代數、交叉率、變異率等)

1.2 蟻群算法原理

研究表明：螞蟻在覓食途中會留下一種外激素．螞蟻利用外激素與其他螞蟻交流、合作，找到較短路徑．經過某地的螞蟻越多，外激素的強度越大．螞蟻擇路偏向選擇外激素強度大的方向．這種跟隨外激素強度前進的行為會隨著經過螞蟻的增多而加強，因為通過較短路徑往返于食物和巢穴之間的螞蟻能以更短的時間經過這條路徑上的點，所以這些點上的外激素就會因螞蟻經過的次數增多而增強．這樣就會有更多的螞蟻選擇此路徑，這條路徑上的外激素就會越來越強，選擇此路徑的螞蟻也越來越多．直到最后，幾乎所有的螞蟻都選擇這條最短的路徑．這是一種正反饋現象．

2.算法改進

在傳統解決方法中，遺傳算法以其快速全局搜索能力在物流領域獲得了廣泛的應用。但遺傳算法在求解到一定程度時，往往作大量的冗余迭代，對于系統中的反饋信息利用不夠，效率較低；蟻群算法也以其較強的魯棒性和智能選擇能力被廣泛應用于旅行商問題 。蟻群算法是通過信息素的累積和更新而收斂于最優路徑,具有分布、并行、全局收斂能力，但由于蟻群算法的全局搜索能力較差，易陷入局部最優，很難得到最優解。

為了克服兩種算法各自的缺陷,形成優勢互補。為此首先利用遺傳算法的隨機搜索、快速性、全局收斂性產生有關問題的初始信息素分布。然后,充分利用蟻群的并行性、正反饋機制以及求解效率高等特征。算法流程如圖1

圖1 遺傳混合算法流程

2.1遺傳混合算法的具體描述如下：

Step1 給出，放置m個螞蟻在n個城市上。

Step 2 把所有螞蟻的初始城市號碼放置到tabuk中，列表tabuk紀錄了當前螞蟻k所走過的城市，當所有n個城市都加入到tabuk中時，螞蟻k便完成了一次循環，此時螞蟻k所走過的路徑便是問題的一個解。

Step 3 螞蟻K從起點開始，按概率的大小選擇下一個城市j,k∈{1，2，…,m},j∈allowedk如果螞蟻k轉移到j ,從allowedk中刪除,并將j加入到tabuk直至allowedk= 時重新回到起點。

Step 4 是否走完所有的城市，否，則轉入Step 3。

Step 5 計算,記錄，更新信息素濃度，所有路徑信息更新，如果,清空tabuk則轉入Step 2。

Step 6 當時，得到相對較優螞蟻的序列。初始化種群。

Step 7 計算適應度值。

Step 8 進行遺傳交叉與變異操作。

Step 9 輸出得到的最短回路及其長度。

2.2 算法過程實現

（1）種群初始化

用蟻群算法進行初始化種群，放m只螞蟻對所有城市進行遍歷，將得到的結果進行優化，做為蟻群算法的初始種群。每只螞蟻走過的路徑的就代表了一條基因（a0、a1、…、am-1、am），對于這條基因表示這只螞蟻首先從a0出發，次之訪問a1、…然后依次訪問am-1、am最后再回到a0。

（2）狀態轉移規則設置

    轉移概率，為t時刻螞蟻由i城到j城的概率。

            （1）

式中，allowedk表示螞蟻k下一步允許選則的城市，表示信息啟發因子，其值越大，該螞蟻越傾向于選擇其他螞蟻經過的路徑，螞蟻之間的協作性超強；β為期望啟發因子，β的大小表明啟發式信息受重視的程度，其值越大，螞蟻選擇離它近的城市的可能性也越大，越接近于貪心規則［6］。為啟發因子，其表達式為: ，每條路上的信息量為：

（2）其中

其中ρ表示路徑上信息的蒸發系數，1-ρ表示信息的保留系數；表示本次循環路徑(i,j)上信息的增量。表示第k只螞蟻在本次循環中留在路徑(i,j)上的信息量，如果螞蟻k沒有經過路徑(i,j)，則的值為零，表示為：

（3）

其中，Q為常數， 表示第k只螞蟻在本次循環中所走過的路徑的長度。

（3）交叉算子的設計

首先隨機地在父體中選擇兩雜交點,再交換雜交段,其它位置根據保持父體中城市的相對次序來確定。例如,設兩父體及雜交點的A1和A2, A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 8 1 6 7 9 3)。交換雜交段于是仍有B1=(2 6 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 3)。在新的城市序列中有重復的數，將雜交段中對應次序排列,即: 7-8、3-1、5-6，依此對應關系替換雜交段中重復的城市數。將B1中(2 6 4)重復的6換為5，B2(9 3)中重復的3換為1.。雜交后的兩個體為B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交雜交。

3.仿真實驗

對TSP問題仿真所用的數據庫是TSPLIB典型51城市的數據。仿真平臺如表1所示。

表1  仿真試驗平臺

設備名稱

型號

CPU

Pentium(R)M 1.66 GH

內存

512M

操作系統

Microsoft Windows XP

仿真軟件

MierosoftVisualC++6.0

3.1 遺傳算法仿真

基本遺傳算法仿真。對51城市路徑優化路徑優化。參數設置如下:種群:50,最大迭代數:5000,交叉概率:0.8,變異概率:0.2

遺傳算法找到最優解的時間是95 s, ,路徑長度497。

3.2 蟻群算法仿真

基本蟻群算法對51城市路徑優化。其參數設置如下：ρ=1α=1，β=8，τ0=0.001Qu=100., m=51

基本蟻群算法找到最優解的時間是68 s, 路徑長度465。

3.3遺傳混合算法

遺傳混合算法對51城市路徑優化。其參數設置如下：種群:51,最大迭代數:5 000,交叉概率:0.8,變異概率:0.001;ρ=1α=1，β=8，τ0=0.001Qu=100，m=51；

遺傳混合算法找到最優解的時間是50 s, 路徑長度459。

遺傳算法、基本蟻群算法、遺傳混合算法對TSPLIB典型51城市的數據進行仿真,仿真結

果對比如表2所

算法名稱

所用時間（s）

最優結果

遺傳算法

95

497

基本蟻群算法

68

465

改進混合算法

50

456

4.結論

本文為了更好地解決物流領域中的旅行商問題，充分發揮遺傳算法的全局搜索能力和蟻群算法的正反饋能力和協同能力，采用了遺傳算法與蟻群算法混合算法進行求解，并且進行了模擬仿真。仿真結果表明，利用遺傳與蟻群混合算法可以找到較好解的能力，大大提高計算效率，結果質量也較好。   

參考文獻：

［1］小平,曹立明.遺傳算法———理論、應用與軟件實現[M].西安交通大學出版社,2002.

［2］[日]玄光男,程潤偉.遺傳算法與工程設計[M].科學出版社, 2000.

［3］胡小兵，黃席樾。蟻群優化算法及其應用[J]. 計算機仿真 2004，24（5）

篇（2）

0引言

路徑規劃是車載導航系統最重要的功能之一[1]。根據圖論中最短路徑理論，不管是最短路徑規劃、最短時間規劃還是最低消費規劃，都可以通過賦予圖中的邊以相應的權值來滿足用戶的不同需求。

通常情況下，路徑搜索可以分為平面搜索和分層搜索兩大類。平面搜索算法中最經典的是20世紀60年代初期由Dijkstra提出的Dijkstra算法，非常適合在帶權有向圖中解決最短路徑問題。但是該算法的時間復雜度為O（n2），效率比較低，因此在實際應用時受到了很大的限制。后來許多學者在存儲結構和排序算法上對Dijkstra算法進行了改進[2-3]，通常改進算法的時間復雜度與節點數成正比，如O（mlbn）或O（m+nlbn）[4]。也有學者通過引入啟發函數的方式進行改進，啟發式搜索以1968年Hart等提出的A*算法為代表，現在仍被廣泛應用，但這些改進算法的效率會隨節點數的增加而急劇下降。此外，平面搜索算法計算出的“最短”路徑并不一定是“最優”路徑，最短路徑中可能存在大量的窄小擁擠的小巷，而最優路徑要盡可能多地包括主干道等快速路段[5]，這就有了分層思想。文獻[6]首先提出了層次空間的推理過程，文獻[7]又將層次空間推理法則引入到行車最優路徑搜索中，但這兩篇文獻均沒有給出具體的路網層次拓撲結構的表達方法[8]。有代表性的分層算法有最近E節點法[9]和最佳E節點法[10]，其中最近E節點法簡單但準確率不高，最佳E節點法能夠得到最優解，但效率低[11]。

本文試圖設計一種實用的分層路徑規劃算法。首先建立分層路網的拓撲結構，然后從搜索空間、搜索策略和數據結構三個方面進行研究，采用啟發式的A*算法作為主搜索方式，引入優先隊列二叉堆作為數據存儲結構，最后通過實驗驗證每項措施的改善效果。

篇（3）

中圖分類號：F252.14 文獻標識碼：A

Abstract： The cigarette distribute route problem is a LS-VRP problem with includes the consideration of distance saving and the work balance between each car. This paper found the module with the object of work balance， car saving and distance saving. Then design the route cut based heuristic algorithm to solve the module and get a good effect in the example problem solving.

Key words： route planning； cigarette distribute； heuristic algorithm； multiple objects

在我國，一般以市級煙草配送中心為中心，直接配送到全市各地的上萬個配送點。負責卷煙配送的車輛由煙草配送中心出發，依次到其負責的收貨點進行配送，最終配送完成后車輛返回配送中心[1]。現有的卷煙配送車輛型號眾多，載貨量也有區別。卷煙配送路線的規劃是一個LS-VRP（大規模車輛路徑）問題，是一個NP問題。對于一般的LS-VRP問題有精確算法、亞啟發式算法和啟發式算法等。

眾所周知，我國卷煙配送工作由來已久，因此各地煙草商業企業在發展中已經形成了自己的配貨順序，并根據配貨順序安排配送車輛。這種配貨順序有其存在的合理性，并且已經在運行之中，進行較大的改動有一定的風險。但是傳統的車輛配送任務分配主要采取人工的方式進行，工作量大且優化程度較低。另外，在解決大規模VRP問題的方法中，一種思想先按照TSP問題利用算法生成一個全局的配送路線，之后對這個總的配送路線進行截斷，來確定分配給每輛車的配送路線，從而生成卷煙配送VRP問題的配送方案。這種方法優化程度較高，而且可以保證較快的計算速度。因此基于大線路截斷成小線路進行配送的方法有一定的實際價值。

而且除了總配送路程最短、費用最小、時間最短等一般VRP問題的約束之外，處于管理上的考慮，卷煙配送過程有其特有的特點，例如要求不同車輛工作時間比較均衡且小于上限、車輛之間的配送量均衡等。因此引入了一些原則進行配送任務劃分來保證車輛工作強度的均衡。

本文研究的基于配送任務均衡的線路截斷方法，屬于一種亞啟發式算法，主要實現的功能是在收貨點配送排序確定的情況下，把這些收貨點的配送任務分配給各配送貨車。貨車從配送中心出發，按照指定的順序配送其負責的收貨點，之后返回配送中心。在這個過程中要考慮配送路徑最短、所用車輛最少、配送工作量均衡的要求。

1 模型建立

收貨點配送任務序列為：

S=s，s，…，s，…，s

其中s，s，…，s表示n個收貨點的收貨量。而其角標表示該收貨點配送的次序。s為第一個配送，s為第二個配送，依次類推，s為最后一個。每個收貨點只能由一個車輛配送。

每個車輛包含標準載貨量和標準服務客戶數兩個指標，這兩個指標由車輛的型號和配送人員的工作時間確定。

配送車輛標準載貨量為：

V=v，v，…，v，…，v

配送車輛標準服務客戶數為：

C=c，c，…，c，…，c

目標函數為：

MinDis=∑d

MinN

MinPv=∑ρv-

MinPc=∑ρc-

式中Dis表示每個配送車輛的配送距離d之和，即總配送距離。N為使用的車輛總數。ρv、ρc分別表示第j輛車的裝載量與標準載貨量、服務客戶數與標準服務客戶數的比值，即裝載率和服務率，用來衡量車輛的工作負荷程度。、表示了所有車輛的裝載率和服務率。Pv與Pc計算了車輛實際裝載率、服務率與平均值的差值之和，其值越大表示車輛的任務分配越不均衡。目標函數反映了實際卷煙配送中的實際要求。

2 模型求解

在實際的配送過程中，首先需要設定每輛車的裝載率和服務率的上下限值ρv， ρv、ρc， ρc。即車輛的裝載率不得高于其上限值，也不能低于其下限值，服務率亦然。這樣可以保證車輛的使用率。如果車輛運力緊張的情況下可以將下限值提高，但會降低在配送距離優化中的調整余地。如果需主要考慮配送里程的節約可以適當擴大區間，從而可以在更寬的范圍內進行配送任務的劃分。

為了保證任務量的均衡和較短的配送距離，本文設計了基于線路截斷的亞啟發式算法進行配送任務劃分。算法的流程如下：

Step1 對每輛車進行模擬裝車，以車輛j為例，將待分配任務序列（第一次循環時即為初始S序列）中的收貨點從前到后依次裝入車輛j中，當車輛j的裝載量與服務率之一達到其下限值時，當前最后一個裝入的點即為其裝載任務的下限點，假設該點為sl，之后繼續裝載，當車輛j的裝載量與服務率之一達到上限值時，最后一個裝入的點即為其裝載任務的上限點，假設該點為s，則車輛j的可截斷區間為s，s。即該車輛的當前配送任務可以是從配送序列的第一個點s開始到s，s中任何一點結束。計算所有車輛的可截斷區間。

Step2 找到每個車輛可截斷區間內相隔距離最長的一組相鄰點s，s，兩點之間距離記錄為Sav，則車輛的模擬配送任務為s…s，

s是剩余配送任務序列的起始點，即新的s。之后比較所有車輛當前模擬裝車的使用效率ρ=ρv+ρc，選擇使用效率最高的車型作為當前循環的所選車型，其配送任務為其對應的s…s，將已配送的點以及該車輛從任務序列和備選車型中刪除。

Step3 如果最后一個車的使用效率低于平均使用效率的20%，則可以通過調高每輛車的裝載率和服務率下限值之后返回Step1，直到將最后一輛車的配送任務分配至其他車輛為止。如果使用效率高于平均使用效率的20%低于85%，則通過調低每輛車的裝載率和服務效率下限值返回Step1，可以減少前面車輛的任務量，提升最后一輛車使用效率。如果最后一輛車的使用效率高于平均使用效率的85%則任務分配結束。

若循環20次之后仍無法跳出循環，則輸出當前解。

3 仿真實驗與數據分析

下面通過Matlab軟件編程進行仿真實驗。

配送任務序列為某地市實際卷煙配送任務，共712個點。

輸入數據：

配送中心與收貨點、各收貨點之間的距離矩陣，各收貨點的收貨量，車輛矩陣：

首次循環的裝車方案為：

當前總配送里程為1 201km。最后一輛車的使用效率1.96為平均使用效率1.93的1.014%，達到終止條件，配送任務分配完畢。整個算法運行時間為1.87s。

篇（4）

【Abstract】Intelligent transportation has a very wide range of applications in modern industry. Inproving route planning algorithm is one of the important ways to increase the efficiency of intelligent transportation. Based on Intelligent Transportation Project in China Robocup competition，an adaptive route planning algorithm is designed. The proposed algorithm can be applied to the intelligent classification of garbage and the automation of logistics. Compare with the exist algorithms， it can change the route and destination before the start of transportation.

【Key words】Route Planning； Adaptive； Intelligent Transportation

0 引言

智能搬運機器人主要指按設定的路線，或者使用視覺、磁線、激光導航的自動行駛的機器人。智能搬運機器人是一種自動導向車（Automated Guided Vehicle，簡稱AGV）[1]， 也稱自動導向搬運車、自動引導搬運車。隨著AGV的性能逐漸提高，智能搬運機器人被廣泛用于工業、農業、醫學、國防等領域[2]。路徑規劃是提高智能搬運機器人性能的一個重要方向[3]。

路徑規劃指的是根據既定的標準，如何規劃一條從起始點到終點的最優路徑[4]。根據環境信息的知情情況，路線規劃又分為局部路徑規劃和全局路徑規劃[5-6]。本文討論的路線規劃以中國機器人大賽中的智能搬運項目為藍本，利用顏色識別技術設計了一個自適應的路徑規劃算法，它可以應用于工業自動化過程中自動化物流、垃圾智能分類等領域。

1 可適應的路徑規劃算法

在描述本文提出的可適應的路徑規劃算法之前，首先介紹機器人大賽智能搬運項目的比賽規則，在1.2節將介紹根據算法設計的機器人。

1.1 路徑規劃規則

圖1所示為中國機器人大賽智能搬運項目中的使用的場地圖。圖中黑字A、B、C、D、E、F、G為待搬運的色塊所在地，其中A、B、C、D、E可隨機放置3-5個色塊，F和G點每點可隨機放置不超過5個色塊。O點所在為起點及終點，圖中a、b、c、d、e為目標所在地，機器人要識別待搬運色塊的顏色，并搬運到相應的顏色目標所在地，機器人的路徑除點a、b、c、d、e外只能為圖中黑色的線條。根據要求，設計的機器人必須有顏色識別、路徑識別存儲等功能。色塊共用5種顏色：綠色、白色、紅色、黑色、藍色。本文假設圖中目標點a、b、c、d、e 的顏色在搬運前是可以隨機調整的，但搬運過程中是固定的，這種假設與生活中的情形比較相符。現有比賽中用到的算法都是固定了目標點的顏色、每個夾角的度數和每段路徑的長度，應用性低，因此本文提出自適應的路徑規劃算法。

1.2 智能搬運機器人設計

本文設計的智能搬運機器人包括如下幾個模塊：（1）路徑檢測；（2）轉向控制；（3）電機驅動；（4）車速檢測；（5）電源管理；（6）物體檢測（7）物體抓取；（8）路徑規劃。主控制器是51單片機，它負責接收賽道數據、賽車速度等反饋信息，并對這些信息進行恰當的處理，形成合適的控制量來對舵機與驅動電機進行控制，采用紅外傳感器控制小車沿著預設的軌道黑線及時調整車身姿態，使之準確、快速地跑完全程，采用四驅差速來進行原地轉向與前進，使用穩壓芯片7805穩定電壓，用顏色傳感器準確識別要抓取物塊的顏色，超聲波傳感器定位需抓取物塊，測算出距離出來以便接下來準確的搬運至目的地。實現這些功能共包含電機模塊，超聲波模塊，顏色傳感器模塊，紅外模塊，伺服電機抓手模塊，電源穩壓模塊。智能車的設計主要體現在電路板和機械結構上面，車的前部攜帶著超聲波探頭，與顏色傳感器，用于識別物體，在顏色傳感器與超聲波探頭下面是紅外模塊用來循跡，來到車身是雙層的結構，在上層前端固定著有三個伺服電機控制的抓手，上層的中間是紅外驅動模塊，車的尾部則是放置電池及電源模塊，由一根銅柱支撐著51的最小系統外加電機驅動的模塊。而車的下層則是裝載著四個電機驅動四個輪子。

本文設計的智能搬運機器人在行駛過程中通過不斷地向地面發射紅外光來進行路徑檢測，當紅外光可遇到白色地面時發生漫發射，反射光被裝在小車上的接收管接收；如果遇到黑線則紅外光被吸收，則小車上的接收管接收不到信號，再通過比較器來采集高低電平，從而實現信號的檢測，最終形成路徑。

1.3 自適應的路徑規劃算法

所謂的自適應指的是沒有完全掌握整個搬運路徑，包括目標點a、b、c、d、e的顏色、兩點間距離，弧線間角度等，這樣，機器人在搬運前必須遍歷路徑并記錄下來。a、b、c、d、e的顏色可在搬運前任意更改，在搬運當中目標顏色不變，每次搬運前機器人都需要自己檢測目標點的眼神。為方便描述，假設E和F并無任何塊。算法令1代表綠色，2代表白色，3代表紅色，4代表黑色，5代表藍色，用數字來記錄顏色，這樣如果算法涉及加權，例如aA是一段斜坡，則預算aA可能更花費時間。算法首先要判斷障礙色塊及目標點a、b、c、d、e的顏色。

該算法如下：

如果點E、F也存在色塊，算法類似。算法可以加入權值。

2 結論

本文針對中國機器人大賽智能搬運項目的路徑規劃算法進行改進，提出自適應的智能路徑規劃算法，同時開發上位機軟件和搬運部件接口。經實驗證明，該算法有效可靠，有較高的效率。

【參考文獻】

[1]陳書光.機器人路徑規劃算法探討[J].商，2012（15）.

[2]寧志剛.一種高效的機器人路徑規劃算法[J].科技致富向導，2011（18）.

[3]周嶸，張志翔，翟曉暉，閔慧芹，孔慶杰.機器人室內路徑規劃算法的實用性研究[J].機械與電子，2016（8）.

篇（5）

一、前言

隨著信息技術在現代企業中的廣泛應用和高速發展，企業信息化程度大幅提高，企業的許多革命性的創新成果得益于此。在激烈的市場競爭中，倉儲配送和信息技術的有機結合為企業帶來了新的機遇，建設智慧倉儲網絡的理念應運而生。而配送作為銜接各個物流節點的關鍵流程，使倉儲網絡形成為一個系統性的整體，保證了物資的正常供應。優化配送車輛路徑能提高配送效率，降低配送成本，并提升配送準確性。

物資公司作為公司的專業分公司，負責管理在上海區域所有工程及運維檢修物資的供應。工程項目物資的供應分為供應商直送現場和倉庫供應現場兩種類型。其中，供應商直送現場為一次配送，關鍵點在于供應計劃與供應商的有效銜接與調度協同；而利用公司倉儲配送網絡，通過中心庫向各周轉庫配送以供應現場物資需求的過程為二次配送。合理二次配送車輛路徑規劃與實施，能提高后續工程建設、運維檢修及應急搶修的需求響應速度，增強物資供應的計劃性和準確性，可有效提升物資供應管理水平。

二、車輛路徑問題定義

車輛路徑問題是指存在幾個物資需求方，各有一定數量的物資需求，由一個配送中心提供物資，并安排一個車隊配送物資。為此需要規劃合理的行車路線以使他們的物資需求得到滿足，且能在一定的約束條件下，達到路程最短或耗時最少的目標。

公司有十二個周轉庫，當周轉庫內某種物資數量低于安全庫存時，由中心庫提供物資進行補庫。由于工程項目對響應速度要求較高，當需要對多個周轉庫進行補庫時，必須綜合周轉庫的地理位置、物資需求量、車輛的運載量、配送次數等，設計出合理的車輛配送路徑。

三、配送路徑規劃意義

1.避免交叉運輸

中心庫車輛配送路徑規劃，將原先零散配送的物資進行整合后，以合理的配送路徑集中配送，避免了交叉運輸的情況，縮短了總配送距離，降低了運輸成本。

2.推進節能環保

車輛配送路徑優化在滿足各周轉庫的物資需求的前提下，以縮短配送車輛的總行駛距離為目標，能提高能源利用效率，推動公司更積極地承擔節能環保的社會責任。

四、配送路徑規劃過程

1.組織結構

物資公司倉儲配送網絡包括了集中的物資調配中心、一個中心庫以及十二個周轉庫。

（1）物資調配中心作為信息匯集、指令的中心，實時獲取中心庫和周轉庫內庫存物資數量、物資需求數量等信息，并根據這些信息判斷是否需要補庫。

（2）如果周轉庫需要補庫，物資調配中心發送補庫指令給中心庫。

（3）中心庫綜合需補庫的周轉庫數量、地理位置及物資需求量等，規劃所需的車輛數、配送路徑等信息，將物資配送至周轉庫。

2.車輛路徑問題描述

對于物資倉儲配送網絡，配送車輛路徑問題可以描述為，十二個周轉庫的位置固定且各有一定的需求量，中心庫用多輛載重量固定的汽車進行配送，要求合理安排汽車路線以使總距離最短，并能滿足以下條件：

（1）每個周轉庫的物資需求到能滿足；

（2）每個周轉庫的物資必須由盡可能少的車輛配送，例如在周轉庫的需求能由一輛汽車滿足的情況下，必須只由一輛汽車配送；

（3）每條配送路徑上各周轉庫的需求量總和不能超過汽車載重量。

3.車輛路徑規劃

將中心庫及十二個周轉庫構成的13個的節點兩兩連線，共有C132=78種組合，即這13個倉庫中任意兩個倉庫間的路徑共計78條。利用Google、百度等電子地圖軟件，將兩個倉庫分別作為起點和終點，搜索出這78條路線以及之間的行駛距離。以字母O表示中心庫，字母A至L表示十二個周轉庫。當有多個周轉庫需要補庫時，配送路徑確定步驟如下：

（1）確定各個周轉庫需要的物資數量；

（2）與汽車載重量進行比較，確定需要的汽車數量；

（3）根據各周轉庫的需求量，運用里程節約法，就近的倉庫由同一汽車配送，同時避免交叉運輸的情況，形成配送路徑；

（4）根據實時路況，對配送路徑進行一定調整，避免高峰期路段擁堵導致無法及時配送。

由于從實際情況考慮，為減少最后配送到的幾個倉庫的等待時間，在12個周轉庫中按地理位置分為兩塊區域，在郊環附近的7個倉庫為一個配送區域，郊環線以內的4個倉庫和崇明區域為一個配送區域。

以郊環線附近7個倉庫的配送為例，如下圖所示，每汽車載重量為5噸，A至G共7個周轉庫需中心庫O配送物資，直線上的數字為距離，括號內的為對應的周轉庫的物資需求量。

4.路徑信息

配送路徑規劃完畢后，將行車路線信息給對應的汽車司機。車輛出發后，利用短信在途跟蹤獲取車輛實時的位置信息，并將實時路況信息傳遞給司機，減少因交通擁堵造成的配送延誤。

五、結語

本文綜合各周轉庫地理位置、需求數量、汽車運載量等方面，運用里程節約法規劃出車輛配送路徑。車輛配送路徑規劃將對原先粗放式的配送方式進行優化，積極配合政府及上級公司對節能環保提出的要求，在滿足各倉庫需求的前提下縮短總配送距離，提高物資配送效率，降低配送成本。物資公司后續將逐步加強自動化和信息化建設，推進倉儲網絡各類信息的實時共享、獲取、分析和處理，運用先進信息技術提高配送準確性和效率效益，確保智慧倉儲網絡的配送脈絡高效穩定，構建一個現代化、智慧化、特色化的倉儲配送體系。

參考文獻：

篇（6）

一、引言

危險天氣區域下，導致飛行事故癥候的事件比較頻繁。在飛機巡航期間，由于受大范圍天氣系統的影響，雷雨，冰雹，龍卷風、閃電等，如果飛機在航路上遇到大面積雷雨區時，一般就會飛機返航、備降。而通常雷暴是在云層中，有的時候即使不下雨，但是云層中依然會有雷暴。雷暴區域附近產生的下擊暴流和風切變，會直接造成起降飛機失控。風切變即是在短距離內風向、風速發生明顯突變的狀況。強烈的風切變瞬間可以使飛機過早地或者被迫復飛。在一定程度下就可以導致飛機失速和難以操縱的危險，造成飛行事故。機組由于對雷暴的認識不清，簽派員在遇到雷雨天氣條件下航班的放行時，往往主對天氣的了解和掌握也主要集中在機場終端區雷雨天氣的研究。航路雷雨天氣下的放行成為一個難點，對其發展趨勢不明白，沒有事先做好充分的繞飛計劃，以及繞飛油量沒有帶夠等因素而導致返航備降。在航路上飛機飛行高度都比較的高，而空域范圍較廣，并且受到的地形限制非常小，解決的辦法可以讓飛機進行繞飛或改變在云上飛行飛行高度等措施來避開雷暴等危險天氣的影響。本文將探討的就是危險天氣區域下的航班改航路徑規劃。

二、人工勢場法路徑規劃

人工勢場模型人工勢場法由Khatib 1986年提出的一種虛擬力法，起初只是為了解決機械手臂在移動抓取物體的時候，能夠不碰到工作臺。他的基本思想是把機器人在周圍環境中的運動，設計成一種抽象的人造引力場中的運動，目標點對移動機器人產生“引力”，障礙物對移動機器人產生“斥力”，最后通過求合力來控制移動機器人的運動。后來該方法在移動機器人上應用也有很好的效果，能產生出非常平滑的運行軌跡。人工勢場法的基本思想是在環境中建立目標位置引力場和受限區周圍斥力場共同作用的人工勢場，搜索勢函數的下降方向來尋找無碰撞路徑。引力和斥力的合力作為移動物體加速力來控制移動物體的運動方向和計算移動物體的位置。該方法結構簡單，在實時避障和平滑控制軌跡方面得到了廣泛的運用。在采用傳統人工勢場路徑規劃模型進行航空器改航路徑規劃時，在狹窄區域容易發生振蕩現象，導致航空器左右來回運動，造成了規劃的不穩定。人工魚群算法人工魚群算法是一種群智能多點并行搜索優化算法。該算法的主要特點是不需要了解問題的特殊信息，只需要對問題進行優劣的比較，有著較快的收斂速度，具有克服局部極值獲得全局極值的能力。王飛等將該算法應用機著落排序問題和地面等待策略問題，取得了較好的應用效果。通過構造單個人工魚來控制人工勢場函數的參數，調用改進人工勢場模型進行改航路徑規劃，生成多條改航路徑，利用適應度函數對生成的改航路徑進行評估，通過算法的覓食、聚群、追尾等行為的選擇，選出適應度好的人工魚參與下一組魚群的進一步計算，通過隨機行為可以在新的空間進行新一輪的搜索，最終生成最優的改航路徑。

如事例1、某航班執行成都—西寧航線，由于西寧機場雷雨天氣備降蘭州。飛機在蘭州落地之后，西寧天氣好轉，雷暴向東移出本場，往蘭州機場方向移動，正好在蘭州到西寧的航路上，且范圍較廣。考慮到蘭州到西寧的航線距離較近，不到150公里，且該航路標高較高，地形較復雜，飛機起飛后繞飛困難等因素，通過對天氣演變趨勢的詳細研究，制定詳細的繞飛計劃和帶夠足夠的繞飛油量后，再次放行飛往西寧。

事例2、某航班執行成都—張家界航線，在飛機進入長沙管制區后，由于航路上有大面積雷暴區，使得飛機繞飛比較困難，而且機載油量有限，備慶。最終由于該天氣系統往張家界機場方向發展，時間較長，且考慮到該機場是特殊機場，取消該航班。

事例3飛行受限區域昆明到貴陽航線所經航路點為： 昆明（ KMG） - 過馬河（SL）- P72- 貴陽（KWE）； 通過 Mercator投影建立經緯度與X - Y 軸的投影關系，則KMG、SL、P72、和 KWE在該平面直角坐標系中坐標分別為 （ - 124. 8 220，64. 2 764）、（ - 118. 6 788，68. 3 736）、（ - 103. 9 652，71. 6 366） 和（ - 82. 2 684，76. 8 524）。根據天氣預報生成飛行受限區域，圖 1 中陰影部分為雷暴云團 A、B、C。假設雷暴云團 A向東北方向以 40 km /h的速度勻速漂移，云團的形狀、面積和強度保持不變；云團 B繞云團幾何中心旋轉，云團 C處于擴張階段。

圖 1 飛行受限區域

優化后的改航路徑利用人工勢場- 人工魚群算法，得到優化的改航路徑。

如圖 2、圖 3所示。

圖 2 優化的改航路徑

圖 3 路徑規劃中的航線角度

改航路徑的修正通過對轉彎角度較大的改航路徑點的判斷，來確定分段點，從而將初始的改航路徑分成 7段進行線性擬合，并計算出擬合后 7段航線的交點，將交點順次連接，生成擬合的改航路徑。

圖 4 分段擬合后生成的改航路徑

如圖 4中實線所示。由于在第 6航段不滿足與受限區的最小距離的約束，所以需要進一步修正。具體如下： 將圖 4中的航段 1、2、3，截彎取直，合并為如圖 5中的第 1航段，原航段 4改為第 2航段，將原航段 5、6合并為第 3航段，原航段 7變為第 4航段，如圖 5所示。經驗證修正后的改航路徑，滿足約束條件，這樣就得到最終的改航路徑。

參考文獻

[1] 謝春生，李雄. 危險天氣影響航路飛行區域的劃設及評估[J]. 中國安全科學學報. 2010（10）

[2] 張靜，徐肖豪，王飛. 天氣影響的機場容量概率分布[J]. 南京航空航天大學學報. 2011（01）

篇（7）

加載規劃求解功能

在Excel2003版本中，通過點擊菜單“工具宏加載宏”，加載規劃求解加載項，便可加載該宏。在Excel2007版本中，通過點擊Office按鈕，點擊“Excel選項加載項轉到Excel加載項”，然后加載規劃求解加載項，便可以加載規劃求解的宏。在Excel2010版本中，通過點擊“文件”選項卡打開“Excel選項”對話框，單擊左側“加載項”標簽，在右側單擊“轉到”按鈕，打開“加載宏”對話框，勾選“規劃求解加載項”復選框，單擊“確定”按鈕，即可在工具欄的“數據”選項卡中出現“分析”選項組，菜單上面就有了“規劃求解”按鈕。

案例

王老師從學校A到學校I參加會議，途中需要經過一些學校，學校之間的距離和線路已在圖1中標明，請幫王老師規劃一下，在不影響去學校I最短距離的情況下，順便探訪其他學校，請將路線描述出來。

1.Dijkstra算法描述及C語言函數實現

為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。即如果存在一條從i到j的最短路徑（Vi...Vk，Vj），Vk是Vj前面的一個頂點，那么（Vi...Vk）也必定是從i到k的最短路徑。例如，對于源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那么通過已知可得從V0到Vj頂點的最短距離dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根據這種思路，假設存在G=，源頂點為V0，U={V0}，dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點。那么可從V-U中選擇使dist[i]值最小的頂點i，將i加入到U中；更新與i直接相鄰頂點的dist值（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）；直到U=V，停止。

/*Dijkstra算法代碼C語言實現：*/

void DijkstraPath（MGraph g，int *dist，int *path，int v0） //v0表示源頂點

{

int i，j，k；

bool *visited=（bool *）malloc（sizeof（bool）*g.n）；

for（i=0；i

{

if（g.matrix[v0][i]>0&&i！=v0）

{

dist[i]=g.matrix[v0][i]；

path[i]=v0； //path記錄最短路徑上從v0到i的前一個頂點

}

else

{

dist[i]=INT_MAX； //若i不與v0直接相鄰，則權值置為無窮大

path[i]=-1；

}

visited[i]=false；

path[v0]=v0；

dist[v0]=0；

}

visited[v0]=true；

for（i=1；i

{

int min=INT_MAX；

int u；

for（j=0；j

{

if（visited[j]==false&&dist[j]

{

min=dist[j]；

u=j；

}

}

visited[u]=true；

for（k=0；k

{

if（visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]

{

dist[k]=min+g.matrix[u][k]；

path[k]=u；

}

}

}

}

2.Excel“規劃求解”功能實現最短路徑

（1）可將學校A到學校I的距離與邏輯關系通過以下表表示。

（2）新建工作簿，將上表各節點的邏輯關系用下Excel工作表表示（如圖2）。

“節點關系”這一欄僅用于描述各節點之間的關系，僅以B點來說（+代表此點出發，-代表以此點進），進入方向為A，出發為C、E、F。所以B=-AB+BC+BE+BF，以此類推。真正反映數量關系的是F欄的“數量（邏輯關系）”，同樣以B節點為例，F19中公式關系是=-D18+D21+D22+D23，通過D欄各線段是否在最短路徑（o表示“不在”，1表示“在”）上，迭代產生。最短路徑設置在G31，使用公式“=SUMPRODUCT（C18：C31，D18：D31）”，通過對D欄、F欄進行規劃求解來設置相應的約束條件以生成最短距離。

3.規劃求解

點擊“數據規劃求解”，目標單元格G31為最短路徑，通過函數SUMPRODUCT（C18：C31，D18：D31）進行求和。因為選取的是最短路徑，所以在“最小值”選項打標記。從下頁圖3可看出規劃求解通過調整所指定的可更改的單元格（可變單元格）D18：D31中的值，可以從目標單元格公式中求得所需的結果。約束條件是在D18：D31中只能是0、1的兩種，結束條件是節點條件的取值與目標值對應。

由于規劃求解過程是一個迭代過程，有的值可能達到1E-9左右，約為0，將“是否為最短路徑”和“數量（邏輯關系）”設置成數值格式，并取消“小數位”。

從上例創建模型的過程中，我們看到可以對規劃求解模型中的可變單元格數值應用約束條件（約束條件：“規劃求解”中設置的限制條件），約束條件可以引用其他影響目標單元格公式的單元格的值。

Excel不僅是一個小型的數據庫軟件，更是一個操作極為方便的工作數據表，幾乎能勝任數據處理的各種要求，功能強大、使用靈活。讓我們共同使用好Excel，提高工作效率。

資訊

便攜辦公利器——華碩PU500商務筆記本

全能輕薄的商務本

華碩PU500作為主流15.6英寸商務本，重量為1.96Kg，厚度只有22mm，擁有深色發絲拉紋設計。屏幕采用防眩光霧面屏。電源適配器體積比傳統適配器小20%，加入電源插接報警，當適配器插頭未完全插入時系統會自動彈出窗口報警，保護電腦安全。

動力強勁的商務本

華碩PU500采用i5-3317U處理器，配備4GB DDR3 1600MHz內存，Intel? HD Graphics 4000顯示芯片。PU500采用“SSD+HDD”的混合硬盤模式（選配），既保持了SSD快速讀取的優勢，又具有傳統機械硬盤的超高性價比。

接口配備齊全包括兩個USB2.0接口、一個支持關機充電的USB3.0接口，同時還配備投影展示常用的VGA視頻輸出接口，HDMI等接口。

最為安全的商務本

篇（8）

中圖分類號：TP39文獻標識碼A文章編號1006-0278（2013）06-172-01

一、引言

隨著虛擬現實技術的日益成熟，只有景色、建筑物等一般視景信息的虛擬場景已不能滿足人們的視覺需求，迫切需求一個有生命的對象引入到虛擬場景中，增加瀏覽者的沉浸感。虛擬場景中虛擬人的路徑規劃是虛擬現實研究中的一項關鍵技術。目前，研究者們已經把研究的重心放在如何為虛擬人規劃出一條行走的最優路徑，使虛擬人的路徑導航更具有真實感和可信度。

由于虛擬環境中的模型多由三角面網格組成，通過使用基于空間多層次劃分的八叉樹方法，充分發揮了其空間劃分的優勢，加快了場景的渲染速度，減少了確定對象的處理時間以及存儲空間①。

文章采用八叉樹和A*算法相結合的方法，對路徑進行規劃，并對A*算法做了改進，以適應八叉樹的存儲結構。

二、密集型區域八叉樹劃分算法

八叉樹是由四叉樹推廣到三維空間而形成的一種三維柵格數據結構，它作為一種場景組織方法，廣泛應用于虛擬現實系統，可顯著減少對場景中多邊形進行排序的時間。

由于傳統八叉樹對空間的劃分是均勻的，導致了最終生成一個結構不平衡的八叉樹，從而增加整個八叉樹的存儲空間以及各結點的遍歷時間。文章采用了對傳統八叉樹算法進行改進，采用基于密集型區域八叉樹劃分方法。密集型區域八叉樹的網格劃分算法是對每一子空間重新建立最小包圍盒，這樣避免了在建立頂點樹時，由于該部分頂點在空間上分布不均勻而導致樹的深度的增加，進而減少了存儲空間，加快了網格模型數據的讀取速度。另外，由于建立了頂點的最小包圍盒，在誤差較小時，只有空間距離比較近的頂點才會聚合在一起；而相距較遠的頂點只有在深層次簡化時才會聚合，這些特點在一定程度上保證了簡化時網格模型的逼真度。

密集型區域八叉樹劃分方法的算法描述如下：

步驟1使用OBB包圍盒方法建立模型的最小包圍盒。

步驟2以包圍盒的X軸、Y軸、Z軸方向的中分面作為分割基準，將包圍盒平均劃分為八個子包圍盒。

步驟3如果每個子空間內存在物體的屬性不相同或未達到規定的限差，則重新從步驟1開始進行劃分。否則，劃分結束，并對劃分后的每一個結點記錄下結點編號、劃分標志、結點在頂點樹中的深度以及它所含的景物面片表的入口指針。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。該算法的創新之處在于選擇下一個被檢查的節點時引入了已知的全局信息，對當前節點距終點的距離做出估計，作為評價該節點處于最優路線上的可能性的量度，這樣就可以首先搜索可能性較大的節點，從而提高了搜索過程的效率。

下面是對A*算法的介紹，我們首先來介紹一下啟發式搜索中的估計函數。因為在啟發式搜索中，對位置的估價是十分重要的。估價函數的表示如下：

其中是節點的估價函數，是已知的，指在狀態空間中從初始節點到節點的實際代價；是從結點到目標節點最佳路徑的估計代價，它體現了搜索的啟發信息，啟發信息決定著算法的啟發能力。啟發信息越多，估價函數就越好，即約束條件越多，則排除的節點就越多，說明這個算法越好。這種做法存在一個平衡的問題，也會使算法的準確性下降。具體的說，代表了搜索的廣度優先趨勢，當時，可以省略，這樣就提高了搜索效率。

A*算法是一個可采納的最好優先算法。A*算法的估價函數可表示為：

這里，是估價函數，是起點到終點的最短路徑值，是到目標的最短路經啟發值。由于這個其實是無法預先知道的，所以我們用前面的估價函數做近似。代替，但需要滿足（在大多數情況下都滿足時，可以不用考慮）。代替，并滿足。可以證明應用這樣的估價函數是可以找到最短路徑的。

四、基于密集型區域八叉樹的A*算法改進

由于使用八叉樹存儲結構存儲的環境地圖擴展步長不一致，采用傳統的A*算法效率較低，因此對A*算法做了改進，以適應八叉樹結構的搜索。改進的辦法是從葉節點開始搜索并為Open表設置兩個優先隊列，命名為隊列1和隊列2（隊列1中存放的節點總是高于隊列2），在兩個隊列中分別存放相鄰層次的全部節點，層次越高的優先級越高。通過這種分層次的搜索，也大大縮小了搜索的空間并縮短了搜索時間，這樣一來大大提高了搜索效率。

五、結束語

篇（9）

一、本文就常見的幾種常見的路徑規劃算法及應用進行簡單的探討如下：

（一）遺傳算法概念

遺傳算法是根據達爾文的進化論，模擬自然選擇的一種智能算法，“適者生存”是它的核心機制。遺傳算法是從代表問題可能潛在解集的一個種群開始的。基于隨機早期人口，根據的原則，優勝劣汰，適者生存，世代演化產生更好的人口大概。在每一代，根據問題域的個體適應度大小來選擇個人，然后選定的個人在自然遺傳學，遺傳算子組合交叉和變異，產生代表性的解集的人口 。通過這些步驟，后生代種群比前代對于環境具有更好的適應性。人口最優個體解碼后可作為近似最優解。

（二）遺傳算法的特點

作為一種智能算法，遺傳算法具有如下特點：①遺傳算法在尋優過程中，只把適應度函數的值作為尋優判據。②遺傳算法是由一個問題集合（種群）開始的，而不是從一個個體開始的。故而遺傳算法的搜索面積很大，適合全局尋優。③遺傳算法根據概率性的變換規則進行個體的優勝劣汰并推動種群的進化。④遺傳算法具有隱含的并行性。⑤遺傳算法具有自組織、自適應以及內在的學習性，同時遺傳算法具有很強的容錯能力。⑥遺傳算法的基本思想簡單。對于復雜的和非線性的問題具有良好的適應性。

（三）遺傳算法的應用

遺傳算法提供了一個整體框架地址復雜系統問題，它不依賴于俞特定領域的問題，問題的類型、 已是強的魯棒性，所以廣泛應用余許多科學： 功能優化遺傳算法的經典應用，是遺傳算法的性能評價的常見的例子，許多人建設的各種復雜的表格功能測試： 連續函數和離散函數，凸、 凹函數、 低維功能和高尺寸功能、 單式功能和更多峰值函數。一些非線性、 多模型、 多目標函數優化問題和其他優化方法很難解決，GA 你可以更好的結果。增加問題的規模，搜索空間的組合優化問題，將會迅速增加，有時的當前枚舉方法和計算很難找到最佳的解決方案。實踐證明，遺傳算法、 組合優化問題的粒子非常有效。例如，已成功應用遺傳算法解決旅行商問題、 背包問題、 裝箱問題、 圖形劃分問題。此外，遺傳算法的生產調度、 自動控制、 機器人技術、 圖像處理和機器學習，人工生命，遺傳編碼，已獲得廣泛的應用。

二、蟻群算法及其應用

（一）蟻群算法概念

蟻群算法又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，靈感來源于螞蟻在尋找食物過程中發現路徑的行為。蟻群算法是一種模擬進化算法。

（二）蟻群算法的特點

①蟻群算法是一種自組織算法。在早期的算法，單一的人工螞蟻障礙找到求解算法，久而久之，通過信息作用的激素，人工螞蟻進化將找到一些解決辦法更接近最優的解決方案，它是無序到有序的過程。

②蟻群算法的并行算法是一種基本的。每個蟻群搜索進程獨立的對方，只能通過信息素通訊。因此，蟻群算法可以看作是一種分布式的多智能體系統，它在問題空間搜索算法開始是一個獨立的解決方案，不僅提高了可靠性，這使得該算法具有強的全局搜索能力。

③蟻群算法是一種積極的反饋的算法。從螞蟻覓食中不難看到螞蟻已設法找到最短路徑的信息的過程取決于直接上的最短路徑的積累，以及信息素的積累是一個積極的反饋過程。這種正反饋的過程進行初步的差距有不斷擴大，并導致系統的最優解的方向發展。

④蟻群算法具有較強的魯棒性。比較與其他算法、 蟻群算法、 初始對齊要求不高，外務大臣蟻群算法用于路由和搜索過程的初步結果不需要手動調整。第二，設立簡單、 便于應用的蟻群算法求解組合優化問題的蟻群算法參數的殖民地，數目。

（三）蟻群算法應用

蟻群算法應用包括：二次分配問題、車間任務調度問題、車輛路線問題、機構同構判定問題、學習模糊規則問題、旅行社新旅游線路與旅行產品的制作等領域。

三、神經網絡算法

（一）神經網絡的概念

人工神經網絡也被稱為神經網絡連接模式，它是一種動物模型，神經網絡的行為特征，分布式并行處理算法的數學模型。網絡依賴于復雜的系統，通過調整內部之間的聯系，大量節點，以實現節能的目的，信息處理。

特征的神經網絡模型的人工神經網絡的主要網絡連接拓撲，神經元的特點，學習規則。目前，近40種神經網絡模型，其中有一個BP網絡，傳感器網絡，自組織映射，神經，波爾茲曼機，自適應共振理論。系統的穩定性與聯想記憶功能密切相關。

神經網絡的應用

篇（10）

近年來電力系統變革迅速，隨著環境保護意識的增強，電網空間規劃需要解決新的挑戰，這些新挑戰主要包含如下幾點：決策分散性使得電網規劃協調難度增加；光伏、風電等分布式能源的接入使得電網規劃出現了越來越多的不確定性；電網的規劃、電網建設模型以及求解受到環境等方面的變換影響很大。

1 傳統算法及原理

（1）運用遺傳計算方法II、經絡和round模擬技術，考慮風電接入等效應。（2）采取基于混合整數的多種線性規劃方法對目前市場下長期多目標的電網規劃問題進行解決。（3）從新定義碳的排放以及預測的模型，根據動態碳排放量建立電網規劃的模型。（4）制定環境友好型的電網規劃，建立雙重指標體系與相關評估模型，從而對局勢進行協調與求解。（5）建立惡意攻擊或撞擊的模擬模型，電網的擴展方式以風險大小為依據。同時，考慮各方面的成本因素，將電網規劃、線路路徑優化等方法與原有方法進行相互比較，可以獲得一種新型電網規劃方法。

以上方式仍然存在弊端：拘束條件“維數災”，方法的提出僅僅可以解決小范圍內電網在空間規劃的問題；忽略了電網損壞造成的損失；變電站位置的選擇沒有考慮在內。根據存在的弊端，本文建立了新的模型。傳統的分析方法是分析上層規劃及排列形式，但是下層要解決的關鍵在于線路路徑的優化方面。此模型提出的遺傳算法以及運用的動態規劃法在相互結合的情況下，可以有多種優化方法。遺傳算法具有比較廣的適應性以及比較強的魯棒性，可以和其它算法相互結合，從而為電網規劃問題提供合適的算法。采用動態規劃法對路徑優化問題進行求解，可以充分利用其速度快和精確度高的計算特點。當兩種方法結合，可以將其最大計算優勢發揮出來，從而實現空間電網規劃求解質量與效率的有效提高。

2 空間電網規劃采用的“位置圖像柵格化表示”

通過應用文獻，能夠把帶有環境的信息地圖進行劃分為NR×NC 的柵格圖表，其中根據排列組合知Ci，j 含義為第i 行的第j 列的數字。假定其中有一柵格，在N個柵格當中，可以采取神經網絡方法或者模式識別法來對柵格線路路徑的相關耗資成本進行計算，同時可以根據實際情況進行更正完善。

路徑通過一個柵格，能夠通過往鄰近柵格方向移動，移動柵格數量為8，標注柵格用來表示八個柵格的移動方向，兩個柵格間距為

。它們分別代表水平間距以及高差。

研究地圖格柵化模型，根據其相似性可以將其引用到電網建設上來，進而通過格柵的排列組合運算來計算電站綜合成本，計算出新建變電站的綜合成本。格柵化模型可以作為核算成本的一個重要模型。

3 新模型理論基礎“空間的電網規劃方式”

3.1 空間電網上層問題分析

首要問題是為新模型制定目標結果函數，由于空間電網規劃屬于上層問題，也就是傳統電網規劃問題，為的是確立即將進行建設的候選線路以及變電站位置。因此首先需要滿足電網對電荷載的承載，其次考慮運營和投資建設成本最優化。上層問題解決目標函數，根據邏輯運算關系可以得到：

其中：e年均電價格；Tmax 損耗的最大荷載的時長以小時為單位；t 為年度index；NT 投資年回收限制； 為年收益率；Ploss 為有功網損；Nw 為新建變電站數目；w 為新建變電站索引；（iw，jw）表示變電站建設在Ciw， jw上；F2 為線路投資成本，由下層問題得到。

3.2 滿足條件

（1）功率平衡原理公式

其中：n 、m 是節點index；Pn 和Qn 分別是節點n 的有功W和無功W注入；Gnm 和Bnm 分別是節點的導納陣中的電導以及電納；Wnm 是節點角度差。

（2）潮流等式（線路）

式中：l 為支路index；Pl、Ql 和Sl 分別為支路l 上的有功W、無功W和視在W；UlF和UlT分別為支路l 首末節點電壓；Rl 和Xl 分別為支路l 的電阻和電抗；Gl 和Bl 分別為支路l 的對地電導和電納；lFlT為支路l 首末節點之間的相角差。

（3）節點電壓約束

式中：NB 為候選線路數目，候選線路的索引范圍為1lNB；NS 為已有支路數目，已有支路索引范圍為NB

3.3 空間電網規劃下層問題分析

確定最終計算下次函數式為首要問題。對下層問題進行解決，就是要對線路路徑優化進行解決，最終是為了得到最小化每條線路耗費的成本，如下方程式所列。

l {（i， j，d）如果線路l在Ci， j上選擇方向d}

其中：

l 為線路l 選中柵格及其上方向的集合；Di，j，d為線路在柵格Ci，j 方向d 上的長度。

3.4 限定條件

（1）路徑參數公式

其中：Rl，0 和Xl，0 分別代表線路l 單位長度線路的電阻以及電抗值；Gl，0 和Bl，0 分別代表線路l 中單位長度對地電導和電納值；sl 為線路l 的長度。

（2）柵格上投建線路條數約束

式中：zl，i，j 表示線路l 是不是經過Ci，j，1 表示是經過，0表示不是經過；Zi，j 為Ci，j 可以投建的線路條數的最多數。上下層的問題是通過限制（4）、（5）、（10）和（11）條件進行結合的，它代表的意思即上層問題判別候選路徑能否運營。

憑借限定條件可以確立電站的位置，也就是說通過它可以判定線段的端點；候選線路與相關線路端點的投建主要由上層決定，而下層的解決對象即基于前者而滯留的線路路徑優化，以進行最合適路徑的選取以及建設成的電氣相關參數的大小調整。

3.5 新模型計算方法

引入混合優化算法，用遺傳算法確定選址，同時結合動態算法來運算，以達到優化路徑的目的。所以，需要不斷運用動態算法，柵格多時候會導致計算變慢。如果端點不變，路徑也不會變，從而最優化路徑就不變。因此，通過增加記憶體，使得算法在經常計算的路徑里保持紀錄路徑。通過紀錄路徑要素，來完成記憶提的作用。優化路徑有利于進一步節約計算所需要的時間，效率可以得到提高，采用記憶機制來完成計算的路徑優化和快速計算。分析采用這種方式跟實際情況的差別，可知因電網的規劃采用的離線變量分析方法，所以不要求及時算出結果，雖然計算耗費了時間，但是這種算法比較符合實際情況。

4 結論

通過比較老式算法與新算法的差別，本文歸納出的空間電網合理規劃方法可以獲取比較精確而且更加合理的規劃結果，通過計算比較，有以下幾條結論：

（1）柵格之間高度的差值對會影響到規劃電網，所以只有將二維電網轉化成三維電網才更合理、更貼近實際。

（2）線路的優化、網架優化以及變電站位置的選取可以在很大程度上影響電網的投資及成本，三方面的完善有利于獲取更優的規劃結果。

（3）記憶的引入和新方法的提出可以解決比較大規模空間的電網規劃問題，使得規劃方式更合理、更優化。