路徑規(guī)劃范文第1篇

關(guān)鍵詞：智能交通 A*算法 靜態(tài)路徑規(guī)劃

中圖分類號：P285 文獻標識碼：A 文章編號：1007-9416（2023）09-0117-02

1 引言

城市交通道路的復(fù)雜性，固定意識的出行路徑引發(fā)的嚴重交通堵塞，使出行者迫切需要獲得正確的出行路徑；出行過程中，對不熟知地理環(huán)境和周圍交通狀況的把握和了解；車輛及出行者對社會服務(wù)的急迫需要；荒野作業(yè)過程中的道路迷失。我們可以得出一個重要的結(jié)論，就是隨著出行者活動范圍的不斷擴大，人們迫切需要對車輛自身所處的位置及周圍環(huán)境有更有效的認識，并作出理性的判定[1]。有效調(diào)高出行車輛行駛過程中的路徑規(guī)劃效果是解決城市交通堵塞的重要方法。

2 建立靜態(tài)路徑規(guī)劃數(shù)學(xué)模型

對于最優(yōu)道路路徑規(guī)劃策略的研究上來說，道路口節(jié)點和路徑就可以對智能交通網(wǎng)進行數(shù)學(xué)邏輯上的描述，這一個基本的數(shù)字路網(wǎng)模型圖可以表示為：

（2.1）

式中：G為智能交通道路的基本電子路網(wǎng)模型；N為道路網(wǎng)絡(luò)路口節(jié)點的集合，ni為表示道路路網(wǎng)的任意一個節(jié)點，xi， yi為該任意節(jié)點的橫和縱坐標；R為道路路網(wǎng)層路徑的ri集合，為道路路網(wǎng)任意一段路徑，為兩個道路口節(jié)點之間或任意一條道路徑的權(quán)重值。

依據(jù)智能交通原始電子地圖，創(chuàng)建交通路網(wǎng)的空間拓撲結(jié)構(gòu)相圖G，以此為基礎(chǔ)建立靜態(tài)路徑規(guī)劃數(shù)學(xué)模型，模型具體描述如下：

2.1 定義智能交通路網(wǎng)的權(quán)值變量

實際智能交通中的兩道路口節(jié)點，相關(guān)的任意道路徑都含有一個權(quán)值，依據(jù)電路的常用定義規(guī)則，稱為道路阻抗，描述了車輛行駛過程中通過該道路路徑所要消耗的能量變量值，該值可以定義：道路路徑的空間距離、通過該道路路徑所需時間、車輛行駛路程繳費，依據(jù)用戶所關(guān)心的目標函數(shù)可以采用不同的權(quán)值測量方法。

最優(yōu)路徑規(guī)劃的目標函數(shù)為：車輛行駛過程中的始末道路最短路徑DistanceMin。設(shè)，式中為車輛行駛過程中的路徑值，。

最優(yōu)路徑規(guī)劃的目標函數(shù)為：車輛行駛過程中的始末道路最短時間DistanceMin。設(shè)，式中為道路路徑的寬度和等級，，為系數(shù)。假設(shè)車輛的平均速度與道路路徑的寬度和等級成正比。

此外，據(jù)用戶所關(guān)心的目標函數(shù)可以采用不同的權(quán)值測量方法，最優(yōu)路徑規(guī)劃的目標函數(shù)為車輛行駛路程繳費最小的情況時，需要考慮車輛行駛過程中的道路的收費和油耗，并忽略車輛其他損耗。

2.2 最優(yōu)路徑規(guī)劃的目標函數(shù)T

依據(jù)用戶所關(guān)心的目標函數(shù)T，可以采用不同的定義方法。通常在最優(yōu)路徑規(guī)劃策略考慮，始末道路節(jié)點的路徑最短、及車輛耗時最小等。

