Approximation Algorithms For Solving Some Routing Problems

Since the Chinese postman problem and the traveling salesman problem were proposed,routing problems have been become a hot topic in the field of combinatorial optimization.Basing on the extensive applications of routings and related problems,we consider five kinds of routing problems in this dissertation.(1)We consider the restricted Chinese postman problem with total penalty and the restricted Chinese postman problem with makespan penalty,and then design two approximation algorithms to solve both,respectively.(2)We study the vertex-load-constrained mixed Chinese postman(VLCMCP,for short)problem,and then present an approximation algorithm to solve it,and in addition,we consider two special versions of the VLCMCP problem,i.e.,the vertex-load-constrained directed Chinese postman problem and the vertex-load-constrained Chinese postman problem,and we construct two optimal algorithms in polynomial time to solve these two special versions,respectively.(3)We address the k-Chinese postman interdiction problem,and we design an approximation algorithm to solve it,in addition,we also present a better approximation algorithm to solve its special version.(4)We propose the heterogeneous Chinese postman problem,and then give two approximation algorithms to solve it.(5)We consider two variations of the k-traveling salesman problem,i.e.,the k-person metric bottleneck traveling salesman problem and the k-person metric scatter traveling salesman problem,then we design two approximation algorithms to solve both,respectively.This dissertation is organized in the following seven chapters.In Chapter 1,we introduce the backgrounds,motivations and main results of the routing problems mentioned-above.In Chapter 2,we present some basic definitions,some related optimization problems and some related results.In Chapter 3,we consider two generalizations of the Chinese postman problem and the traveling salesman problem,i.e.,the restricted Chinese postman problem with total penalty and the restricted Chinese postman problem with makespan penalty,then we design two 3/2-approximation algorithms in time O(n3)and O(n3m)to solve them,respectively.In Chapter 4,we study a generalization of the mixed Chinese postman problem,i.e.,the vertex-load-constrained mixed Chinese postman problem,and employing techniques of graph theory and network flow,then we design a(3,2)-approximation algorithm in time O(m2logn)to solve this problem.At the same time,we show that the algorithm mentioned-above can output an optimal solution for the vertexload-constrained directed Chinese postman problem.In addition,we present an optimal algorithm in time O(m3)to solve the vertex-load-constrained Chinese postman problem.In Chapter 5,we address a generalization of the k-Chinese postman problem,i.e.,the k-Chinese postman interdiction problem.Using an α-approximation algorithm Aa to solve the minimization knapsack problem,we design an(α+β)approximation algorithm in time O(n3+f(n,m))to solve the problem,where f(n,m)is the complexity of the algorithm Aα and β=7/2-1/k-(?)1/k」.In addition,we design an β-approximation algorithm in time O(n3)to solve this problem with unit costs,where β is defined as above.In Chapter 6,we propose another generalization of the k-Chinese postman problem,i.e.,the heterogeneous Chinese postman problem.For any small numberδ>0,analyzing the upper and lower bounds of the optimal value and using a guess technique,we give a 20.8765(1+δ)-approximation algorithm to solve this problem.In addition,considering that a ratio between the maximum speed and the minimum speed of vehicles is generally small in real life,and using a splitting technique,we design an(1+λmax/λmin-1/k)-approximation algorithm in time O(n3)to resolve this problem,where Amax and Amin are the maximum speed and minimum speed of vehicles,respectively.In Chapter 7,we consider two generalizations of the metric bottleneck traveling salesman problem and the metric scatter traveling salesman problem respectively,i.e.,the k-person metric bottleneck traveling salesman problem and the k-person metric scatter traveling salesman problem,then we design two 2-approximation algorithms in time O(n4)and O(n3)to solve the two problems,respectively.Finally,we summarize the results obtained and then put forward some new problems that we think to be worth of further studying in future.