A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Summary <s> In the classical vehicle-routing problem (VRP) the objective is to service some geographically scattered customers with a given number of vehicles at the minimal cost. In the present paper, we consider a variant of the VRP where the vehicles should deliver some goods between groups of customers. The customers have an associated time window, a precedence number, and a quantity. Each vehicle should visit the customers within their time windows, in nondecreasing order of precedence respecting the capacity of the vehicle. The problem will be denoted the pickup-and-delivery problem with time windows and precedence constraints (PDPTWP). The PDPTWP has applications in the transportation of live animals where veterinary rules demand that the livestocks are visited in a given sequence in order not to spread specific diseases. We propose a tighter formulation of the PDPTWP based on Dantzig-Wolfe decomposition. The formulation splits the problem into a master problem, which is a kind of set-covering problem, and a subproblem that generates legal routes for a single vehicle. The LP-relaxation of the decomposed problem is solved through delayed column generation. Computational experiments show that the obtained bounds are less than 0.24% from optimum for the considered problems. As solving the pricing problems takes up the majority of the solution time, a reformulation of the problem is proposed that makes use of the precedence constraints. By merging customers having the same precedence number into "super nodes," the pricing problem may be reformulated as a shortest-path problem defined on an acyclic layered graph. This makes it possible to solve the pricing problem in pseudopolynomial time through dynamic programming. The paper concludes with a comprehensive computational study involving real-life instances from the transportation of live pigs. It is demonstrated that instances with up to 580 nodes can be solved to optimality. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Summary <s> In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm. <s> BIB002
Summarizing, the largest static PDP problem instance solved to optimality with a state-ofthe-art method comprises 205 requests BIB001 . However, the size of the largest instance solved is not always a good indicator; tightly constrained problems are easier to solve than less tightly constrained ones. The benchmark data set most often used to assess the performance of (meta)heuristic methods for the static PDPTW is the one described in ) (LL01, LL01+, see Table 6 ). Recent new best results have been presented in  and , two metaheuristic solution procedures. The metaheuristic of still holds the best results for a part of the smaller instances. However, also exact methods advanced; the more tightly constrained part of the LL01 data set has recently been solved by a state-of-the-art branch and cut and price algorithm BIB002 . To summarize, over the last decades, in the field of dynamic PDP, a number of solution procedures have been developed. However, the proposed algorithms cannot be directly compared since, so far, no standardized simulation environment has been used by more than one group of authors. Benchmark instances are available; e.g. those used in  , see Section 4. State-of-the-art exact methods for the static DARP solve some instances with up to 96 requests to optimality . However, the same limitation applies as stated in Section 3.2.4, i.e. the size of the test instance is not a very meaningful indicator; tightly constrained instances are easier to solve than those with less tight constraints and no standardized data set has been solved by the proposed approaches. In case of heuristic and metaheuristic methods, comparison becomes even harder since a large part of the solution procedures developed are motivated by real world problem situations. They differ regarding problem type (single and multi depot, homogeneous and heterogeneous fleet), constraints, and objective(s). Moreover, even when the same data sets are used different objectives are considered (see e.g. Laporte, 2003a, Jørgensen et al., 2007) . Consequently, we can only state that in general heuristic methods run faster whereas metaheuristics usually outperform basic heuristic procedures with respect to solution quality. To summarize, only a limited number of solution algorithms have been proposed for the dynamic DARP. Most of them are based on repeated calls of static solution routines. Comparison across the different methods proposed becomes a difficult task since a majority of the work presented is motivated by real life applications. Consequently, each solution methodology was tested on different data sets with varying problem specific characteristics. Whenever a solution method originally developed for the static case was used we refer to Section 3.4 of this survey for further details on its performance in a static setting. Table 6 provides the interested reader with information on available benchmark instances used in the literature. Column one gives the literature reference. Column two through four state the problem type, the size of the different instances in terms of number of requests per instance, and the number of instances provided. Then, a brief description of the data set as well as the abbreviations used in this article are given.