車輛在智能交通網(wǎng)絡(luò)的行駛過程中，始末道路口節(jié)點之間的道路徑，分為m條路徑，車輛通過每條路徑的時間為。最優(yōu)路徑規(guī)劃的目標函數(shù)T定義為：

標函數(shù)T為最小路徑：

； （2.2）

標函數(shù)T為最小路徑：

， （2.3）

因為：

（2.4）

則：

（2.5）

3 A-star算法設(shè)計

A-star算法是一種路徑規(guī)劃過程中比較經(jīng)典的預(yù)測方式的搜索算法。采用智能交通網(wǎng)的全局信息變量，通過選擇合理的預(yù)測估計評價函數(shù)，預(yù)設(shè)置優(yōu)先查詢的到路徑方向，以減少搜索的道路口節(jié)點及路徑的路段個數(shù)，實現(xiàn)查詢的最優(yōu)效率。以道路口節(jié)點之間的歐式距離及道路等級為A-star算法預(yù)測啟發(fā)式的評價指標，定義如下所示：

（3.1）

其中，是始點到當(dāng)前節(jié)點之間實際所產(chǎn)生的通過道路路徑的費用，即是始末兩節(jié)點之間的，每段路徑的道路等級乘以道路的路徑長度相加的代數(shù)和，是當(dāng)前節(jié)點到目的地節(jié)點的最小代價值，本文取當(dāng)前節(jié)點到目的地節(jié)點的歐式距離，為表智能交通道路分類序號值，取值為0、1、2；選擇道路等級作為算法價值的評價指標，主要是考慮智能交通網(wǎng)中的高等級路，道路的路況及安全系數(shù)較高，雖然不是車輛行駛過程中的最短路徑，但是可以給行車者帶來精神放松，提升交通安全指標。A-star算法主程序框圖如圖3.1所示。

4 實驗研究

車輛的靜態(tài)最優(yōu)路徑軌跡規(guī)劃，以復(fù)雜情況較大的北京市東城區(qū)的三環(huán)和四環(huán)之間的道路網(wǎng)數(shù)據(jù)為路徑規(guī)劃源。東西距離10KM，南北距離4KM。技術(shù)平臺支持：Inter Pentium 4 1.8GHz，512M內(nèi)存，Microsoft Windows server 2003操作系統(tǒng)。采用道路網(wǎng)道路功能的兩層分類：略圖層和詳圖層，細線為略圖層網(wǎng)絡(luò)結(jié)構(gòu)，粗線為詳圖層網(wǎng)絡(luò)結(jié)構(gòu)。交通網(wǎng)略圖層包含道路的路徑段178條，道路口節(jié)點數(shù)53個，交通管制的轉(zhuǎn)向限制為8條；詳圖層包括道路路徑段2031條，道路口節(jié)點1419個，交通管制的轉(zhuǎn)向限制為2307條。在路徑規(guī)劃仿真平臺中，任意選擇車輛行駛路徑的始末點，A*實驗結(jié)果統(tǒng)計如表4.1所示。

5 結(jié)語

在智能交通網(wǎng)中的靜態(tài)路徑規(guī)劃算法研究中，具有啟發(fā)式的A*算法能夠?qū)崿F(xiàn)車輛的靜態(tài)最優(yōu)路徑規(guī)劃，最優(yōu)路徑規(guī)劃策略能夠直接有效的提高道路的使用效率。減少城市交通堵塞情況的產(chǎn)生，可以做到節(jié)能減排的效果，產(chǎn)生更多的經(jīng)濟和社會效益。

參考文獻

[1]常青，楊東凱，寇艷紅，張其善.車輛導(dǎo)航定位方法及應(yīng)用[M].北京：機械工業(yè)出版社，2005.

[2]陸化普.智能交通運輸系統(tǒng).北京：人民交通出版社，2002.

[3]G.A.Giannopoulos The application of information and communication technologies in transport. European Journal of Operational Research 152（2023）：302-320.

路徑規(guī)劃范文第2篇

