Approximation algorithms for the capacitated vehicle routing problem

The Vehicle Routing Problem (VRP) is a generalization of the Traveling Salesman Problem (TSP) and is also one of the most challenging tasks in the area of combinatorial optimization. In the VRP we are given p vehicles and an undirected complete graph G = (V,E) where edge weights satisfying the triangle inequality. The objective is to find a separate tour for each vehicle while minimizing the total cost of the tours. In the Capacitated Vehicle Routing Problem (CVRP), each vehicle has a limited capacity k, and it is required that the vehicle should never exceed its capacity at any point of the tours. In this thesis we present approximation algorithms for the CVRP. The CVRP, in fact, represents a large class of TSP-like problems. We consider approximation algorithms for three variants of the CVRP, namely the Capacitated Vehicle Routing Problem with Pickups and Deliveries (CVRPPD), variants of the Cycle Covering Problem (CCP), and the Capacitated Vehicle Routing Problem with Multi-Depots. Many practical applications, such as mail delivery and bus routing, can be modeled by the CVRPPD. In this class of problems, we focus on the k-delivery Traveling Salesman Problem, the Capacitated Dial-a-Ride Problem, and the Black and White Traveling Salesman Problem (BWTSP). We propose a rule to improve the approximation ratios for the first two problems. We also give a constant factor matching based approximation algorithm for the BWTSP. In the second part of the thesis we investigate some NP-hard variants of the CCP. These variants consider two additional constraints. One constraint is on the number of vertices in each cycle, and the other is on the number of cycles appearing in a cycle cover. We present constant factor approximation algorithms for these problems. Different from the default settings of the CVRP, where only a central depot is involved, in the CVRP with Multi-Depots and Multi-Vehicles, the vehicles may start from different depots. In this category we study a model of the Multi-Depot Capacitated Vehicle Routing Problem (MDCVRP) and the Multi-Vehicle Scheduling Problem (MVSP). We propose a dynamic programming based method to design approximation algorithms for these problems.