A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> SC96 <s> The Pickup and Delivery Problem with Time Windows (PDPTW) is a generalization of the well studied Vehicle Routing Problem with Time Windows (VRPTW). Since it models several typical planning situations in operational transportation logistics and public transit, the PDPTW has attracted growing interest in recent years. This paper proposes a Grouping Genetic Algorithm (GGA) for solving the PDPTW which features a group-oriented genetic encoding in which each gene represents a group of requests instead of a single request. The GGA is subject to a comparative test on the basis of two publicly available benchmark problem sets that comprise 9 and 56 PDPTW instances, respectively. The results show that the proposed GGA is competitive. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> SC96 <s> The Vehicle Routing Problem with Backhauls is a generalization of the ordinary capacitated vehicle routing problem where goods are delivered from the depot to the linehaul customers, and additional goods are brought back to the depot from the backhaul customers. Numerous ways of modeling the backhaul constraints have been proposed in the literature, each imposing different restrictions on the handling of backhaul customers. A survey of these models is presented, and a unified model is developed that is capable of handling most variants of the problem from the literature. The unified model can be seen as a Rich Pickup and Delivery Problem with Time Windows, which can be solved through an improved version of the large neighborhood search heuristic proposed by Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Technical Report, DIKU, University of Copenhagen, 2004]. The results obtained in this way are comparable to or improve on similar results found by state of the art heuristics for the various variants of the problem. The heuristic has been tested on 338 problems from the literature and it has improved the best known solution for 227 of these. An additional benefit of the unified modeling and solution method is that it allows the dispatcher to mix various variants of the Vehicle Routing Problem with Backhauls for the individual customers or vehicles. <s> BIB002
Bench. = Benchmark, Con. = Constraints, heur. = heuristic(s), HF = Heterogeneous Fleet, HG = Heterogeneous Goods, LIFO = Last-In-First-Out, MD = Multi Depot, NV = Number of Vehicles, Obj. = Objective(s), req. = requests, RC = Routing Cost, RD = Route Duration, split = split deliveries, (m)TW = (multiple) Time Windows, TWV = TW Violation, transf. = transfers between vehicles, UC = Unsatisfied Customers; The respective benchmark instances are described in Section 4. Entries marked by an asterisk (*) are described in further detail in the text. 1 i.e. an iterative procedure based on an insertion algorithm. It prioritizes requests that caused difficulties in previous iterations. Table 3 gives an overview of the different metaheuristic solution methods proposed for the static PDP. For each reference the same information as in the previous tables is provided. A variable neighborhood search for an extension of the SPDP is discussed in (Carrabs et al., 2007) . The problem tackled includes a further constraint regarding rear loading, i.e. items can only be delivered in a LIFO matter. Eight different construction techniques are used to generate an initial solution. The neighborhoods are defined by couple exchange, block exchange, relocate-block, 2-opt-L (2-opt considering only LIFO-feasible arc exchanges) and multi-relocate operators. develop a tabu embedded simulated annealing approach for the PDP. Pickup and delivery pair swap neighborhoods are defined. These are based on a shift, an exchange, and a rearrange operator. The first two define the neighborhoods searched by the metaheuristic, the third is used for postoptimization purposes. BIB001 proposes a grouping genetic algorithm for the PDP. It differs from traditional genetic algorithms in that a group-oriented genetic encoding is used. The encoding used by BIB001 corresponds to the cluster of requests forming a route. The routing aspect, not comprised in the encoding, is added while decoding the chromosome.  present an adaptive large neighborhood search algorithm for the PDPTW. Multiple depots as well as the existence of service times can be handled by the approach at hand. In BIB002 ) the proposed method is used to solve VRP and VRPB instances by transforming them into rich PDPTW. We refer to part I of this survey for further details on this solution procedure.