消防車路徑優化問題的研究
2017-09-20 00:31:40袁威威
魅力中國 2017年13期
袁威威
摘要：對消防車的路徑進行研究，確定最佳路線以提高滅火速度，縮短消防車抵達起火處時間，采用鄰接矩陣算法作為求解該問題的核心算法，尋找到時間最少和路徑最短的最優路徑。
關鍵詞：鄰接矩陣；路徑優化；有向圖
目前我國絕大多線路優化，是憑借經驗，也有少部分開始借助于信息技術實現線路的優化工作。本文求解最佳路徑的過程即尋找最短時間和最短路徑，我們將路徑抽象為有向圖，利用有向圖的鄰接矩陣。尋找到時間最少和路徑最短的最優路徑。
一、應用舉例
下面以某小區為例
假設將小區的十字路口設為v1，v2，v3，v4，v5為有向圖的五個定點，小區的主干線為有向圖的邊，通過每條路的時間為有向圖邊的權。下面我們可以得到鄰接矩陣如下：
在小區中任意選取兩點v3到v2從加權值為根據圖二和距離矩陣D可知，當v5發生災情時，消防站點v3可到達v5的路徑有：v3-v4-v5，v3-v2-v5，v3-v2-v1-v5，v3-2-v4-v5，-v5，v3-v4-v2-v1-v5等若干條路線，所以從v2可到達v4兩處之間的加權值最小的路線為v3-v4-v5加權值為15，其他的兩兩任意兩頂點之間也可根據這樣的算法得出兩頂點之間的最短距離。
二、結論
采用鄰接矩陣算法能夠方便求出火災救援所需的最短路徑，如突發交通事故或是車輛擁擠引起的交通堵塞。這需受密切注意掌握最新交通動態信息，及時準確地獲取動態的路段耗時特征，并及時計算最佳行車路徑，做出準確合理的應急決策。如果路徑復雜本算法可以通過程序重復使用，只需輸入相應的仞始數據即可，極大的減少了人力資源的浪費。endprint
