三維裝載約束的車輛路徑問題的模擬退火算法論文說明

　　傳統(tǒng)的車輛路徑問題只考慮物品裝載的質(zhì)量屬性約束，而忽略其他裝載屬性約束。針對這種情況，研究了三維裝載約束的車輛路徑問題，提出了三維裝載的處理算法，基于模擬退火算法設(shè)計了一種兩階段啟發(fā)式算法進行求解： 第 1 階段通過啟發(fā)式算法得到初始解; 第 2 階段通過模擬退火算法對初始解進行改進，構(gòu)造了測試集對結(jié)果進行驗證。實驗結(jié)果顯示該算法是能夠有效的求解該問題。

　　車輛路徑問題（ Vehicle routing problem，VRP） 在 1959 年被 Dantzig 等首次提出，至今已擴展出多種不同類型的問題，這些擴展問題包括很多： 帶時間窗的車輛路徑問題、開放車輛路徑問題、不確定車輛路徑問題等等。但是這些擴展問題在考慮車輛裝載只關(guān)注物品質(zhì)量屬性約束，而很少考慮其他物品裝載屬性約束。本文研究的問題為考慮物品長度、高度和寬度的三維裝載約束的車輛路徑問 題 （ Three-Dimension Loading Capacitated Vehicle Routing Problem，3L-CVRP） 。該問題中，每一個物品在裝載時，除了質(zhì)量屬性外，還要考慮體積、裝載順序、物體耐壓與否、最小支持面等其他裝載屬性。

　　3L-CVRP 是 三 維 裝 載 問 題 （ Three-dimensional Loading Problem，3L-LP） 和 VRP 問題的結(jié)合。對于 3L-LP 有很多研究成果，如 Bortfeldt 等和 Pisinger 等，但是 3L-CVRP 的研究還是空白。本文基于啟發(fā)式 算 法 和 模 擬 退 火 算 法 （ Simulated Annealing， SA） 建立兩階段啟發(fā)式算法對 3L-CVRP 問題進行了求解，并通過實驗結(jié)果對算法的性能進行了分析。