Design And Analysis Of Algorithms For Some Routing Problems

This thesis aims to study some routing problems, focusing on the design and anal-ysis of algorithms for the vehicle scheduling problem, the clustered traveling salesman problem, the online traveling salesman problem and so on. It consists of five chapters.In Chapter1, we introduce the background, some preliminary concepts, the formu-lations and a review about the routing problems.In Chapter2, we consider the single vehicle scheduling problem with release and service time requirements on a tree or a cycle. The objective is to minimize the makespan. Two versions of the problem are considered. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a9/5-approximation algorithm for the tour-version and a27/14-approximation algorithm for the path-version. For the problem on a cycle, we present12/7-approximation algorithms for both versions.In Chapter3, we discuss the single vehicle scheduling problem in which some cus-tomers with release and service time requirements, are located at the vertices of a line, and a vehicle, initially waiting at some vertex, has to serve all the customers. The cus-tomers are partitioned into several consecutive clusters, and the customers in each cluster must be served consecutively. The objective is to minimize the makespan. In the case where the service time of each customer is zero, we show that both versions can be solved in O(n2) time. In the case where the service time of each customer is given arbitrarily, we present a16/9-approximation algorithm for the tour-version and a13/7-approximation algorithm for the path-version.In Chapter4, we address the clustered traveling salesman problem. Given a weighted undirected graph, the vertex set is partitioned into several clusters. Two kinds of objec-tives are considered. One is finding a shortest tour, the other is finding a shortest path, such that all vertices are visited and the vertices of each cluster are visited consecutively. Supposing that no starting and ending vertices of any cluster are specified, We present a13/6-approximation algorithm for the tour objective and a33/14-approximation algo- rithm for the path objective.In Chapter5, we treat the online quota asymmetric traveling salesman problem (OL-QATSP, for short) and online multiple asymmetric traveling salesman problem (OL-MATSP, for short). The inputs of the problems consist of a quasi-metric space and a sequence of requests, where each request is specified by a release time, a point in the space and a weight. For the OL-QATSP, the objective is to minimize the time when the server has served some requests with the total weight at least a given quota, and returned to its initial location. We prove that the lower bound of the problem is2and present a (1+ρ)-competitive algorithm, where ρ is the approximation ratio of the corresponding offline problem without release times. For the OL-MATSP, in which a crew of servers are given and the requests do not have weight, the objective is to minimize the time by which all requests have been severed and all servers have returned to their initial location. We prove that the lower bound of the problem is3+(?)/2≈2.618and present a (1+ρ+2ρ/1+(?))-competitive algorithm, where the definition of ρ is similar to the previous one.