【摘要】： 本文以現(xiàn)代物流業(yè)中港口集裝箱的裝卸調(diào)度作業(yè)問題為背景,通過抽象和簡化將其等價(jià)轉(zhuǎn)化為平行機(jī)排序理論中的最早完工時(shí)間問題,提出了三種近似算法并分析了各近似算法的時(shí)間復(fù)雜性以及各自的適用條件,對近似算法性能的分析主要采用了學(xué)術(shù)界常見的最差情形下的“競爭比分析”來衡量各近似算法所求得的近似解和最優(yōu)解之間的關(guān)系,本文的主要研究成果及貢獻(xiàn)如下： 1,針對可組合型集裝箱裝卸調(diào)度問題提出了近似算法APA,并證明了近似算法APA的競爭比為4／3-1／3K(K≥2),其時(shí)間復(fù)雜性為O(n3+nlogn),該算法的局限性在于當(dāng)K≥t+1時(shí)顯然可以通過拆分的方法對近似解作進(jìn)一步的優(yōu)化。 2,在近似算法APA的基礎(chǔ)上,通過拆分優(yōu)化的方法提出了近似算法APB,其時(shí)間復(fù)雜性為O(n3+nlogn+K),并證明了在任一情況下近似算法APB的解均不差于近似算法APA的解,即CmaxAPB≤CmaxAPA；特別地當(dāng)K≥t+1時(shí),近似算法APB能夠?qū)⒔飧倪M(jìn)至CmaxAPB≤CmaxAPA,且二者近似解的比值下界K／2K-1(K≥2)隨著車輛數(shù)K的增大而減�。蝗欢捎趯θ我獾腒≥2在最差情形下近似算法APB無法作進(jìn)一步的優(yōu)化改進(jìn),因而對任意的K≥2近似算法APB的競爭比為4／3-1／3K(K≥2)。 3,針對一類特殊情形分析了近似算法APB對競爭比的具體改進(jìn),即τ≥1且K≥5時(shí),近似算法APB有效地將競爭比改進(jìn)至 4,針對可拆分型集裝箱調(diào)度問題將其轉(zhuǎn)化為Pm |setup splitting|Cmax,通過改進(jìn)近似算法LSU的拆分規(guī)則提出了近似算法APC,其時(shí)間復(fù)雜性為O((n+K)log(n+K)),并證明了在任意情形下近似算法APC的解均優(yōu)于近似算法LSU的近似解,具體的將競爭比改進(jìn)至 本文所提出的各近似算法均能在多項(xiàng)式時(shí)間內(nèi)求得和最優(yōu)解較為接近的近似算,能夠有效響應(yīng)客戶的實(shí)時(shí)需求,因而具有較好的理論意義和實(shí)際應(yīng)用價(jià)值。
【學(xué)位授予單位】：復(fù)旦大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2010
【分類號】：F552;U695.22
【圖文】：

復(fù)旦大學(xué)碩士學(xué)位論文圖3一1具有準(zhǔn)備時(shí)間的可拆分組合問題的原型圖3一1中各圖例說明:矩形代表處理終端(港口、碼頭等)以及系統(tǒng)的可用資源K輛車，分別用K，長，K，……，玲表示;實(shí)線三角形代表收貨工作點(diǎn)一Pick一 uPJob，實(shí)線圓形代表送貨工作點(diǎn)- DeliveryJob。如圖3一1所示，可知在港口集裝箱調(diào)度問題原型中的單個(gè)工作的完工時(shí)間有如下特性:總完工時(shí)間由兩部分組成，即運(yùn)輸時(shí)間和裝卸時(shí)間，其中運(yùn)輸時(shí)間取決于每個(gè)工作點(diǎn)和港口終端的距離

復(fù)旦大學(xué)碩士學(xué)位論文圖4一1原問題等價(jià)轉(zhuǎn)換化為t個(gè)雙向工作圈后的描述圖4一1的對應(yīng)圖例說明:矩形代表港口處理終端及K輛車:1，2，3，……，K;實(shí)線三角形代表收貨工作點(diǎn)一Pick一 uPJob，實(shí)線圓形代表送貨工作點(diǎn)- DeliveryJob;虛線三角形代表引入的虛擬收貨工作點(diǎn)一 D~yPick一 uPJob，虛線圓形代表引入的虛擬送貨工作點(diǎn)一D~yDeliveryjob。4.2近似算法ApA的提出及性質(zhì)分析4.2.1近似算法APA的原理及步驟由本文第4.1節(jié)中的引理4.1知，可通過整數(shù)規(guī)劃Al。在O(n，)時(shí)間內(nèi)求得單輛車情況下最早完工時(shí)間的解

以C~(oPT)表示可組合型集裝箱調(diào)度問題的最優(yōu)解，v表示每輛車的速度(所有車輛均為同速、勻速、恒速機(jī))，則由平行機(jī)排序問題最優(yōu)解的性質(zhì)以及圖4一2所示的已知條件可知:cma二(onT)z格。一(2d卜Zd獷干“‘呱‘釁+’d獷+‘”+2d器)/vk……(4一3)Zd，獷+Zd’F+Zd’彗+Zd，夢+……+Zd，F(xiàn)+Zd’獷)/vk其中:t=max{np，nd}又由圖4一1可知，可組合型集裝箱調(diào)度問題轉(zhuǎn)化為t個(gè)雙向工作圈以后，每個(gè)雙向工作圈的加工時(shí)間為P’，=(d’尸+叮+�！�)/v

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 張潛,高立群,胡祥培,吳畏;物流配送路徑多目標(biāo)優(yōu)化的聚類-改進(jìn)遺傳算法[J];控制與決策;2003年04期

2 吳宗彥;王景華;張建軍;張利;;基于蟻群算法的智能運(yùn)輸調(diào)度問題的研究[J];計(jì)算機(jī)工程與應(yīng)用;2006年35期

3 任傳祥,張海,范躍祖;混合遺傳-模擬退火算法在公交智能調(diào)度中的應(yīng)用[J];系統(tǒng)仿真學(xué)報(bào);2005年09期

4 郭耀煌，李軍;車輛優(yōu)化調(diào)度問題的研究現(xiàn)狀評述[J];西南交通大學(xué)學(xué)報(bào);1995年04期

5 胡大偉;朱志強(qiáng);胡勇;;車輛路徑問題的模擬退火算法[J];中國公路學(xué)報(bào);2006年04期

本文編號：2755846