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.
* Vehicle routing Haimovich and Rinnoy Kan @cite_33 proved the following lower bound Although their result addresses the unit-demand case, it generalizes to instances where all non-zero client demand @math is at least one for every client @math . :
@cite_33
1529079830 2031722814 2137208273 2073588680
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. This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear programming for solving the associated Lagrangian dual problem. This algorithm creates easier constrained shortest path subproblems because less negative cycles are introduced and it leads to faster multiplier convergence due to a stabilization of the dual variables. We have embedded the stabilized cutting-plane algorithm in a branch-and-bound search and introduce strong valid inequalities at the master problem level by Lagrangian relaxation. The result is a Lagrangian branch-and-cut-and-price (LBCP) algorithm for the VRPTW. Making use of this acceleration strategy at the master problem level gives a significant speed-up compared to algorithms in the literature based on traditional column generation. We have solved two test problems introduced in 2001 by Gehring and Homberger with 400 and 1000 customers respectively, which to date are the largest problems ever solved to optimality. We have implemented the LBCP algorithm using the ABACUS open-source framework for solving mixed-integer linear-programs by branch, cut, and price. 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. Vehicle Routing Problems have been extensively analyzed to reduce transportation costs. More particularly, the Vehicle Routing Problem with Time Windows (VRPTW) imposes the period of time of customer availability as a constraint, a common characteristic in real world situations. Using minimization of the total distance as the main objective to be fulfilled, this work implements an efficient algorithm which associates non-monotonic Simulated Annealing to Hill-Climbing and Random Restart. The algorithm is compared to the best results published in the literature for the 56 Solomon instances and it is shown how statistical methods can be used to boost the performance of the method.