序論：速發(fā)表網(wǎng)結(jié)合其深厚的文秘經(jīng)驗，特別為您篩選了11篇路徑規(guī)劃典型算法范文。如果您需要更多原創(chuàng)資料，歡迎隨時與我們的客服老師聯(lián)系，希望您能從中汲取靈感和知識！

篇1

交通運輸?shù)默F(xiàn)代化使人們享受便利的同時，也面臨道路擁堵、事故頻發(fā)等問}。近年來，智能交通系統(tǒng)越來越受到人們的重視，它涉及到交通領(lǐng)域諸多方面，如最優(yōu)路徑選擇、車輛路徑規(guī)劃、動態(tài)車輛調(diào)度、交通流量控制等。其中一個重要的應(yīng)用是一類典型的以數(shù)學(xué)理論為基礎(chǔ)的組合優(yōu)化問題，而蟻群算法具有內(nèi)在的搜索機制及正反饋性，適合求解一系列的組合優(yōu)化問題。

1 蟻群算法描述

蟻群算法源于20世紀90年代初意大利學(xué)者M.Dorigo首次提出的螞蟻系統(tǒng)。它是基于種群的啟發(fā)式放生進化系統(tǒng)，是通過對蟻群覓食過程中其行為的研究而得出的一種算法。主要思路是螞蟻借助自己路徑尋優(yōu)的能力可以找到巢穴與食物之間最短的途徑。在尋找過程中主要依靠的是每個螞蟻在行進過程中留下的揮發(fā)性分泌物――信息素，依靠信息素，蟻群的螞蟻之間可以相互合作，相互配合，因此形成的正反饋可以使每只螞蟻找到所有路徑中最短的路徑。

螞蟻a從節(jié)點j移動至k的轉(zhuǎn)移概率可以從式（1）中獲?。?/p>

（1）

（2）

（3）

2 蟻群算法的應(yīng)用優(yōu)勢

蟻群算法，又名螞蟻算法，螞蟻可以利用信息素的濃度大小從而尋找到覓食的最優(yōu)路徑。該算法的優(yōu)點可以總結(jié)為：

2.1 并行分布式計算

每個螞蟻都是獨立的個體，在覓食過程中屬于多起點同時啟動，互不影響，從根本上分析該過程屬于分布式的多Agent系統(tǒng)，整體蟻群最終任務(wù)的順利完成不會由于某些個體的缺陷而受到影響。該算法具有真實可用性，并且可用于解決對單目標的優(yōu)化或者對多目標的優(yōu)化等重要問題。此外，螞蟻算法還可進行并行計算。

2.2 魯棒性

蟻群算法的最終結(jié)果與螞蟻最初選擇的路徑無太大關(guān)系，在利用人工仿真螞蟻進行問題求解過程中，不需要對其進行人工的修整。把問題簡單化，可以和其他算法相互結(jié)合求解最優(yōu)問題。

2.3 自組織性

蟻群算法組織指令的來源為系統(tǒng)內(nèi)部，它不受外界環(huán)境的干擾，因此該算法具有自組織性。

2.4 正反饋性

螞蟻對于最優(yōu)路徑的選擇主要依靠路徑上信息素濃度的多少，信息素的堆積是正反饋的過程，路徑上信息素的含量越多則該路徑被選擇的幾率就會越大，正反饋的作用是使整體能夠更快的尋找到最優(yōu)途徑，正反饋在蟻群算法中處于重要地位。

2.5 易于實現(xiàn)

它是一種啟發(fā)示算法，其計算復(fù)雜性為，整個算法的空間復(fù)雜度是：。

3 蟻群算法在智能交通領(lǐng)域的應(yīng)用空間

蟻群算法在解決組合優(yōu)化問題方面有著明顯的優(yōu)勢，從而在智能交通領(lǐng)域也有著廣泛的應(yīng)用空間。

3.1 車輛路徑導(dǎo)航

根據(jù)行車人員的需要，根據(jù)對實時路況信息的統(tǒng)計，系統(tǒng)可以智能的為其推薦最優(yōu)路徑，節(jié)省時間，節(jié)省資源。

3.2 動態(tài)車輛調(diào)度

當客戶需要調(diào)度中心為其進行車輛服務(wù)時，調(diào)度中心要考慮到客戶的情況，要考慮到效率的問題，要考慮到行車路線、行駛時間等問題。蟻群算法便可迅速得到合理的解決方案，使客戶和調(diào)度中心均可受益。

3.3 車輛路徑規(guī)劃

面對多個客戶不同的要求時，配送中心要根據(jù)實際情況進行車輛的配送，通過蟻群算法系統(tǒng)獲取整體的最優(yōu)路線，根據(jù)路線規(guī)劃，及時進行車輛出發(fā)以滿足客戶要求，同時充分利用了道路資源和車輛資源。

3.4 公共交通智能化調(diào)度

利用先進的技術(shù)手段、大型數(shù)據(jù)庫技術(shù)等動態(tài)地獲取實時交通信息，實現(xiàn)對車輛的實時監(jiān)控和調(diào)度，最終建立集運營指揮調(diào)度、綜合業(yè)務(wù)通信及信息服務(wù)等為一體的智能化管理系統(tǒng)。

3.5 交通流量控制

通過蟻群算法簡化復(fù)雜的道路交通網(wǎng)絡(luò)，盡量使交通流量在各個道路上分布均勻，避免因流量過大而造成車輛的阻塞。及時了解交通流量情況，緩解了交通擁擠，降低了交通事故的發(fā)生率。

參考文獻

[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41

[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999

[3]楊海.蟻群算法及其在智能交通中的應(yīng)用[D].濟南：山東師范大學(xué)，2008：14-18

作者簡介

白曉（1979-），女。工學(xué)碩士學(xué)位?，F(xiàn)供職于廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系。主要研究方向為軟件工程、智能算法。

篇2

1 引言

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

2 背景知識

神經(jīng)網(wǎng)絡(luò)模擬生物進化思維，具有獨特的結(jié)構(gòu)神經(jīng)元反饋機制，其具有分布式信息存儲、自適應(yīng)學(xué)習、并行計算和容錯能力較強的特點，以其獨特的結(jié)構(gòu)和信息處理方法，在自動化控制、組合優(yōu)化領(lǐng)域得到了廣泛的應(yīng)用，尤其是大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分析和態(tài)勢預(yù)測中，神經(jīng)網(wǎng)絡(luò)能夠建立一個良好的分類學(xué)習模型，并且在學(xué)習過程中優(yōu)化每一層的神經(jīng)元和神經(jīng)元連接的每一個節(jié)點。1993年，Banta等將神經(jīng)網(wǎng)絡(luò)應(yīng)用于移動機器人路徑規(guī)劃過程中，近年來，得到了廣泛的研究和發(fā)展，morcaso等人構(gòu)建利用一個能夠?qū)崿F(xiàn)自組織的神經(jīng)網(wǎng)絡(luò)實現(xiàn)機器人導(dǎo)航的功能，并且可以通過傳感器訓(xùn)練網(wǎng)絡(luò)，取得更好的發(fā)展，確定系統(tǒng)的最佳路徑。神經(jīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)模型可以分為：

2.1 前向網(wǎng)絡(luò)

網(wǎng)絡(luò)中各個神經(jīng)元接受前一級的輸入，并輸出到下一級，網(wǎng)絡(luò)中沒有反饋，可以用一個有向無環(huán)路圖表示。這種網(wǎng)絡(luò)實現(xiàn)信號從輸入空間到輸出空間的變換，它的信息處理能力來自于簡單非線性函數(shù)的多次復(fù)合。網(wǎng)絡(luò)結(jié)構(gòu)簡單，易于實現(xiàn)。反傳網(wǎng)絡(luò)是一種典型的前向網(wǎng)絡(luò)。

2.2 反饋網(wǎng)絡(luò)

網(wǎng)絡(luò)內(nèi)神經(jīng)元間有反饋，可以用一個無向的完備圖表示。這種神經(jīng)網(wǎng)絡(luò)的信息處理是狀態(tài)的變換，可以用動力學(xué)系統(tǒng)理論處理。系統(tǒng)的穩(wěn)定性與聯(lián)想記憶功能有密切關(guān)系。Hopfield網(wǎng)絡(luò)、波耳茲曼機均屬于這種類型。

3 基于人工神經(jīng)網(wǎng)絡(luò)的移動機器人路徑規(guī)劃算法

神經(jīng)網(wǎng)絡(luò)解決移動機器人路徑規(guī)劃的思路是：使用神經(jīng)網(wǎng)絡(luò)算法能夠描述機器人移動環(huán)境的各種約束，計算碰撞函數(shù)，該算法能夠?qū)⒌窂近c集作為碰撞能量函數(shù)和距離函數(shù)的和當做算法需要優(yōu)化的目標函數(shù)，通過求解優(yōu)化函數(shù)，能夠確定點集，實現(xiàn)路徑最優(yōu)規(guī)劃。神經(jīng)網(wǎng)絡(luò)算法在移動機器人路徑規(guī)劃過程中的算法如下：

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

