Discrete Mathematics and Optimization Seminar
Sept. 22, 2008
Special cases of the Vehicle Routing Problem
Yoshiaki Oda
Keio University, Japan
The Traveling Salesman Problem (TSP) is one of the most famous NP-hard problems. So, much works have been done to study polynomially solvable cases, that is, to find good conditions for distance matrices such that an optimal tour can be found in polynomial time. These good conditions give some restriction on the optimal tour, for example, Monge property, Demidenko conditions and so on. Moreover, it is significant to find algorithms which compute the shortest tour with the restriction. A pyramidal tour appears frequently in those concepts. For a given weighted graph G, a vertex v of G, and an integer k, the Vehicle Routing Problem (VRP) is to find a minimum weight connected subgraph F of G such that F is a union of at most k cycles sharing only one vertex x. In this talk, we apply good conditions for the TSP to the VRP. At first, we define a new concept which is an extension of a pyramidal tour and we show that a minimum weight connected subgraph among them can be computed in polynomial time. Next, we show that if a given weighted graph satisfies several conditions for the TSP, an optimal solution for the VRP can also be computed in polynomial time.