關(guān)鍵詞:移動機器人 路徑規(guī)劃 障礙物

中圖分類號:TP24 文獻標識碼:A 文章編號:1007-9416(2023)08-0015-02

1 引言

在有障礙物的工作環(huán)境中,如果機器人及障礙物的位置可以實時測得,則可以尋找一種移動機器人的優(yōu)化路徑規(guī)劃算法,使機器人在運動過程中無碰撞地繞過所有的障礙物,安全的到達指定目標位置[1]。

路徑規(guī)劃問題根據(jù)機器人的工作環(huán)境模型可以分為兩種,一種是基于模型的路徑規(guī)劃,作業(yè)環(huán)境的全部信息都是預(yù)知的;另一種是基于傳感器的路徑規(guī)劃,作業(yè)環(huán)境的信息是全部未知或部分未知的。

本文提出一種計算簡單、容易實現(xiàn)的移動機器人路徑規(guī)劃方法,可供側(cè)重于應(yīng)用的讀者參考。

2 問題描述

設(shè)機器人在長度為L的L×L的二維平面上能夠自由運動,將機器人模型化為點狀態(tài)機器人,在L×L的二維平面上存在若干個靜態(tài)障礙物和在一定范圍內(nèi)運動的動態(tài)障礙物,根據(jù)安全性的要求進行了相應(yīng)的“膨脹化”處理,使“膨脹化”后的障礙物邊界為安全區(qū)域,“膨脹化”后的障礙物邊界區(qū)域內(nèi)為凸型,邊界為光滑曲線,邊界上各點曲率半徑≤δ(其中δ是正常量,可假設(shè)為圓的半徑),曲率中心在障礙物內(nèi)部,單個機器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑[2]。設(shè)終點(目標)的坐標為已知,機器人在任何時刻都能測出機器人所在位置與終點連線和機器人到障礙物邊界的切線的夾角。根據(jù)夾角的大小來判斷所選擇的無碰撞行走路徑[3]。如圖1所示,由于角α

3 路徑規(guī)劃原理

3.1 求切線法的路徑規(guī)劃原理

根據(jù)幾何學(xué)園外兩點到園的四條切線,其切線與兩點連線夾角小的兩條線段之和小于切線與兩點連線夾角大的兩條線段之和。如圖2所示。設(shè)A和B兩點坐標分別為(XA,YA)和(XB,YB),如果角α

由(X-XB)/(XA-XB)=(Y-YB)/(YA-YB)得:(YA-YB)X-(XA-XB)Y+(XAYB-YAXB)=0

(2)利用夾角求切線方程

如果測出過A、B兩點與園的切線和AB直線的夾角,則可求出切線方程。

在圖2中,直線AN的方程為:Y-YA=tanα(X-XA)

直線AM的方程為:Y-YA=tanβ(X-XA)

直線NB的方程為:Y-YB=tanα1(X-XB)

直線MB的方程為:Y-YB=tanβ1(X-XB)

(3)由四條切線求點A到點B的最短路徑

根據(jù)角α

3.2 首先判斷機器人和給定的目標位置之間是否存在障礙物

如圖1所示,以R代表機器人,坐標為(XR,YR),以G代表目標位置,其坐標為(XG,YG),障礙物為A、B、C、D、E、F等,坐標為 (XA,YA)、(XB,YB)、(XC,YC)、(XD,YD)、(XE,YE)、(XF,YF)等。Rr表示機器人半徑、Ri(i=A、B、C、D、E、F)表示障礙物的碰撞半徑,也就是說在其半徑以外無碰撞的危險。要根據(jù)實際情況和控制要求來確定碰撞半徑。碰撞半徑Rp一般選擇大于障礙物的半徑Ri加上機器人半徑Rr,即Rp>Ri+Rr。

3.3 單障礙物情況

