Traveling Salesman Problem and Capacitated Vehicle Routing

In the traveling salesman problem (TSP), we look for a minimum length tour visiting a given set of n vertices. As a natural generalization of TSP, we consider the capacitated vehicle routing problem (CVRP). In CVRP, we are given a tour capacity k and a vertex called depot, and we look for a minimum length collection of tours starting and ending at the depot, such that those tours together visit a given set of n vertices and each tour visits at most k vertices. In this talk, I am going to talk about recent progress on both TSP and CVRP.