（2）動態(tài)優(yōu)化神經(jīng)網(wǎng)絡(luò)，根據(jù)神經(jīng)網(wǎng)絡(luò)的目標節(jié)點和障礙物的具置信息，在神經(jīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的映射中產(chǎn)生神經(jīng)元的外部輸入；

（3）確定目標值附件的神經(jīng)元活性值，并且使用局部側(cè)的各個神經(jīng)元之間，連接整個神經(jīng)網(wǎng)絡(luò)，并且在各個神經(jīng)元中進行傳播。

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

（5）如果機器人到達目標點則路徑規(guī)劃過程結(jié)束，否則轉(zhuǎn)步驟（2）。

4 基于人工神經(jīng)網(wǎng)絡(luò)的移動機器人路徑規(guī)劃技術(shù)展望

未來時間內(nèi)，人工神經(jīng)在機器人路徑規(guī)劃過程中的應(yīng)用主要發(fā)展方向包括以下幾個方面：

4.1 與信息論相融合，確定神經(jīng)網(wǎng)絡(luò)的最優(yōu)化化目標解

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

4.2 與遺傳算法想結(jié)合，確定全局最優(yōu)解

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

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

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

5 結(jié)語

隨著移動機器人技術(shù)的發(fā)展，路徑規(guī)劃作為最重要的一個組成部分，其得到了許多的應(yīng)用和發(fā)展，其在導(dǎo)航過程中，也引入了許多先進的算法，比如神經(jīng)網(wǎng)絡(luò)，更加優(yōu)化了移動的路徑。未來時間內(nèi)，隨著神經(jīng)網(wǎng)絡(luò)技術(shù)的改進，可以引入遺傳算法、信息論、蟻群算法等，將這些算法優(yōu)勢結(jié)合，將會是路徑規(guī)劃更加準確和精確。

參考文獻

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

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

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

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

篇3

二、算法模型

基于時間成本的物流線路優(yōu)化計算主要運用到三個求解算法，分別是聚類算法、最優(yōu)路徑算法和訂單日規(guī)劃算法。基本求解方案是：第一步按照車輛裝載率完成對客戶興趣點聚類；第二步細致優(yōu)化配送路徑；第三步平衡每日訂單分布。

1.聚類算法

聚類是空間數(shù)據(jù)挖掘中的一個重要研究領(lǐng)域，是指將物理的或抽象的對象分組成為由類似對象組成的多個類（簇）的過程。

以紹興煙草為例，聚類計算時首先采用自下而上的一階段方法對全地區(qū)26000個零售戶點進行聚類，獲得411個初始聚類結(jié)果。再根據(jù)實際需求，按照類容量將前408個類作為直接指派的初始類核，以配送車裝載率90%作為類容量上限，進行直接指派聚類，最終獲得聚類結(jié)果。

2.最優(yōu)路徑算法

最優(yōu)路徑算法的目標是尋找給定起點和終點間的最短路徑，文章采用Dijkstra（迪杰斯特拉）算法。Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

⑴初始時，S只包含源點，即S=v。U包含除v外的其他頂點，U中頂點u對應(yīng)的距離值為邊上的權(quán)（若v與u有邊）或 （若u不是v的出邊鄰接點）。

⑵從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。

⑶以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值為頂點k的距離加上邊上的權(quán)。

⑷重復(fù)步驟（2）和（3）直到所有頂點都包含在S中。

3.配送工作量模型和訂單日規(guī)劃算法

進行訂單日規(guī)劃時，文章引入工作量模型概念，將綜合作業(yè)時間作為線路優(yōu)化的單一標準，把送貨戶數(shù)、送貨量、行駛里程等多維度統(tǒng)一轉(zhuǎn)換成工作時間，解決線路優(yōu)化時指標過多，計算困難的問題。

綜合作業(yè)時間=裝車交接時間+車輛行駛時間+基本服務(wù)時間+客戶交接時間+現(xiàn)金繳款時間。裝車交接時間=（裝車準備時間車次）+（裝車框數(shù)單框裝車時間）

訂單日規(guī)劃算法的目標是確定各配送線路的配送車輛和配送日，規(guī)劃要求滿足以下約束條件：車輛數(shù)最少；一周內(nèi)各配送車輛工作時間基本均衡；每天各配送車輛工作時間基本均衡；每天工作時間上限設(shè)定6.5小時。

訂單日規(guī)劃算法模型：

約束條件：

（1.1）

（1.2）

（1.3）

（1.4）

i 需要安排的路線序號；取值范圍從1到路線的最大數(shù)；

j 送貨車序號；取值范圍從1到指定車輛數(shù)；

k訂單日的序號；取值范圍從1到5，表示一周配送5天；

b每天所有車輛工作時間的上限；

c每輛車一周工作量上限；

d每輛車每天工作量的上限，d為6.5小時。

公式（1.1）一條路線有卻只能有某輛車在某一天配送；

公式（1.2）每天所有車

的工作量不能超過上限b；

公式（1.3）每輛車每周的工作量不能超過上限c；

篇4

關(guān)鍵詞：多機器人；路徑規(guī)劃；強化學(xué)習；評判準則

Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.

Key words:multirobot；path planning;reinforcement learning;evaluating criteria 

近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributed problem solving）和MAS（multiagent system）兩個方面。一些從事機器人學(xué)的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應(yīng)用于多機器人系統(tǒng)的研究中，將單個機器人視做一個能獨立執(zhí)行特定任務(wù)的智能體，并把這種多機器人系統(tǒng)稱為多智能體機器人系統(tǒng)（MARS）。因此，本文中多機器人系統(tǒng)等同于多智能體機器人系統(tǒng)。目前，多機器人系統(tǒng)已經(jīng)成為學(xué)術(shù)界研究的熱點，而路徑規(guī)劃研究又是其核心部分。

機器人路徑規(guī)劃問題可以建模為一個帶約束的優(yōu)化問題，其包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務(wù)，它是移動機器人導(dǎo)航與控制的基礎(chǔ)。單個移動機器人路徑規(guī)劃研究一直是機器人研究的重點，且已經(jīng)有許多成果[1~3]，例如在靜態(tài)環(huán)境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據(jù)理論建圖等；動態(tài)環(huán)境中常見的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規(guī)劃研究比單個機器人路徑規(guī)劃要復(fù)雜得多，必須考慮多機器人系統(tǒng)中機器人之間的避碰機制、機器人之間的相互協(xié)作機制、通信機制等問題。

1 多機器人路徑規(guī)劃方法

單個機器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規(guī)劃側(cè)重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機器人路徑時，更多考慮的是多機器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強化學(xué)習等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規(guī)劃方法擴展而來的。

1）傳統(tǒng)方法 多機器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環(huán)境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產(chǎn)生斥力，目標點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢，機器人在勢場中受到抽象力作用，抽象力使得機器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術(shù)的多機器人路徑規(guī)劃，較好地解決了這個問題。

2）智能優(yōu)化方法 多機器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問題，如多機器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構(gòu)建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達為路徑中一系列中途節(jié)點，并轉(zhuǎn)換為二進制串；然后進行遺傳操作（如選擇、交叉、復(fù)制、變異），經(jīng)過N次進化，輸出當前的最優(yōu)個體即機器人的最優(yōu)路徑。遺傳算法的缺點是運算速度不快，進化眾多的規(guī)劃要占據(jù)很大的存儲空間和運算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。 

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷， 使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機器人的路徑規(guī)劃問題。

朱慶保[9]提出了在全局未知環(huán)境下多機器人運動螞蟻導(dǎo)航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導(dǎo)航子目標，再由兩組螞蟻相互協(xié)作完成機器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進行與其他機器人的碰撞預(yù)測與避碰規(guī)劃。因此，機器人的前進路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導(dǎo)下，使機器人沿一條全局優(yōu)化的路徑到達目標點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機器人缺乏必要的學(xué)習，以至于整個機器人系統(tǒng)路徑難以是最優(yōu)路徑。

強化學(xué)習[10，11] (又稱再激勵學(xué)習)是一種重要的機器學(xué)習方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

強化學(xué)習算法一般包含了兩個步驟：a）從當前學(xué)習循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過所獲得的瞬時獎懲值對該策略進行評估。學(xué)習循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強化學(xué)習方法有：Monte Carlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′學(xué)習算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學(xué)習的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點。M. J. Mataric[12]首次把強化學(xué)習引入到多機器人環(huán)境中。而基于強化學(xué)習的多機器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構(gòu)建環(huán)境地圖；強化學(xué)習可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設(shè)計為基于行為分解的無模型非均勻結(jié)構(gòu)，新的再勵函數(shù)結(jié)構(gòu)使得學(xué)習速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機器人的趨向目標和避障行為密切相關(guān)，對反映各基本行為的再勵函數(shù)取加權(quán)和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設(shè)計得合理與否及其確切程度將影響再勵學(xué)習的收斂速度。王醒策等人[14]在動態(tài)編隊的強化學(xué)習算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強化學(xué)習方法進行路徑規(guī)劃。其缺點是學(xué)習次數(shù)較多、效率不高，當機器人數(shù)目增加時，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強化學(xué)習的路徑規(guī)劃在多機器人環(huán)境下的學(xué)習將變得比較困難，需要對傳統(tǒng)的強化學(xué)習加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強化學(xué)習[16]等。

3)其他方法 除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃，把運籌學(xué)中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居，第一層鄰居的鄰居為該機器人的第二層鄰居， 依此類推。那么層級越高（即越近)的鄰居，它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結(jié)合的多移動機器人路徑規(guī)劃方法。其首先構(gòu)造一個以各機器人最優(yōu)運動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng)， 在離線狀態(tài)下完成; 然后各機器人在此專家系統(tǒng)的支持下， 以最優(yōu)規(guī)劃策略為基礎(chǔ)， 采用速度遷移算法， 自主決定其控制。該方法擁有較好的穩(wěn)定性與復(fù)雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規(guī)劃框架較好地解決了多機器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規(guī)劃。以基于行為的導(dǎo)航算法為基礎(chǔ)，把機器人隊列的運動過程劃分為正常運動、避障和恢復(fù)隊形三個階段。在避障階段，引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時，規(guī)劃機器人的局部目標位姿使隊列快速恢復(fù)隊形。其算法重點為避障機器人進入避障狀態(tài)，暫時脫離隊列，并以虛擬機器人代替避障機器人。

2 多機器人避碰和避障

避障和避碰是多機器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內(nèi)外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎(chǔ)，擴充并完善了路徑/速度分解方案來協(xié)調(diào)多機器人，設(shè)立集中管理agent進行整體規(guī)劃，為每個機器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運動特征進行分布式規(guī)劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對簡單的子系統(tǒng)問題，由各智能機器人依據(jù)任務(wù)要求和環(huán)境變化， 獨立調(diào)整自身運動狀態(tài)，完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強化學(xué)習多機器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突，避免死鎖，提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過調(diào)整機器人的運動速度實現(xiàn)多機器人避碰，將避碰問題轉(zhuǎn)換為高維線性空間的優(yōu)化問題， 并進一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點是系統(tǒng)的復(fù)雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強、便于數(shù)學(xué)描述，且適合于多自由度機器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力，并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機器人的運動狀態(tài)和運動要求結(jié)合起來，有效地保證機器人的安全性，提高機器人在復(fù)雜動態(tài)環(huán)境下行為決策的準確性和魯棒性。

3 多機器人協(xié)作和協(xié)調(diào)機制