機器人在任何時刻都能夠測得機器人的位置坐標(XR,YR),目標位置是已知的(XG,YG),可測量出機器人與目標連線和機器人與障礙物碰撞圓的切線的兩個夾角αi和βi(i=1,2,…)。若αi

3.4 多障礙物情況

對于多障礙物情況,可將移動機器人繞過多個障礙物最終到達目標位置作為一個總?cè)蝿?wù),每當(dāng)繞過一個障礙物作為一個分任務(wù)�？�?cè)蝿?wù)就可分解為多個分任務(wù),設(shè)第i個分任務(wù)的目標點為Gi和中途點為Bi,執(zhí)行第i個分任務(wù)時,如果在到達Gi的路徑上存在障礙物,則增加第i+1個分任務(wù),此時目標點Gi+1就是Bi;以此類推,尋找切線路徑直至到達給定的最終目標位置,計算所有分任務(wù)的最短切線路徑之和即為所求的最優(yōu)路徑[4]。

4 行路徑算法

(1)機器人朝著目標按直線方向行走,直到以下任一情況發(fā)生:

①已經(jīng)到達目標,結(jié)束。

②在機器人與目標之間發(fā)現(xiàn)障礙物,轉(zhuǎn)(2);

(2)按路徑規(guī)劃的原理選擇路徑,轉(zhuǎn)(1)。

5 結(jié)語

移動機器人路徑規(guī)劃的算法有很多,每一種算法能夠適用于幾種特定的場合。一個好的算法,不但理論簡單,計算快捷,容易理解,便于實現(xiàn),而且實現(xiàn)的效果好,能夠提高運行效率。本文介紹的移動機器人的路徑規(guī)劃方法,容易理解,便于實現(xiàn),可適用于某些特定的場合。

參考文獻

[1] 李彩虹,李貽斌,范晨.移動機器人動態(tài)避障算法[J].山東大學(xué)學(xué)報,2007,5(37):60-64.

[2] 陳剛.復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法[J].機器人,2001,(3):230-233.

路徑規(guī)劃范文第3篇

關(guān)鍵詞：限制搜索區(qū)域；多比例尺；最優(yōu)路徑規(guī)劃算法；Dijkstra算法

為了提高大區(qū)域路網(wǎng)路徑規(guī)劃的效率,國內(nèi)外很多專家學(xué)者做了大量的研究工作，提出了一些新的算法。這些算法大多數(shù)采用路網(wǎng)分級技術(shù)或分解技術(shù)來減少大規(guī)模路網(wǎng)的存儲需求和計算的開銷，如文獻[1~3]中提出的算法。然而現(xiàn)有的路網(wǎng)分級分解技術(shù)存在著一些問題,主要表現(xiàn)在[4]:路網(wǎng)分解沒有統(tǒng)一的標準；路網(wǎng)分級處理時,大多按照道路的屬性,如主干道、次干道等,對路網(wǎng)進行分級,要求屬性信息非常完整,否則無法分級；若提取出的每一級路網(wǎng)不連通時將無法處理；在涉及到幾百甚至幾千幅地圖時,從每幅地圖中提取主干道、次干道路網(wǎng)再拼接成多級路網(wǎng),其工作量巨大,可行性不強；等等。針對以上問題，本文提出一種限制搜索區(qū)域的多比例尺最優(yōu)路徑規(guī)劃算法（multi�瞫caleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，MORPARSA）。

1MORPARSA

1．1路網(wǎng)的空間分布特性

與普通的平面網(wǎng)絡(luò)圖相比,描述實際城市路網(wǎng)的拓撲圖通常具有以下特點[5,6]：每個節(jié)點相連的路段數(shù)一般不超過5，多為2、3或4；網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代化都市)；網(wǎng)絡(luò)中有表示供車輛調(diào)頭的專門換向節(jié)點,而且一般距當(dāng)前路口500m左右。

1．2區(qū)域限制的思想

