需求可拆分的容量約束弧路徑問(wèn)題研究.pdf

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

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

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

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