引論：我們為您整理了13篇路徑規劃典型算法范文，供您借鑒以豐富您的創作。它們是您寫作時的寶貴資源，期望它們能夠激發您的創作靈感，讓您的文章更具深度。

篇1

實際應用當中，AGV的工作路徑隨著不同工廠的環境條件和規劃可能各不相同。

圖1.1中AGV軌道模型，圖中圓圈內的數字代表該位置的站點號，直有向線代表直線軌道，彎曲的有向線代表半圓軌道，線上的數值代表其長度或者半圓的半徑。圖1.1所示顯然為一個有向賦權圖，記為G（V，E），V為圖中所有站點的集合，顯然非空，E為任意站點Vi到另一站點Vj的邊的集合。

2.AGV調度問題研究

2.1單個AGV路徑規劃算法

單個AGV的調度問題可以簡化為AGV的路徑規劃問題，即等價為求最短路徑問題。

Dijkstra算法是一種用于計算有向圖中一個節點到其他所有節點最短路徑的典型圖形搜索算法。其時間復雜度O（V2+E）～O（VlgV+E）取決于是否采用最小優先級隊列。

實現的具體方法，即當不用隊列而用數組實現時為O（V2），用二叉最小堆來實現時為：

O（（V+E）lgV），用Fibonacci堆來實現時為：

O（VlgV+E）。采用Fibonacci堆使算法的運行時間性能相比于O（V2）雖然有一些提高，但是編程時由于其常數較大，多數時候會發現其實際運行速度并沒有明顯的提高，并沒有多大的效率優勢。算法具體步驟為：

1）分組初始化，集合S中只有源節點v0，T由除V外的剩余節點組成。根據圖的信息初始化各個節點的鄰接關系和權值。

2）從T中選取與v0有鄰接關系且權值最小的頂點Tp，把Tp又加入到S中（v0到Tp的最短路徑值即為其權值大小，最短路徑為v0Tp）。

3）以Tp為中間節點，考察T中與Tp鄰接的節點。如果從源節點v0經過Tp到T中節點的距離比不經過Tp時距離短，則修改T中已比較過的頂點的路徑值為經過Tp的路徑。

4）判斷T是否為空，或者源頂點到目的頂點的最短路徑是否已經找到，若沒有則

重新返回步驟2再次尋找。否則，推出循環，算法結束。

2.2 多個AGV路徑規劃算法

協調各個AGV之間能夠無碰撞地高效完成其工廠里的作業任務，是多AGV調度系統的主要任務。相向沖突、站點沖突、拐角沖突、趕超沖突是多AGV運行過程中常見的幾種基本沖突。多AGV的任務調度問題的典型的有效方法有以下幾種：

（1）基于時間窗的AGV無碰撞路徑規劃

針對每段路徑引入時間窗來指示該路段在某段時間是否已經被AGV占用，根據接受任務的優先級依次分配空閑的AGV，并利用算法選擇最優路徑，并產生各路徑的時間窗。

（2）混合區域控制模型調度方法

通過對AGV的工作空間進行按不同的區域建模，AGV作業于不同區域內，且一個區域中最多只有一臺AGV位于其中。

（3）線段網絡控制調度算法通過把AGV小車的路線分為可進行控制的若干條路段，當小車將要或已經在一個路段上行駛時，AGV調度系統將這個路段及其終點分配給該AGV，當AGV行駛離開此路段的起始點一定距離后，系統又將該路段釋放。

（4）兩階段控制調度算法

將AGV的調度控制系統分為離線路徑表的生成和在線交通控制兩個模塊，其中離線路徑表生成模塊根據路徑網路模型離線生成各結點間的所有路徑，而在線交通控制模塊根據下達的任務和工作中AGV的運行信息利用路徑庫中的路徑表生成無沖突的最佳路徑。

兩階段控制算法，利用已知信息先離線生成路徑庫，能很好的減少在線階段的運行負擔，提高系統實時性，且分階段的控制方法使得實現和優化改進更簡單。但是該算法生成的不是各結點的k條最優路徑，當某個路段堵塞時，又要附加約束條件在線重新生成最優路徑，使得效率反而更差。因此提出離線階段對每個頂點生成k條最短路徑集，以改進兩階段控制算法。

3 AGV調度算法算法分析與實現

（1）流程分析

假設AGV任務離線批量下發，本系統基于改進的兩階段控制算法的流程圖設計如圖3.1所示。正如圖3.1所示，路徑規劃工作大部分靜態工作如最優路徑的生成等由調度系統離線階段完成，而系統在線階段主要負責動態的狀態監控和資源的管理以及進行突況處理。突況下如果下位機可以采用一般的等待策略解決，則調度系統只負責路徑資源時間窗的更新即可；若發現等待超時，即視為不能解決，則需以當前站點為起點重新為該任務進行路徑規劃。

在任務下發后，AGV開始執行任務，AGV執行任務過程中的避障策略算法如圖圖3.2所示。AGV根據調度系統對任務的路徑規劃，從起點開始不斷檢測障礙物和沖突以確定是否進行下一步。當遇到沖突時，首先自行進行等待處理，若調度系統發現等到時間過長而超時會對任務進行重新路徑規劃并發送任務的更新命令，AGV接收到該命令后會終止當前流程重新任務的執行。同時，AGV會定時不斷的向監控調度系統更新AGV自身的狀態信息，供調度系統決策使用。

結論

篇2

在移動機器人導航技術應用過程中，路徑規劃是一種必不可少的算法，路徑規劃要求機器人可以自己判定障礙物，以便自主決定路徑，能夠避開障礙物，自主路徑規劃可以自動的要求移動機器人能夠安全實現智能化移動的標志，通常而言，機器人選擇的路徑包括很多個，因此，在路徑最短、使用時間最短、消耗的能量最少等預定的準則下，能夠選擇一條最優化的路徑，成為許多計算機學者研究的熱點和難點。

2 背景知識

神經網絡模擬生物進化思維，具有獨特的結構神經元反饋機制，其具有分布式信息存儲、自適應學習、并行計算和容錯能力較強的特點，以其獨特的結構和信息處理方法，在自動化控制、組合優化領域得到了廣泛的應用，尤其是大規模網絡數據分析和態勢預測中，神經網絡能夠建立一個良好的分類學習模型，并且在學習過程中優化每一層的神經元和神經元連接的每一個節點。1993年，Banta等將神經網絡應用于移動機器人路徑規劃過程中，近年來，得到了廣泛的研究和發展，morcaso等人構建利用一個能夠實現自組織的神經網絡實現機器人導航的功能，并且可以通過傳感器訓練網絡，取得更好的發展，確定系統的最佳路徑。神經網絡拓撲結構模型可以分為：

2.1 前向網絡

網絡中各個神經元接受前一級的輸入，并輸出到下一級，網絡中沒有反饋，可以用一個有向無環路圖表示。這種網絡實現信號從輸入空間到輸出空間的變換，它的信息處理能力來自于簡單非線性函數的多次復合。網絡結構簡單，易于實現。反傳網絡是一種典型的前向網絡。

2.2 反饋網絡

網絡內神經元間有反饋，可以用一個無向的完備圖表示。這種神經網絡的信息處理是狀態的變換，可以用動力學系統理論處理。系統的穩定性與聯想記憶功能有密切關系。Hopfield網絡、波耳茲曼機均屬于這種類型。

3 基于人工神經網絡的移動機器人路徑規劃算法

神經網絡解決移動機器人路徑規劃的思路是：使用神經網絡算法能夠描述機器人移動環境的各種約束，計算碰撞函數，該算法能夠將迭代路徑點集作為碰撞能量函數和距離函數的和當做算法需要優化的目標函數，通過求解優化函數，能夠確定點集，實現路徑最優規劃。神經網絡算法在移動機器人路徑規劃過程中的算法如下：

（1）神將網絡算法能夠初始化神經網絡中的所有神經元為零，確定目標點位置的神經元活性值，并且能夠神經網絡每層的神經元連接將神經元的值傳播到出發點；

（2）動態優化神經網絡，根據神經網絡的目標節點和障礙物的具置信息，在神經網絡拓撲結構中的映射中產生神經元的外部輸入；

（3）確定目標值附件的神經元活性值，并且使用局部側的各個神經元之間，連接整個神經網絡，并且在各個神經元中進行傳播。

（4）利用爬山法搜索當前鄰域內活性值最大的神經元，如果鄰域內的神經元活性值都不大于當前神經元的活性值，則機器人保持在原處不動；否則下一個位置的神經元為鄰域內具有最大活性值的神經元。

（5）如果機器人到達目標點則路徑規劃過程結束，否則轉步驟（2）。

4 基于人工神經網絡的移動機器人路徑規劃技術展望

未來時間內，人工神經在機器人路徑規劃過程中的應用主要發展方向包括以下幾個方面：

4.1 與信息論相融合，確定神經網絡的最優化化目標解

在神經網絡應用過程中，由于經驗值較為難以確定，因此在神經網絡的應用過程中，將神經網絡看做是一個貝葉斯網絡，根據貝葉斯網絡含有的信息熵，確定神經網絡的目標函數的最優解，以便更好的判斷機器人移動的最佳路徑。

4.2 與遺傳算法想結合，確定全局最優解

將神經網絡和遺傳算法結合起來，其可以將機器人的移動環境設置為一個二維的環境，障礙物的數目、位置和形狀是任意的，路徑規劃可以由二維工作空間一系列的基本點構成，神經網絡決定機器人的運動控制規則，利用相關的神經元的傳感器作用獲未知環境的情況，將障礙信息和目標點之間的距離作為神經網絡的輸入信息，使用遺傳算法完成神經網絡的權值訓練，神經網絡的輸出作為移動機器人的運動作用力，實現一個可以在未知環境中進行的機器人運動路徑規劃。

4.3 與蟻群算法相結合，降低搜索空間，提高路徑規劃準確性

為了提高神經網絡的搜索準確性和提高效率，可以將蟻群算法與神經網絡相互結合，蟻群算法的路徑規劃方法首先采用柵格法對機器人工作環境進行建模，然后將機器人出發點作為蟻巢位置，路徑規劃最終目標點作為蟻群食物源，通過螞蟻間相互協作找到一條避開障礙物的最優機器人移動路徑。

5 結語

隨著移動機器人技術的發展，路徑規劃作為最重要的一個組成部分，其得到了許多的應用和發展，其在導航過程中，也引入了許多先進的算法，比如神經網絡，更加優化了移動的路徑。未來時間內，隨著神經網絡技術的改進，可以引入遺傳算法、信息論、蟻群算法等，將這些算法優勢結合，將會是路徑規劃更加準確和精確。

參考文獻

[1]朱大奇,顏明重,滕蓉. 移動機器人路徑規劃技術綜述[J].控制與決策,2010,25(7): 961-967.

