多庫車輛路徑問題的混合遺傳算法

摘要
成品從倉庫到客戶的配送是物流管理的現(xiàn)實而具有挑戰(zhàn)的問題。良好的路徑選擇和調(diào)度安排能提高客戶滿意度，因為更多的客戶能再更短的時間獲得服務(wù)。配送問題一般可闡述為車輛路徑問題（VRP）。然而，有一個一個假設(shè)——只能有一個倉庫（Depot）?，F(xiàn)實中如一個物流公司不止有一個倉庫，VPR就不適用了。為解決這一局限，本論文將研究多倉庫的車輛路徑問題（MDVRP）。這種方法很難，這就意味著沒有有效的算法來尋優(yōu)。為解決這個問題，本論文將闡述兩種遺傳算法（HGA）。兩種算法的主要不同是算法1的初始解是隨機(jī)的。算法2的初始步驟融合了Clark和Wright的節(jié)能方法和最近鄰啟發(fā)式算法。我們進(jìn)行了大量的計算研究來對比不同規(guī)模問題的算法，證明現(xiàn)代配送中HGA2優(yōu)于HGA1。
關(guān)鍵詞：物流，配送管理，車輛路徑問題（VRP），多庫（MD），混合遺傳算法（HGA）

1.介紹
車輛路徑問題（VRP）之所以被廣泛研究是因為它被發(fā)現(xiàn)廣泛適用于許多現(xiàn)實世界的情況，包括物流配送問題。描述VRP很容易，但求解很難。如一個公司有一個確定位置和無限容量的倉庫以及知道需求和位置的客戶（Customer）群。一般來講，客戶的總需求超過車輛容量，因此就需要不只一輛車把產(chǎn)品從倉庫運輸?shù)娇蛻羰种?。在VRP中，每輛車為一條路徑，每輛車或每條路徑只為一個客戶服務(wù)。路徑的起點和終點都是倉庫。公司的決策者要決定那條路為那個客戶服務(wù)，這就是路徑問題。當(dāng)然也需要首先考慮那個客戶應(yīng)該第一個服務(wù)，其次是路徑，這就是調(diào)度問題。VRP的目標(biāo)是為所有客戶服務(wù)耗費的時間和路程。毫無疑問，良好的路徑和調(diào)度可以提高客戶滿意度因為更多的客服可以在更短時間接受服務(wù)。VRP與著名的旅行商問題（TSP）類似，不同的是旅行商問題中使用的車輛沒有容量限制，可通過單一路徑服務(wù)客戶。換句話說，TSP只考慮調(diào)度問題，因此比考慮調(diào)度與路徑的VRP簡單。