[發明專利]一種基于遺傳算法的地下物流節點間路徑規劃方法

在審

• 申請號: 201711310342.3
• 申請日: 2017-12-11
• 公開（公告）號: CN107977751A
• 公開（公告）日: 2018-05-01
• 發明（設計）人: 劉良桂;伍偉;王玲敏;賈會玲;張宇
• 申請（專利權）人: 浙江理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 黃歡娣,邱啟旺

技術領域

本發明涉及地下空間開發與應用及交通運輸工程領域，尤其涉及一種基于遺傳算法的地下物流節點間路徑規劃方法。

背景技術

路徑規劃技術在很多領域都具有廣泛的應用。在高新科技領域的應用有:機器人的自主無碰行動；無人機的避障突防飛行；巡航導彈躲避雷達搜索、防反彈襲擊、完成突防爆破任務等。在日常生活領域的應用有:GPS導航；基于GIS系統的道路規劃；城市道路網規劃導航等。在決策管理領域的應用有:物流管理中的車輛問題(VRP)及類似的資源管理資源配置問題。通信技術領域的路由問題等。凡是可拓撲為點線網絡的規劃問題基本上都可以采用路徑規劃的方法解決。

路徑規劃的核心就是算法的設計，路徑規劃算法目前已經得到了廣泛的關注，從傳統算法，到后來的結合仿生學發展起來的算法，智能算法已經取得了巨大的進展。不同的智能算法特點不同，適用范圍和領域也就不同，因而從算法本身特點及其應用來研究路徑規劃智能算法，對路徑規劃技術的發展具有重要意義。

傳統的路徑規劃算法有:模擬退火算法、人工勢場法、模糊邏輯算法、禁忌搜索算法等；圖形學的方法有：C空間法、柵格法、自由空間法、voronoi圖法等；智能仿生學算法就是人們通過仿生學研究，發現的算法，常用到的有:蟻群算法、神經網絡算法、粒子群算法、遺傳算法等。

遺傳算法(Genetic Algorithms，簡稱GA)是當代人工智能科學的一個重要研究分支，是一種模擬達爾文遺傳選擇和自然淘汰的生物進化過程中的計算模型。它的思想源于生物遺傳學和適者生存的自然規律，是按照基因遺傳學原理而實現的一種迭代過程的搜索算法。最大的優點是易于與其他算法相結合，并充分發揮自身迭代的優勢，缺點是運算效率不高，不如蟻群算法有先天優勢，但其改進算法也是目前研究的熱點。

不同于地上運輸，地下物流系統建設過程中地下管道鋪設造價較高、維修困難，所以在建設地下物流系統時既要考慮成本因素，又要使得地下物流系統具有一定的抗風險能力。同時地下物流系統的布局結構對整個物流系統的效率和穩定性至關重要，因此合理規劃地下物流系統網絡十分關鍵。

發明內容

本發明使用遺傳算法優化地下物流系統中路徑規劃的問題，提供一種基于遺傳算法的地下物流節點間路徑規劃方法。

本發明的目的是通過以下技術方案實現的：1.一種基于遺傳算法的地下物流節點間路徑規劃方法，其特征在于，包括以下步驟：

(1)獲取物流中心o₁和其他物流節點的位置坐標；

(2)按照物流節點與物流中心距離的大小，由近至遠將物流節點進行排序，以此標記為o₂,o₃,o₄,...o_n；n為物流節點的個數；

(3)計算物流節點o_i與o_j之間的距離，記為w_ij；

(4)采用二進制編碼方式，以1表示物流節點o_i與物流中心直接相連，服務于物流節點o_i的路徑d_i＝w_1i；以0表示物流節點o_i不與物流中心直接相連，服務于物流節點o_i的路徑d_i＝min(w_ij),其中j∈(2,3,...i-1)。

利用上述二進制的編碼方式，進行種群初始化，獲得l個個體，對l個個體進行適應度計算，個體適應度的大小分為兩部分，分別為該個體生成路徑總距離的大小以及該個體所具有的抗風險能力，即：

adaptation＝adaptation_distance+adaptation_risk

其中式中m為與物流中心直接相連的節點數量，α為權重系數。

(5)經過遺傳操作，求得適應度最小的個體即為最優的路徑規劃。

本發明的有益效果在于：

(1)針對地下物流系統的特殊性(地下管道鋪設造價較高、維修困難)，本發明在路徑規劃過程中既考慮整體造價最低，又引入抗風險能力權重比，使得地下物流系統建設過程中盡可能降低造價又保障地下物流系統具有一定的抗風險能力，提高了地下物流路徑規劃的合理性；

(2)本發明同時具有良好的可擴展性，如若需要引入其它因素，只需修改適應度adaptation的計算公式，方便靈活；