多機器人間的運動協(xié)調(diào)[27~31]是多機器人路徑規(guī)劃的關(guān)鍵，也是多機器人與單機器人路徑規(guī)劃相區(qū)別的根本所在。多機器人系統(tǒng)在復(fù)雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務(wù)要求的約束，需要在有限時間、資源的情況下進行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細地規(guī)劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機器人之間進行合作，將一個任務(wù)分成多個子任務(wù)，根據(jù)各自的特點完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

多機器人間典型的協(xié)調(diào)方法[32]有合同網(wǎng)協(xié)議[33]、黑板模型、結(jié)果共享的協(xié)同方法、市場機制。近年來強化學(xué)習在多機器人協(xié)作方面也得到很好的應(yīng)用，陳雪江[32]在基于強化學(xué)習的多機器人協(xié)作方面展開了研究，提出了多智能體協(xié)作的兩層強化學(xué)習方法來求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問題。其主要通過在單個智能體中構(gòu)筑兩層強化學(xué)習單元來實現(xiàn)：第一層強化學(xué)習單元負責學(xué)習智能體的聯(lián)合任務(wù)協(xié)作策略；第二層強化學(xué)習單元負責學(xué)習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協(xié)調(diào)方法；通過對環(huán)境的拓撲建模，從基于行為的機器人學(xué)角度出發(fā)，對任務(wù)進行分解并設(shè)計目標行為，以多目標行為決策理論作為決策支持，從而達到多機器人運動協(xié)調(diào)的目的。

4 多機器人路徑規(guī)劃方(算)法的判優(yōu)準則

通常評價機器人路徑規(guī)劃方(算)法的標準文獻[35]有正確性、時間/空間復(fù)雜度、并行性、可靠性、擴展性、魯棒性和學(xué)習。而多機器人的路徑規(guī)劃除了以上一些衡量標準之外，還需要考慮整個系統(tǒng)的最優(yōu)化以及機器人間的協(xié)調(diào)性。

1)正確性 是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過有窮時間的計算能給出正確的答案。但在多機器人路徑規(guī)劃算法中，正確性主要指:路徑規(guī)劃算法要生成多個機器人協(xié)調(diào)運動的無碰安全路徑;這條路徑是優(yōu)化的。

2)安全性 一般指多機器人所生成的各路徑中節(jié)點與障礙物有一定的距離。但在實際的應(yīng)用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優(yōu)化條件加權(quán)綜合而得到的結(jié)果。

3)復(fù)雜度 一個算法的復(fù)雜性高低體現(xiàn)在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復(fù)雜性越高；反之，所需要的資源越少，該算法的復(fù)雜性就越低。算法的復(fù)雜性包括時間復(fù)雜度和空間復(fù)雜度。

在多機器人的路徑規(guī)劃算法中，算法的復(fù)雜度分析顯得尤為重要。一般地，單機器人路徑規(guī)劃算法的時空復(fù)雜度已經(jīng)頗高，它們的數(shù)量級至少是O(n2)；多機器人的路徑規(guī)劃算法不僅是m-O(n2)(即m個機器人路徑規(guī)劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協(xié)調(diào)需要花費大量的時間和空間。通常多機器人的路徑規(guī)劃算法與機器人的個數(shù)呈指數(shù)關(guān)系O(km×n2)（k為常數(shù)）。這對多機器人路徑規(guī)劃算法的時間/空間復(fù)雜度控制是一個很嚴峻的考驗。

4)并行性 算法的并行性從算法設(shè)計、編寫程序、編譯和運行等多個不同的層次來體現(xiàn)。路徑規(guī)劃過程需要大量的計算，當處理的環(huán)境比較復(fù)雜，機器人工作的環(huán)境過于緊湊，尤其是機器人數(shù)量很多時，算法的時間/空間復(fù)雜度勢必會成為算法效率的關(guān)鍵。因此，在算法設(shè)計和運行上的并行性是通?？紤]的方法。對多個機器人的路徑規(guī)劃盡量采用分布式多進程的規(guī)劃機制，以實現(xiàn)每個機器人路徑規(guī)劃的并行性。

5)可靠性 把多個機器人及其工作環(huán)境看成是一個系統(tǒng)，多機器人處于它們各自的起始點時，稱該系統(tǒng)處于初始狀態(tài)；當它們處于各自的目標點時，稱該系統(tǒng)處于目標狀態(tài)。多機器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過程可能會歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉(zhuǎn)移關(guān)系，就會導(dǎo)致系統(tǒng)紊亂，出現(xiàn)機器人間的碰撞、找不到路徑等惡性后果，使任務(wù)失敗。所以這就對算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關(guān)系，建立有限狀態(tài)自動機模型或Petri網(wǎng)模型，并以此為指導(dǎo)，按照軟件工程的思想，構(gòu)造恰當?shù)乃惴ㄝ斎雭韺λ惴ǖ目煽啃赃M行檢驗。

6)可擴展性 在多機器人的路徑規(guī)劃算法中，可擴展性主要是指一種路徑規(guī)劃算法在邏輯上，或者說在實現(xiàn)上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數(shù)到更多的機器人數(shù)。可擴展性在各種路徑規(guī)劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發(fā)、從對環(huán)境描述的適宜程度出發(fā)、從算法解決這一問題的復(fù)雜度出發(fā)、從算法本身的自適應(yīng)出發(fā)等來考慮。

7)魯棒性和學(xué)習 魯棒性對于多機器人系統(tǒng)非常重要。因為許多應(yīng)用，如路徑規(guī)劃要求連續(xù)的作業(yè)、系統(tǒng)中的單個機器人出現(xiàn)故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務(wù)。學(xué)習是在線適應(yīng)特定的任務(wù)。雖然通用的系統(tǒng)非常有用，但將它用于特定應(yīng)用上時，通常需要調(diào)整一些參數(shù)。具有在線調(diào)整相關(guān)參數(shù)的能力是非常吸引人的，這在將體系結(jié)構(gòu)轉(zhuǎn)移到其他應(yīng)用時可以節(jié)省許多工作。尤其是多機器人系統(tǒng)中機器人的自身學(xué)習和相互間的學(xué)習能夠大大提高整個系統(tǒng)的效率和系統(tǒng)的穩(wěn)定性。

8）最優(yōu)化 對動態(tài)環(huán)境有優(yōu)化反應(yīng)。由于有些應(yīng)用領(lǐng)域涉及的是動態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應(yīng)能力成為能否成功的關(guān)鍵。

5 結(jié)束語

綜上所述，國內(nèi)外研究者在多機器人路徑規(guī)劃取得了一些成果，但是在協(xié)作、學(xué)習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協(xié)調(diào)性，增強機器人自身以及相互間的學(xué)習以提高多機器人系統(tǒng)的效率和魯棒性都有待深入研究。近年來無線通信技術(shù)得到長足發(fā)展，但在目前的技術(shù)條件下，在多機器人系統(tǒng)中實現(xiàn)所有機器人之間的點對點實時通信還有較大困難，這也是大多數(shù)多機器人系統(tǒng)仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統(tǒng)對通信速度的依賴程度也是一個非常重要的問題。

總之，多機器人路徑規(guī)劃設(shè)計和實現(xiàn)是一項極其復(fù)雜的系統(tǒng)工程，展望其能在結(jié)合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡(luò)、人工勢場的改進、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻：

［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應(yīng)用:研究生用書[M].3版.北京：清華大學(xué)出版社，2004：124-198.

[3]譚民，王碩，曹志強.多機器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動態(tài)環(huán)境下多移動機器人路徑規(guī)劃的一種新方法[J].機器人，2001，23（5）：407-410.

[5]顧國昌，李亞波.基于總體勢減小的動態(tài)調(diào)度技術(shù)解決多機器人的路徑規(guī)劃[J].機器人，2001，23（2）：171-174.

[6]孫樹棟，林茂.基于遺傳算法的多移動機器人協(xié)調(diào)路徑規(guī)劃[J].自動化學(xué)報，2000，26（5）：672-676.