Dijkstra算法求解的是某個源點到其余各節(jié)點的最短路徑，它按節(jié)點距起始點距離遞增的順序產(chǎn)生最短路徑，因此該算法在最短路徑的搜索過程中具有很大的盲目性，隨時都準備向四面八方展開[5]。該算法搜索的區(qū)域是整個路網(wǎng)平面，時間復(fù)雜度為�玂(n��2)。其中n�珵槁肪W(wǎng)中的節(jié)點數(shù)。

由于實際城市路網(wǎng)結(jié)構(gòu)相對比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代化都市，如西安市)[5~7]中，��最短路徑一般都會落入以起始點S和目標點D的連線為對角線的矩形區(qū)域中，如圖1中的小矩形。應(yīng)該說明的是，在靠近兩節(jié)點的附近，有時可能會出現(xiàn)短距離的反向路徑(指在線段SD的兩端點外，沿SD或DS延長線方向的路徑，反映在實際系統(tǒng)中，通常代表車輛為轉(zhuǎn)入合適車道行駛所走過的路徑)[5]，此時最短路徑顯然不會落在以S和D的連線為對角線的矩形區(qū)域中，因此將以S和D的連線為對角線的矩形四邊向外各擴展��500m，形成一個更大的矩形作為限制區(qū)域，如圖1所示。

如果路網(wǎng)中的節(jié)點在整個路網(wǎng)平面內(nèi)均勻分布(即節(jié)點數(shù)與其所占區(qū)域的面積成正比，即使局部節(jié)點的分布不均勻)，那么搜索過程中實際所需訪問的節(jié)點數(shù)就可用搜索掃過區(qū)域的面積�獵表示，進而搜索的時間復(fù)雜度可表示為�㎡(C��2)[5]。假設(shè)圖1中整個路網(wǎng)平面的面積為C��1，大矩形的面積為C��2。由于�〤��2＜＜C��1,��合理限制搜索區(qū)域理論上可以提高路徑規(guī)劃的效率。

1．3多比例尺路網(wǎng)數(shù)據(jù)模型

人們習(xí)慣于用比例尺的概念來描述地圖對現(xiàn)實世界不同詳盡程度的表達，比例尺越大，對現(xiàn)實世界的描述就越詳細，對空間對象幾何形的描述也越詳細�？梢杂帽壤�尺來描述不同重要程度的道路，如圖2所示。

我國基礎(chǔ)地理信息的比例尺系列包括��1∶100萬、��1∶50萬、��1∶25萬、��1∶10萬、��1∶5萬、��1∶1萬等，多比例尺自然就起到了分級的作用。

多比例尺信息的這種分級特性與道路的屬性信息相關(guān)，主要道路存在于小比例尺地圖中，次要道路存在于大比例尺地圖中，而且大比例尺地圖中包含了小比例尺地圖中的道路，顯示了更為詳細的道路信息。因此，可以采用多比例尺數(shù)據(jù)構(gòu)建多級路網(wǎng)結(jié)構(gòu)處理大區(qū)域的路徑搜索問題[4,8],如圖3所示。

基于多比例尺數(shù)據(jù)構(gòu)建的多級路網(wǎng)模型解決了原有的分級分解算法中存在的一些問題,主要改進的問題如下[4,8]:根據(jù)道路屬性對道路進行分級時，需要作一些處理,很難保證提取的同一級路網(wǎng)是連通的，采用多比例尺數(shù)據(jù)構(gòu)建的多級路網(wǎng),多比例尺本身起到了分級的作用，在每一比例尺下,路網(wǎng)數(shù)據(jù)具有連通性�，F(xiàn)有的分級分解算法一般按照道路的屬性對路網(wǎng)進行分級,因而在道路屬性信息不完整的情況下無法處理；在大區(qū)域范圍內(nèi),即使屬性信息齊全,提取構(gòu)建多級路網(wǎng)工作量繁重、不易實施。在全國基本比例尺地形圖庫已經(jīng)建立的情況下,采用多比例尺數(shù)據(jù)構(gòu)建多級路網(wǎng)顯然是可行的。

