基本信息
學位級別
博士論文
學位授予單位
華中科技大學
學位授予時間
2007
關鍵字
物流 物資運輸 車輛調度 車輛路徑 遺傳算法
館藏號
F253.4
館藏目錄
2009\F253.4\4
中文摘要
隨著經濟全球化和信息化進程的不斷加快，物流作為具有廣闊前景和增值功能的新興服務業，正在全球範圍內迅速發展，它對於提高國家經濟運行質量和效益、最佳化資源配置、增強企業競爭力和促進企業生產力的發展具有重要意義。運輸服務是物流組成中的重要環節，降低運輸成本、提高運輸質量和效率成為加快物流發展的有效途徑。 車輛路徑問題是運輸服務最佳化中的核心問題，它通過對貨物的運輸線路進行最佳化，在滿足客戶需求的前提下，儘量以最低的運輸成本將貨物送達目的地。在過去幾十年間，車輛路徑問題得到了廣泛的關注和研究，並取得了豐富的研究成果。本文首先對這類問題的構成、分類以及求解算法的研究現狀等進行了歸納和概括。 最小-最大車輛路徑問題，是與一般車輛路徑問題目標不同的一類問題，它要求在整個行車線路中，行程最長的線路行駛距離最短。本文根據這類問題的特點，採用遺傳算法和禁忌搜尋算法進行了求解。並在禁忌搜尋算法中，針對最長的線路生成鄰域，將該算法用於標準算例的求解，得到了較好的結果。 在實際的線路計畫和執行過程中，往往會出現新的客戶請求或客戶信息的變化，這時要求系統能快速回響這種信息更新，並重新制定線路計畫。這類問題稱為動態車輛路徑問題。對於基本的動態車輛路徑問題，本文研究了相應的處理策略，分析了系統的基本組成，將整個動態問題轉換為一系列的靜態子問題，對子問題採用禁忌搜尋算法進行求解。以整個線路的行駛距離作為目標，採用該算法對9個標準算例進行了測試，與文獻中其他算法的計算結果相比較，有3個問題得到了最好解，7個問題得到了最好平均解。 由於交通管制和客戶營業時間等實際約束，某些客戶只能在某些時間段接受車輛為其提供的服務，即客戶有時間窗限制，本文在帶時間窗的動態車輛路徑問題中，分析了三種線路間局部搜尋方法：重定位法，節點交換法和2-opt*法，以及兩種線路內局部搜尋方法：2-opt法和Or-opt法，並將這些方法的不同組合套用於靜態子問題初始解的改進。通過對標準算例的求解結果進行分析和比較得出：線上路間進行局部搜尋時，重定位法的效果最好，2-opt*法次之，節點交換法的最差；線上路內進行局部搜尋時，2-opt法優於Or-opt法。同時，也分析了客戶出現時間的早晚，客戶地理位置的分布以及不同的客戶時間窗範圍對結果線路中使用的車輛數量，整個線路的行駛距離和客戶延遲時間的影響。 在帶時間窗的動態收取和運送問題中，要求從某一客戶的收取點提取貨物，送到其相應的運送點。因此要求同一客戶的收取點和運送點必須由同一台車輛來執行服務，且必須在訪問運送點之前先訪問提取點。本文在描述該問題特點的基礎上，採用了啟發式方法對該問題進行求解，並對基本算例進行了測試。