[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報，2000，21（2）：146-149.

[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.

[9]朱慶保.全局未知環(huán)境下多機器人運動螞蟻導(dǎo)航算法[J].軟件學(xué)報，2006，17（9）：1890-1898.

[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽，陳世福，陸鑫.強化學(xué)習研究綜述[J].自動化學(xué)報，2004，30（1）：

86-100.

[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.

[13]張芳，顏國正，林良明.基于再勵學(xué)習的多移動機器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計算機工程與應(yīng)用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國昌.多機器人動態(tài)編隊的強化學(xué)習算法研究[J].計算機研究與發(fā)展，2003，40（10）：1444-1450.

[15]宋一然.基于強化學(xué)習的多機器人路徑規(guī)劃方法[J].莆田學(xué)院學(xué)報，2006，13（2）：38-41.

[16]韓學(xué)東，洪炳熔.基于人工神經(jīng)網(wǎng)絡(luò)的多機器人協(xié)作學(xué)習研究[J].計算機工程與設(shè)計，2002，23（6）：1-3.

[17]唐振民，趙春霞，楊靜宇，等.基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報，2003，27（5）：610-615.

[18]孫茂相，周明，王艷紅，等.多移動機器人實時最優(yōu)運動規(guī)劃[J].控制與決策，1998，

13（2）：125-130.

[19]焦立男，唐振民.基于局部傳感和通訊的多機器人運動規(guī)劃框架[J].計算機工程與應(yīng)用，2007，43(17)：89-93.

[20]沈捷，費樹岷，鄭波.多移動機器人保持隊形路徑規(guī)劃[J].東南大學(xué)學(xué)報，2005，35(3):391-395.

[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.

[22]徐潼，唐振民.多機器人系統(tǒng)中的動態(tài)避碰規(guī)劃[J].計算機工程，2003，29(17):

79-81，104.

[23]周明，孫茂相，尹朝萬，等.多移動機器人分布式智能避撞規(guī)劃系統(tǒng)[J].機器人，1999，21（2）：139-143.

[24]任炏，陳宗海.基于強化學(xué)習算法的多機器人系統(tǒng)的沖突消解的方法[J].控制與決策，2006，21(4):430-434，439.

[25]歐錦軍，朱楓.一種多移動機器人避碰規(guī)劃方法[J].機器人，2000，22(6):474-481.

[26]景興建，王越超，談大龍.基于人工協(xié)調(diào)場的多移動機器人實時協(xié)調(diào)避碰規(guī)劃[J].控制理論與應(yīng)用，2004，21(5):757-764.

[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.

[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.

[29]薛宏濤，葉媛媛，沈林成，等.多智能體系統(tǒng)體系結(jié)構(gòu)及協(xié)調(diào)機制研究綜述[J].機器人，2001，23（1）：85-90.

[30]周風余，李貽斌，宋銳，等.基于混合式多智能體系統(tǒng)的協(xié)作多機器人系統(tǒng)研究[J].山東大學(xué)學(xué)報:工學(xué)版，2005，35(1):82-87.

[31]夏冰，張佐，張毅，等.基于多智能體系統(tǒng)的動態(tài)路徑選擇算法研究[J].公路交通科技，2003，20（1）：93-96.

[32]陳雪江.基于強化學(xué)習的多機器人協(xié)作機制研究[D].杭州：浙江工業(yè)大學(xué)，2004.

篇5

引言

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

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

1 遺傳算法與蟻群算法

1.1 遺傳算法原理

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

1.2 蟻群算法原理

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

2.算法改進

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

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

圖1 遺傳混合算法流程

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

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

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

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

Step 4 是否走完所有的城市，否，則轉(zhuǎn)入Step 3。

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

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

Step 7 計算適應(yīng)度值。

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

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

2.2 算法過程實現(xiàn)

（1）種群初始化

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

（2）狀態(tài)轉(zhuǎn)移規(guī)則設(shè)置

    轉(zhuǎn)移概率，為t時刻螞蟻由i城到j(luò)城的概率。

            （1）

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

（2）其中

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

（3）

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

（3）交叉算子的設(shè)計

首先隨機地在父體中選擇兩雜交點,再交換雜交段,其它位置根據(jù)保持父體中城市的相對次序來確定。例如,設(shè)兩父體及雜交點的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)。在新的城市序列中有重復(fù)的數(shù)，將雜交段中對應(yīng)次序排列,即: 7-8、3-1、5-6，依此對應(yīng)關(guān)系替換雜交段中重復(fù)的城市數(shù)。將B1中(2 6 4)重復(fù)的6換為5，B2(9 3)中重復(fù)的3換為1.。雜交后的兩個體為B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交雜交。

3.仿真實驗

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

表1  仿真試驗平臺

設(shè)備名稱

型號

CPU

Pentium(R)M 1.66 GH

內(nèi)存

512M

操作系統(tǒng)

Microsoft Windows XP

仿真軟件

MierosoftVisualC++6.0

3.1 遺傳算法仿真

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

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

3.2 蟻群算法仿真

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

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

3.3遺傳混合算法

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

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

遺傳算法、基本蟻群算法、遺傳混合算法對TSPLIB典型51城市的數(shù)據(jù)進行仿真,仿真結(jié)

果對比如表2所

算法名稱

所用時間（s）

最優(yōu)結(jié)果

遺傳算法

95

497

基本蟻群算法

68

465

改進混合算法

50

456

4.結(jié)論

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

參考文獻：

［1］小平,曹立明.遺傳算法———理論、應(yīng)用與軟件實現(xiàn)[M].西安交通大學(xué)出版社,2002.

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

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

篇6

 

一、概述各移動運營商及移動通信相關(guān)技術(shù)咨詢單位在進行規(guī)劃方案驗證時，傳統(tǒng)的方法是通過規(guī)劃仿真軟件使用宏蜂窩傳播模型及20米精度三維電子地圖對規(guī)劃方案進行仿真驗證；然而，宏蜂窩傳播模型的應(yīng)用范圍和自身局限性限制了規(guī)劃方案仿真驗證的精度：首先，宏蜂窩傳播模型的應(yīng)用范圍一般在500米以上，而CBD區(qū)域基站的覆蓋半徑一般在500米以下。其次，宏蜂窩傳播模型只能從宏觀上反映方案覆蓋效果，無法根據(jù)建筑物的高度從微觀上反映局部的覆蓋情況。因此，需要采用更合適的傳播模型配合高精度的三維電子地圖對CBD區(qū)域的規(guī)劃方案進行仿真驗證，以確保該重點區(qū)域無線網(wǎng)絡(luò)建成后的網(wǎng)絡(luò)性能。

目前射線跟蹤模型作為一種高精度的規(guī)劃仿真?zhèn)鞑ツＰ驮诖笾行统鞘懈采w重點區(qū)域的規(guī)劃方案仿真驗證中得到廣泛應(yīng)用。本文首先對射線跟蹤模型的原理進行探討，然后以WaveCall公司的WaveSight模型為例說明射線跟蹤模型的應(yīng)用方法。其結(jié)果有助于應(yīng)用射線跟蹤模型對規(guī)劃方案進行精確驗證，對規(guī)劃工作有積極的參考和指導(dǎo)作用。

二、射線跟蹤模型簡介2.1 微蜂窩傳播模型介紹 當前傳播模型根據(jù)應(yīng)用范圍可分為宏蜂窩傳播模型和微蜂窩傳播模型，宏蜂窩傳播模型應(yīng)用范圍為1km至幾十km；而微蜂窩傳播模型應(yīng)用范圍僅為幾百米，一般只適用于基站附近區(qū)域。免費論文。由于CBD區(qū)域基站的覆蓋一般在500米以內(nèi)，因此應(yīng)用微蜂窩傳播模型對該區(qū)域規(guī)劃方案的效果進行仿真驗證更為合適。

微蜂窩傳播模型根據(jù)模型建立方法，可分為經(jīng)驗?zāi)Ｐ?，確定性模型以及混合模型；

l經(jīng)驗?zāi)Ｐ?/p>

經(jīng)驗?zāi)Ｐ褪窃诖罅繙y量的基礎(chǔ)上產(chǎn)生的，該模型與室外傳統(tǒng)宏蜂窩傳播模型類似，不考慮理論計算，對基站附近測量大量數(shù)據(jù)后統(tǒng)計歸納出經(jīng)驗?zāi)Ｐ汀?/p>

l確定性模型

確定性模型是依據(jù)電波傳播理論計算出接收點與發(fā)射點之間的傳播損耗。射線跟蹤模型是一種典型的確定性模型，確定性模型不考慮測量，僅在確定計算公式中的個別參數(shù)時需要測量驗證。

l混合模型

混合模型結(jié)合了經(jīng)驗?zāi)Ｐ秃痛_定性模型，一方面混合模型以電波傳播理論為依據(jù)得出電波的傳播模型，同時需要對基站附近測量大量數(shù)據(jù)以統(tǒng)計確定傳播模型中的參數(shù)值。

2.2 射線跟蹤模型介紹 射線跟蹤模型是一種確定性模型，其基本原理為標準衍射理論（Uniform Theory ofDiffraction，簡稱UTD）。根據(jù)標準衍射理論，高頻率的電磁波遠場傳播特性可簡化為射線（Ray）模型。因此射線跟蹤模型實際上是采用光學(xué)方法，考慮電波的反射、衍射和散射，結(jié)合高精度的三維電子地圖（包括建筑物矢量及建筑物高度），對傳播損耗進行準確預(yù)測。

由于在電波傳播過程中影響的因素過多，在實際計算預(yù)測中無法把所有的影響因素都考慮進去，因此需要簡化傳播因素；射線跟蹤算法把建筑物的反射簡化為光滑平面反射、建筑物邊緣散射以及建筑物邊緣衍射。

根據(jù)考慮路徑的種類不同，射線跟蹤模型可分為三種：

l2D射線跟蹤模型

只考慮水平切面的傳播路徑，即第一類路徑。

l3D射線跟蹤模型

只考慮水平切面以及垂直切面的傳播路徑，即第一類及第三類路徑。

l全3D射線跟蹤模型

考慮所有傳播路徑，即考慮所有第一、二、三類路徑。

三、射線跟蹤模型基本原理射線跟蹤模型的基本原理是簡化傳播因素，采用光學(xué)方法定位傳播路徑并計算各接收點與發(fā)射點之間的路徑損耗；因此，射線跟蹤模型的關(guān)鍵在于如何定位接收點與發(fā)射點之間的傳播路徑并計算路徑損耗。免費論文。

3.1 水平切面的傳播損耗從發(fā)射源在接收點之間可能存在很多傳播路徑，但是一般只有一到兩條強度最強，在傳播中起主導(dǎo)作用的主導(dǎo)傳播路徑。路徑損耗計算時只需計算主導(dǎo)傳播路徑的損耗即可。免費論文。

3.2 垂直切面的傳播損耗 相對于水平切面的傳播損耗，垂直切面的傳播損耗計算要簡單一些，計算垂直切面的傳播損耗時，需要首先確定發(fā)射源與接收點之間的垂直傳播路徑，然后計算其中各個刀鋒衍射損耗，其路徑損耗為各刀鋒衍射損耗之和。

3.3 射線跟蹤模型簡要結(jié)論 根據(jù)射線跟蹤模型的理論以及相關(guān)資料，可以得到射線跟蹤模型的簡要結(jié)論如下：

1.對近距離的場強預(yù)測， 水平切面算法（2D射線跟蹤算法）起主導(dǎo)作用。

2.全3D方向算法中全3D路徑（即第三類路徑）對遠距離的場強預(yù)測準確性影響很大。

3.在整齊規(guī)劃的建筑群中，對遠距離的場強預(yù)測，垂直切面算法可取代全3D方向算法。

四、射線跟蹤模型的應(yīng)用 本節(jié)主要以WaveCall公司的WaveSight射線跟蹤模型為例，對射線跟蹤模型的應(yīng)用進行說明。

WaveCall公司的WaveSight射線跟蹤模型作為AIRCOM公司的規(guī)劃軟件Enterprise的插件，可用于高精度的規(guī)劃方案仿真驗證。該模型基于標準衍射理論及射線跟蹤算法，綜合考慮電波傳播范圍內(nèi)建筑物的輪廓、高度、地形剖面圖，對電波的傳播特性進行準確預(yù)測。

WaveSight模型是一種3D射線跟蹤模型，該模型包括兩種類型路徑：水平切面路徑以及垂直切面路徑。

