隨機時變網路環境下的物流配送路徑最佳化問題研究

《隨機時變網路環境下的物流配送路徑最佳化問題研究》是依託同濟大學，由段征宇擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：隨機時變網路環境下的物流配送路徑最佳化問題研究
• 項目類別：青年科學基金項目
• 項目負責人：段征宇
• 依託單位：同濟大學

中文摘要

車輛路徑問題（Vehicle Routing Problem, VRP）是物流配送的核心問題，國內外學者已經展開了大量研究工作。以往的研究大多假設路網的行程時間是常數或按某一確定型函式變化。但對於實際路網，由於受到交通流量、突發事故、天氣等因素的影響，行程時間往往經常發生變化，具有一定的隨機性。本課題研究隨機時變路網環境下，如何安排車輛的配送線路和時刻表，在保證一定配送服務水平的基礎上，使得綜合配送成本達到最優。主要內容包括：以海量的實際交通數據為基礎，研究隨機時變路網的行程時間分布特性和預測方法；建立基於可靠度的車輛路徑問題的數學模型；面向大規模實際路網，研究車輛配送路徑的最佳化算法；以及針對突發交通事件的配送路徑動態調整策略和方法。本研究考慮了路網交通狀況的時變特徵和隨機性，更加符合物流配送的實際情況，對於降低配送成本，提高配送服務水平和客戶滿意度具有重意義。

結題摘要

本課題圍繞隨機時變路網環境下的配送車輛路徑問題展開研究，主要完成了5部分工作：隨機時變網路的行程時間特徵、隨機時變網路建模、隨機時變網路的最優路徑問題、隨機時變網路的車輛路徑問題以及模型和算法的軟體實現。首先，基於線圈數據、浮動車數據和車牌照數據等實際交通數據，分析了網路交通狀態的可預測性；從機率分布、統計指標、時間序列特徵等角度分析了路逕行程時間的可靠性；針對行程時間波動率的尖峰厚尾特徵，通過ARCH模型分析了路逕行程時間的波動性。接著，以行程車速的時間依賴函式為基礎對隨機時變路網進行建模，並通過實際浮動車數據，對路網進行標定。接下來，針對傳統基於行程時間隨機分布建模方法的計算時間複雜度高，只能求解小規模網路的不足，基於魯棒最佳化方法，分別採用3種魯棒最佳化準則，對隨機時變路網的最優路徑問題進行建模；證明了在路網滿足“先入先出”特性的條件下，可以將原問題轉換為確定型時變路網的行程時間最短路徑問題；設計了改進Dijkstra算法；通過測試算例和實際算例證明了算法具有較高的效率。然後，對於確定型時變路網的車輛路徑問題，提出了一種出發時刻最佳化的路徑構造算法；將魯棒最佳化方法引入隨機時變路網的車輛路徑問題的建模，並將其轉換為確定型時變路網的車輛路徑問題；設計了路徑構造算法和蟻群算法；通過測試算例和實際算例證明了算法的有效性，即使對於1000個客戶節點的大規模問題，算法仍具有較高的計算效率。最後，從計算效率角度出發，進行了上述模型和算法的電腦程式設計，並採用組件化方式開發了軟體。