1．4算法描述

設(shè)多級路網(wǎng)一共有�玏級(W≥1)。

輸入：多比例尺路網(wǎng)數(shù)據(jù)，起始點S、目標點D為路網(wǎng)中任意指定的兩個節(jié)點。

輸出：S和D之間的一條最優(yōu)路徑。��

3結(jié)束語

本文提出的MORPARSA可以提高路徑規(guī)劃的效率。多級路網(wǎng)中,低級網(wǎng)絡(luò)一般為主要干道,符合駕駛者首先選擇行駛在主干道的愿望,避開了交通不方便的次要道路,合理性較高。

參考文獻：

[1]彭飛,柳重堪,張其善.車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J].北京航空航天大學(xué)學(xué)報,2002,28(1):70-73.

[2]陳則王,袁信.基于分層分解的一種實時車輛路徑規(guī)劃算法[J].南京航空航天大學(xué)學(xué)報,2003,35(2):193��197.

[3]JAGADEESHGR,SRIKANTHANT.Heuristictechniquesfor�゛c�勃ヽeleratinghierarchicalroutingonroadnetworks[J].IEEETransonIntelligentTransportationSystems,2002,3(4):301-309.

[4]陳玉敏,龔健雅,史文中.多級道路網(wǎng)的最優(yōu)路徑算法研究[J].武漢大學(xué)學(xué)報,2006,31(1):70-73.

[5]付夢印,李杰,鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報,2004,24(10):881-884.

[6]嚴寒冰,劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計算機學(xué)報,2000,23(2):210-215.

[7]王曉麗,楊兆升,呂旭濤，等.平行四邊形限制最短路徑算法及其在道路網(wǎng)絡(luò)中的應(yīng)用[J].吉林大學(xué)學(xué)報,2006,36(1):123��127.

路徑規(guī)劃范文第4篇

關(guān)鍵詞：動態(tài)規(guī)范 路徑圖 多階段決策

一、動態(tài)規(guī)劃簡介

動態(tài)規(guī)劃是運籌學(xué)的一個分支，它是解決多階段決策過程的最優(yōu)化的一種數(shù)學(xué)方法。美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在1951年根據(jù)一類多階段決策問題的特點，把多階段決策問題變換為一系列互相關(guān)聯(lián)的單階段問題，然后逐個加以解決，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法。動態(tài)規(guī)劃的方法在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有廣泛的應(yīng)用，并且獲得了顯著的效果�？梢杂脕斫鉀Q最優(yōu)路徑問題、資源分配問題、設(shè)備更新問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、貨郎擔(dān)問題、采購與銷售問題、限期采購問題、生產(chǎn)過程最優(yōu)控制問題等。

二、建立動態(tài)規(guī)劃模型的步驟

動態(tài)規(guī)范模型在日常生產(chǎn)、生活中應(yīng)用廣泛，建立動態(tài)規(guī)范模型一般遵循以下步驟：

（1）將問題的過程劃分成恰當(dāng)?shù)碾A段（一般按時間或空間的先后順序）；

（2）正確選擇狀態(tài)變量SK ，使它既能描述過程的演變，又要滿足無后效性；

（3）正確設(shè)立決策變量uk ，明確每階段的允許決策集合Dk（Sk ）；（通常選擇所求解問題的關(guān)鍵變量作為決策變量）

（4）根據(jù)第K階段的狀態(tài)變量和決策變量正確寫出狀態(tài)轉(zhuǎn)移方程

（5）正確寫出指標函數(shù)

指數(shù)函數(shù)應(yīng)滿足下面三個性質(zhì)：①是定義在全過程和所以子過程上的數(shù)量函數(shù)； ② 要具有可分離性，并滿足遞推關(guān)系。③函數(shù)對變量 Vk+1，n要嚴格單調(diào)。