對比傳統(tǒng)射線跟蹤模型，WaveSight 具有優(yōu)點十分明顯：首先，WaveSight射線跟蹤模型采用了不同于傳統(tǒng)射線跟蹤模型的算法，空前地提高了計算效率：該模型完成一個基站的覆蓋預(yù)測所需時間僅是傳統(tǒng)射線跟蹤模型所需時間的1/3左右，不僅保證了覆蓋預(yù)測的精度，同時還保證了覆蓋預(yù)測的速度。此外，WaveSight 模型使用簡單，該模型不需要使用測試數(shù)據(jù)對其進行調(diào)校，僅需要輸入兩個參數(shù)：使用頻率及接收端高度。

WaveSight 射線跟蹤模型的缺點是：僅適用于市區(qū)環(huán)境，對電子地圖精度要求較高，不僅要求地圖精度必須達到5m 以上，而且要求提供建筑物矢量信息以及高度信息。

五、結(jié)論及后續(xù)工作 本文首先對射線跟蹤模型的原理進行探討，然后給出射線跟蹤模型的簡要結(jié)論，最后以WaveCall公司的WaveSight模型為例說明射線跟蹤模型的應(yīng)用方法。其結(jié)果有助于應(yīng)用射線跟蹤模型對規(guī)劃方案進行精確驗證，對規(guī)劃工作有積極的參考和指導(dǎo)作用。

今后研究工作可以再上述研究基礎(chǔ)上進一步展開，對全3D射線跟蹤算法進行進一步的探討，同時也可以對其它射線跟蹤模型如WinProp模型等進行研究，

進一步研究射線跟蹤傳播模型算法，更精確地城市CBD區(qū)域進行預(yù)測，指導(dǎo)網(wǎng)絡(luò)的規(guī)劃及優(yōu)化工作。

【參考文獻】

1．WaveCall公司；《WaveCallPropagationWhitePaper》；2001

篇7

中圖分類號：P208 文獻標識碼：A 文章編號：1007-9599 （2013） 02-0000-02

1 概述

物流產(chǎn)業(yè)隨著基礎(chǔ)工業(yè)的不斷壯大及消費市場的蓬勃發(fā)展而快速興起。而中國的物流企業(yè)不論從技術(shù)裝備還是管理水平與國外仍存在較大差距，概括起來有一下幾個方面：對現(xiàn)代物流理念上的差距，企業(yè)規(guī)模方面的差距，社會需求方面的差距，管理體制方面的差距，專業(yè)手段方面的差距，專門人才方面的差距。據(jù)對美國物流業(yè)的統(tǒng)計與分析，以運輸為主的物流企業(yè)年平均資產(chǎn)回報率為8.3%（irr），倉儲為7.1%，綜合服務(wù)為14.8%。在中國大部分物流企業(yè)的年平均資產(chǎn)回報率僅為1%。這一數(shù)據(jù)，不僅說明了中國物流效率低下，同時企業(yè)仍有很大的空間通過物流來降低成本。

如何應(yīng)用先進的技術(shù)手段來提高物流業(yè)的經(jīng)營效率，及時高效、經(jīng)濟地將商品配送到客戶手中，成了大家探討的話題，這也就是現(xiàn)代物流領(lǐng)域中備受關(guān)注的車輛路徑問題（vehicle routing problem，VRP）。物流配送路徑規(guī)劃的優(yōu)化與否，對物流配送效率、費用和服務(wù)水平影響較大。而此類問題都涉及如何處理大量的空間數(shù)據(jù)與屬性數(shù)據(jù)而縮短物流時間、降低成本的問題。

地理信息系統(tǒng)作為不僅具有對空間和屬性數(shù)據(jù)采集、處理和顯示功能，而且可為系統(tǒng)用戶進行預(yù)測，監(jiān)測、規(guī)劃管理和決策提供科學(xué)依據(jù)。它可以有效的結(jié)合最優(yōu)路徑、各種VRP模型、車輛行駛成本等要素，在可視化分析以及物流規(guī)劃路徑分析等方面具有不可替代的作用。GIS技術(shù)與現(xiàn)代物流工程技術(shù)相結(jié)合，給現(xiàn)代物流行業(yè)提供了巨大的發(fā)展空間，為物流企業(yè)完善管理手段、減低管理成本、提高經(jīng)濟效益、最終提升核心競爭力提供了機遇。

2 技術(shù)實現(xiàn)途徑研究

物流配送車輛路線優(yōu)化問題由Dautzig和Ramser于1959年首次提出，該問題一般定義為：對一系列給定的顧客（取貨點或送貨點），確定適當?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過它們，最后返回配送中心。并在滿足一定的約束條件下（如車輛容量限制、顧客需求量、交發(fā)貨時間等），達到一定的目標（如路程最短、費用最少等）。配送中心的每次配送活動通常面對多個非固定用戶，并且這些用戶分布在不同的地點，同時他們的配送時間和配送數(shù)量也都不盡相同。如果配送中心不合理規(guī)劃車輛、貨物的運輸路線，常會影響了配送服務(wù)水平，還會造成運輸成本的上升，因此對車輛及貨物的配送路線進行規(guī)劃是配送中心的一項重要工作。

車輛路線優(yōu)化問題一般可根據(jù)空間特性和時間特性分為車輛路線規(guī)劃問題和車輛調(diào)度問題。當不考慮時間要求，僅根據(jù)空間位置安排車輛的線路時稱為車輛線路或車輛路徑規(guī)劃問題（VRP）。當考慮時間要求安排運輸線路時稱為車輛調(diào)度問題（VSP）。本文不考慮時間要求，主要針對第一類VRP問題，提出相應(yīng)的技術(shù)實現(xiàn)方案研究。

典型的VRP具有以下特征：（1）所有車輛從倉庫出發(fā)，并最終回到倉庫；（2）所有車輛必須滿足一定的約束；（3）多輛車負責多個客戶；（4）每個客戶由一輛車訪問一次；（5）車輛的路線上可以取送貨。目前研究的車輛路線規(guī)劃的模型主要有兩類，一類為網(wǎng)絡(luò)圖模型，另一類為數(shù)學(xué)模型。由于VRP難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運輸問題的主要方法，多年來許多學(xué)者對車輛運輸問題進行了研究，提出了各種各樣的啟發(fā)式方法。

物流公司的業(yè)務(wù)一般具有配送范圍廣的特點，本文主要針對大范圍跨省配送的案例進行智能路徑規(guī)劃，因此影響因素較多，主要包括：（1）大范圍、跨省的配送交通網(wǎng)絡(luò)圖；（2）復(fù)雜的車輛運作規(guī)則，包括運行時間、運載能力、運行成本計算、駕駛員工作時間限制等；（3）復(fù)雜的道路選擇優(yōu)先級；（4）復(fù)雜的運輸車輛優(yōu)先級；（5）客戶訂單及運輸車輛數(shù)據(jù)；（6）取貨及分發(fā)過程；（7）繁雜的配送規(guī)則，如倉庫、貨物、客戶的時間等；（8）運輸車輛的重復(fù)利用，要求同一輛車在符合多個約束條件下盡可能多的參與到不同路線的配送中。

本文主要基于ArcObjects的網(wǎng)絡(luò)分析和地圖展示等組件進行二次開發(fā)，同時對其提供的車輛路徑規(guī)劃算法進行了拓展性研究。

3 功能模塊設(shè)計方案

3.1 軟件架構(gòu)設(shè)計

系統(tǒng)建設(shè)遵循SOA架構(gòu)，由數(shù)據(jù)資源層、組件層、服務(wù)層和表現(xiàn)層組成。數(shù)據(jù)資源層包括各種數(shù)據(jù)庫、關(guān)系型數(shù)據(jù)庫和空間數(shù)據(jù)庫引擎ArcSDE，實現(xiàn)對物流業(yè)務(wù)數(shù)據(jù)的存儲和管理；組件層包括接口協(xié)議、GIS組件、其他中間件；服務(wù)層實現(xiàn)計算功能，接受表現(xiàn)層的請求進行計算；表現(xiàn)層采用多種形式展現(xiàn)分析結(jié)果。

3.2 軟件功能設(shè)計

本系統(tǒng)是物流業(yè)務(wù)管理系統(tǒng)的一部分，主要提供歷史數(shù)據(jù)管理模塊、線路優(yōu)化分析模塊、地圖操作模塊，同時提供與其他相關(guān)業(yè)務(wù)系統(tǒng)的擴展功能。

（1）線路優(yōu)化分析模塊

線路優(yōu)化分析模塊是系統(tǒng)的關(guān)鍵，提供兩種分析結(jié)果：一種是基于AO自帶的網(wǎng)絡(luò)分析模塊設(shè)計，計算分析結(jié)果；另一種是歷次根據(jù)具體路況等信息的實際調(diào)度結(jié)果。

實際調(diào)度結(jié)果來自車輛GPS監(jiān)控數(shù)據(jù)，并將實際調(diào)度結(jié)果作為輸入，用來校正線路優(yōu)化分析方法，最后生成最優(yōu)路徑規(guī)劃。

（2）地圖展示模塊

地圖展示模塊，在配送交通網(wǎng)絡(luò)圖上展示道路基本信息、周邊環(huán)境、倉庫及客戶地點、車輛位置信息等。同時將各種車輛路徑規(guī)劃分析結(jié)果以地圖形式展示?；贏rcGIS提供的基礎(chǔ)地圖操作功能，實現(xiàn)地圖縮放、瀏覽、鷹眼、圖層控制、測量、選擇、標注、信息查詢等功能。

（3）歷史數(shù)據(jù)管理模塊

歷史數(shù)據(jù)管理主要存儲歷史客戶訂單數(shù)據(jù)、實時路況信息、歷史路徑規(guī)劃分析結(jié)果、實際運輸路徑等，可支持對歷史數(shù)據(jù)的查詢和修改。

（4）擴展功能模塊

提供與其他相關(guān)業(yè)務(wù)系統(tǒng)、車載GPS設(shè)備、車輛監(jiān)控設(shè)備等的接口，便于系統(tǒng)的擴展。

3.4 數(shù)據(jù)庫設(shè)計

本系統(tǒng)中涉及的數(shù)據(jù)庫主要包括元數(shù)據(jù)庫、基礎(chǔ)地理空間數(shù)據(jù)庫、業(yè)務(wù)數(shù)據(jù)庫、分析模型數(shù)據(jù)庫、歷史數(shù)據(jù)庫等。

