Algorithm Design And Performance Analysis For Network Scheduling And Vehicle Routing Problems

In this thesis,we consider some combinatorial optimization problems on networks,in-cluding vehicle scheduling problems,capacitated vehicle routing problems and 2-delivery traveling salesman problem.We study the properties of these problems.Based on these properties,we design algorithms for the problems.We also analysis the worst case per-formance of these algorithms and the computational complexity of the algorithms.This thesis includes the following five chapters:In Chapter 1,we first introduce some basic concepts and definitions of combinato-rial optimization problems and network optimization problems.Then we summary the research status of the related fields.Finally,the main results of this thesis are presented.In Chapter 2,we consider the tour version and path version of single vehicle schedul-ing problem(SVSP)on tree/cycle-shaped networks.The main idea is to construct several alternative solutions and then choose the optimal one.Some alternative solutions are ob-tained by solving the simplification of the original problem,some other ones are obtained by a method based on set partition.For the tour-version of SVSP on tree-shaped network,we first prove that it equals to the tour-version of SVRP on tree-shaped network.Then,we provide a 16/9-approximation algorithm for the latter,and a 16/9-approximation al-gorithm for the former is also obtained.For the path-version of SVSP on tree-shaped network,we presented a 48/25-approximation algorithm by calling the approximation algorithm for the tour-version.For the tour-version and path-version of SVSP on cycle-shaped network,we present a 5/3-approximation algorithm and a 29/17-approximation algorithm,respectively.In Chapter 3,we research capacitated vehicle routing problems(CVRP)to minimize the total distance traveled by vehicles.We consider two special cases of the problem,CVRP on line-shaped network with unsplittable demand and CVRP on cycle-shaped network with splittable demand.For CVRP on line-shaped network with unsplittable demand,we introduce the concept of standard instance and present the lower bound of the problem.Based on the lower bound,we give a structure of the 5/3-approximation algorithm.As a subsequence a corresponding algorithm.For CVRP on cycle-shaped net-work with splittable demand,we show the properties of an optimal solution and provide a pseudo-polynomial optimal algorithm with time complexity O(nC).In Chapter 4,we consider capacitated vehicle routing problems to minimize the maximal driving distance of the vehicles.This problem can be seen as a generation of the problem studied in the previous chapter,and is also NP-hard.We also consider two special cases as that in the previous chapter.For the case that the network is line-shaped and each customer has an unsplittable demand,we show that this problem has no polynomial-time algorithm with performance ratio less than 2 on condition that P?NP,and provide a 2-approximation algorithm which runs in O(n2)time.For the case that the network is cycle-shaped and each customer has a splittable demand,we propose a pseudo-polynomial approximation scheme.In Chapter 5,we study a special case of the k-dTSP problem where k=2.We consider the 2-DTSP problem on tree-shaped networks and general networks.For the 2-dTSP problem on tree-shaped network,we propose a polynomial-time optimal algorithm by optimizing the structure of the tree.For the 2-dTSP problem on general networks,we propose a 5/2-approximation algorithm which runs in polynomial time.In Chapter 6,we conclude our research results and present several topics for future research.