本書在簡要闡述旅行商問題、車輛路徑問題的基礎上,介紹了復雜約束車輛路徑問題及其研究現狀,并補充了實際物流企業涉及的多種新型約束,完善了實際物流優化調度中的各類約束條件。針對復雜約束車輛路徑問題,作者基于蟻群優化算法及各組成環節的核心思想,針對多個核心步驟改進了算法,并且結合相關的算法研究,建立了一個針對實際物流調度問題的統一應用框架,該應用框架較好地優化了實際物流企業調度。最后,筆者結合蟻群優化算法和強化學習算法的優點,并針對它們的缺點和痛點,根據市場經濟自動優化資源配置的機制及反壟斷、風險投資機制,開創性地設計和建立了市場經濟優化算法。
本書可作為從事智能優化算法及其應用研究,特別是組合優化問題研究的相關科技工作者、專業技術人員的參考書,也可作為計算機、運籌學等專業本科生及研究生的參考書。
隨著電子商務、快遞、外賣、生產供應鏈等業務的迅猛發展,物流作為基礎行業也得到了快速發展,伴隨而來的是物流成本及規模的日漸擴大,于是物流成本優化問題亟待系統性地解決。
一方面,作為物流行業核心的車輛路徑問題(VRP),其主要目標是尋找一個成本最優路徑。車輛路徑問題屬于組合優化問題,求解的難度隨著規模的增大而急劇加大,稱之為“組合爆炸”。另外,隨著物流行業的發展,除了基本的車輛容量約束外,其他如異構車型、時間窗約束、甩掛運輸、多倉庫配送等新型的物流約束條件層出不窮,稱之為復雜約束車輛路徑問題(Rich VRP)。規模和約束的疊加使得復雜約束車輛路徑問題的求解更為困難,更具有挑戰性。
另一方面,隨著計算機技術尤其是以5G通信為代表的通信技術及物聯網技術的發展,物流、信息流、資金流中數據的收集、傳輸和處理的規模和速度也在不斷增大,因此對物流運輸優化提出了更高的效率需求。在物流運輸過程中經常會出現各類突發事件,例如道路交通事故形成的交通阻塞,運輸車輛發生事故或故障拋錨,以及客戶現實情況的快速變化導致的加單、減單、取消、變更、延誤等,這些意料之外的動態變化疊加近乎實時的數據信息收集及處理反饋要求,對解決復雜約束車輛路徑問題算法提出了更高的要求。
筆者擁有25年以上的IT行業經驗,長期在IT行業頭部企業及500強外企工作,有著豐富的軟件設計、開發和實踐經驗,且長期關注在蟻群優化算法及在復雜約束車輛路徑問題方面的應用研究,筆者的研究均結合一些中大型物流企業的實際物流調度業務需求,并取得了20%~50%的實際優化效果。
在結合蟻群優化算法和強化學習算法的基礎上,特別是針對蟻群優化算法的不足,筆者獨自設計和實現了市場經濟優化算法,并進行其在復雜約束車輛路徑問題上的應用研究。市場經濟優化算法的設計思想可有效解決易陷入局部最優和探索與利用困境的問題,其核心方法也適用于改進其他元啟發式算法或強化學習算法。
學術研究只解決了核心問題解決方案的有無問題,實際應用研究還需要具備深厚的算法設計能力,以解決后續多個實際應用中的困難,這樣才能將解決方案落地成為一個完整的可行性方案。
本書內容包括從學術層面介紹旅行商問題、車輛路徑問題和復雜約束車輛路徑問題,并綜述了目前解決相應問題的各類算法,著重闡述了蟻群優化算法;最后針對復雜約束車輛路徑問題,并結合實際物流企業的需求、實現及效果進一步展示了相關研究的實用價值。
本書結合筆者的IT企業經歷及研究成果,綜合學術研究和實際應用,具有較高的學術研究和實踐參考價值,適合組合優化研究方向及實際物流優化的研究者參考。
著者
202302
第1章 緒論
1.1 物流行業背景及現狀 /1
1.2 解決車輛路徑問題的意義 /4
1.3 基本的旅行商問題和車輛路徑問題 /5
1.3.1 旅行商問題(TSP) /5
1.3.2 車輛路徑問題(VRP) /7
小結 /9
第2章 復雜約束車輛路徑問題(Rich VRP)
2.1 復雜約束車輛路徑問題(Rich VRP)的具體內容 /10
2.2 復雜約束車輛路徑問題(Rich VRP)在實踐中的新增約束 /15
2.3 其他車輛路徑問題的研究現狀 /19
2.4 車輛路徑問題關聯裝載問題概述 /20
小結 /23
第3章 復雜約束車輛路徑問題的算法現狀
3.1 解決Rich VRP的算法研究概述 /24
3.2 解決Rich VRP的精確算法 /25
3.3 解決Rich VRP的近似算法 /28
3.4 解決Rich VRP的元啟發式算法 /30
3.5 解決Rich VRP的機器學習算法 /36
3.6 解決Rich VRP的強化學習算法 /40
3.7 單智能體強化學習與多智能體強化學習 /41
3.8 主流強化學習與組合優化問題 /42
3.9 各類算法的比較 /43
小結 /47
第4章 蟻群優化算法及其改進研究
4.1 蟻群優化算法(ACO)原理 /48
4.2 選擇蟻群優化算法(ACO)的原因 /50
4.3 蟻群優化算法(ACO)研究現狀 /52
4.4 蟻群優化算法在Rich VRP的研究現狀 /56
4.5 蟻群優化算法與強化學習算法的結合 /58
小結 /61
第5章 Levy ACO算法
5.1 萊維分布和萊維飛行模式概述 /62
5.2 Levy ACO的算法設計 /66
5.3 實驗環境說明 /69
5.4 實驗結果及其分析 /73
5.5 Levy ACO與其他最新算法的比較 /80
5.5.1 Levy ACO與ACO相關最新算法的比較 /80
5.5.2 Levy ACO與非ACO最新算法的比較 /83
小結 /84
第6章 Greedy Levy ACO算法
6.1 Epsilon Greedy機制 /85
6.2 Greedy Levy ACO的算法設計 /87
6.3 實驗環境說明 /88
6.4 實驗結果及其分析 /89
6.5 Greedy Levy ACO與其他最新算法的比較 /96
6.5.1 Greedy Levy ACO與ACO相關最新算法的比較 /96
6.5.2 Greedy Levy ACO與非ACO最新算法的比較 /99
小結 /100
第7章 Contributionbased ACO算法
7.1 強化學習算法中的獎勵機制 /101
7.2 管理學激勵理論概述 /102
7.3 經典ACO算法中的信息素更新邏輯 /103
7.4 Contributionbased ACO的算法設計 /104
7.5 實驗環境說明 /106
7.6 實驗結果及其分析 /106
7.7 ACO改進算法的比較、關系和作用 /112
小結 /116
第8章 Rich VRP分析及統一應用框架的建模
8.1 Rich VRP統一應用框架分析 /118
8.1.1 車型的定義及意義 /118
8.1.2 Rich VRP約束分析 /119
8.1.3 多車型車隊概念 /121
8.1.4 多車型及多信息素 /122
8.1.5 多信息素下的ACO信息素邏輯 /124
8.1.6 信息素更新改進策略 /124
8.1.7 與車型無關約束的實現 /126
8.2 Rich VRP統一應用框架的ACO算法邏輯 /128
8.2.1 車輛選擇邏輯 /128
8.2.2 候選節點選擇邏輯 /129
8.3 Rich VRP統一應用框架性能提升的設計 /130
8.4 Rich VRP統一應用框架系統的實現條件 /131
8.4.1 開發語言的選擇 /131
8.4.2 基礎開發庫的選擇 /132
8.4.3 數據庫中間件的選擇 /132
8.4.4 電子地圖的選擇 /133
8.4.5 GPU或CPU等并行機制的選擇 /133
8.5 Rich VRP統一應用框架實驗結果 /135
小結 /138
第9章 Rich VRP的實際應用及效果分析
9.1 Rich VRP的應用背景 /139
9.2 Rich VRP的應用環境 /140
9.2.1 Rich VRP中的節點信息和訂單信息 /141
9.2.2 Rich VRP中的路網信息 /141
9.2.3 Rich VRP中的車輛信息 /142
9.2.4 Rich VRP中的節點、路網、車輛、訂單信息的關系 /143
9.3 Rich VRP應用實例 /143
9.3.1 某銀行ATM機清機運鈔車線路優化項目 /144
9.3.2 某汽車生產供應鏈優化項目 /146
9.3.3 某冷鏈互聯網服務平臺運輸優化項目 /149
9.3.4 某倉儲服務企業攬貨線路優化項目 /150
9.3.5 某倉儲服務企業倉庫揀選運輸優化項目 /153
小結 /155
第10章 市場經濟優化算法(MEO-Q)
10.1 組合優化問題中的難點 /158
10.2 Qlearning算法及AntQ算法 /158
10.2.1 Qlearning算法 /158
10.2.2 AntQ算法及其與QLearning算法的比較 /160
10.2.3 現有算法的不足和市場經濟優化算法的改進措施 /162
10.3 市場經濟理論對于組合優化問題的意義 /163
10.4 市場經濟優化算法的主要內容 /164
10.4.1 市場經濟優化算法中的價格機制及成本利潤模式 /165
10.4.2 市場經濟優化算法中的反壟斷機制 /167
10.4.3 市場經濟優化算法中的風險投資機制 /170
10.4.4 市場經濟優化算法中的總體算法結構 /171
10.4.5 市場經濟優化算法中的其他設計 /173
10.5 市場經濟優化算法的實驗設置 /173
10.6 市場經濟優化算法的實驗結果 /173
10.6.1 市場經濟優化算法實驗總體結果 /173
10.6.2 市場經濟優化算法實驗中具體數據集的詳細結果 /176
10.6.3 市場經濟優化算法實驗與最新強化學習算法性能的對比 /185
10.7 市場經濟優化算法的后續研究 /186
10.7.1
市場經濟優化算法后續改進之一——融合LKH算法 /186
10.7.2 市場經濟優化算法后續改進之二——解的重復性過濾 /186
10.7.3
將市場經濟優化算法應用于Rich VRP統一應用框架 /187
小結 /187
附錄 英文縮寫說明 /188
參考文獻 /190