基于兩階段求解的動態車輛路徑問題研究

陳　誠，邱榮祖

(福建農林大學交通與土木工程學院，福建 福州 350002)

?

基于兩階段求解的動態車輛路徑問題研究

陳誠，邱榮祖

(福建農林大學交通與土木工程學院，福建 福州 350002)

[摘要]采用兩階段求解思想，通過設置定時間隔，將動態信息轉化成靜態信息，從而實現對動態車輛路徑問題的求解.分別建立了初始優化和實時優化階段的數學模型，以節約算法解為初始解，利用禁忌搜索算法完成初始優化階段的車輛路徑問題求解；在實時優化階段，分別對節約算法和禁忌搜索算法進行適當修正后再進行求解.利用數值測試實驗對客戶不同地理位置分布下定時間隔的設置進行測試分析.結果表明，該算法簡單明了，易于實現.此外，客戶的地理位置分布不同，對定時間隔的敏感性也不同，混合分布最為敏感，其次是隨機分布，集聚分布最不敏感；最后，給出了相應的累計服務客戶數量曲線，并結合車輛總行駛距離，明確了不同客戶位置分布下的較優定時間隔設置.

[關鍵詞]動態車輛問題；兩階段求解；定時間隔；禁忌搜索

0引言

車輛路徑問題(vehicle routing problem，VRP)自1959年Dantzig和Ramser提出后[1]，成為了國內外眾多學者研究的熱點.在過去幾十年中，對該問題的研究取得了豐富的研究成果.然而在這些研究成果中，大多是在靜態的環境下進行的，即靜態VRP(Vehicle Routing Problem)，但這與現實環境動態變化的特點不相符.因此，為了更好地解決實際問題，有必要對動態VRP進行研究.

對動態車輛路徑問題研究，最……