[2]劉毅.移動機器人路徑規劃中的仿真研究[J].計算機仿真,2011,28(6): 227-230.

[3]熊開封,張華.基于改進型 FNN 的移動機器人未知環境路徑規劃[J].制造業自動化,2013,35(22): 1-4.

[4]柳長安,鄢小虎,劉春陽.基于改進蟻群算法的移動機器人動態路徑規劃方法[J].電子學報,2011,39(5).

篇3

一、對最佳路徑的分析

配電網故障區域恢復供電的最佳路徑事實上是在故障情況下的配電網絡重構。主要的目的在于，能夠快速的將非故障區域供電恢復，與此同時，還能夠有效的滿足線路負載容量的要求以及線損最小等各個方面的條件。現階段，在配網自動化領域中研究最多的在于怎樣能夠快速的實現故障隔離以及快速的恢復費故障區域的供電技術方法，因此，在恢復路徑的最優化選擇方面出現了較多的研究。

一般而言，配電網故障區域恢復供電的路徑為多目標最佳路徑問題，現階段在最佳路徑問題的研究上較多的便是城市交通網絡中的最短路徑問題的研究。由于問題解決的思路存在著極大的不同點，因此最短路徑問題能夠被分為單元最短路徑算法與基于啟發式搜索最短路徑算法[1]。這與鄧群，孫才新，周駁仍凇恫捎枚態規劃技術實現配電網恢復供電》一文中的觀點極為相似。其中，單元最短路徑算法主要體現在幾個方面，即：

第一，在GIS空間查詢語言方面的最短路徑。該職工路徑的研究方法在當前還停留在理論研究方面，例如在MAX中定義了一套空間查詢語言，該套語言對其完備性給予了相關證明，同時通過舉證的方式，對范圍查詢與時態查詢等進行了應用分析。

雖然，對于GIS空間發展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數據庫技術發展的制約與影響，導致實際的應用領域和背景的不同，使其和商用之間還有很長的一段距離。

第二，在功能模塊思想路徑方面，需要按照不同的分類方法實施，而單元最短路徑問題的算法能夠被分為很多種，例如神經網絡法與基于人工智能的啟發式搜索算法等，對于不同的背景應用需求和具體軟件應用的環境，各種算法在空間的復雜程度與時間的復雜程度等都有明顯的體現[2]，這與李振坤，周偉杰，錢嘯等在《有源配電網孤島恢復供電及黑啟動策略研究》一文中有著相似的觀點。并且各種算法在故障恢復方法中各具特色。

另外，啟發式搜索最短路徑算法也是一種有效的手段。基于啟發式方向策略最短路徑算法，其中包括空間有效方向的可控參數法，該方法能夠有效的調節相關系數，在有效方向上路徑無效的時候，能夠確保得到有效的路徑。

二、最佳路徑的選擇方法分析

事實上，配電網故障區域恢復供電的最佳路徑并不是簡單的路徑問題，而是多目標最佳路徑問題。為此，在研究配電網非故障區域恢復供電的最佳路徑過程中，需要對其展開綜合的分析。

首先，在多目標分析方面，通常在選擇配電網非故障區域恢復供電最佳路徑的時候，最為重視的目標為：

第一，在恢復供電路徑的過程中，饋線負荷不能過載，同時，還需要確保恢復區域的電壓質量能夠與實際規定的標準要求相吻合。當供電質量可靠性最高的時候，那么恢復的時間將會很短[3]；這與鄧昆英，汪鳳嬌，饒杰等在《智能配電網有功自治互動建模研究》一文中的觀點極為相似。另外，供電過程中，線損最低，證明開關拉合的次數最少，同時現場的操作點也會最少。

第二，在動態規劃技術恢復供電的最短路徑方面需要明確，動態規劃主要是運籌學的一個分支，它是求解決策過程的最優的數學方式。早在很久以前，就已經有研究人員對多階段過程轉化問題轉化為一系列的單階段問題，并且逐一進行求解，這標志著解決這類過程優化問題的新方法的創立，即動態規劃技術。

本文主要將一典型的復雜配電網絡作為研究例子，該連通系包括10個電源點，8個分支點，同時聯絡開關有16個。將其加入到配網潮流方向和典型的運動方式中，將聯絡開關和電源點作為定點，那么可以將其分為26個定點。盡管從數量上頂點比較多，但是由于存在著較為復雜的網絡關系，使得該問題成為一個極為簡單的最短路徑問題[4]。這與楊建在《配電網無功補償系統的關鍵技術研究》一文中的觀點有著相似之處。加之恢復路徑主要指費故障區域相關的聯絡開關與相應路由，為此我們可以將其理解為從不同電源點出發到各個聯絡開關的最短路徑問題，這樣一來，故障恢復工作的實施便簡單的多。

總結

本文主要從兩個方面左手，共同分析了采用動態規劃技術實現配電網恢復供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個方面可以看出，利用動態規劃技術去實現配電網恢復供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網絡還缺少標準的規范要求，導致配電網常常出現一些事故。因此，恢復配電網供電已經成為當務之急。隨著科技的發展，智能配電網已經被廣泛的應用在供電方面，這為平穩供電提供了一定的保障，同時也為恢復配電網故障供電創建了良好的環境與條件等。

參考文獻

[1]鄧群，孫才新，周駁.采用動態規劃技術實現配電網恢復供電[J].重慶大學學報（自然科學版），2006，29（3）：40-44.

[2]李振坤，周偉杰，錢嘯等.有源配電網孤島恢復供電及黑啟動策略研究[J].電工技術學報，2015，30（21）：67-75.

[3]鄧昆英，汪鳳嬌，饒杰等.智能配電網有功自治互動建模研究[J].機電工程技術，2014，（2）：4-7.

篇4

1嵌入式智能機器人路徑技術的研究

智能機器人路徑規劃是指處于有障礙物的工作條件下，如何尋找一條適當的運動路徑（從給定起點到終點），在運動過程中，使機器人能夠安全的規避全部障礙物。

（1）嵌入式智能機器人路徑規劃的發展趨勢

從近些年的研究成果來看，有以下趨勢：第一，以功能或行為為基礎的智能機器熱的路徑規劃。以功能或行為為基礎的機器人具有一種典型的慎思結構，又被稱為基于功能的控制體系結構，其主要內容是基于模型自頂向下的感知、建模、規劃和動作。智能機器人路徑規劃問題，建模時，能夠設置成為有約束性的規劃問題，確保機器人能夠完成路徑規劃、路徑規避和定位等方面的任務。由于不同的機器人掌握信息環境的程度存在差異，可將智能機器人的路徑規劃分為兩種，其一是以傳感器為基礎的局部路徑規劃，具體是獲知了作業環境中的所有信息，主要包括：自由空間法、構型空間法以及神經網絡法等；其二是以模型為基礎的全局路徑規劃，具體是指已經全部獲知或部分獲知作業環境中的信息，主要包括混合法、滾動窗口法、人工勢場法等。第二，神經網絡、模糊控制等一系列算法不斷涌現并相互結合形成新的算法。第三，智能機器人的系統路徑規劃。智能機器人的工作環境逐漸復雜化，再加上工作任務的增加，單智能機器人無法負荷這樣的工作要求。因此，將會出現單個智能機器人路徑規劃與多智能機器人的合作相結合的發展趨勢。

（2）機器人智能規劃中的特點

智能機器人路徑規劃中主要存在以下特點，①復雜性，是指環境復雜，機器人的路徑規劃復雜，且路徑規劃過程中需要很大的計算量支持。②隨機性，是指工作環境的變化復雜，存在較多的不確定因素和隨機性。③約束性，在機器人運動的過程中，其速度、形狀等方面均存在約束。

2智能機器人路徑規劃的算法研究

（1）局部路徑規劃算法研究

1）模糊邏輯控制法

在環境模型不完善的情況下，可以使用模糊邏輯算法。這種算法的推理和計算簡單，對傳感器信息的要求較低，且對機器人的行為有較高的穩定性、一致性以及連續性，能夠有效的解決在路徑規劃過程中遇到的一些問題。雖然這種算法能夠圓滿的解決未知環境下的規劃問題，但仍存在靈活性較差、無法學習的不足之處。

2）遺傳算法

遺傳算法是解決最佳化的搜索方法，屬于進化算法的一種。這種算法最初借鑒了進化生物學中突變、自然選擇、交叉和變異等現象而發展起來的，它采用群體搜索技術，實施選擇、交叉、變異等一系列遺傳操作后，使種群在迭代中不斷進化。這種算法的理論推導簡單，問題的最優解能夠直接得出。遺傳算法的基本思想是路徑轉換為二進制串，首先將路徑群體實施初始化操作，然后對路徑群體實施選擇、復制等一系列遺傳操作。通過多次進化后，達到最佳的進化狀態，停止進化并將當前存在的最優個體輸出。雖然遺傳算法得推導理論簡單，但路徑規劃過程中仍存在效率低、個體編碼不合理等問題。

（2）全局路徑規劃算法研究

1）構型空間法

構型空間法主要包括優化算法和可視圖法。第一，優化算法。第二，可視圖算法。路徑圖主要由機器人中的一維網絡曲線自由空間中的節點構成。因此，在同路徑圖中，路徑初始狀態的點一一與目標狀態的點相對應，從而促使點間搜索路徑問題替代了路徑規劃問題。這就要求點與點之間的連線是無法穿越障礙物，即機器人與障礙物點、目標點與障礙物點、以及頂點與障礙物頂點之間的連線是可視的，然后，采取有效的搜索方法，搜索最優路徑（起始點到目標點），從而使搜索最優路徑問題演變為可視直線最短距離的問題。可視圖法雖然能夠得到最短路徑。第二，優化算法。采用優化算法時，為了簡化可視圖和減少路徑搜索時間，有部分可有可無的連線可以刪除，最終實現求得最短路徑的目的。

2）神經網絡法

人工神經網絡一種自適應非線性動態系統，主要是由大量神經元組成。在工作環境廣泛、精度要求高的條件下，采用神經網絡法表示環境，將會取得顯著效果。在全局路徑規劃中應用神經網絡法，能夠將障礙約束變成懲罰函數，并用神經網絡來描述碰撞懲罰函數進而將約束優化問題轉變為無約束最優問題，實現全局路徑規劃。神經網絡法具有較強的學習能力，但整體應用于路徑規劃中的效果不明顯，這是因為智能機器人的工作環境復雜，并伴有一定的隨機性，數學公式無法進行準確的描述。

3嵌入式智能機器人路徑規劃算法的應用與實現

