隨著時代的發(fā)展與進(jìn)步,物流調(diào)度、出租車調(diào)度、機(jī)械與人工調(diào)度在社會及企業(yè)中扮演著越來越重要的角色,引起了眾多數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家的關(guān)注。本文主要研究了最小鄉(xiāng)村郵遞員覆蓋問題（MRPCP）和最小中國郵遞員覆蓋問題（MCPCP）,提出了圖分解算法,并在此基礎(chǔ)上給出了近似算法。最小鄉(xiāng)村郵遞員覆蓋問題是在一個無向賦權(quán)圖G=（V,E）上,通過最少數(shù)量的回路覆蓋給定的邊子集,其中這些回路的長度不超過上界λ。而最小中國郵遞員覆蓋問題是最小鄉(xiāng)村郵遞員覆蓋問題的一個特殊情況,即邊子集R就是圖上的所有邊集E的情況（R=E）。首先,我們由圈覆蓋問題的近似算法進(jìn)行簡單的推廣得到了關(guān)于最小鄉(xiāng)村郵遞員覆蓋問題的7近似算法;其次,考慮到在圈覆蓋問題中主要用到了樹分解的思想,由此我們提出一套關(guān)于在一般圖上的圖分解算法,借用圖分解算法,我們先后得到了關(guān)于最小鄉(xiāng)村郵遞員覆蓋問題的兩個不同復(fù)雜度的5近似算法。最后,我們還研究了中國郵遞員覆蓋問題,得到了4近似算法。 

【文章頁數(shù)】：41 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 引言
    1.1 背景
    1.2 論文主要工作
第2章 預(yù)備知識
    2.1 鄉(xiāng)村郵遞員問題和中國郵遞員問題
    2.2 最小鄉(xiāng)村郵遞員路徑覆蓋問題和最小中國郵遞員路徑覆蓋問題
    2.3 最小鄉(xiāng)村郵遞員覆蓋問題和最小中國郵遞員覆蓋問題
    2.4 樹分解和圖分解
第3章 最小鄉(xiāng)村郵遞員覆蓋問題的近似算法
    3.1 一個復(fù)雜性為O(n~2 log n)的7近似算法
    3.2 一個簡單的復(fù)雜性為O(n~2 log n+nR|E|)的5近似算法
    3.3 一個更快的復(fù)雜性為O(|E|+nlogn)的5近似算法
第4章 最小中國郵遞員覆蓋問題
    4.1 一個復(fù)雜性為O(n~3)的4近似算法
第5章 總結(jié)
參考文獻(xiàn)
致謝
發(fā)表以及完成論文


【參考文獻(xiàn)】：
期刊論文
[1]中國郵遞員問題50年[J]. 高敬振,高勃.  運籌學(xué)學(xué)報. 2013(01)
[2]中國郵遞員問題的研究與發(fā)展[J]. 楊靜,殷志祥,鄒德杰.  科技信息. 2012(32)
[3]郵政速遞網(wǎng)絡(luò)流程優(yōu)化問題探討[J]. 蘇偉燦.  郵政研究. 2010(01)
[4]中國郵遞員問題的DNA計算[J]. 李瑋,王雷.  計算機(jī)應(yīng)用. 2009(07)
[5]求解中國郵遞員問題的一種思路[J]. 吳杰.  科技資訊. 2007(14)
[6]中國郵遞員問題的動態(tài)規(guī)劃算法研究[J]. 費蓉,崔杜武.  計算機(jī)研究與發(fā)展. 2005(02)
[7]中國投遞員問題綜述[J]. 管梅谷.  數(shù)學(xué)研究與評論. 1984(01)
[8]奇偶點圖上作業(yè)法[J]. 管梅谷.  數(shù)學(xué)學(xué)報. 1960(03)



本文編號：3688012