[發明專利]求解帶硬時間窗時變關聯物流運輸車輛路徑問題的方法

有效

• 申請號: 201410289898.9
• 申請日: 2014-06-26
• 公開（公告）號: CN104036379B
• 公開（公告）日: 2019-06-25
• 發明（設計）人: 蔡延光;郭帥;蔡顥
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 廣州市南鋒專利事務所有限公司 44228
• 代理人: 劉媖

本發明公開了一種求解帶硬時間窗時變關聯物流運輸車輛路徑問題的方法，它包括以下兩個步驟，1）建立具有硬時間窗約束的時變關聯物流運輸車輛路徑問題的數學模型；2）設計一種免疫蟻群混沌禁忌搜索算法對問題進行求解。本發明的有益效果為：更準確的反映物流運輸車輛路徑問題中的實際情況，使基于此制定的調度方案更加可靠；以車輛行駛距離最短為優化目標，可以更好的滿足對于硬時間窗的適應。引入免疫蟻群混沌禁忌搜索算法，使算法具有更好的全局和局部尋優能力，使算法在解決大規模問題時具有更高的效率。

技術領域

本發明屬于物流路徑規劃控制領域，尤其涉及一種求解帶硬時間窗時變關聯物流運輸車輛路徑問題的方法。

背景技術

配送是物流系統的核心環節，是伴隨著市場而誕生的一種必然的市場行為，隨著市場競爭的日益激烈以及客戶要求的不斷提高，配送在未來的市場競爭中將起到舉足輕重的作用。在配送業務中，配送車輛優化調度問題的涉及面較廣，需要考慮的因素也很多，對配送企業提高服務質量、降低經營成本、增加經濟效益的影響也很大。

國內外學者著力于研究車輛路徑問題，主要因為它是物流配送和交通運輸的核心問題，只有解決了調度問題才能使配送有效合理。

現有的車輛路徑問題具有以下問題：所有車輛貨物的裝載沒有考慮貨物之間的關聯約束。

因此，現有的物流配送方法存在缺陷，需要改進。

帶硬時間窗時變關聯物流運輸車輛路徑問題基于上述的問題建立了時變速度情況下具有貨物關聯約束的車輛路徑問題的數學模型。

近幾年，雖然一些學者在研究車輛路徑問題中用到了精確算法，但是啟發式算法能在可行的時間復雜度之內優化該問題十分具有優勢，大多數學者還是著力研究啟發式算法來解決車輛路徑問題。總的來說，帶硬時間窗時變關聯物流運輸車輛路徑問題具有多重約束，因而比普通車輛問題難。在這里我們對禁忌搜索算法進行一定的改進，提出一種新的混合算法，用其求解具有多重約束的物流運輸車輛路徑問題。

發明內容

本發明針對上述問題的不足，公開了一種求解帶硬時間窗時變關聯物流運輸車輛路徑問題的方法，本發明的目的在于建立一種具有多重約束，更能反映物流運輸車輛路徑問題實際情況的數學模型，并提出響應的求解算法進行求解。

本發明的帶硬時間窗時變關聯物流運輸車輛路徑問題方法包含兩部分內容：(1)建立了帶硬時間窗時變關聯物流運輸車輛路徑問題的模型，該模型以車輛行駛路徑最短我目標函數，在約束條件中除了考慮載重，距離，時間窗還加入了時變約束，貨物性質關聯約束。針對禁忌搜索算法嚴重依賴初始解，鄰域解的缺陷提出了免疫蟻群混沌禁忌搜索算法，對建立的模型進行求解。

一種求解帶硬時間窗時變關聯物流運輸車輛路徑問題的方法，其特征在于，它包括以下步驟：

步驟1)，建立具有硬時間窗約束的時變關聯物流運輸車輛路徑問題的數學模型，具體步驟如下：