帶時(shí)間窗車輛路徑問題的精確算法研究

帶時(shí)間窗車輛路徑問題的精確算法研究帶時(shí)間窗的車輛路徑問題(VehicleRoutingProblemwithTimeWindows,VRPTW)是經(jīng)典的組合優(yōu)化問題,也是目前應(yīng)用最廣泛的運(yùn)輸問題之一。本文從理論基礎(chǔ)做起,立足于精確算法,對(duì)VRPTW的整數(shù)線性規(guī)劃領(lǐng)域進(jìn)行了較為全面的理論研究,并初步涉獵了約束規(guī)劃領(lǐng)域。在算法上,本文選擇使用當(dāng)前主流的列生成算法,其中子問題是帶資源約束的最短路徑問題(ElementaryShortestPathProblemwithResourceConstraints,ESPPRC)。在運(yùn)用列生成算法求解VRPTW時(shí),子問題難以快速求解是一直困擾我們的主要問題,所以我們圍繞子問題進(jìn)行了深入研究,發(fā)現(xiàn)對(duì)它的研究大多都是運(yùn)用動(dòng)態(tài)規(guī)劃的思路求解。近幾年來有少數(shù)外國學(xué)者開始對(duì)ESPPRC的整數(shù)線性規(guī)劃模型進(jìn)行研究,但成果并不顯著,所以我們選擇ESPPRC的整數(shù)線性規(guī)劃領(lǐng)域作為主要研究的對(duì)象,試圖有所突破。本文主要的研究成果和創(chuàng)新點(diǎn)如下:(1)研究了ESPPRC的多胞形(polytope)結(jié)構(gòu)并證明出一個(gè)小平面定義(facet-defining)的不等式。在組合優(yōu)化領(lǐng)域,多面體結(jié)構(gòu)的研究主要集中在旅行商問題和帶容量約束的車輛路徑問題上,在上世紀(jì)末由老一輩的學(xué)者們攻克。國內(nèi)外對(duì)ESPPRC的多面體結(jié)構(gòu)研究非常少,學(xué)者們更加熱衷于用動(dòng)態(tài)規(guī)劃的方法進(jìn)行求解,或者將旅行商問題中經(jīng)典的不等式加以演變應(yīng)用在ESPPRC中。我們運(yùn)用多面體理論,對(duì)ESPPRC的多胞形(polytope)結(jié)構(gòu)進(jìn)行了研究與證明,找到了一個(gè)小平面定義(facet-defining)的不等式。(2)針對(duì)ESPPRC提出了三組有效不等式。通過對(duì)動(dòng)態(tài)規(guī)劃和約束規(guī)劃相關(guān)理論的借鑒,本文對(duì)ESPPRC提出了適用于整數(shù)線性規(guī)劃的統(tǒng)治規(guī)則。研究了ESPPRC的多面體結(jié)構(gòu),并發(fā)現(xiàn)了一組符合小平面定義(facet-defining)的不等式。接著,基于以上的理論,創(chuàng)新性地提出了三種有效不等式,并給出了證明。最后用Solomon基準(zhǔn)測(cè)試包的修改版測(cè)試了這三個(gè)模型的性能,效果顯著。(3)將二維車流的數(shù)學(xué)模型應(yīng)用在VRPTW中。我們將CVRP(CapacitatedVehicleRoutingProblem)中的二維車流模型擴(kuò)展至VRPTW中,用它來替代列生成算法中的分支-切割過程,為解決VRPTW提供了一種新思路。同時(shí)對(duì)最