[發明專利]一種大規模節點的物流配送路徑優化方法及系統

在審

• 申請號: 202011301884.6
• 申請日: 2020-11-19
• 公開（公告）號: CN112232602A
• 公開（公告）日: 2021-01-15
• 發明（設計）人: 鄒娟;周金龍;陳天;鄭金華;楊圣祥
• 申請（專利權）人: 湘潭大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 北京化育知識產權代理有限公司 11833
• 代理人: 涂琪順

本發明涉及一種大規模節點的物流配送路徑優化方法及系統。該方法包括：根據運送節點和各運送節點之間的運輸成本生成初始種群，種群中每個個體代表隨機產生的一條路徑；確定成本最小的目標優化函數；采用差分分組方法對運送節點進行相關性分組；保持其他節點不變，對每一組節點進行協同優化，得到多個路徑；計算各路徑的適應度函數值，適應度函數為目標優化函數；判斷當前評價次數是否大于最大評價次數；若是，則輸出最終適應度最小的路徑，即成本最小的物流配送路徑方案，若否，則重新確定路徑。本發明能夠解決采用人為劃分節點區域的隨機性、不確定性，容易陷入局部最優解，無法最大程度減少運輸成本的問題。

技術領域

本發明涉及物流配送路徑優化領域，特別是涉及一種大規模節點的物流配送路徑優化方法及系統。

背景技術

物流配送路徑優化的目標是在有限時間內能找出一條最佳路徑，使得路徑能經過所有必經物流節點且代價總和最小。雖然路徑優化問題研究廣泛，但是大規模節點的路徑優化卻尚未得到較好地解決。因為隨著路徑節點的增加，獲得全局最優解需要搜索的組合數呈指數級上升，傳統的優化方法易陷入局部最優解。目前，處理大規模節點的路徑優化常用的方法是把大規模的節點根據它們的聚集距離，人為將節點劃分為若干區域，分別對每一個小規模區域單獨用Djkstra或蟻群算法等進行優化，因為人為劃分節點的不確定性，這樣得到的優化路徑往往是局部最優的。

發明內容

本發明的目的是提供一種大規模節點的物流配送路徑優化方法及系統，以解決采用人為劃分節點區域的隨機性、不確定性，容易陷入局部最優解，無法最大程度減少運輸成本的問題。

為實現上述目的，本發明提供了如下方案：

一種大規模節點的物流配送路徑優化方法，包括：

構建節點關系網，所述節點關系網包括：物流配送路徑的所有運送節點以及所述運送節點兩兩之間的運輸成本；

根據所述運送節點和各所述運送節點之間的運輸成本生成初始種群，所述種群中每個個體代表隨機產生的一條路徑；

確定成本最小的目標優化函數；

采用差分分組方法對所述運送節點進行相關性分組；

保持其他節點不變，對每一組節點進行協同優化，得到多個路徑；

計算各所述路徑的適應度函數值，所述適應度函數為目標優化函數；

判斷當前評價次數是否大于最大評價次數；

若是，則輸出最終適應度最小的路徑，即成本最小的物流配送路徑方案，

若否，則“保持其他節點不變，對每一組節點進行協同優化，得到多個路徑”。

可選地，所述運輸成本包括人工成本、燃油成本、維護成本以及管理成本。

可選地，所述根據所述運送節點和各所述運送節點之間的運輸成本生成初始種群，具體包括：

根據所述運送節點和各所述運送節點之間的運輸成本，采用大規模協同進化算法生成初始種群，所述種群中包含N個個體，每個所述個體有n個決策變量，每個所述個體代表一條經過所有運送節點的路徑，每個所述個體均采用自然編碼。

可選地，所述適應度函數值的計算公式為：

其中Dist為任意兩個決策變量之間的距離，即任意兩個運送節點之間的運輸成本，n是決策變量個數，即節點個數，w_j代表任意一個節點j，其中1≤j≤n。

可選地，所述保持其他節點不變，對每一組節點進行協同優化，得到多個路徑，具體包括：