4 結(jié)束語

本文將物流車輛路徑規(guī)劃理論算法的研究與地理信息系統(tǒng)的網(wǎng)絡(luò)分析模塊相結(jié)合，經(jīng)過二次開發(fā)，形成了用于實際的物流車輛路徑規(guī)劃信息系統(tǒng)。另外車輛路徑規(guī)劃設(shè)計約束較多，本文中不考慮時間要求，僅根據(jù)空間位置安排車輛的線路，同時不考慮裝箱問題。

車輛路徑規(guī)劃問題是現(xiàn)代物流業(yè)的熱點問題，但是基本停留在理論算法層面，隨著技術(shù)的不斷進步，必然出現(xiàn)考慮更多約束的先進算法，希望將這些算法真正與現(xiàn)代物流業(yè)結(jié)合，那將會是一個跨越式的進步。

篇8

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）32-0190-04

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

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

本文的內(nèi)容首先對iOS平臺開發(fā)相關(guān)技術(shù)進行了簡要介紹，然后對訂單配送路徑規(guī)劃系統(tǒng)進行分析，設(shè)計出了整體的技術(shù)方案與系統(tǒng)架構(gòu)，然后對系統(tǒng)功能進行詳細實現(xiàn)，包括倉庫、訂單查詢，地圖位置顯示、路線規(guī)劃及導(dǎo)航等功能，最后進行結(jié)果分析與總結(jié)。

1 iOS開發(fā)平臺介紹

1.1 iOS系統(tǒng)架構(gòu)

iOS平臺應(yīng)用的開發(fā)語言主要有Objective-C和Swift語言，由于swift作為一門新生語言使用人數(shù)較少的原因，本系統(tǒng)采用了主流開發(fā)語言O(shè)bjective-C進行編碼開發(fā)。Objective-C作ANSI C的超集[4]，不僅擴展了面向?qū)ο笤O(shè)計的能力，如類、消息、繼承，同時它可以調(diào)用C的函數(shù)，也可以通過C++對象訪問方法，具有對C和C++語言的兼容性。

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

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

1.2 iOS 地圖SDK

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

2 整體方案設(shè)計

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

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

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

3 基于iOS的路徑規(guī)劃App設(shè)計

3.1 App開發(fā)模式

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

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

3.2 重要功能設(shè)計及關(guān)鍵技術(shù)實現(xiàn)

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

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

圖6 路徑規(guī)劃

系統(tǒng)主要的路徑規(guī)劃功能在電子地圖的地理信息背景下完成了標注及路線可視化如圖6所示，其關(guān)鍵技術(shù)的實現(xiàn)如下：

1）初始化地圖服務(wù)

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

2）分組待配送訂單

因為業(yè)務(wù)要求需要將待配送訂單按各自對應(yīng)的出貨倉庫進行分組配送，系統(tǒng)中通過自定義實現(xiàn)分組方法：-（void）groupAction：（NSMutableArray *）array； 其中參數(shù)array中存儲著多個配送單對象XJDeliveryOrder。方法實現(xiàn)中利用可變的集合對象NSMutableSet保存的內(nèi)容對象不重復(fù)的特性，用_warehouseSet記錄不同的倉庫信息：_warehouseSet = [NSMutableSet set]； [array enumerateObjectsUsing Block： ^（ XJDeliveryOrder * _Nonnull order， NSUInteger idx， BOOL * _Nonnull stop） {[_warehouseSet addObject：order.warehouseName]； }]； 同時該方法中利用謂詞NSPredicate過濾數(shù)組array實現(xiàn)按倉庫名稱分組：[_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）添加標注及氣泡視圖

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

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

4）路徑規(guī)劃及繪制路線

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

5）最優(yōu)路徑算法

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

4 系統(tǒng)測評與應(yīng)用實例

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

本系統(tǒng)中路徑規(guī)劃功能的實現(xiàn)采用了將多個倉庫多配送點的路徑規(guī)劃分解為多個單倉庫多點配送的思想。下面一系列圖示說明了多個單倉庫出發(fā)到多個配送點的路徑規(guī)劃對比結(jié)果。

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

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

5 結(jié)束語

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

參考文獻：

[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].系統(tǒng)工程理論與實踐，2011（8）.

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

篇9

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2010)09-2132-02

Application of C-W Algorithm in Logistics Distribution Vehicle Scheduling

CAO Jing-xia1,2

(1.School of Information Engineering, Jiangnan University, Wuxi 2141222, China; 2.Jiangyin Polytechnic College, Jiangyin 214400, China)

Abstract: Logistics Distribution Vehicle Scheduling is a very crucial step in the process of logistic distribution. This paper briefly describes the most representative algorithm, points out that the heuristic algorithm is the main method to solve vehicle routing problem, and demonstrates its applicability to solving the problem of vehicle scheduling by citing the examples of C-W algorithm, a typical method among the heuristic algorithm.

Key words: C-W algorithm; delivery vehicle scheduling; heuristic algorithm

隨著我國市場經(jīng)濟的建立和發(fā)展,作為“第三利潤源泉”的物流日益受到政府有關(guān)部門和廣大企業(yè)的重視,成為當前最重要的競爭領(lǐng)域。配送是物流活動中直接與消費者相連的環(huán)節(jié),在物流的各項成本中,配送成本占了相當高的比例。配送車輛調(diào)度的合理與否對配送速度、成本、效益影響很大,采用科學(xué)、合理的方法來進行配送車輛調(diào)度,是物流配送中非常關(guān)鍵的一環(huán)。

1 物流配送車輛路徑問題(VRP) 概述

物流配送車輛路徑問題(Vehicle Routing Problem ,VRP) 最早是由Dantzig 和Ramser于1959年提出的,一經(jīng)提出立即引起了運籌學(xué)、物流科學(xué)、計算機應(yīng)用等學(xué)科專家和運輸問題制定和管理者的極大關(guān)注。

該問題的研究目標是對一系列的顧客需求點設(shè)計適當?shù)穆肪€,使車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等) 下, 達到一定的優(yōu)化目標(如里程最短、費用最少、時間盡量少、車隊規(guī)模盡量小、車輛利用率盡量高等)。

2 VRP問題的求解算法

VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一,即隨著客戶數(shù)量的增加,可選的配送路徑方案數(shù)量將以指數(shù)速度急劇增長,即出現(xiàn)組合爆炸現(xiàn)象,因此通常的做法就是應(yīng)用相關(guān)技術(shù)將問題分解或者轉(zhuǎn)化為一個或者多個已經(jīng)研究過的基本問題,再使用相對比較成熟的基本理論和方法求解。VRP問題的求解方法基本上可以分為精確算法和啟發(fā)式算法兩大類。

2.1 求解VRP問題的精確算法

求解VRP問題的精確算法主要運用線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)來描述物流系統(tǒng)的數(shù)量關(guān)系,以便求得最優(yōu)解。求解VRP問題常用的精確算法有分枝定界法、割平面法、動態(tài)規(guī)劃法、網(wǎng)絡(luò)流算法等。這些方法從理論上給出了VRP問題精確求法,在可以求解的情況下,其解通常要優(yōu)于啟發(fā)式算法。由于精確算法在求解時引入了嚴格的數(shù)學(xué)方法(手段),因而無法避開指數(shù)爆炸問題,使其獲得整個系統(tǒng)的最優(yōu)解越來越困難,因此,這些算法都是針對某一特定問題設(shè)計的, 適用能力較差, 在實際中其應(yīng)用范圍很有限。

2.2 求解VRP問題的啟發(fā)式算法

為了克服精確算法的不足,可以運用一些經(jīng)驗法則來降低優(yōu)化模型的數(shù)學(xué)精確程度,并通過模仿人的跟蹤校正過程來求取運輸系統(tǒng)的滿意解,為此專家們主要把精力花在構(gòu)造高質(zhì)量的啟發(fā)式算法上。啟發(fā)式算法能同時滿足詳細描繪和求解問題的需要,較精確式算法更加實用。

目前己經(jīng)提出的啟發(fā)式算法很多,按照Cesar Reg的分類法,基本可以分為構(gòu)造啟發(fā)式算法(節(jié)約算法、最鄰近法、插入法、掃描法)、兩階段啟發(fā)式算法、不完全優(yōu)化算法和智能化啟發(fā)式算法(禁忌搜索算法、模擬退火法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、微粒群算法等)四類。啟發(fā)式算法中由Clarke 和Wright 在1964 年提出的節(jié)約法(簡記為C-W算法)具有非常典型的代表性。

3 C-W算法的應(yīng)用

3.1 定義與原理

C-W算法是根據(jù)物流中心的運輸能力和物流中心到各送/ 取貨點以及各個送/ 取貨點之間的距離,制訂使總的車輛運輸噸公里數(shù)(或者時間或者費用)最小的方案。

C-W算法的基本思路如圖1所示,已知P點為配送中心,它分別向用戶A 和B送貨。設(shè)P點到用戶A 和用戶B 的距離分別為a 和b。用戶A 和用戶B 之間的距離為c,現(xiàn)有兩種送貨方案,如圖1(a)和(b)所示。

在圖1(a)中配送距離為2(a+b);圖1(b)中,配送距離為a+b+c。對比這兩個方案,2(a+b)-(a+b+c)=a+b-c,很明顯,由三角形的幾何性質(zhì)可知, 三角形中任意兩條邊的邊長之和大于第三邊的邊長。即:a+b-c>0 。連接AB所得的節(jié)約量是a+b-c。

3.2 實例

為了使C-W算法體現(xiàn)較為明了,選取較典型的實例介紹。假設(shè)配送中心使用同類型的配送車(主要是裝載量和容積相同),保證一條線路上各用戶的貨運量之和不大于車輛的載重量。

基本資料介紹:

現(xiàn)有6個用戶(標號是1,…,6),各個用戶的貨運量是gi(噸)(i=1,…,6),這些用戶由配送中心(標號是0)發(fā)出的載重量為8噸的車輛完成配送任務(wù),要求最后的路線安排使總距離最小。具體數(shù)據(jù)見表1、表2。

首先,把各個點單獨與配送中心相連,構(gòu)建僅含一個點的初始路線,得到總的距離為:2*(40+60+75+90+200+100)=1130km

