圖路由問題近幾年來一直都是計(jì)算機(jī)科學(xué)和組合優(yōu)化領(lǐng)域中的熱門問題。很多學(xué)者都對旅行商推廣和變形問題做了深入的研究。在本文中,我們研究的是著名的旅行商問題（TSP）的兩個推廣問題。第一個問題我們研究的帶罰的聚類旅行商問題:給定一個完全無向圖G=（V,E）,V表示頂點(diǎn)集合,E表示邊集合,并且邊權(quán)重c（e）滿足三角不等式。頂點(diǎn)集合V被劃分為k個聚類,并且每個聚類的起始點(diǎn)si和終止點(diǎn)ti都已經(jīng)確定。對于每一個聚類i而言,都存在一個罰值πi,這個問題的目標(biāo)是找一個環(huán)游使得經(jīng)過的聚類的總權(quán)重和不在環(huán)游上的聚類的罰函數(shù)值的總和達(dá)到最小。對于這個問題,我們給出了一個近似比為25/6的近似算法。第二個問題是一般聚類路由問題,在這個問題中,給定完全圖G=（V,E）,V表示頂點(diǎn)集合,E表示邊集合。其中頂點(diǎn)集被劃分為C1,…,Ck個聚類。V’（?）V和E’（?）E分別是初始給定的必過點(diǎn)子集和必過邊子集。并且邊權(quán)重l（e）滿足三角不等式。這個問題的目標(biāo)是找到一個環(huán)游使得經(jīng)過必過點(diǎn)V’僅一次,經(jīng)過必過邊E’至少一次,并且總權(quán)重達(dá)到最小。對于這個問題,每個聚類只能遍歷一次。針對于起始點(diǎn)和終止點(diǎn)是否確定,我們把這個問題... 

【文章來源】：南京師范大學(xué)江蘇省 211工程院校

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

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

【文章目錄】：
Abstract （in English）
Abstract （in Chinese）
Chapter 1 Introduction
    1.1 The background of routing problem and its generations
    1.2 Basic definitions
    1.3 Our results
    1.4 Organization of the thesis
Chapter 2 Basic Algorithm and Preliminary Work
    2.1 Christofides' algorithm for TSP
    2.2 Short-cut algorithm
    2.3 Three subproblems and corresponding algorithms
        2.3.1 The Travelling Salesman Path Problem
        2.3.2 The Stacker Crane Problem
        2.3.3 The Rural Postman Problem
Chapter 3 The Prize-collecting Cluster Travelling Salesman Problem
    3.1 Introduction of the prize-collecting cluster traveling salesman problem
        3.1.1 Basic knowledge
        3.1.2 The algorithm and its analysis
Chapter 4 The Cluster General Routing Problem
    4.1 The cluster general routing problem with specified end vertices
        4.1.1 The algorithm and its analysis
    4.2 The cluster general routing problem with unspecified end vertices
        4.2.1 The algorithm and its analysis
Chapter 5 Conclusion
Bibliography
Acknowledgements



本文編號：3139015