需求可拆分的容量約束弧路徑問題研究.pdf

1、 需求可拆分的容量約束弧路徑問題研究 需求可拆分的容量約束弧路徑問題研究 Research of Split Delivery Capacitated Arc Routing Problem 學科專業(yè)：運籌學與控制論 研 究 生：李慶華 指導教師：林丹 教授 天津大學理學院 二零一二年五月 i 中 文 摘 要 本文所研究的需求可拆分的容量約束弧路徑問題是一個運籌學領域中的組合優(yōu)化問題。它在現(xiàn)實生活中具有非常廣泛的應用，如：冬季道路

2、撒鹽問題、市政垃圾清理問題、郵件投遞問題等都能抽象為需求可拆分的容量約束弧路徑問題。 通常，車輛運輸成本是具有容量約束的弧路徑問題的總成本的主要組成部分，因此通過優(yōu)化車輛路徑安排可有效地降低成本，同時也能提高服務水平和降低零擔空載率。通常的容量約束弧路徑問題的研究中，都設定了預先條件，即每個客戶的需求(指小于車輛容量的需求)必須由一輛車且必須在一次服務中完成。然而，在滿足服務要求前提下的實際運作中，通過需求的拆分可進一步降低運輸成本，尤

3、其是在需求量較大的情況下?；谏鲜鲈?，選擇需求可拆分的容量約束弧路徑問題作為本文的研究主題。 由于問題本身的復雜性，現(xiàn)有的研究工作均無法在此問題規(guī)模的多項式時間內找到全局最優(yōu)解。構造型啟發(fā)式方法得到的解可作為元啟發(fā)式算法的初始解，從而保證元啟發(fā)式算法的性能優(yōu)于構造型啟發(fā)式方法。因此，本文考慮利用構造型啟發(fā)式算法來對問題進行求解，求出的是問題的初始解。 本文在廣泛深入地查閱國內外文獻的基礎上，通過理論分析、建模、算法求解這一過程對需求可

4、拆分的容量約束弧路徑問題進行了深入研究，研究重點在于如何利用構造型啟發(fā)式算法求解需求可拆分的容量約束弧路徑問題。主要內容如下： 首先， 簡要介紹了容量約束弧路徑問題和需求可拆分的車輛路徑問題的起源和發(fā)展歷史，歸納總結了其求解方法。建立了需求可拆分的容量約束弧路徑問題的整數(shù)規(guī)劃模型，對可行解的基本特性進行了分析，證明了判斷解是否可行的兩個重要判據，并對拆分需求的意義進行了簡單分析。 其次，系統(tǒng)、詳盡的介紹了三種算法的基本理論和方法，在目前