The vehicle routing problem is a generalization of the traveling salesman problem, but is a special case of the pickup and delivery problem. In this problem, we are give p vehicles and a complete graph G, and the objective is to find a separate tour for each vehicle with respect to minimizing or maximizing some objective function, such as the total cost of the tours. This problem has direct relevance to the industry-related research we are pursuing. The vehicle routing problem has numerous variations, and has been extensively investigated by many researchers. Various techniques, such as linear programming, local search, and even clustering, have been applied or designed to solve these problems. However, as a well recognized method of dealing with NP-hard problems, good approximation algorithms have not been well explored for this problem. In this project, we want to devise approximation algorithms for the vehicle routing problems with two constraints, one is the vehicle capacity constraint and the other is the job time window constraint.
Recently, we have showed that a variant of the classical TSP, called black and white TSP, can be approximated with approximation factor 4.