發(fā)布時(shí)間：2022-10-08 16:04

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

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

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

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


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



本文編號(hào)：3688012