然后,連接兩兩用戶到同一條線路上得到節(jié)約值(節(jié)約量公式a+b-c),節(jié)約值越大,說明兩用戶連在一起時運距減少的越多,如果是負值就不應(yīng)該把兩用戶連在同一條線路上。

C-W算法解題步驟:

1)計算各用戶之間的節(jié)約值(節(jié)約量公式a+b-c)

例如:連接用戶1和用戶2時,節(jié)約量=40+60-65=35

連接用戶3和用戶5時,節(jié)約量=75+200-50=225,類似可以得到其他,如表3。

2)按照從大到小的順序排序,見表4。

表4 節(jié)約里程排序表

3)連接點對,見表5。

根據(jù)表,得到最后的路線安排如下:

0-3-5-6-0

0-1-2-4-0

比初始路線節(jié)約運距:230+225+50+35=540km

通過使用C-W算法,對配送線路進行組合以后,由原來的6條初始化線路,減少到2條組合線路, 運行距離從開始的1130km 縮短為590 km ,節(jié)約的里程相當可觀。不難明白, 中國的物流行業(yè)是一座金山。只有不斷進行物流管理和技術(shù)創(chuàng)新,提高物流效率, 才可能大幅降低整個業(yè)務(wù)成本。

參考文獻:

[1] 李如姣.“節(jié)約里程法”在某物流公司配送中心的實際運用[J].科技咨詢,2008(28):156-158.

篇10

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2011)21-5080-03

Research on Technology of Nodes Localization Based on Mobile Beacon for Wireless Sensor Network (WSN)

DING Hui, LI Bo-yong, AI Shu-liang

(Chenzhou Vocational and Technical College, Chenzhou 423000, China)

Abstract：Wireless sensor network has been used in many field. Nodes location of WSN has provided the basic information for many applications. Nodes location based on mobile beacon is one of the important research fields. Some basic principles and performance evaluating criterions of nodes localization based on mobile beacon for WSN are introduced. Some issues which need to be resolved in future are discussed.

Key words: wireless sensor network (WSN); mobile beacon; nodes localization

隨著傳感器技術(shù)、無線通信、微電子技術(shù)以及嵌入式計算等技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network 簡稱WSN)得到了廣泛應(yīng)用，成為當今活躍的研究領(lǐng)域。無線傳感器網(wǎng)絡(luò)是新型的傳感器網(wǎng)絡(luò)，同時也是一個多學(xué)科交叉的領(lǐng)域，與當今主流無線網(wǎng)絡(luò)技術(shù)一樣，均使用802.15.4的標準，由具有感知能力、通信能力和計算能力的大量微型傳感器節(jié)點組成，具有低成本、低功耗的優(yōu)點和強大的數(shù)據(jù)獲取和處理能力。

在無線傳感器網(wǎng)絡(luò)的眾多應(yīng)用中,如：國防軍事、環(huán)境監(jiān)測、交通管理、醫(yī)療衛(wèi)生、目標跟蹤、物流管理、入侵檢測、交通流量監(jiān)控和勘測應(yīng)用等領(lǐng)域, 監(jiān)測到事件之后需要確定事件發(fā)生的位置，信息融合后得到的相關(guān)數(shù)據(jù)信息如果不包含事件位置信息將毫無意義，只有帶有標識位置信息的傳感數(shù)據(jù)才有實際的意義。傳感器節(jié)點自身的正確定位是提供事件位置信息的前提, 因此節(jié)點的精確定位基礎(chǔ)而關(guān)鍵[1] 。

1 無線傳感器網(wǎng)絡(luò)節(jié)點定位的分類及基本方法

節(jié)點定位是指確定傳感器節(jié)點的相對位置或絕對位置，節(jié)點所采集到的數(shù)據(jù)必須結(jié)合其在測量坐標系內(nèi)的位置信息才有意義。人工部署傳感節(jié)點和為所有節(jié)點安裝GPS接收器都會受到成本、功耗、節(jié)點體積、擴展性等方面的限制，甚至在某些應(yīng)用中是根本無法實現(xiàn)的。通常是為部分節(jié)點配置定位裝置（如GPS接收器）或事先標定其準確位置，這些節(jié)點稱為信標節(jié)點（也稱錨節(jié)點），再利用信標節(jié)點的相關(guān)信息采用一定的機制與算法實現(xiàn)無線傳感器網(wǎng)絡(luò)節(jié)點的自身定位。目前人們提出了兩類節(jié)點定位算法[2]：基于測量距離的定位算法與測量距離無關(guān)的定位算法?；诰嚯x的定位方法首先使用測距技術(shù)測量相鄰節(jié)點間的實際距離或方位，然后使用三邊測量法、三角測量法、最小二乘估計法等方法進行定位。與測量距離無關(guān)的定位算法主要包括：APIT、質(zhì)心算法、DV-Hop、Amorphous等。

1.1 基于無線傳感器網(wǎng)絡(luò)自身定位系統(tǒng)的分類[1,3-5]

1) 絕對定位與相對定位。絕對定位與物理定位類似，定位結(jié)果是一個坐標位置，如經(jīng)緯度。而相對定位通常是以傳感區(qū)域某點為參考，建立整個網(wǎng)絡(luò)的相對坐標系統(tǒng)。

2) 物理定位與符號定位。經(jīng)緯度就是物理位置；而某個節(jié)點在某街道的某門牌的建筑物內(nèi)就是符號位置。一定條件下，物理定位和符號定位可以相互轉(zhuǎn)換。與物理定位相比，符號定位在一些特定的應(yīng)用場合更加便于使用。

3) 集中式計算與分布式計算定位。集中式計算是指把所需信息傳送到某個中心節(jié)點，并在那里進行節(jié)點定位計算的方式；分布式計算是指依賴節(jié)點間的信息交換和協(xié)調(diào)，由節(jié)點自行計算的定位方式。

4) 移動信標與固定信標定位。移動信標節(jié)點是一類裝備了GPS或其它定位裝置的可移動節(jié)點，它在移動的過程中周期性自己的位置信息?；谝苿有艠说奈粗?jié)點定位有很多優(yōu)點，如定位成本低，容易達到很高的定位精度、可實現(xiàn)分布式定位計算、易于實現(xiàn)三維定位等。而固定信標節(jié)點是一類裝備了GPS或其它定位裝置的不可移動節(jié)點。

1.2 基于距離的節(jié)點坐標計算基本方法

待定位節(jié)點在獲得與鄰近信標節(jié)點的距離信息后，通常采用下列方法計算自身的位置[3]。

1) 三邊測量法：利用網(wǎng)絡(luò)中三個信標節(jié)點的位置坐標以及未知節(jié)點到這三個信標節(jié)點的距離，運用幾何方法求出未知節(jié)點的坐標。

2) 三角測量法：利用網(wǎng)絡(luò)中三個信標節(jié)點的位置坐標以及未知節(jié)點為角頂點角邊分別為三個信標節(jié)點的角度，運用幾何方法求出未知節(jié)點的坐標。

3) 最小二乘估計法：利用未知節(jié)點的相鄰節(jié)點中的多個信標節(jié)點的位置坐標以及它們與未知節(jié)點的距離或角度，運用最小均方差估計方法求出未知節(jié)點的坐標。

1.3 常用的測距方法

1) 信號接收強度（RSSI）測距法

已知發(fā)射功率和天線接收增益，在接收節(jié)點測量信號接收功率，計算傳播損耗，使用理論或經(jīng)驗的無線電傳播模型由傳播損耗計算出信源與接收者間的距離。通常使用下列對數(shù)-常態(tài)分布模型來計算節(jié)點間的距離[1]。

PL(d)=PL(d0)+10λ?log(d/d0)+X （1）

PL(d0)=32.44+10λ?log(d0)+ 10λ?log(f) （2）

RSSI=發(fā)射功率+天線增益-路徑損耗(PL(d)) （3）

其中PL(d)[dB]是經(jīng)過距離d后的路徑損耗，X是平均值為0的高斯分布隨機變數(shù)，其標準差取為4至10，λ為取衰減因子通常為2至3.5，f是頻率，取d0=1(m)，這樣根據(jù)上述3式可得節(jié)點間的距離。

2) 到達時間測距法

到達時間(TOA)技術(shù)通過測量信號傳播時間來測量距離，若電波從信標節(jié)點到未知節(jié)點的傳播時間為t，電波傳播速度為c，則信標節(jié)點到未知節(jié)點的距離為t×c。

3) 時間差測距法

TDOA測距是通過測量兩種不同信號到達未知節(jié)點的時間差，再根據(jù)兩種信號傳播速度來計算未知節(jié)點與信標節(jié)點之間的距離，通常采用電波和超聲波組合。

4) 到達角定位法

到達角(AOA)定位法采用陣列天線或多個接收器組合來獲取相鄰節(jié)點所處位置的方向，從而構(gòu)成從接收機到發(fā)射機的方位線。兩條方位線的交點就是未知節(jié)點的位置。

1.4 典型非測距算法

基于距離測量和角度測量的定位算法的缺點是對專用硬件有一定的要求，從而使傳感器節(jié)點成本和體積加大，限制了它的實用性。非測距的算法不需要測量未知節(jié)點到信標節(jié)點的距離，在成本和功耗方面比基于測距的定位方法具有一定的優(yōu)勢，但是精度相對不足。

1) DV－h(huán)op算法

為了避免對節(jié)點間距離的直接測量， Niculescu等人提出了DV－h(huán)op算法[3]。該算法基本思想是：用網(wǎng)絡(luò)中節(jié)點的平均每跳距離和信標到待定位節(jié)點之間的跳數(shù)乘積來表示待定位節(jié)點到信標節(jié)點之間的距離，再用三角定位來獲得待定位節(jié)點的位置坐標。

2) 質(zhì)心法

質(zhì)心法由南加州大學(xué)Nirupama Bulusu等學(xué)者提出[3]，該算法是未知節(jié)點以所有可收到信號的信標節(jié)點的幾何質(zhì)心作為自己的估計位置，它是一種基于網(wǎng)絡(luò)連通性的室外節(jié)點定位算法。

3) APIT 算法

一個未知節(jié)點任選3個能夠與之通信的信標節(jié)點構(gòu)成一個三角形，并測試自身位置是在這個三角形內(nèi)部還是在其外部；然后再選擇另外3個信標節(jié)點進行同樣的測試，直到窮盡所有的組合或者達到所需的精度。