嵌入式智能機器人的組成部分主要有驅動控制器和嵌入式微處理器。嵌入式智能機器人的硬件結構有較高的可擴展性、良好的獨立性以及較小的功耗等特征，且能夠得到嵌入式系統的充分支持。嵌入式智能機器人的主板是機器人的大腦，主要擔任機器人運動過程中的實時計算工作。隨著嵌入式技術的不斷發展，為智能機器人的路徑規劃算法的實現和運用提供了無限的可能性，再加上以SOC技術為基礎的高性能32位嵌入式微處理器的廣泛應用，為智能機器人研究領域中，引入實時操作系統提供了強有力的物質基礎，同時這將是機電控制系統的未來發展趨勢。嵌入式智能機器人路徑算法的主要從獲取和決策兩方面實現，獲取是指通過感知系統獲取所需要的環境信息，決策是指通過決策運算后，得出的控制數據由伺服控制系統接收，同還能夠實現與其他機器人的通訊和人機交互。嵌入式智能機器人路徑規劃的運用，需要嵌入式操作系統有較好的實時性、可靠性，并對系統成本提出了更高的要求，此外，根據系統擁有的定制和裁減的特點，在開展多任務管理的同時也能夠保證工作的實時性能。嵌入式智能機器人路徑算法，不需要使用復雜的系統即功能，如文件系統等。嵌入式智能機器人路徑技術的研究重點主要在仿人智能和仿生智能兩方面，隨著我國科學技術的發展，嵌入式智能機器人與多種學科交叉和結合，比如，人工智能、認知科學等，使其智能化的行為程度不斷的提升。此外，嵌入式系統還適用于在功能、體積等方面有嚴格規定的專業計算機系統，使計算機系統具體專用性強、實時性好、微內核精簡等優勢，由此可見將嵌入式智能機器人路徑規劃算法與嵌入式技術相結合是未來智能化機器人的重要發展方向。

4總結

隨著我國科技水平的不斷提高，遙感技術、控制技術等諸多技術的進一步發展，在智能機器人研究領域，嵌入式智能機器人路徑技術也已經取得了顯著的成就。在未來的機器人系統中，遺傳算法、神經網絡法、模糊邏輯控制法等將會進一步應用于嵌入式智能機器人的研究中，使機器人的各方面性能得到顯著提升。

【參考文獻】 

篇5

