The concept of bounded highway dimension was developed to capture observed properties of the metrics of road networks. We show that a graph with bounded highway dimension, for any vertex, can be embedded into a a graph of bounded treewidth in such a way that the distance between @math and @math is preserved up to an additive error of @math times the distance from @math or @math to the selected vertex. We show that this theorem yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most @math units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set @math of distinguished vertices. The treewidth depends on @math , and the distance between @math and @math is preserved up to an additive error of @math times the distance from @math and @math to @math . This embedding result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed @math , there is a PTAS for @math -Center in graphs of bounded highway dimension. In this problem, the goal is to minimize @math such that there exist @math vertices (the centers) such that every vertex is within distance @math of some center. Similarly, for fixed @math , there is a PTAS for @math -Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the @math centers.
Little is known for higher dimensions or other metrics. Kachay gave a PTAS in @math that requires @math to be @math @cite_13 , and Hamaguchi and Katoh @cite_16 and Asano, Katoh, and Kawashima @cite_25 focused on constant-factor approximation algorithms for the case where the graph is a tree and client demand is divisible. Becker, Klein and Saulpic @cite_32 gave the first approximation scheme for a non-Euclidean metric: they describe a quasi-polynomial-time approximation scheme in planar graphs, but only when the capacity @math is polylogarithmic in the graph size. They introduce the idea of an error that depends on the distance to the depot, which we also use in the embedding presented in our work here.
@cite_32 @cite_16 @cite_13 @cite_25
2966058519 2137208273 2559541197 1529079830
In this paper we deal with a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We show that the problem is NP-complete and propose a 1.5-approximation algorithm for the problem. We also give some computational results. Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem remaining NP-hard even in the Euclidean spaces of fixed dimension. Thirty years ago, in their celebrated paper, M. Haimovich and A. Rinnoy Kan proposed the first PTAS for the Planar Single Depot CVRP based on their Iterated Tour Partition heuristic. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose an EPTAS for the Euclidean CVRP for any fixed dimension. This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint We propose a 1.35078-approximation algorithm for the problem (exactly, (√41 - 1) 4), which is an improvement over the existing 1.5-approximation.