4) Amorphous 算法

Amorphous 定位算法[3]采用與 DV-Hop 算法類似的方法獲得距信標節(jié)點的跳數(shù)，稱為梯度值。未知節(jié)點收集鄰居節(jié)點的梯度值，計算關(guān)于某個信標節(jié)點的局部梯度平均值。Amorphous 算法假定預(yù)先知道網(wǎng)絡(luò)的密度，然后離線計算網(wǎng)絡(luò)的平均每跳距離，最后當獲得3個或更多錨節(jié)點的梯度值后，未知節(jié)點計算與每個錨節(jié)點的距離，并使用三邊測量法和最大似然估計法估算自身位置。

2 基于移動信標的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)

無論是距離相關(guān)還是距離無關(guān)定位算法，常采用固定信標節(jié)點方式測量距離、相對角度、傳播時間差及傳播時間等進行節(jié)點定位[1]。通常參與定位的固定信標節(jié)點越多, 定位精度將越高。但是信標節(jié)點的成本遠遠高于普通節(jié)點，當定位工作完成后，信標節(jié)點將轉(zhuǎn)成普通的傳感器節(jié)點使用。因此信標點越多，布設(shè)整個網(wǎng)絡(luò)的成本將會增大, 定位算法的計算負荷以及通訊負荷將會增大[1] ，過多的信標節(jié)點將會造成較大的浪費。所以利用移動節(jié)點發(fā)出的虛擬坐標點進行輔助定位的思想將成為節(jié)點定位研究的一個重要研究方向。

假定整個WSN由靜止節(jié)點以及移動節(jié)點(如撒播節(jié)點完畢的飛機、運動的車輛、移動的小型機器人或普通的能移動的傳感器節(jié)點等) 兩種類型節(jié)點構(gòu)成。根據(jù)傳感器網(wǎng)絡(luò)的規(guī)模大小, 可以配置一個或者多個移動節(jié)點。各移動節(jié)點均配置一個GPS接收器用于定位移動信標節(jié)點本身, 并有足夠的能量自我移動或捆綁移動機器人、移動車輛或三維空間中的飛機等工具。移動節(jié)點在傳感器區(qū)域內(nèi)按照一定的運動路徑移動, 并周期性地發(fā)送坐標位置信息, 待定位節(jié)點根據(jù)接收到的坐標信息與采用適當?shù)亩ㄎ凰惴ㄍ瓿啥ㄎ籟6] 。

近幾年有一些研究者對移動錨節(jié)點路徑規(guī)劃展開研究，提出了一些比較好的路徑規(guī)劃方案。移動錨節(jié)點路徑規(guī)劃主要有兩個目標：

1) 移動軌跡能夠覆蓋網(wǎng)絡(luò)中的所有未知節(jié)點；

2) 為未知節(jié)點定位提供質(zhì)量好的信標點。

如果滿足網(wǎng)絡(luò)節(jié)點均勻分布的條件，規(guī)劃路徑通常采用靜態(tài)規(guī)劃路徑，移動錨節(jié)點都按照預(yù)先規(guī)劃的路徑移動，不具有根據(jù)節(jié)點分布狀況靈活變化的性能。文獻[7]針對移動錨節(jié)點的路徑規(guī)劃問題利用空間填充線理論提出了SCAN、DOUBLESCAN以及HILBERT路徑規(guī)劃方法，分別如圖1、圖2和圖3所示。在節(jié)點通信距離小和空間填充線密度大的條件下， SCAN路徑比HILBERT路徑的定位結(jié)果準確。但是在節(jié)點通信距離大、空間填充線密度較小時，HILBERT路徑明顯優(yōu)于SCAN路徑。

SCAN路徑存在明顯的缺點就是提供了大量共線的信標點，HILBERT路徑通過增加移動路徑長度解決了信標點共線性的問題，只要達到一定的密度就可以為定位提供優(yōu)質(zhì)的不共線信標點。為了解決信標點存在共線性的問題，文獻[8]提出了圓形規(guī)劃路徑和S形規(guī)劃路徑方法，如圖4和圖5所示。圓形規(guī)劃路徑完全覆蓋方形網(wǎng)絡(luò)區(qū)域時必須增加大圓路徑，這很大程度增加了路徑的長度。而圓形的直徑非常大時，在局部帶來了信標點的共線性問題。S形路徑通過引入S形曲線代替直線，解決了信標點共線性問題。

而對于實際環(huán)境中節(jié)點非均勻分布的情況，文獻[9]提出了提出了寬度優(yōu)先和回溯式貪婪算法。這種方法能夠根據(jù)網(wǎng)絡(luò)信息自適應(yīng)進行路徑規(guī)劃，規(guī)劃路徑不再是規(guī)則的圖形，能夠充分利用節(jié)點分布信息覆蓋所有節(jié)點，保證路徑最短，克服了靜態(tài)路徑規(guī)劃的缺點。文獻[10]提出讓一個攜帶GPS的移動信標采用隨機移動模型的方式盡量遍歷傳感區(qū)域，然后采用分布式算法為未知節(jié)點定位，該方法結(jié)合了基于測距方法的優(yōu)點，并且無需布置固定的信標節(jié)點，節(jié)省了成本開銷，但是由于移動信標的移動模型采用隨機的方式，難以讓其移動范圍覆蓋整個傳感區(qū)域，從而有些未知節(jié)點無法定位。

3 定位算法的評價標準

定位算法設(shè)計的優(yōu)劣通常以下列幾個評價標準[11]來評價：

1）定位精度：一般用誤差值與節(jié)點無線射程的比例表示，是定位技術(shù)首要的評價指標。

2）定位覆蓋率：指利用定位算法能夠進行定位的節(jié)點數(shù)與總的未知節(jié)點個數(shù)之比，它是評價定位算法的另外一個重要的指標。

3）信標節(jié)點密度：信標節(jié)點占所有節(jié)點的比例或者是單位區(qū)域內(nèi)信標節(jié)點的數(shù)目。

4）節(jié)點密度：節(jié)點密度通常以網(wǎng)絡(luò)的平均連通度來表示。

5）功耗：功耗是指傳感器節(jié)點在單位時間內(nèi)所消耗的能源的數(shù)量。由于傳感器節(jié)點不會始終在工作的，有時候會處于休眠狀態(tài)，但這同樣也會消耗少量的能量，因此，傳感器節(jié)點的功耗一般會有兩個，一個是工作時的功耗，另一個是待機時的功耗。

6）成本：包括時間、空間和費用。時間指一個系統(tǒng)的安裝、配置和定位所需的時間?？臻g包括一個定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點的數(shù)量、安裝尺寸等。費用則包括實現(xiàn)某種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點設(shè)備的總費用。

7）魯棒性：定位系統(tǒng)和算法必須具有很強的容錯性和自適應(yīng)性，能夠通過自身調(diào)整或重構(gòu)糾正錯誤、適應(yīng)環(huán)境、減小各種誤差的影響，以提高定位精度。

上述的這些評價指標不僅是評價WSN自身定位系統(tǒng)和算法的標準，也是其設(shè)計和實現(xiàn)的優(yōu)化目標。

4 結(jié)束語

使用移動信標節(jié)點來完成WSN所有節(jié)點的定位，就必須要足夠的時間讓移動信標節(jié)點遍歷完整個網(wǎng)絡(luò), 為了減小所有節(jié)點定位所需的時間以及提高定位效率，如何進一步優(yōu)化移動信標節(jié)點的運動路徑將成為基于移動信標的WSN節(jié)點定位技術(shù)更研究的重要方向。

參考文獻：

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[2] A l-Karaki.JN, Kamal.AE. Routing Techniques in Wireless Sensor Networks: A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6, Dec,2004:6-28.

[3] 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報,2005,16(5):857-869.

[4] Kushwaha,M. Molnar,K. Sallai,J. Volgyesi, P. Maroti, M. Ledeczi, A. Sensor Node Localization Using Mobile Acoustic Beacons[C], In proc. 2005. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov,2005.

[5] 倪巍,王宗欣.基于接收信號強度測量的室內(nèi)定位算法[J].復(fù)旦學(xué)報(自然科學(xué)版),2004.43(1):72-76.

[6] Mihail L. Sichitiu ,Vaidyanathan Ramadurai. Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.

[7] Koutsonilas D, Das S M, Hu Y Charlie. Path Planning of mobile landmarks for localization in wireless sensor networks[J].Computer Communication.2007,30(13): 2577-259.

[8] Rui Huang,Zaruba Gergely V. Static Pathplanning for mobile beaeons to localize sensor networks[C] / /Proc of IEEE PerComW. Piscataway,NJ:IEEE，2007:323-330.

[9] Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma. Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sensor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.

篇11

中圖分類號：U116.2 文獻標識碼：A

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 引 言

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

企業(yè)通過選取恰當?shù)呐渌吐窂?，對運輸車輛進行優(yōu)化調(diào)度，可以明顯提高配送效率，有效減少車輛的空駛率和行駛距離，降低運輸成本，加快響應(yīng)客戶的速度從而提高客戶服務(wù)質(zhì)量，提高企業(yè)的核心競爭力。VRP作為物流系統(tǒng)優(yōu)化環(huán)節(jié)中關(guān)鍵的一環(huán)，其研究成果已經(jīng)應(yīng)用到快遞和報紙配送連鎖商店線路優(yōu)化以及城市綠化車線路優(yōu)化等社會實際問題中，因而車輛路徑問題的優(yōu)化研究具有很好的現(xiàn)實意義。

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

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

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

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

2 VRP的求解算法與研究現(xiàn)狀

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

2.1 遺傳算法（Genetic Algorithm，GA）

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

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

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

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

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

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

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

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

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

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

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

2.5 蝙蝠算法（Bat Algorithm，BA）

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

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

3 總結(jié)與展望

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

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

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

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

參考文獻：

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

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

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

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

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

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

-1636.

[7] 魏江寧，夏唐斌. 基于混合模擬退火算法的多階段庫存路徑問題研究[J]. 工業(yè)工程與管理，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]. 系統(tǒng)工程理論與實踐，2011，31（8）：1508

-1516.

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

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

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

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

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