物流與國民經濟及生活的諸多領域密切相關，得到越來越多的重視，甚至被看作是企業“第三利潤的源泉”。因此，作為物流領域中的典型問題，旅行商問題(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）

篇6

一、路徑規劃的意義

白車身焊接機器人焊接中制定出一條合理的路徑規劃可以有效縮短機器人生產時間，進而縮短整個工期，提高整個生產效率，某種程度上降低了生產成本。另一方面，白車身焊接機器人焊接路徑規劃具有一定的典型性，在自動駕駛、服務機器人、挖掘機器人等路徑規劃研究方面具有重要的借鑒意義，具有較高的社會價值和經濟價值。

二、白車身焊接機器人焊接路徑規劃

（一）路徑規劃的基本任務

現代化工業生產的主要目標是為了獲得較高的制造質量、取得較高的生產率，而付出較低的生產成本，這是現代企業提高自身競爭力的重要手段，也是路徑規劃中的主要任務之一，而在路徑規劃的過程中要想保證焊接質量主要取決于以下兩點：

第一，最大程度的使用機器人工位。使用機器人工位能夠有效降低工人的勞動強度，減少人為錯誤幾率，提高焊接的準確性，保證焊接的順利進行，從而保證焊接的穩定性。

第二，要完成所有的焊接點，保證焊接的工藝參數。

要想實現較低的制造成本就是最大化的利用現有資源，提高機器人的工作效率，縮短機器人工位的生產周期，減少機器人的使用數量。路徑規劃的重要方向就是提高生產率，保證生產環節的順利進行，縮短生產周期，提高生產率。

（二）路徑規劃

白車身焊接機器人焊接路徑規劃主要有兩個分支，一是改變工藝參數，使用新的工藝方法和輔助設備。二是要提高分配的合理性、提高焊接順序的合理性，提高合理性的目標是為了減少機器人工位的生產周期。第二個分支實現的途徑主要是通過提高機器人焊接路徑的合理性，從而提高單個機器人的生產效率，最終縮短整個生產周期。

（三）遺傳算法

遺傳算法是進化算法中產生最早、應用最廣泛的一種基本算法，在工程技術和經濟管理領域都有廣泛的應用。遺傳算法有群體搜索和遺傳算子兩個基本特征，所謂的群體搜索打破了領域的限制，使信息可以廣泛分布于整個空間。而遺傳算子就是使染色體進行隨機操作，以降低人機交互的依賴。兩個特征保證了遺傳算法具有最優的搜索能力、最簡明的操作能力以及信息處理的隱秘能力。

白車身焊接路徑規劃主要問題如下：

第一，白車身中所需要焊接的焊接點眾多。

第二，在生產的過程中常常追求沒有意義的高精度。

第三，在解答相關問題時需要運用數學方法。

第四，因為方案最終應用于企業，所以數學方法最好要簡潔明了，便于學習。

綜上，在路徑研究時需要運用遺傳算法，主要優勢在于：

第一，遺傳算法的計算步驟比較簡單明了，在實際操作時便于學習和使用。在計算時大大減少了計算量，從而節約時間。

第二，能夠在很大程度上優化焊接作業順序，減輕焊接的工作量。

第三，減少定量分析與定性分析的工作量。

第四，能夠很好的掌控全局，在全局中找到最優解。

三、路徑規劃的仿真

（一）仿真系統的各要素

路徑仿真系統一般要具有以下幾個基本要素：

第一，對仿真問題的描述。模型和仿真運行控制共同組成了一個仿真系統，而一個特定的模型又是由一個參數和一組參數值構成。例如白車身點焊機器人焊接路徑的參數模型一般包括家具模型、機器人模型、側圍模型，在這基礎之上還加入了具體的參數值，就形成了特定的模型。

第二，行為產生器。模型確定以后就要對模型進行試驗，這是一套試驗的軟件，行為產生器可以生成一組根據時間變化的數據，這類數據是仿真的物資基礎。

第三，模型行為及對行為的處理。

模型行為可以大致分為三種：軌跡行為、結構行為以及點行為。

仿真系統中都要獲取軌跡行為，這些行為的獲取主要是根據時間的推移而產生的。

（二）仿真軟件的選擇

一個完善的機器人仿真系統可以依據機器人的運動學、動力學、行為軌跡等多項內容進行仿真計算，并可以根據機器人的實際操作內容進行仿真操作過程，并不依賴于真正的機器人。但目前最主要的工作是對機器人的路徑規劃做一個仿真方案，而不是設計出一個機器人的仿真系統。在進行機器人路徑規劃時需要一定的條件，在現實生活中可以有多個選擇，最好的選擇就是使用一些類似CAR這種專業軟件，如果條件不允許可以選擇VC++或者使用CATIA等軟件進行仿真。VC++自主編寫的優點在于針對性比較強，在做路徑時可以考慮多方面因素，然而缺點是不能建立詳細的三維模型，在實際操作時不能全方面的展現白車身焊接工位情況，且工作量較大。CATIA與VC++相比最大的優勢就是可以建立詳細的三維模型，能夠全方位展現工位情況，仿真軌跡最為真實，在仿真過程中還可以檢查是否干涉。而缺點也是比較明顯的，在仿真的過程中不能將動力學和控制算法考慮在內。

四、小結

白車身主要是以鋼結構為主的支架，是汽車中重要組成部分。而車身制造是整個環節中比較復雜又極為重要的一環，影響整個汽車的質量。我國研究白車身焊接機器人焊接路徑仍處于落后階段，為了提高綜合競爭力需要加大技術投資，提高我國白車身制造綜合競爭。

參考文獻：

篇7

1 群智能算法概述

群智能算法是近幾十年發展起來的一類基于生物群體行為規律的全局概率搜索算法。這些算法將搜索空間中的每一個可行解視為生物個體，解的搜索和優化過程視為個體的進化或覓食過程。生物個體適應環境的能力用來度量待求解問題的目標函數，生物個體的進化或覓食過程用來模擬優化中較差的可行解被具有優勢的可行解替代的迭代過程。下文將對幾種典型的群智能算法進行簡要的介紹。

2 典型群智能優化算法

2.1 蟻群算法

1991年意大利學者Dorigo M等受到自然界中蟻群覓食行為啟發而提出了蟻群算法 （Ant Colony Optimization， ACO）。

蟻群算法的思想是：在最短路徑的找尋過程中，每只螞蟻只可以根據局部信息調整路徑上的信息素，一輪循環結束后，采取全局信息對路徑上的信息量再進行一次調整，且只對尋優過程中發現的最好路徑上的信息素進行加強。在蟻群算法中，螞蟻逐步地構造問題的可行解，在解的構造期間，每只螞蟻使用概率方式向下一個節點跳轉，這個節點是具有較強信息素和較高啟發式因子的方向，直至無法進一步移動。此時，螞蟻所走路徑對應于待求解問題的一個可行解。

蟻群算法目前已成功地用于解決旅行商TSP問題、數據挖掘、二次指派問題、網絡路由優化、機器人路徑規劃、圖著色、物流配送車輛調度、PID控制參數優化及無線傳感器網絡等問題。

2.2 粒子群算法

1995年美國的Kennedy等受鳥群捕食行為的啟發而提出了粒子群算法（Particle Swarm Optimization， PSO）。

粒子群算法的思想是：將群體中的任一個個體，即每個可行解，視為D維搜索空間的一個有飛行方向和速度的粒子。所有的粒子都有一個被目標函數決定的適應值，且記憶了自身曾經獲得的最好位置及當前位置，視為自身的飛行經驗。同時每個粒子還知道整個群體所有粒子已獲得的最優位置，視為群體的飛行經驗。在迭代過程中，所有的粒子將不斷地統計個體的飛行經驗和整個群體的飛行經驗，以此動態調整本身飛行的方向和速度。在此過程中，個體逐步遷移到較優的區域，使群體最終搜索到問題的最優解。

粒子群算法的應用領域眾多，如模式識別與圖像處理、工程應用、神經網絡訓練、模糊系統控制、化工系統處理、濾波器設計、仿人智能控制參數優化、數據聚類等。

2.3 人工魚算法

2002年由我國的李曉磊等受魚群運動行為的啟發而提出了人工魚群算法 （Artificial Fish-Swarm Algorithm， AFSA）。

人工魚群算法的思想是：將人工魚隨機地分布于解空間中，解空間中包含著若干局部最優值和一個全局最優值。可將最優值視為食物的濃度，而全局最優值為最大的食物濃度，且人工魚將移動聚集到食物濃度較大的區域，通過移動策略來控制人工魚個體的四種行為（覓食、聚群、追尾和隨機），用視野來限制個體的鄰域，用步長來控制個體探索的進度，用擁擠度來控制群體的過度密集。尋優期間，每次迭代執行完，人工魚都將對比自身狀態和公告板狀態，如自身具有優勢，則更新公告板狀態，確保公告板為最優狀態。

人工魚群算法已在參數估計、組合優化、前向神經網絡優化、電力系統無功優化、輸電網規劃、邊坡穩定、非線性方程求解等方面得到應用，且取得了較好的效果。

2.4 混合蛙跳算法

2003年Eusuff等人受青蛙覓食特征的啟發而提出了混合蛙跳算法[4] （Shuffled Frog Leaping Algorithm， SFLA）。

混合蛙跳算法的思想是：將青蛙個體隨機地分布于解空間中，每只青蛙表示解空間的一個解。在進化更新的過程中既有全局性的信息交流，還有內部的信息交流。根據青蛙個體的適應度值的優劣進行排序和分組，組內只有適應度最差的青蛙更新，元進化并混合各組，在各組一輪元進化后，將組中的青蛙重新排序、分組并記錄全局最優解，之后再繼續局部搜索的過程。青蛙更新的學習對象首先是組內最優，其次是群體最優，若兩次都未能進步，則隨機初始化。

混合蛙跳算法已經應用于多個領域，如水資源網絡優化、數據聚類、橋面修復、風電場電力系統動態優化、裝配線排序、流水車間調度、PID控制器參數調節等。

2.5 人工蜂算法

2005年由土耳其的Karaboga等受蜜蜂采蜜行為的啟發而提出了人工蜂群算法（Artificial Bee Colony， ABC）。

人工蜂群算法的思想是：將虛擬蜜蜂群初始時隨機分布在解空間中，將食物源的位置抽象成解空間中的點（可行解）。通過三種蜜蜂對食物源位置（解）修正，進行一次循環搜索過程。引領蜂通過對比附近食物源的花蜜量（適應度），來對現有食物源位置（解）進行修正。如果新食物源的花蜜量（適應度）比現有的高，那么引領蜂記憶新食物源（解），放棄現有的。在引領蜂的搜索過程完成后，它們通過跳舞與跟隨蜂傳遞食物源信息。跟隨蜂通過匯總和評估所有食物源信息，計算出一個關于花蜜量的概率值，通過比較概率選取食物源。跟隨蜂也是根據貪婪選擇策略來更新當前食物源的位置。利用偵察蜂來使得陷入局部搜索停滯的蜜蜂跳出。

人工蜂群算法已經應用于多個領域，如車輛路徑問題、人工神經網絡訓練、作業車間調度問題、數據聚類以及各類連續優化問題等。

2.6 螢火蟲算法

2009年由劍橋大學的Xin-She Yang受螢火蟲發光行為的啟發而提出了螢火蟲算法（Firefly Algorithm， FA）。

螢火蟲算法的思想是：將螢火蟲個體作為解隨機地分布于解空間中。解的搜索和優化過程視為每只螢火蟲的移動和吸引過程。個體所在位置的優劣用來度量所求問題目標函數。個體進化的過程用來模擬優化中較差的可行解被具有優勢的可行解替代的迭代過程。螢火蟲根據自身亮度和吸引度兩個要素來更新自己的位置。螢火蟲所在位置的目標值決定其能產生的熒光亮度，所處位置（目標值）越好其亮度越高。螢火蟲的亮度與吸引力成正比，視線范圍內，亮度稍弱的螢火蟲將被吸引，朝著較亮螢火蟲的方向移動，以完成的位置進化。當亮度相同時，螢火蟲則隨機地進行位置移動。螢火蟲之間的距離與亮度和吸引度成反比，也即距離越大，亮度和吸引度越小。

目前螢火蟲算法已應用在生產調度、路徑規劃、神經網絡訓練、天線陣列設計優化、圖像處理、機械結構設計優化、負載經濟均衡分配問題、復雜函數優化等方面。

3 結論

本文在簡述群智能算法的基礎上，對近年來發展的幾種典型的群智能算法的生物原理、算法思想和應用進行了闡述和研究，為群智能算法的深入研究奠定了基礎。

參考文獻

[1]Colomi A，Dorigo M，Maniezzo V.The Ant System： An autocatalytic optimization process，Technical Report 91-016，Dept.of Electronics，Politecnicco di Milano，Italy，1991.

[2]Kennedy J，Eberhart RC.Particle swarm optimization[C].IEEE International Conference on Neural Networks，Perth，Piscataway，NJ，Australia： IEEE Service Center，1995，1942-1948.

[3]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，2002，11，32-38.

篇8

Design and Implementation of Order Routing System Based on iOS

XU Jing-hui

（North China University of Technology， Beijing 100144， China）

Abstract： The routing problem of multi-warehouse and multi-distribution task in order distribution has the characteristics of picking from the warehouse and returning to the starting warehouse after completing the delivery task by multiple distribution points. In view of the current path planning applications on the mobile platform to solve the known starting point to the end of the route planning， after a number of points along the planning has not yet been a good application to achieve. Therefore， this paper combines the path planning and iOS platform to make full use of the characteristics of electronic map application， design and implement the order routing system based on iOS in order to provide the optimal path results. This paper focuses on how to realize the function of map display and operation， map location， mark drawing， route planning and so on. Finally， using the real order data of inventory management platform， the test proves the effectiveness and convenience of the system.

Key words： route plan； multi-warehouse multi-distribution tasks； iOS； digital map； optimal path

在實際訂單配送環節中，路徑規劃要求找出車輛從倉庫取貨出發依次經過一系列配送點后返回倉庫的最短回路路徑。目前關于路徑規劃的研究多數集中在常見路徑算法的改進及優化方面[1-3]，對于路徑規劃應用系統的研究還較少。國內iOS平臺上有關路徑規劃的熱門應用有高德地圖、百度地圖等App，但它們也只提供了支持公交、駕車及步行三種出行方式的點到點的路徑規劃，對于從起點經過多個沿途點到達終點的路線規劃并未涉及。鑒于目前尚未有將路徑規劃與iOS移動平臺的應用特點充分相結合的應用，本文就設計開發了iOS平臺上基于電子地圖的路徑規劃系統――稱之為“易配送系統”。易配送系統可在用戶使用期間自動定位用戶當前所在位置，同時提供倉庫到各配送點的路線規劃和導航等主要功能，還通過服務端的接口服務將數據封裝成XML編碼格式通過網絡提供給客戶端，保障了訂單數據的真實性與實時性。在系統開發過程中利用高德iOS地圖SDK進行應用開發，提供了可視化的路徑規劃人機交互界面。

本文的內容首先對iOS平臺開發相關技術進行了簡要介紹，然后對訂單配送路徑規劃系統進行分析，設計出了整體的技術方案與系統架構，然后對系統功能進行詳細實現，包括倉庫、訂單查詢，地圖位置顯示、路線規劃及導航等功能，最后進行結果分析與總結。

1 iOS開發平臺介紹

1.1 iOS系統架構

iOS平臺應用的開發語言主要有Objective-C和Swift語言，由于swift作為一門新生語言使用人數較少的原因，本系統采用了主流開發語言Objective-C進行編碼開發。Objective-C作ANSI C的超集[4]，不僅擴展了面向對象設計的能力，如類、消息、繼承，同時它可以調用C的函數，也可以通過C++對象訪問方法，具有對C和C++語言的兼容性。

蘋果公司最新推出的iOS 10 SDK （Software Development Kit， 軟件開發工具包）增加了新的API （Application Programming Interface， 應用程序編程接口）和服務，能夠支持更多新類型的應用程序和功能。目前基于iOS平臺開發的應用程序可以擴展到消息、Siri、電話和地圖等系統自帶服務，擁有了更吸引人的功能。圖1為iOS系統架構圖：

圖中可觸摸層主要提供用戶交互相關的服務如界面控件、事件管理、通知中心、地圖，包含以下框架：UIKit、Notification Center、MapKit等；媒體層主要提供圖像引擎、音頻引擎及視頻引擎框架；核心服務層為程序提供基礎的系統服務如網絡訪問、瀏覽器引擎、定位、文件訪問、數據庫訪問等。最底層的核心系統層為上層結構提供了最基礎的服務包括操作系統內核服務、本地認證、安全、加速等。

1.2 iOS 地圖SDK

iOS 地圖SDK 是高德提供的一套基于 iOS 6.0.0 及以上版本的地圖應用程序開發接口，供開發者在iOS應用中加入地圖相關的功能[6]。它提供的四種地圖模式包括：標準地圖、衛星地圖、夜景模式地圖和導航模式地圖。開發者不僅可以利用其地圖計算工具實現坐標轉換和距離或面積計算，而且可以調用API完成出行路線規劃及點標注、折線、面的繪制等工作。這些實現的提前需要注冊并認證成為高德開發者，接著為應用申請APIKey，然后將iOS地圖SDK配置到應用工程中，這里可以采用手動和自動化兩種配置方式。前者的配置過程簡單易操作，但更新操作代價大，后者配置過程稍顯負雜，但更新很方便。手動配置的方式則需要手動向工程項目中導入MAMapKit.framework和AMapSearchKit. framework兩個包，當框架有更新時需將工程中舊框架刪除并添加新框架，其使用稍顯麻煩。本系統的實現采用了自動化配置工程的方式，利用第三方庫管理工具CocoaPods通過命令：pod ‘AMap3DMap’， ‘～>4.0’和pod ‘AMapSearch’， ‘～>4.0’完成自動導入框架的目的，當框架更新時只需執行pod update即可實現項目中框架的更新。

2 整體方案設計

通常App功能復雜的情況下需要有后臺服務器的業務處理支持，本文涉及的路徑規劃功能需要處理的計算量會隨著配送點個數的增長呈指數階上升，因此需要后臺服務器的強大計算能力處理路徑規劃結果，進而減輕客戶端內存使用壓力。

本系統整體技術方案的設計綜合考慮了移動應用端、服務端（包括應用服務器和提供商服務器）以及數據庫服務器三部分所涉及的技術及其簡要的功能模塊劃分，如下圖2所示：

其中應用服務端是典型的電商進銷存管理系統，移動端LBS應用――易配送App的實現需要在進銷存Web系統的表示層、業務邏輯層、數據持久層添加相應的訂單配送接口，該接口將服務端經過處理的數據結果封裝成XML標準的數據格式通過HTTP協議傳輸給App。

3 基于iOS的路徑規劃App設計

3.1 App開發模式

易配送App采用Objective-C開發語言，開發工具為Xcode7.0，主要針對iPhone進行設計的。系統的設計模式采用了MVC范型如圖3。由于系統所涉及的內容數據均通過網絡請求服務器實時更新獲取，故采用了iOS App開發模式中的Native App，以保證有較好的網絡環境以及節省的帶寬，以便利用充分的設備資源來提供良好的交互體驗。

該系統平臺中的位置信息主要體現在：位置服務和地圖。位置服務是由Core Location框架負責，它將用戶的位置及方向信息以Objective-C語言能識別的形式羅列出來[4]；地圖服務通過應用中集成的高德開發平臺提供的MAMapKit框架負責，利用它可以展示出地圖和圖釘標注等信息。易配送App的路徑規劃模塊有效地將Core Location框架和MAMapKit框架結合起來，以實現地圖定位、距離測試、路線顯示及導航功能。

3.2 重要功能設計及關鍵技術實現

系統的主界面設計采用了圖文結合的布局方式如圖4，使用戶能夠快速便捷的操作系統。對于信息查詢類似功能的界面多采用表視圖結構，得到了清楚地展示大量內容信息的效果如圖5所展示的待配送訂單列表。

圖4 主界面 圖5 待配送列表

圖6 路徑規劃

系統主要的路徑規劃功能在電子地圖的地理信息背景下完成了標注及路線可視化如圖6所示，其關鍵技術的實現如下：

1）初始化地圖服務

系統中地圖服務的使用首先需要初始化地圖控件，這需要在創建MAMapView之前需要先綁定APIKey：[MAMapServices sharedServices].apiKey = APIKey； 和[AMapSearchServices sharedServices].apiKey = APIKey；接著初始化MAMapView地圖控件：_mapView = [[MAMapView alloc] initWithFrame： self.view. frame]；并o系統添加地圖視圖：[self.view addSubview：_mapView]；

2）分組待配送訂單

因為業務要求需要將待配送訂單按各自對應的出貨倉庫進行分組配送，系統中通過自定義實現分組方法：-（void）groupAction：（NSMutableArray *）array； 其中參數array中存儲著多個配送單對象XJDeliveryOrder。方法實現中利用可變的集合對象NSMutableSet保存的內容對象不重復的特性，用_warehouseSet記錄不同的倉庫信息：_warehouseSet = [NSMutableSet set]； [array enumerateObjectsUsing Block： ^（ XJDeliveryOrder * _Nonnull order， NSUInteger idx， BOOL * _Nonnull stop） {[_warehouseSet addObject：order.warehouseName]； }]； 同時該方法中利用謂詞NSPredicate過濾數組array實現按倉庫名稱分組：[_warehouseSet enumerateObjectsUsingBlock：^（NSString * _Nonnull warehouseName， BOOL * _Nonnull stop） {NSPredicate *predicate = [NSPredicate predicateWithFormat： @"warehouseName = %@"， warehouseName]；NSArray *tempArr = [NSArray arrayWithArray：[array filteredArrayUsingPredicate：predicate]]； [groupArr addObject： tempArr]；}]；

3）添加標注及氣泡視圖

給地圖添加標注需要調用地理編碼請求：[self.search AMapGeocodeSearch： geo]； 其中對象geo為AMapGeocodeSearchRequest類對象且其屬性值address不為空，該請求會回調AMapSearchDelegate中的方法：- （void）onGeocodeSearchDone： （AMapGeocodeSearchRequest*）request response：（AMapGeocodeSearchResponse *） response；其中response對象中包含了經緯度信息并且該方法中調用了添加標注方法：[_mapView addAnnotation：pointAn]；其中對象pointAn為MAPointAnnotation類對象。

實現觸摸標注彈出氣泡的效果需要實現MAMapViewDelegate委托中-（MAAnnotationView*）mapView：（MAMapView*）mapViewviewForAnnotaion： （id< MAAnotation>）annotation；和-（void）mapView：（MAMapView*）mapView didSelect AnnotationView：（MAAnnotationView *）view；方法。

4）路徑規劃及繪制路線

iOS地圖API提供了按參數順序進行路徑規劃的方法：[_search AMapDriving RouteSearch：request]；其中request為AMapDrivingRouteSearchRequ -est對象，需要給定request的屬性：起點origin、終點destination和沿途點waypoints的值。而對于最優路徑的規劃只能通過自定義方法：-（void）planBestPaths WithLoaction：（CLLocationCoordinate2D）location wayPoints： （NSArray*） wayPoints；該方法中調用了網絡請求服務器方法，并能夠獲取服務器返回的處理結果，其結果中包含了多個經緯度字符串，需要利用方法- （CLLocationCoordinate2D *）coordinatesForString：（NSString*）string coordinateCount：（NSUInteger *）coordinate Count parseToken：（NSString *）token；來解析經緯度，然后系統利用解析得到的經緯度調用[MAPolyline polylineWithCoordinates：coordinates count：count]來繪制路線。

5）最優路徑算法

本系統的服務端路徑規劃接口實現中采用了適合解決單回路最短路徑問題的算法――最近c插入算法。最近插入法是一種啟發式算法，它不僅適用于各種復雜的TSP問題，對于中小規模問題同樣適用。圖7為算法具體流程。算法的實現是在后臺服務端通過java語言實現的，這里就不做詳細說明了。

4 系統測評與應用實例

為了對系統的功能及路徑優化效果進行測試，采用了如下的實驗環境：客戶端是所有系統為iOS 7.0及以上iPhone手機，安裝App后即可使用；服務端為可安裝運行在windows平臺下的進銷存管理系統；數據庫為Oracle數據庫安裝在Linux數據庫服務器上。

本系統中路徑規劃功能的實現采用了將多個倉庫多配送點的路徑規劃分解為多個單倉庫多點配送的思想。下面一系列圖示說明了多個單倉庫出發到多個配送點的路徑規劃對比結果。

圖8中顯示當天需要規劃路徑的所有點，包括三個倉庫和八個客戶位置。接下來分別對三個倉庫進行出貨配送安排，如圖9為從總倉庫出發的配送路線對比，其中上圖為按下單順序依次配送的路線圖，下圖為根據與出發倉庫距離由近到遠的依次配送的路線圖，從圖中可以明顯看出兩者各自的路程代價，表1為各倉庫配送路徑的對比結果。

通過實驗測試結果表明，當單次規劃的配送數量小于等于6時，本系統的最優路徑準確且計算處理很快，幾乎網絡無延遲。當單次規劃的配送數量大于6小于17時，優化結果準確但是處理速度變慢，并且處理響應時間雖配送數量呈現指數階增長。當單次規劃的配送數量大于16時，服務端需通過一定路徑優化算法處理大規模計算，但其結果往往是最優解的近似值而非最優路徑值。

5 結束語

本文是在iOS系統上基于電子地圖的應用開發，基本實現了小規模訂單配送的路徑規劃功能。經過優化的路徑的確節省了許多里程，真正意義上為企業提高了效益。但是本系統還存在一些不足之處，如適合處理小規模訂單配送路徑規劃的局限性，系統的可擴展性有待加強。在今后的學習和研究中，將進一步深化和擴展該應用的功能，提供更加豐富的視圖信息和交互方式，實現更良好的路徑規劃體驗。

參考文獻：

[1] WANG Tiejun，WU Kaijun. Study multi-depots vehicle routing based on improve -ed particle swarm optimization[J]. Computer Engineering and Applications，2013， 49（2）： 5-8.

[2] 馬建華，房勇，袁杰.多車場多車型最快完成車輛路徑問題的變異蟻群算法[J].系統工程理論與實踐，2011（8）.

[3] 李波，邱紅艷.基于雙層模糊聚類的多車場車輛路徑遺傳算法[J].計算機工程與應用，2014（5）.

篇9

0 前言

移動機器人的實現涉及自動控制、智能、機械等多種學科。它通常被應用在醫療領域、工業領域等方面。從整體角度來講，移動機器人的應用促進了生產效率的顯著提升。路徑規劃技術是移動機器人的關鍵技術之一，研究該技術具有一定的現實意義。

1 路徑規劃技術的作用

將路徑規劃技術應用在移動機器人中，能夠產生的作用主要包含以下幾種：

（1）運動方面。路徑規劃技術的主要作用是其能夠保證移動機器人完成從起點到終點的運動。（2）障礙物方面。設計移動機器人的最終目的是將其應用在實際環境中，在實際環境下，移動機器人的運行路線中可能存在一定數量的障礙物，為了保證最終目的地的順利達到，需要利用路徑規劃技術實現對障礙物的有效避開[1]。（3）運行軌跡方面。對于移動機器人而言，除了實現障礙物躲避、達到最終目的地這兩種作用之外，應用路徑規劃技術還可以產生一定的優化運行軌跡作用。在移動機器人的使用過程中，在路徑規劃技術的作用下，機器人可以完成對最佳運行路線的判斷，進而更好地完成相應任務。

2 移動機器人路徑規劃技術綜述

移動機器人的路徑規劃技術主要包含以下幾種：

2.1 局部路徑規劃方面

在局部路徑規劃方面，能夠被應用在移動機器人中的技術主要包含以下幾種：

（1）神經網絡路徑規劃技術。從本質上講，可以將移動機器人的路徑規劃看成是空間到行為空間感知過程的一種映射，因此，可以利用神經網絡的方式將其表現出來。就神經網絡路徑規劃技術而言，首先需要將相關傳感器數據當成網絡輸入，并將網絡輸出看成是某固定場合中期望運動方向角增量。在這種情況下，原始樣本集則可以用不同選定位置對應的數據代替。為了保證樣本集數據的有效性，需要將原始樣本集中的沖突樣本數據以及重復樣本數據剔除掉。對最終樣本集應用模糊規則，實現神經網絡的有效訓練。當典型樣本學習完成之后，移動機器人對規則的掌握水平發生了顯著提升，進而使得移動機器人在產生智能性能的基礎上，順利完成相應運動[2]。

（2）人工勢場路徑規劃技術。這種規劃技術是指，將移動機器人在實際環境中的運動過程當成其在虛擬人工受力場中的一種運動。在虛擬人工受力場中，目標終點會對移動機器人產生一定的引力，而該受力場中的障礙物則會對其產生一定的斥力。在某固定算法的作用下，這兩種不同的作用力會產生相應的勢，進而形成勢場。當移動機器人在該場中運動時，勢場中的抽象力會作用在移動機器人上，使得其完成對障礙物的有效避開。在人工勢場路徑規劃技術的實際應用過程中，由于結構簡單等因素的影響，移動機器人在到達終點之前可能會停留在局部最優點位置上。對此，需要從數學的角度出發，對勢場方程進行重新定義，通過這種方式排除勢場中的局部極值，繼而保證移動機器人運動的順利進行[3]。

（3）遺傳路徑規劃技術。這種路徑規劃技術建立在自然遺傳機制等理論的基礎上。這種技術通過變異、選擇以及交叉對控制機構的正確計算程序進行合理編制，進而實現數學方式基礎上生物進化過程的合理模擬。當移動機器人的適應度函數為正數時，允許適應度函數具有不連續或不可導特點。由于這種路徑規劃技術不涉及梯度信息，因此其能夠更好地解決移動機器人在實際運動過程中遇到的問題。遺傳路徑規劃技術的應用優勢在于，它能夠實現跟蹤與規劃的同時進行，因此，遺傳路徑規劃技術通常被應用在具有時變特點的未知環境中。

2.2 全局路徑規劃方面

在該方面，可以被應用在移動機器人中的技術主要包含以下幾種：

（1）柵格路徑規劃技術。這種技術是指，在將實際工作環境分成許多包含二值信息的網格單元的基礎上，應用優化算法完成最佳路徑的規劃搜索。在這種規劃技術中，其網格單元通常是由八叉樹或者四叉樹的方式表示出來。在該技術的應用中，柵格的作用是完成相關環境信息的記錄。如果柵格中某位置的累計值相對較低，代表移動機器人可以從該位置通過；如果柵格中某個位置的累計值相對較高，則表示該位置存在障礙物，此時，移動機器人需要利用優化算法將該障礙物避開[4]。

（2）可視圖路徑規劃技術。這種路徑規劃技術是指，將整個移動機器人看成一個點，然后分別將其與障礙物以及目標終點連接起來，上述連線要求為保證所連直線不會碰觸障礙物。當所有連線都連完之后，即完成了一整張可視圖。在該可視圖中，由于起點到目標終點之間的連線都不涉及障礙物，因此上述所有連線都屬于有效直線。在這種情況下，需要解決的問題主要是從這些連線中找出一條距離最短的連線。對此，需要應用優化算法將可視圖中距離較長的連線刪除，這種處理方式能夠有效提升移動機器人的搜索時間。

（3）拓撲路徑規劃技術。這種規劃技術是指，將移動機器人的移動范圍，即規劃區域分成多個具有拓撲特征的子空間，然后利用不同子空間之間的連通性完成拓撲網絡的構建。當該網絡構建完成后，直接從網絡中找出能夠使得機器人順利從起點移動到終點的拓撲路徑，將所得的拓撲路徑作為參考依據完成幾何路徑的計算。這種規劃技術的劣勢主要表現為其拓撲網絡的構建過程較為復雜。但這種規劃技術可以實現移動機器人搜索空間的有效縮小[5]。

3 結論

路徑規劃技術主要分為局部規劃和全局規劃兩方面。這兩方面分別包含人工勢場路徑規劃技術以及神經網絡路徑規劃技術等。應用這些規劃技術之后，移動機器人可以在避開障礙物的基礎上，順利完成起點到終點最優運行軌跡的運動。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005（02）：439-443.

[3]鮑慶勇，李舜酩，沈`，門秀花.自主移動機器人局部路徑規劃綜述[J].傳感器與微系統，2009（09）：1-4+11.

篇10

貪心算法是用來求解某些問題最優解的一種有效算法，它可以簡單迅速的解決很多實際應用的問題，在圖論領域也有著非常廣泛的應用。

1 貪心算法概述

1.1 貪心算法定義

貪心算法是一種經過改進的分級處理的方法。貪心算法在進行決策的時候總會做出對目前情況最好的選擇。和動態規劃算法不同的是，貪心算法并不考慮問題的整體最優，而只是選擇某種意義上的局部最優。所以，貪心方法未必能針對所有問題求得整體的最優解，但是對于許多問題而言，它卻能得到整體最優解。在某些情況下，貪心算法雖然得不到整體最優解，卻可以得到最優解的很好的近似。

1.2 貪心算法的基本要素

對于一個具體問題，怎樣才能知道能否可以用貪心算法求解并得到最優解呢？在實際應用中人們總結出了兩個重要的性質：

（1）貪心選擇性質；（2）最優子結構性質。

許多可以利用貪心方法求解的問題一般都具備這兩個性質。

1.3 貪心算法的求解步驟

貪心算法求解問題首先要確定一個貪心準則，每一步都是按這個準則選取優化方案。按照這種度量標準對此問題的n個輸入排序，并按序一次輸入一個量。如果這個輸入和當前已構成在這種量度意義下的部分最優解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。因此貪心準則的選取直接關系到可行解能否達到最優。

2 貪心算法求解單源點最短路徑問題

圖論中有一個非常典型的問題：單源點最短路徑問題。問題描述如下：對于有向帶權圖G =（V，E），其中每條邊上的權值是一個非負實數。選定V中的一個頂點，稱之為源點。這個問題求解的是從源點到圖G中其他所有頂點的最短路徑的長度。所謂的長度是指經過的各邊上的權值總和。

Dijkstra算法正是利用貪心算法求解此問題，用迄今已生成的所有路徑長度之和為最小作為貪心準則，為此，每一條單獨的路徑都必須具有最小長度。此算法的實現步驟為：將頂點集合分為S和V-S這兩個子集。子集S中均為已求得最短路徑的頂點。初始時，集合S中只有源點，接下來不斷做貪心選擇來擴充此集合。取G中的一個頂點v，把從源點到v點并且只經過S中頂點的路徑稱為從源點到頂點v的特殊路徑，設置數組dist記錄每個頂點當前所對應的最短特殊路徑的長度。Dijkstra算法每次都從子集V-S中取出特殊路徑長度為最短的頂點，并把該頂點添加至子集S，隨后對數組dist進行修改。一旦子集S等于頂點集V，算法結束。數組dist中記錄的就是源點到圖中其他各頂點的最短路徑的長度。

例如，下圖1中的有向帶權圖，采用Dijkstra算法，從源點1到圖中剩余各頂點間最短路徑的計算過程如下表1所示：

3 貪心算法求解最小生成樹問題

最小生成樹是非常具有實際應用價值的圖論問題，具體描述如下：已知無向連通帶權圖G=（V，E）。E中每條邊（u，v）的權值設為c[u][v]。求圖G的生成樹G’，使得G’上各邊權值的總和是所有生成樹中各邊權值總和最小的。這個問題被稱為最小生成樹問題。最小生成樹的求解方法有多種，其中應用比較廣泛的幾種算法，如Prim算法和Kruskal算法都是采用了貪心算法的策略。

3.1 Prim算法

Prim算法的基本思想為：首先選擇圖中任意頂點u，并將u置于頂點集合的子集S中。如果S是頂點集合V的真子集，就繼續選擇頂點j添加到子集S中，這里的j必須滿足條件i?S，j?V-S，且c[i][j]是權值最小的邊。按照同樣的步驟不斷進行貪心選擇，直到子集S=V為止。此時，選取到的所有的邊就構成了圖G的一棵最小生成樹。例如，對于圖2中的無向連通帶權圖，按照Prim算法求最小生成樹的過程如圖3所示。

3.2 Kruskal算法

Kruskal算法構造最小生成樹的過程相比Prim算法更加簡單明了。首先將無向連通帶權圖G的n個頂點作為n個孤立的連通分支。并按照權值給所有的邊從小到大進行排序。將第一條邊加入到連通分支，然后按權值遞增的順序依次查看剩下的每一條邊，如果這條邊加入構成回路就拋棄，繼續考察下一條邊，反之加入到連通分支中。一旦加入邊的條數等于n-1，則算法結束。剩下唯一的連通分支就是要求取的最小生成樹。

例如，對上圖2，按Kruskal算法求得最小生成樹的過程如下圖4所示。

比較上述兩種方法可以看出，雖然都是利用貪心算法解決，但是由于選擇的貪心準則不一樣，因次求解步驟和最小生成樹的選邊過程都是不一樣的。

4 總結

貪心算法也存在著缺點，比如應用范疇比較狹窄而且有一些極難證明，但是針對圖論的部分問題，比如上述的兩個典型問題，貪心算法不但能夠正確的求解，而且與其他算法相比，更是體現了其高效的優勢。當然，圖論中還有許多未解的問題，這些問題能否用貪心算法求解，或者能否找到更好的貪心準則提高求解的效率則需要更加深入的研究和發現。

參考文獻：

[1]余祥宣，崔國華，鄒海明.計算機算法基礎（第三版）[M].華中科技大學出版社，2006.

篇11

Abstract： Vehicle routing problem is the core problem in logistics management and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars' research situation， summarized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems.

Key words： vehicle routing problem； heuristic algorithm； optimization

0 引 言

隨著科技的進步和電子商務的飛速發展，作為國民經濟中一個重要行業的物流產業已成為拉動國家經濟發展與提高居民生活水平的重要動力源泉，而物流行業中的車輛路徑問題（Vehicle Routing Problem， VRP）是制約物流行業發展的一個關鍵要素，其研究也受到人們的廣泛關注。車輛路徑問題是物流管理與運輸組織優化中的核心問題之一，是指在滿足一定的約束條件（如時間限制、車載容量限制、交通限制等）下，通過對一系列收貨點與發貨點客戶合理安排行車路線，在客戶的需求得到滿足的前提下，達到配送車輛最少、配送時間最短、配送成本最低、配送路程最短等目標。該問題由Dantzig和Ramser[1]于1959年在優化亞特蘭大煉油廠的運輸路徑問題時首次提出，現已成為運籌學中一類經典的組合優化問題，是典型的NP-難題。

企業通過選取恰當的配送路徑，對運輸車輛進行優化調度，可以明顯提高配送效率，有效減少車輛的空駛率和行駛距離，降低運輸成本，加快響應客戶的速度從而提高客戶服務質量，提高企業的核心競爭力。VRP作為物流系統優化環節中關鍵的一環，其研究成果已經應用到快遞和報紙配送連鎖商店線路優化以及城市綠化車線路優化等社會實際問題中，因而車輛路徑問題的優化研究具有很好的現實意義。

1 車輛路徑問題的分類與基本模型

VRP的構成要素通常包括車輛、客戶點、貨物、配送中心（車場）、道路網絡、目標函數和約束條件等，根據側重點的不同，VRP可以分為不同的類型。根據運輸車輛載貨狀況分類可分為非滿載車輛路徑問題和滿載車輛路徑問題；根據任務特征可分為僅裝貨、僅卸貨和裝卸混合的車輛路徑問題；根據優化目標的數量可分為單目標車輛路徑問題和多目標車輛路徑問題；根據配送車輛是否相同可分為同型車輛路徑問題和異型車輛路徑問題；根據客戶對貨物接收與發送有無時間窗約束可分為不帶時間窗的車輛路徑問題和帶時間窗的車輛路徑問題；根據客戶需求是否可拆分可分為需求可拆分車輛路徑問題和需求不可拆分車輛路徑問題；根據客戶是否優先可分為優先約束車輛路徑問題和無優先約束車輛路徑問題；根據配送與取貨完成后車輛是否需要返回出發點可分為開放式車輛路徑問題和閉合式車輛路徑問題；還可以將上述兩個或更多約束條件結合起來，構成一些更復雜的車輛路徑問題。

由于VRP的約束條件不同引起了其分類多種多樣，而不同類型的VRP其模型構造及求解算法有很大差別。VRP的一般數學模型為：

在上述模型中，式（1）表示目標函數，式（2）表示約束條件。其他VRP模型大致都是在此模型的基礎上根據約束條件完善形成的。

2 VRP的求解算法與研究現狀

VRP的求解方法，基本上可分為精確算法和啟發式算法兩大類。由于精確算法的計算難度與計算量隨著客戶點的增多呈指數級增加，在實際中應用范圍有限，而啟發式算法則具有全局搜索能力強、求解效率高的特點，求出的解也具有較好的參考性，因此，目前大部分研究者們主要把精力集中在如何構造高質量的啟發式算法上，本文也主要討論一些近年來研究比較多的啟發式優化算法。針對VRP問題目前已提出了大量的啟發式算法，其中研究較多的主要包括以下算法：

2.1 遺傳算法（Genetic Algorithm，GA）

GA是一種通過模擬生物進化過程來搜索最優解的方法，該方法通過對群體進行選擇、交叉和變異等操作，產生代表新的解集的種群，根據個體適應度大小選擇個體，通過迭代逐步使群體進化到近似最優解狀態。但是該算法具有搜索速度慢、易早熟、總體可行解質量不高等缺點。

采用遺傳算法研究VRP問題的研究現狀包括：蔣波[2]設計了遺傳算法求解以配送總成本最小為目標函數和帶有懲罰函數的VRPTW模型；趙辰[3]基于遺傳算法求解了從生產中心到倉庫之間的路徑優化問題，設計了配送路徑優化決策；張群和顏瑞[4]建立了多配送中心、多車型車輛路徑問題混合模型，并采用一種新的模糊遺傳算法求解該問題。

2.2 模擬退火算法（Simulated Annealing，SA）

SA同禁忌搜索算法一樣，也屬于局部搜素算法，但是模擬退火算法是模仿金屬加工中退火的過程，通過一個溫度函數作為目標函數，使其趨于最小值，是一種基于概率的算法。

采用模擬退火算法研究VRP問題的研究現狀包括：郎茂祥[5]研究了裝卸混合車輛路徑問題，并構造了模擬退火算法求解該問題；穆東等[6]提出了一種并行模擬退火算法，并將該算法的應用領域擴展到其他車輛路徑問題和組合優化問題；魏江寧和夏唐斌[7]以模擬退火算法為基礎，研究了單個集散點與多個客戶之間的運輸問題；Mirabi和Fatemi Ghomi等[8]提出了一種基于模擬退火思想的三步啟發式算法求解最小化配送時間的多配送中心VRP模型。

2.3 蟻群算法（Ant Colony Optimization，ACO）

蟻群算法是人們受螞蟻可以快速找到食物的自然現象啟發提出的。蟻群算法所建立的機制，主要包括螞蟻的記憶、螞蟻利用信息素進行交互通信及螞蟻的集群活動三個方面。單個螞蟻缺乏智能，但整個蟻群則表現為一種有效的智能行為。通過這種群體智能行為建立的路徑選擇機制可使蟻群算法的搜索向最優解靠近。

采用蟻群算法研究VRP問題的研究現狀包括：馬建華等[9]研究了基于動態規劃方法的多車場最快完成車輛路徑問題的變異蟻群算法；辛穎[10]通過對MMAS蟻群算法進行了三種策略的改造，指出蟻群算法可以找到相對較好的解和很強的魯棒性；陳迎欣[11]針對蟻群算法的缺點，分別對信息素更新策略、啟發因子進行改進，引入搜索熱區機制，有效解決車輛路徑優化問題；段征宇等[12]通過最小成本的最鄰近法生成蟻群算法和局部搜索操作設計了一種求解TDVRP問題的改進蟻群算法。

2.4 粒子群算法（Particle Swarm Optimization，PSO）

PSO算法是通過對鳥群覓食行為的研究而得出的一種群體并行優化算法，它從隨機解出發，通過迭代尋找最優解。蟻群算法具有容易實現、收斂速度快、精度高等優點，在多種優化問題上均取得了較好的效果。但是由于PSO算法是通過粒子之間的相互作用來尋找最優解，缺乏像遺傳算法那樣的變異機制，因而PSO算法容易陷入局部最優。

采用粒子群算法研究VRP問題的研究現狀包括：馬炫等[13]提出了一種基于粒子交換原理的整數粒子更新方法求解有時間窗約束的車輛路徑問題；吳耀華和張念志[14]以處理集貨或送貨非滿載帶時間窗車輛路徑優化問題為背景，提出了帶自調節機制的局部近鄰粒子群算法解決VRP問題。

2.5 蝙蝠算法（Bat Algorithm，BA）

蝙蝠算法是劍橋大學學者Yang[15]于2010年提出的一種新型群智能進化算法，模擬自然界中蝙蝠通過超聲波搜索、捕食獵物的生物學特性，是一種基于種群的隨機尋優算法。截至目前，蝙蝠算法主要用于求解連續域的函數優化問題，只有少數學者將其用來求解離散型問題，具有很好的研究前景。

采用蝙蝠算法研究VRP問題的研究現狀包括：馬祥麗等[16]將蝙蝠算法應用于求解VRP問題，在蝙蝠速度更新公式中引入了慣性權重，對基本蝙蝠算法進行了改進，克服了基本蝙蝠算法的不足之處；馬祥麗等[16]針對VRPTW問題的具體特性重新定義了蝙蝠算法的操作算子，設計了求解VRPTW 問題的蝙蝠算法，并采用罰函數的方式對目標函數進行了簡化求解。

3 總結與展望

車輛路徑問題由于約束條件的不同其分類多種多樣，數學模型與求解算法也層出不窮。本文總結了近幾年一些相關學者對VRP問題的研究和求解算法，通過較為系統地總結VRP問題，本文總結出以下當前研究存在的問題和今后可能的研究方向：

（1）研究目標太過理想化。目前學者研究VRP的研究過于注重成本最小和路徑最短，大部分是單目標優化，而在實際應用中，配送的駕駛員也可能會因許多原因耽誤計劃的行程，顧客的需求各異甚至沖突，顧客滿意度與企業成本最小化目標之間存在效益悖反的矛盾。今后的研究可以將成本、路程、駕駛員休息、顧客滿意度等多個目標聯合起來進行研究，并可以通過線性加權的方式進行綜合求解。

（2）單個約束的VRP問題由于研究時間較長，現在已經研究的較為成熟，而且其應用局限也比較大，應該考慮將多個約束條件結合起來，建立符合實際的多約束條件的車輛路徑問題，更好地解決企業的配送優化。

（3）雖然啟發式算法具有全局搜索能力強，運算方便等優點，但是也存在著局部搜索能力差、收斂時間過長、易陷于局部最優等問題。使用單一的群智能算法不是求解VRP的最有效算法，將兩種和多種群智能算法結合起來研究車輛路徑問題，取長補短，是今后應該考慮的問題；同時，應考慮尋求更多的智能優化算法來求解VRP問題。

參考文獻：

[1] GB. Dantzig， JK. Ramser. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 蔣波. 基于遺傳算法的帶時間窗車輛路徑優化問題研究[D]. 北京：北京交通大學（碩士學位論文），2010.

[3] 趙辰. 基于遺傳算法的車輛路徑優化問題研究[D]. 天津：天津大學（碩士學位論文），2012.

[4] 張群，顏瑞. 基于改進遺傳算法的混合車輛路徑問題[J]. 中國管理科學，2012，20（2）：121-128.

[5] 郎茂祥. 裝卸混合車輛路徑問題的模擬退火算法研究[J]. 系統工程學報，2005，20（5）：485-491.

[6] 穆東，王超，王勝春，等. 基于并行模擬退火算法求解時間依懶型車輛路徑問題[J]. 計算機集成制造系統，2015，21（6）：1626

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業工程與管理，2015，20（3）：1-8.

[8] M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing， 2010，26（6）：564-569.

[9] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統工程理論與實踐，2011，31（8）：1508

-1516.

[10] 辛穎. 基于蟻群算法的車輛路徑規劃問題求解研究[D]. 長春：吉林大學（碩士學位論文），2015.

[11] 陳迎欣. 基于改進蟻群算法的車輛路徑優化問題研究[J]. 計算機應用研究，2012，29（6）：2031-2034.

[12] 段征宇，楊東援，王上. 時間依賴型車輛路徑問題的一種改進蟻群算法[J]. 控制理論與應用，2010，27（11）：1557-1563.

[13] 馬炫，彭M，劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應用，2009，45（27）：200-204.

[14] 吳耀華，張念志. 帶時間窗車輛路徑問題的改進粒子群算法研究[J]. 計算機工程與應用，2010，46（15）：230-235.

篇12

1背景

數據結構和算法是計算機科學與技術、軟件工程等相關專業的專業基礎課,其重要性不言而喻,在教學過程中需要運用多種教學方法,讓學生領會算法實現的過程和本質,加深對所學知識的理解、記憶和應用。在數據結構和算法課程教學中,圖狀結構的教學是一個難點,特別是涉及到圖的具體應用時,更讓學生難以掌握,本文將圖示教學法應用到數據結構中關于圖狀結構的一個典型應用――最小生成樹問題,給出該教學方法的基本方法和過程,取得了良好的教學效果。

最小生成樹是圖狀(網絡)結構中一個典型的實踐應用,可以解決實際中諸如公路網的規劃,即在n個城市中,如何規劃n-1條公路,使得n個城市都可以連接起來,而所有城市間的連接線長度的總和最短(所要修建的公路長度最短,因而費用最少)。

對于這個典型的應用,絕大多數教科書均介紹了普里姆(Prim)算法,用于求最小生成樹問題,然而教科書對這個算法實現的論述,一般是先介紹應用背景,然后就給出算法實現的過程,缺少形象的算法分析過程,課堂教學講解如果按照這種方式去傳授,學生在理解上十分吃力,而且不能有效地長期記憶。筆者結合自己在教學中的經驗,將以上算法采用了圖示教學法來分析其基本原理和實現過程,并給出算法實現過程,取得了良好的效果。

2教學方法

圖示教學法就是用各種圖形表示的方法描述問題、引導學生的思考,增強對新知識的記憶,并在教學中被廣泛使用。最小生成樹屬于網絡的實踐應用,下面以圖1為例,用圖示教學法來對最小生成樹算法進行圖示過程分析。

假設某一區域內有n個城市,現要為這些城市修建城間公路,使得任意兩城市間都能夠相互通達(連通),由于要求所有的城市都在該公路網上,某兩個城市間的道路稱為一個路段,則修建的道路路段總數應等于n-1個(容易理解:如果路段總數小于n-1,則會有存在城市不能處在該道路網的節點上;如果路段總數大于n-1則會存在某兩個城市間有至少兩個路段,則路段距離的總和將不是最小),先從這些城市中任選一個作為種子,把剩下的城市用路段連接到由該種子城市為起始點的城市網絡中,保證路段長度總和最小(最優路段網),則最后連接好的路段即為最小生成樹。

如圖1,每個帶圈的數字表示一個城市,城市間的邊表示城市間的距離,如果兩城市間沒有邊存在,則表示這兩個城市間不適宜修道路(如有山脈或河流隔斷,造價太高),假設種子城市為數字1(選定的網絡的起始頂點),通過圖示教學法求最優路段網的過程如圖2:

圖中,Li-j表示城市i與城市j間的距離,例如在(b)中,當把城市2加入到最優路段網后,城市3、4、6與該最優路段網的距離發生了變化,例如城市3,由于由L1-3(=∞)> L2-3(=5),故其與最優路段網的距離由原先的∞也轉變為5

首先構造一個初始最優路段網,但該網絡只有一個節點,即“種子城市”,其位于圖2(a)中的中心圓圈內,圈外的節點稱為節點或城市。然后根據圖1城市間的距離(網絡節點間的邊的權值),求其它所有城市(網絡節點)與種子城市間的距離(通過訪問網絡的物理存儲結構如鄰接表獲取),該圖表示僅通過了種子城市來連接所有的其它城市,圖中中心圓圈外的城市當前還沒有加入到最優路段網規劃中,圈外連接每個城市與中心圓圈的實線表示該城市如果按當前規劃方案加入到該路段網時所需要建造的路段長度(即網絡邊的權),圈內的虛線表示當前城市通過某一個最優路段網中的某城市為“橋梁”,而進入到該網絡中。例如,城市2如果通過城市1進入規劃網,則需要修建長度為16(僅表示相對數值)的道路,城市5要修建長度19的道路,城市6要修建長度21的道路,而城市3和城市4無法通過城市1來連接到最優路段網中(距離為無窮大,∞),而必須通過其它城市作為“橋梁”,來進入該規劃網絡中。很明顯,如果按照該方案來把所有的城市都加入到初始最優路段網,得到的路段網如圖2(g),需要修建的路段網總長度為∞,顯然不是最優路段網。

注意到為了使規劃的路段網是最優的(路段長度總和最小),只要保證每次加入到最優路段網中的城市都具有最短路段長度,則最后的路段總長度也必然最小。在圖2(a)中,城市2與種子城市具有最小的距離(16),因而不可能找到其它任何一個路段,實現“種子城市與其它城市實現互連時,種子城市到其它任意一個城市的路段距離小于該值”,因而路段②-①必然是滿足種子城市連通其它城市的最優路段,將城市2加入到最優路段網后,得到圖2(b)。注意到當城市2加入到最優路段網后,城市3、4、6如果是通過城市2為“橋梁”(圖中的虛線所示),加入到該最優路段網中,可以使各自的路段長度由原先的∞、∞和21分別縮短到5、6、11(其它城市通過城市2無法實現路段長度縮短,因為保持不變),此時路段總長度也由原先的∞縮小到57(即16+5+6+19+11),較圖2(a),該方案有了很大的進步。然而該網絡仍不是最優路段網,因為其僅保證了路段②-①的最優性(注意圓圈內的網絡是最優的),而其它城市到該網絡中的路段并非最優,這樣不能保證路段總長度最小。

進一步注意到,在所有的當前城市中,城市3距離最優路段網的距離最短(5),也就是為了使當前最優路段網(圓圈內的城市及連線)與其它城市能夠實現連通,且連通后的路段總長度最小,所以當前應加入城市3(圖2(c))。城市3的加入或許可以使得其它的城市通過該城市為“橋梁”,而縮短城市到最優路段網的距離(當然這里城市3的加入實際并沒有使其它城市到最優路段網的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優路段網中(因為在余下的城市中,城市4到最優路段網的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優路段網的距離由原來的19縮短到18(其它路段不變)。第5步將城市6加入到最優路段網中(圖2(e)),該城市的加入沒有影響余下的城市(當前僅剩一個城市,即城市5),最后將城市5加入到最優路段網中(圖2(f))。得到的最終的最優路段網如圖2(h),其路段長度的總和為56(16+5+11+6+18)。

3算法求解

有了如上的圖示教學法描述的計算最小生成樹實現基本過程,在講解算法時就比較容易了。算法在實現時需要構造三個輔助數組:第1個數組A[n](n為節點數)記錄當前節點是節點還是已加入最短路段(路徑)網的節點,數組元素A[i]=0或1,0表示節點i是一個節點,當加入到最短路段(路徑)網后,A[i]=1;第2個數組B[n]記錄各節點到最短路段(路徑)網的距離,用B[n]表示;第3個數組C[n]記錄節點通過最短路段(路徑)網內的哪一個節點為“橋梁”而進入該路段(路徑)網的。注意這里的路徑R和路段L是兩個不同的概念,路段是節點的邊,而路徑是具有共同節點的有序邊起節點與尾節點首尾相連在一起的序列,如在圖1中,其中的一個路徑R1-3=L1-2+L2-3。下面結合圖2和圖3,給出這些數組的值在計算過程中的變化情況。

輔助數組的變化情況如下圖3所示,其中圖3(a)即對應于圖2(a),圖3(b)對應于圖2(b),依此類推。在圖3(a)中,首先只有第一個節點進入最短路段網,因此A[1]=1,其它的A元素均為0,節點與最短路段網的距離B[i]與圖2(a)中的距離對應,這里節點1由于已在最短路段網,所以B[1]=0,由于所有的節點目前都是通過節點1與最短路段網連接,因而所有的C[i]的值都是1。在圖3(b)中,由于節點2距最短路段網的距離最小(16),節點2進入最短路段網,因而A[2]=1,此時由于節點2已進入最短路段網,因而B[2]=0,而節點3和節點4通過節點2,使它們距最短路段網的距離由原先的∞縮短到5和6,節點6也通過節點2使B[6]由21縮小到11。圖3(c)、3(d)、3(e)、3(f)的過程不再贅述。最后的結果(圖3(f))表明,節點1通過其本身進入最短路段網,節點2通過節點1進入最短路段網,節點3、4、6均通過節點2為“橋梁”進入最短路段網,而節點5通過節點4進入最短路段網。

基于上述分析,不難給出以上算法的實現描述:

(1) 初始化數組A、B、C,結果如圖2(a)、圖3(a),這里假設以節點1為起始(源)節點,共有n個節點。

(2) 反復執行如下操作:將B[i]中值最小的元素對應的編號i(即節點i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對應的B[j]和C[j]的值,修改的依據是:如果B[j]>Li-j,則用B[j]的值更改為Li-j。直至所有的A[i](1

(3) 輸出結果,將B、C的最后值輸出即可以得到最后結果,B所有的元素最后都為0,表示所有的元素都進入了最短路段網(最小生成數網),而C中的元素值表示的是當前節點元素(即節點1、2、3、4、5或6)是通過C中表示的節點編號而進入最短路段網的,即:節點1是通過其自身進入路段網,節點2通過節點1進入路段網,節點3、4和6均通過節點2進入路段網,節點5通過節點4進入路段網。

4結論

本文提出將圖示教學法可應用于數據結構和算法課程教學的多個環節中,有些算法在大多數教科書中有了一定的圖示過程表示,而有些算法卻沒有給出形象的圖示表示,因而需要在教學中應補充。本文以圖狀結構中的最小生成樹算法為例,通過圖示分析,詳細地講解這個算法的核心思想和實現過程,通過視覺刺激,使學生能夠加深對這個算法過程的把握,取得了良好的教學效果。

參考文獻:

[1] 戴敏,于長云,董玉濤. 高效學習數據結構[J]. 計算機教育,2006(2):59-60.

篇13

文章編號：1671-489X（2014）04-0040-03

以計算機和互聯網為代表的現代科技迅猛發展，越來越多的具有高科技含量的裝備在教育領域得到了廣泛應用，使教育裝備的分配、管理、保障、運輸和更新等工作變得更加復雜。這勢必要求學校的管理人員不僅要定性、更要定量地研究教育裝備的決策問題，否則將無法做出可行性決策，更不要提什么優化了。同時，我國的社會發展階段和經濟發展水平共同決定了教育經費的數目是有限的，在保證日常教學和科研的前提下，如何盡可能地壓縮管理成本是教育裝備管理工作中面臨的難題。

因此，本文以如何使教育裝備在運輸過程中的成本最低為切入點，提出教育裝備中心選址的最優化問題，采用Floyd最短路徑算法實現其求解，為教育裝備的管理工作提供科學依據。

1 數學模型

圖論的產生和發展經歷了200多年歷史，1736年瑞士著名數學家歐拉（L.Euler）提出并解決了“哥尼斯堡七橋問題”，標志著圖論的起源[1]。隨著現代生產和科學技術的迅猛發展，特別是計算機的出現和互聯網的普及，使圖論方法得以快速擴展，圖論已成為現代數學科學中的一門引人注目的新興學科，滲透到物理學、化學、電工學、管理學、控制論、信息論等諸多學科[2-3]。

最短路徑的求取是圖論中的一個典型問題。所謂最短路徑是指在指定網絡中兩點間的一條距離最小的路[4]。在求解網絡上任意節點間最短路徑的方法中，學術界一致公認的較好的算法是Dijkstra和Floyd算法。這兩個方法的主要區別是：Dijkstra算法可以計算從圖中某一點到其他各點的最短路徑；Floyd算法主要用于計算圖中所有點之間的最短路徑。顯然，在研究教育裝備運輸問題時，可以采用Dijkstra方法進行計算，從而得到裝備中心到目標學校之間的最短路徑。

當目標學校有多個校區時，裝備中心地址的選擇必須考慮多方面因素，其中最基本的一點是保證該裝備中心到所有校區的最短路徑之和最小。此時，如果采用狄克斯屈拉算法，需要計算備選地址和各個校區之間的最短距離，該過程需要重復多次，且計算繁瑣；而計算圖中所有點之間的最短路徑正是Floyd算法所“擅長”的。因此，本文在研究教育裝備中心的選址問題時，優選Floyd算法。

表1中每行的合計數表示教材配送中心建于該校區時，滿足所有校區每學期教學需要的大學英語教材運輸的冊千米數。從表中可以看出C列的合計數最小，表明當把教材配送中心建于C校區時，教材運輸的冊千米數最小，為107 500。

3 結論

雖然規模龐大的高校校區比較分散，但是每學年在每個校區開設的專業和在校生規模基本保持不變，這就保證了每個校區每學年需要的教育裝備數目基本保持穩定。因此，高校在建設裝備中心時的選址問題必須充分考慮如何使總的運輸成本最低，往往一個錯誤的決策將導致在以后每次裝備運輸中都產生浪費。本文依據Floyd最短路徑算法給出了定量計算，通過本文的實例相信可以為每位管理者提供嶄新的思路。

參考文獻

[1]李慧.教育裝備運籌規劃[M].北京：北京大學出版社，2010：100-116.

[2]辛宇.基于運籌學圖論的物流網絡優化研究[J].中國外資，2011（6）：125-127.

[3]蔣智凱.淺談運籌學教學[J].重慶科技學院學報：社會科學版，2010（24）：176-177.

[4]徐俊明.圖論及其應用[M].3版.北京：中國科學技術大學出版社，2010：84-90.