多約束動(dòng)態(tài)路徑規(guī)劃研究與應(yīng)用.pdf

1、隨著經(jīng)濟(jì)的發(fā)展，人們發(fā)現(xiàn)路上的車越來(lái)越多了，但是交通也越來(lái)越堵了，人們出行漸漸成了令人頭疼的問(wèn)題，開(kāi)車必須使用GPS路徑導(dǎo)航系統(tǒng)已成了普遍現(xiàn)象，在車輛擁堵不是很嚴(yán)重的情況下，簡(jiǎn)單的導(dǎo)航系統(tǒng)還能滿足大眾的需求，然而隨著車輛越來(lái)越多，道路的擁擠程度越來(lái)越嚴(yán)重，現(xiàn)有的路徑規(guī)劃系統(tǒng)僅僅規(guī)劃出最短路線漸漸不能滿足人們的需求，人們希望有一個(gè)能夠考慮當(dāng)前各種約束信息的規(guī)劃路徑系統(tǒng)，在路徑規(guī)劃系統(tǒng)中考慮當(dāng)前交通狀況，而只不是靜態(tài)路徑。有了這樣的需求，我

2、們?cè)诒菊撐闹形覀冎饕隽藘煞矫娴墓ぷ?，其一：?duì)多約束動(dòng)態(tài)路徑規(guī)劃算法進(jìn)行研究?jī)?yōu)化；其二：我們結(jié)合供應(yīng)鏈管理系統(tǒng)，將多約束動(dòng)態(tài)路徑規(guī)劃算法應(yīng)用于供應(yīng)鏈管理系統(tǒng)中，對(duì)整個(gè)系統(tǒng)進(jìn)行了設(shè)計(jì)和實(shí)現(xiàn)。
　　在多約束動(dòng)態(tài)路徑規(guī)劃研究中，選取現(xiàn)有的路徑搜索算法中比較經(jīng)典的算法Dijkstra算法和A*算法，通過(guò)比較這兩種算法的執(zhí)行過(guò)程和執(zhí)行特點(diǎn)以及供應(yīng)鏈系統(tǒng)中歲算法的實(shí)時(shí)性要求，選定對(duì)A*算法進(jìn)行優(yōu)化，并通過(guò)選定不同的測(cè)試用例，比較這三種算法在搜

3、索結(jié)果精準(zhǔn)度、搜索計(jì)算時(shí)間以及訪問(wèn)節(jié)點(diǎn)數(shù)三個(gè)方面的對(duì)比，選出優(yōu)化的A*算法作為多約束路徑搜索的主要算法。之后根據(jù)用戶在使用的過(guò)程中對(duì)多約束路徑的需求，我們將優(yōu)化的A*算法與多約束最優(yōu)路徑問(wèn)題相結(jié)合，通過(guò)設(shè)計(jì)極限權(quán)值向量，求取極限權(quán)值向量最小的路徑，來(lái)求取滿足多種約束條件的最優(yōu)路徑問(wèn)題。之后，為了防止“擁堵漂移”現(xiàn)象的發(fā)生，我們?cè)诼窂揭?guī)劃的過(guò)程中，使用了Kpath搜索策略，使得規(guī)劃出來(lái)的路徑不僅有最優(yōu)路徑，還有次優(yōu)和再次優(yōu)路徑，有效地防止

4、“擁擠漂移”的發(fā)生。
　　在供應(yīng)鏈管理系統(tǒng)中，我們首先分析了供應(yīng)鏈管理模型，對(duì)供應(yīng)鏈中最為核心的物流運(yùn)輸環(huán)節(jié)進(jìn)行分析，建立基于多約束動(dòng)態(tài)路徑規(guī)劃的系統(tǒng)。在系統(tǒng)中，結(jié)合MIS和GIS技術(shù)，在充分分析供應(yīng)鏈管理系統(tǒng)設(shè)計(jì)的需求的基礎(chǔ)上，對(duì)系統(tǒng)的體系結(jié)構(gòu)進(jìn)行精心設(shè)計(jì)，并對(duì)系統(tǒng)中的不同角色予以不同的使用權(quán)限。利用空間數(shù)據(jù)信息，結(jié)合WebGIS框架，對(duì)空間數(shù)據(jù)進(jìn)行管理，通過(guò)設(shè)計(jì)簡(jiǎn)潔友好的客戶端界面，便于用戶選取規(guī)劃路線的起點(diǎn)與終點(diǎn)，并將規(guī)劃結(jié)