[發明專利]一種調度方法

在審

• 申請號: 202110463378.5
• 申請日: 2021-04-23
• 公開（公告）號: CN113177757A
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 李進;余建成
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q10/06;G06K9/62;G06N3/00
• 代理公司: 杭州裕陽聯合專利代理有限公司 33289
• 代理人: 田金霞

本發明披露了物流配送領域的一種調度方法，以任務節點總行駛距離、最小二氧化碳排放量、客戶滿意度實現目標；以聚類算法，獲取若干任務節點聚類；以任務節點聚類作為初始染色體，確定目標函數評價群體，利用適應度函數選擇最佳的染色體，根據遺傳算法生成的若干組優化解，確定信息素初始分布情況，利用優化蟻群算法求解運輸裝置物流配送調度數據，直到達到最大循環次數或算法收斂時停止運算，輸出最優路徑及其長度。本發明融合聚類客戶區域劃分和遺傳蟻群優化算法，提高了物流運輸裝置調度的全局尋優能力，使得區域劃分得到物流運輸裝置調度安排能夠最大限度的減少車輛二氧化碳的排放量，并大幅度降低物流運輸成本。

技術領域

本發明涉及一種調度技術，尤其涉及融合融合K-means聚類客戶區域劃分、遺傳算法與蟻群算法的物流運輸調度方法。

背景技術

物流和交通運輸領域一個重要的問題是車輛調度問題(Vehicle SchedulingProblem，簡稱VSP)。其中，如何減少二氧化碳排放是產業界和學術界關注的主要問題之一。環境友好型物流運輸調度問題(Environmental-friendly Logistics TransportationScheduling Problem，簡稱ELTSP)是車輛調度問題的擴展。該問題對保護環境，減少有害氣體的排放起到至關重要的作用。

在物流運輸技術中，大多數企業忽視了二氧化碳的排放及其對環境的影響。最近，許多公司和企業開始采用不同的技術來減少二氧化碳的排放量。距離是減少二氧化碳的主要因素之一，二氧化碳與汽車行駛的距離成正比。物流調度問題是交通運輸和供應鏈管理系統中的主要問題之一，物流調度問題本質上是一個組合優化中的整數規劃問題。其問題是，從配送中心倉庫運送貨物給客戶，目標是使總行駛距離最小化。在環境友好型物流運輸調度問題中，還將考慮二氧化碳排放的最小化。

遺傳算法(Genetic Algorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會陷入局部最優解的快速下降陷阱；并且利用它的內在并行性，可以方便地進行分布式計算，加快求解速度。但是遺傳算法的局部搜索能力較差，導致單純的遺傳算法比較費時，在進化后期搜索效率較低。

蟻群算法(Ant Colony Optimization)是由意大利學者Maniezzo團隊受螞蟻合作覓食行為的啟發提出的計算模型，是一種尋找優化路徑的啟發式隨機搜索算法。蟻群算法在搜索過程保持較高的獨立性，信息通信通過信息素不斷的積累，從而構成一個正反饋機制；并且在問題空間多點同時進行獨立解搜索操作，使整套算法在保持良好全局搜索能力的同時有高穩健性和并行性，易于與其他算法相結合。但是傳統的蟻群算法在路徑搜索時會出現收斂速度慢、易陷入局部最優、路徑過長等問題。

發明內容

本發明針對現有技術中的缺點，提供了一種融合了K-means聚類客戶區域劃分、遺傳算法與蟻群算法的運輸裝置調度技術，用于物流配送系統與貨運系統中減少汽車尾氣排放和提高物流運輸調度規劃。

為了解決上述技術問題，本發明通過下述技術方案得以解決：

一種調度方法，包括以下步驟：

以所有啟用運輸裝置的任務節點總行駛距離為目標一；以二氧化碳排放量為目標二；以滿足時間窗口的滿意度為目標三；

以聚類算法，根據任務節點坐標，獲取若干任務節點聚類；

以任務節點聚類組合作為初始染色體確定目標函數評價群體，利用以所述目標一、目標二、目標三為目標函數值的適應度函數選擇最佳的染色體，生成若干配送調度方案；

以所述配送調度方案確定信息素初始分布，執行蟻群算法；以局部信息素大小變化調整信息素計算方法，獲取優化蟻群算法；