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

2、們在本論文中我們主要做了兩方面的工作，其一：對多約束動態(tài)路徑規(guī)劃算法進行研究優(yōu)化；其二：我們結合供應鏈管理系統(tǒng)，將多約束動態(tài)路徑規(guī)劃算法應用于供應鏈管理系統(tǒng)中，對整個系統(tǒng)進行了設計和實現(xiàn)。
　　在多約束動態(tài)路徑規(guī)劃研究中，選取現(xiàn)有的路徑搜索算法中比較經(jīng)典的算法Dijkstra算法和A*算法，通過比較這兩種算法的執(zhí)行過程和執(zhí)行特點以及供應鏈系統(tǒng)中歲算法的實時性要求，選定對A*算法進行優(yōu)化，并通過選定不同的測試用例，比較這三種算法在搜

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

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