（6）寫出動態(tài)規(guī)劃的基本方程包括邊界條件。

（7）求解模型。

三、用路徑圖求解動態(tài)規(guī)劃問題應(yīng)用舉例

用動態(tài)規(guī)劃的方法求解實際問題通�？梢园瓷厦娴牟襟E來建立模型，有部分問題可以化為（最短）路徑問題，用路徑圖能直觀的理解上面的算法。

如某建筑公司新購置了四臺挖掘機，準備分給甲、乙、丙三個公司，事先請專家調(diào)查了各分公司的經(jīng)營情況，并對各種分配方案進行了經(jīng)濟效益的估計，見下表，其中機器數(shù)為0時的收益，是指已有的經(jīng)營收益，問應(yīng)如何分配這四臺機器，使總的收益為最多？

本題用動態(tài)規(guī)劃的常規(guī)方法建模求解可參看[1]，下面采用本文要講的路徑圖的方法來求解，更直觀易懂。

具體解答過程如下：

解：由于有三個公司，所以劃分為三個階段，狀態(tài)變量 表示第k階段初分配者手中擁有的機器總數(shù)，決策變量 表示第k階段分配給第k個用戶的機器數(shù)，狀態(tài)轉(zhuǎn)移方程為： Sk+1=sk-uk

階段指標函數(shù)： vk（sk，uk）=gk（uk）表示k階段公司k利用所分到的資源（機器）產(chǎn)生的收益；最優(yōu)值函數(shù)fk（sk） 表示將機器數(shù)sk 分配給公司k到公司丙所獲得的最大收益：

表示狀態(tài)變量所取的值，狀態(tài)連線上小于5的數(shù)字表示決策變量所取的值，[數(shù)字]表示該階段的指標值（收益）， 表示該狀態(tài)到最后一個公司的最大收益，粗線條表示最優(yōu)策略路徑，從上圖很容易看出最大收益為164萬元，最優(yōu)策略是：u1=3，u2=0，u3=1 ，即分給甲3臺，乙不分，丙1臺時，總收益164萬元最大。

結(jié)束語：

對于最段路徑問題、資源分配問題、生產(chǎn)與存儲計劃問題，只要階段不是太多，狀態(tài)變量的取值不超過6個，一般可以采用路徑圖直觀的求解出模型的解。

參考文獻：

[1]岳宏志，藺小林，運籌學(xué)[M]，東北財經(jīng)大學(xué)出版社，2023.8.

路徑規(guī)劃范文第5篇

【關(guān)鍵詞】虛擬場景；路經(jīng)規(guī)劃；八叉樹；A*算法

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

一、引言

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

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

文章采用八叉樹和A*算法相結(jié)合的方法，對路徑進行規(guī)劃，并對A*算法做了改進，以適應(yīng)八叉樹的存儲結(jié)構(gòu)。

二、密集型區(qū)域八叉樹劃分算法

八叉樹是由四叉樹推廣到三維空間而形成的一種三維柵格數(shù)據(jù)結(jié)構(gòu)，它作為一種場景組織方法，廣泛應(yīng)用于虛擬現(xiàn)實系統(tǒng)，可顯著減少對場景中多邊形進行排序的時間。

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

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

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

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

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

三、A*算法

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

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

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

A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：

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

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

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

五、結(jié)束語

針對于復(fù)雜的3D環(huán)境，文章根據(jù)八叉樹適合虛擬場景劃分的特點，采用了一種適合密集型區(qū)域的八叉樹劃分方法，進行場景劃分。為適合八叉樹的存儲結(jié)構(gòu)，對A*算法做了改進，引入優(yōu)先級隊列并采用了分層結(jié)構(gòu)，采用了從葉節(jié)點到根節(jié)點的搜索方法，規(guī)劃出了虛擬人行走的最優(yōu)路徑。