This paper is the second part of a comprehensive survey on routing problems involving pickups and deliveries. Basically, two problem classes can be distinguished. The first part dealt with the transportation of goods from the depot to linehaul customers and from backhaul customers to the depot. The second part now considers all those problems where goods are transported between pickup and delivery locations, denoted as Vehicle Routing Problems with Pickups and Deliveries (VRPPD). These are the Pickup and Delivery Vehicle Routing Problem (PDVRP -unpaired pickup and delivery points), the classical Pickup and Delivery Problem (PDP -paired pickup and delivery points), and the Dial-A-Ride Problem (DARP -passenger transportation between paired pickup and delivery points and user inconvenience taken into consideration). Single as well as multi vehicle mathematical problem formulations for all three VRPPD types are given, and the respective exact, heuristic, and metaheuristic solution methods are discussed. The aim of this paper is to present a classification scheme as well as a comprehensive survey on pickup and delivery problems and their variants. Part I of this survey presented all problem types belonging to the class of Vehicle Routing Problems with Backhauls (VRPB), where goods are transported from a depot to linehaul customers and from backhaul customers to a depot. Furthermore, the motivation for this survey was given. Part II covers all problem types where goods are transported between pickup and delivery locations, referred to as Vehicle Routing Problems with Pickups and Deliveries (VRPPD). The two pickup and delivery problem classes as well as their subclasses are depicted in Figure 1 . The gray part was discussed in part I of this survey. The numbers indicated in the boxes specify the sections covering the respective problems. The first two indicators refer to the modeling part while the last refer to the sections on solution methods. The class we denote VRPPD refers to problems where goods are transported from pickup to delivery points. It can be further divided into two subclasses. The first subclass refers to situations where pickup and delivery locations are unpaired. A homogeneous good is considered. Each unit picked up can be used to fulfill the demand of any delivery customer. In the literature mostly the single vehicle case is tackled, denoted as capacitated traveling 1 Figure 1 : Pickup and delivery problems. The numbers indicated refer to the sections covering the respective problems. Problems (GPDP) transportation from/to a depot (VRPB) salesman problem with pickups and deliveries (Anily and Bramel, 1999), One-Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP) (Hernández-Pérez and SalazarGonzález, 2003), and traveling salesman problem with pickup and delivery (Hernández-Pérez and Salazar-González, 2004a ). Since also a multi vehicle application has been reported in the literature (see Dror et al., 1998) we will denote this problem class as Pickup and Delivery Vehicle Routing Problem (PDVRP) and Pickup and Delivery Traveling Salesman Problem (PDTSP), in the multi and in the single vehicle case, respectively. The second VRPPD subclass comprises the classical Pickup and Delivery Problem (PDP) and the Dial-A-Ride Problem (DARP). Both types consider transportation requests, each associated with an origin and a destination, resulting in paired pickup and delivery points. The PDP deals with the transportation of goods while the DARP deals with passenger transportation. This difference is usually expressed in terms of additional constraints or objectives that explicitly take user (in)convenience into account. The single vehicle variant of the PDP has also been referred to as pickup-delivery traveling salesman problem (Kalantari et al., 1985) and the multi vehicle case as vehicle routing problem with pickup and delivery (Derigs and Döhmer, 2008) . However, a majority of the work published denotes this problem class as Pickup and Delivery Problem (PDP) (see e.g. Dumas et al., 1991 , van der Bruggen et al., 1993 . We will follow this naming. Dial-a-ride problems are also mostly referred to as such. However, some authors, such as Toth and Vigo (1996) , denote the same problem as the handicapped persons transportation problem. The dynamic version is also referred to as demand responsive transport (compare e.g. Mageean and Nelson, 2003) . We denote the single vehicle case of the PDP as SPDP, the single vehicle case of the DARP as SDARP. In the field of transportation two problem classes can be distinguished: full-truck-load problems and less-than-truck-load problems. Full-truck-load problems deal with vehicles of unit capacity as well as unit demand or supply at every customer location. In case of paired pickup and delivery locations, no other customer can be visited between a pickup and its associated delivery location (see Archetti and Speranza, 2004 , Coslovich et al., 2006a , Currie and Salhi, 2003 , de Meulemeester et al., 1997 , Doerner et al., 2001 , Fleischmann et al., 2004 , Gronalt et al., 2003 , Gronalt and Hirsch, 2007 , Imai et al., 2007 , Jordan and Burns, 1984 , Jordan, 1987 , Powell et al., 1995 ,b, Regan et al., 1996a,b, 1998 , Russell and Challinor, 1988 , Wang and Regan, 2002 , Yang et al., 1998 . Furthermore, there exists a problem class that is by definition not part of the full-truckload class, since vehicles with capacity two are considered. However, these problems are strongly related to the full-truck-load category since they originate from the same application area (container dispatching). The aim of this paper is to present a concise classification scheme and survey limited to vehicle routing problems involving pickup and delivery operations where the routing and not the scheduling aspect is of predominant importance. Therefore, full-truck-load dispatching approaches as well as approaches strongly related to this class (see e.g. Archetti et al., 2005 , le Blanc et al., 2006 will not be covered in this article. Also literature on sequencing problems, e.g. arising at intermodal stations, involving gantry crane pickup and delivery operations (compare e.g. Böse et al., 1999 , Böse et al., 2000 , Gutenschwager et al., 2003 will not be part of this survey. The remainder of this paper is organized as follows. First, in order to clearly define the different VRPPD types, consistent mathematical problem formulations for the single and for the multi vehicle case are given. Then, solution methods are discussed in subsections devoted to the corresponding problems. In each of these subsections exact, heuristic, and metaheuristic solution methods are presented. Also related work will be mentioned. Section 4 gives an overview of existing benchmark instances for the different problem classes as well as some information regarding best known solutions. Concluding remarks and possible directions for future research are provided at the very end of this survey. In the following section consistent mathematical problem formulations will be presented. First, the notation used throughout the survey is given. After that two basic problem formulations are introduced, one for the single and one for the multi vehicle case. These are adjusted to the unpaired pickup and delivery problem, the classical pickup and delivery problem, and the dial-a-ride problem, respectively. Note that the mathematical models are only given for definition purposes, regardless the strength of their LP relaxations or whether they were used in the context of additive bounding, branch and cut algorithms, or Lagrange relaxations. We refer the interested reader to the work summarized in the sections on exact solution procedures for additional information concerning these aspects. All problems defined are NP-hard as they generalize the well-known Traveling Salesman Problem (TSP) (Garey and Johnson, 1979 Note that this notation is valid for the symmetric and for the asymmetric case. In the symmetric case t k ij = t k ji and c k ij = c k ji , arc (i, j) and arc (j, i) could thus be modeled by one edge. Consequently, fewer variables would be needed. However, since we focus on problem definition and not on computational efficiency, we refrain from presenting these variants here. VRPPD are modeled on complete graphs G = (V, A) where V is the set of all vertices V = {0, n +ñ + 1} ∪ P ∪ D, and A the set of all arcs. For practical reasons the arc set can be reduced to During the optimization process some or all of the following decision variables are determined, depending on the problem considered. Note that vehicle dependent start as well as end vertices can easily be introduced into the model. However, for the sake of simplicity we will not consider this extension in our formulation. In the single vehicle problem formulation the superscript k can be omitted, resulting in the parameter coefficients c ij , t ij , C, T and the decision variables x ij , Q i , B i . The single vehicle model for the different VRPPD is based on an open TSP formulation. For Then, the open TSP formulation is min subject to: j:(i,j)∈A The objective function (1) minimizes total routing cost. Equalities (2) and (3) ensure that each vertex is visited exactly once. Constraints (4) present one of several possibilities to ensure route-connectivity. For other options we refer to part I of this survey. 4 Here it is assumed that every unit picked up can be used to satisfy every delivery customer's demand. Similar to the TSPMB, described in part I of this survey, vehicle loading constraints have to be amended to formulation (1) - (5), In difference to the TSPMB the initial load of the vehicle is free here (see Hernández-Pérez and Salazar-González, 2004a) . Furthermore, the PDTSP (PDVRP) is the only VRPPD class where equality is needed in (6a), for all other problem types a "≥" sign would suffice. The SPDP considers situations where pickup and delivery vertices are paired, i.e. n =ñ. In the literature it is common to refer to such a vertex pair as a request, indexed by i = 1, ..., n with i being the origin or pickup point and n + i the corresponding destination or delivery point. To ensure that every destination is only visited after its origin, in addition to (1) - (3), (5), and (6), precedence constraints are needed which are usually modeled via time variables, Constraints (7) state that every origin is to be visited before its destination and (8) ensure that time variables are consistent with travel and service times. Note that (8) also guarantee that short cycles are avoided and therefore inequalities (4) are not needed, given that ( The SDARP deals with the transportation of people. Problems of this kind arise, e.g., in connection with the transportation of handicapped or elderly persons. Another possible application is, however, the transportation of perishable goods, that also requires maximum ride time limits. In addition to the basic model, given in (1) - (3) and (5) - (8), user inconvenience must be considered. This can be handled by another term in the objective function or by additional constraints. Here we choose to formulate a maximum user ride time limit, Constraints referring to the compliance with Time Windows (TW), can be added to all of the above formulations. In the context of passenger transportation TW are usually present. Note that the above formulations are not linear due to constraints (6a) and (8). These can be linearized using a big M formulation (cf. Cordeau, 2006). 5 The basic model for multi vehicle pickup and delivery problems is an adapted three index vehicle routing problem formulation of the one proposed in (Cordeau et al., 2002, p. 158f.) for the VRPTW. min subject to: i:(i,j)∈A The objective function (11) minimizes total routing cost. Constraints (12) state that every vertex has to be served exactly once. Equalities (13) and (14) guarantee that every vehicle starts at the depot and returns to the depot at the end of its route. Note that this does not mean that every vehicle has to be used. A vehicle may only use the arc (0, n +ñ + 1), i.e. it does not leave the depot. Flow conservation is ensured by (15). Time variables are used to eliminate subtours in (16), given that (t k ij + d i ) > 0 for all (i, j) ∈ A. Constraints (17) and (18) guarantee that a vehicle's capacity is not exceeded throughout its tour. It should be noted that this formulation requires the introduction of additional decision variables, Q k i , corresponding to the total load of vehicle k at vertex i. These variables are not needed to formulate the basic VRP but are essential for its extension to a pickup and delivery problem. In VRP formulations inequalities similar to (17) are sometimes used to ensure route connectivity (accomplished by (16) in the above formulation). Furthermore, in (17) equality is only needed for the PDVRP (PDTSP). For all other VRPPD types it can be replaced by "≥". Non-linear constraints, given in (16) and (17), can be linearized using a big M formulation (cf. Cordeau, 2006). The special characteristic of the PDVRP is that every unit picked up can be used to satisfy every customer's demand. The above formulation (11) -(19) already is an appropriate formulation for the PDVRP. No additional adaptations are needed. Here every pickup point is associated with a delivery point and therefore n =ñ. In addition to (11) -(19), two more sets of constraints are needed. First, both origin and destination of 6 a request must be served by the same vehicle, Furthermore, delivery can only occur after pickup, i.e. To extend the multi vehicle PDP to the multi vehicle DARP, again, as in the single vehicle case, constraints related to user inconvenience need to be added. As for the single vehicle version, we will restrict this requirement to adding maximum user ride time constraints to formulation (11) - (21): Two more sets of constraints can be added to all of the above problem classes. These are time window and maximum route duration restrictions, 3 Solution methods for VRPPD In the following section an overview of the different solution methods for the PDVRP, the PDP, and the DARP are presented. Solution methods classify into exact, heuristic, and metaheuristic approaches. A description of the benchmark instances used is given in Section 4. For references to general information on the solution concepts applied, we refer to the first part of this paper. Another survey on different solution methods can be found in (Berbeglia et al., 2007) . Because of maximum paper length restrictions, it was not possible to describe all the work published in detail. An overview of the proposed methods is given in tabular form. Only contributions we considered especially important, for recency or originality reasons, are described in further detail. These are marked by an asterisk in the different tables. Solution methods are ordered chronologically within the tables, according to single and multi vehicle approaches. Further details on solution algorithms are given in the same order. The PDVRP, i.e. the problem class where every good can be picked up and transported anywhere, did not receive as much attention in the literature as the other problem classes. Moreover, most of the literature is restricted to the PDTSP. Therefore, with the exception of (Dror et al., 1998) , all the solution methods presented are only applicable to the one vehicle case. To the authors' knowledge no metaheuristic approach for the PDTSP has been proposed until today. 7 The only exact method proposed for the problem at hand was introduced in Salazar-González, 2003, 2004a). It is a branch and cut algorithm. To speed up the algorithm construction and improvement heuristics are applied. They are used to obtain feasible solutions from the solution of the LP relaxation at the current node. The construction heuristic is an adaptation of the nearest insertion algorithm. It is improved by 2-opt and 3-opt exchanges (Lin, 1965) . The test instances solved are adaptations of the ones used in (Mosheiov, 1994) and (Gendreau et al., 1999) , containing up to 75 customers. A special case of the PDTSP is considered in (Chalasani and Motwani, 1999); the number of goods to be picked up is equal to the number of goods to be delivered; the demand (supply) at every delivery (pickup) location is equal to one. This problem is an extension of the swapping problem where the vehicle's capacity is also set to one. Chalasani and Motwani propose an approximation algorithm with a worst case bound of 9.5. They use Christofides' heuristic (Christofides, 1975) to construct two traveling salesman tours, one containing only pickup locations, and one containing only delivery locations. These two tours are then combined by means of decomposition and matching. Anily and Bramel (1999) devise a polynomial time iterated tour matching algorithm for the same problem. Two heuristic methods can be found in (Hernández-Pérez and Salazar-González, 2004b). The first algorithm is of the construction-improvement type, using a greedy construction procedure, improved by 2-opt and 3-opt exchanges. The second heuristic is based on incomplete optimization; the branch and cut procedure, described in (Hernández-Pérez and Salazar-González, 2004a), is used on a reduced number of variables associated with promising edges. Random instances with up to 500 customers are solved. An approximation algorithm on a tree graph is developed in (Lim et al., 2005) . It is based on a recurrent construction process and has a worst case bound of 2. The PDTSP on a tree and on a line is also subject to investigation in (Wang et al., 2006) . They propose an O(|V | 2 / min {C, |V |}) algorithm for the line case. The unit capacity as well as the uncapacitated version can be solved in linear time. On a tree an O(|V |) algorithm is devised for the case of unit capacity and an O(|V | 2 ) algorithm for the uncapacitated case. Finally, Dror et al. (1998) propose a heuristic algorithm for the application of the multi vehicle PDVRP to the redistribution of self-service cars. It is related to Dijkstra's algorithm (Dijkstra, 1959) . Also other solution approaches are briefly discussed. Solution methods for the classical pickup and delivery problem (PDP), where every transportation request is associated with a pickup and a delivery point, are presented in this section. Lokin (1978) was the first to discuss the incorporation of precedence constraints into the traditional TSP, needed to formulate the PDP. The first attempt to generalize the PDP in unified notation was proposed in (Savelsbergh and Sol, 1995) , covering all possible versions of the PDP, including the dial-a-ride problem. They also provide a brief overview of existing solution methods until 1995. Mitrović-Minić (1998) presents a survey on the PDP with Time Windows (PDPTW). An early survey on vehicle routing problems already including the PDP is given in (Desrochers et al., 1988) . Cordeau et al. (2004) review demand responsive transport, covering PDP and DARP. A review of recent work focusing on exact approaches is given in . Further surveys on solution methods can be found in (Assad, 1988 , Desaulniers et al., 2002 , Desrochers et al., 1988 . In the following 8 paragraphs the various solution techniques for the static PDP are summarized according to exact, heuristic, and metaheuristic approaches. A number of exact solution procedures have been presented for the static PDP. In Table 1 the different techniques are briefly described. The literature reference, objective(s), and additional constraints considered, are given. Furthermore, either the benchmark instances used, or the size of the largest instance solved to optimality, in terms of number of requests, are provided. Entries marked by an asterisk are described in further detail below. Ruland and Rodin (1997) present a branch and cut algorithm to solve the SPDP. It includes cutting plane generation in the bounding phase as well as a greedy route construction procedure to generate the first upper bound. A branch and bound algorithm for the single vehicle PDPTW with Last-In-First-Out (LIFO) loading, i.e. goods have to be delivered in the reverse order they were picked up, is reported in (Cordeau et al., 2006) . They propose three mathematical problem formulations and various valid inequalities. These are based on existing inequalities for PDP and new problem specific ones. The first exact solution method applicable to both the single as well as the multi vehicle case dates back to (Kalantari et al., 1985) . The branch and bound algorithm described is an extension of the one developed by Little et al. (1963) 9 A column generation approach is elaborated in . They consider heterogeneous vehicles, time windows as well as multiple depots. The constrained shortest path problems are solved by means of a forward dynamic programming algorithm. Ropke and Cordeau (2006) introduce a branch and pricing algorithm with additional valid inequalities. The elementary constrained shortest path problem with time windows, capacity, and pickup and delivery restrictions is the natural pricing problem of the PDPTW. It is solved by means of a label setting shortest path algorithm. Valid inequalities are added in a branch and cut fashion; their impact on the structure of the pricing problem is discussed. A branch and cut algorithm departing from two different 2-index PDPTW formulations is studied in . Formulation one makes use of time variables. In formulation two time related constraints are modelled by means of infeasible path inequalities. The latter formulation proves more efficient when used as a basis for the branch and cut algorithm. New valid inequalities to strengthen the proposed formulations are also discussed. Heuristics for the static PDP have first been proposed in the 1980s. Table 2 gives an overview of the various heuristic solution techniques developed since then. Information concerning the type of problem considered, objective(s) used, additional constraints, the type of algorithm proposed as well as either the benchmark instances solved or the largest instance considered for testing purposes is given. Sexton and Choi (1986) use Bender's decomposition procedure to solve the static SPDP approximately. Initial solutions are constructed using a space-time heuristic. The route improvement phase is based on Bender's decomposition. As soft time windows are considered, the objective function takes into account the total operating time as well as time window violation penalties. A construction-improvement heuristic algorithm for the static SPDP is discussed in (van der Bruggen et al., 1993) . First, a feasible initial solution is constructed. Then, this solution is improved by exchange procedures maintaining feasibility at all times. Renaud et al. (2000) also propose a construction-improvement algorithm for the same problem. They use a double insertion construction heuristic improved by deletion and reinsertion (4-opt* (Renaud et al., 1996) ). Renaud et al. (2002) present seven different perturbation heuristics to generate near optimal solutions for the static SPDP. In all seven implementations, first, an initial solution is computed which is improved by a 4-opt** heuristic, an adaptation of the 4-opt* heuristic, such that precedence constraints are respected at all times. Then, a perturbation scheme is applied (instance, algorithmic or solution perturbation), followed by a post-optimization phase. The last two steps are repeated until a stopping criterion is met. The best results are obtained with the solution perturbation scheme. Xu et al. (2003) propose a column generation based heuristic algorithm for the multi vehicle case. They consider several additional constraints, such as multiple time windows at pickup and delivery locations, loading restrictions, compatibility of goods and vehicles as well as driver working hours. The column generation master problem can be solved using a commercial LP solver. The resulting subproblems are solved by means of two heuristics, called merge and two-phase, i.e. merging trips and greedy deletion and insertion of requests. Lu and Dessouky (2006) elaborate on a construction heuristic. It does not only incorporate distance increase into the evaluation criterion but also time window slack reduction as well as visual attractiveness (referred to as crossing length percentage). 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. 10 Li and Lim (2001) 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 11 exchange, and a rearrange operator. The first two define the neighborhoods searched by the metaheuristic, the third is used for postoptimization purposes. Pankratz (2005b) 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 Pankratz (2005b) corresponds to the cluster of requests forming a route. The routing aspect, not comprised in the encoding, is added while decoding the chromosome. Ropke and Pisinger (2006a) 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 Pisinger, 2006b ) 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. A two-stage hybrid algorithm for the static PDPTW is presented in . The first phase uses simulated annealing to decrease the number of vehicles needed. The second phase consists of a large neighborhood search algorithm in order to reduce total travel cost. Derigs and Döhmer (2008) discuss an indirect (evolutionary) local search heuristic for the same problem. In indirect search solutions are encoded such that the problem of securing feasibility is separated from the metaheuristic search process. Here a greedy decoding is used. Summarizing, the largest static PDP problem instance solved to optimality with a state-ofthe-art method comprises 205 requests (Sigurd et al., 2004) . 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 (Ropke and Pisinger, 2006a) and , two metaheuristic solution procedures. The metaheuristic of Li and Lim (2001) 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 (Ropke and Cordeau, 2006) .
For a survey on recent work in this field, refer to REF .
A survey on pickup and delivery problems: Part i: Transportation between customers and depot
Journal für Betriebswirtschaft
Computer Science