A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour. The motivation of the branching and the calculation of the lower bounds are based on ideas frequently used in solving assignment problems. Computationally, the algorithm extends the size of problem that can reasonably be solved without using methods special to the particular problem. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solution for problems involving no more than 13 cities; the time required (IBM 7094 II) varies from 60 milliseconds for a 9-city problem to 1.75 seconds for a 13-city problem. The second algorithm produces precisely characterized, locally optimal solutions for large problems (up to 145 cities) in an extremely short time and is based on a general heuristic approach believed to be of general applicability to various optimization problems. The average time required to obtain a locally optimal solution is under 30n3 microseconds where n is the number of cities involved. Repeated runs on a problem from random initial tours result in a high probability of finding the optimal solution among the locally optimal solutions obtained. For large problems where many locally optimal solutions have to be obtained in order to be reasonably assured of having the optimal solution, an efficient reduction scheme is incorporated in the program to reduce the total computation time by a substantial amount. <s> BIB002 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed in two parts I and II. Part I focuses on the “static” case of the problem. In this case, intermediate requests that may appear during the execution of the route are not considered. A generalized objective function is examined, the minimization of a weighted combination of the time to service all customers and of the total degree of “dissatisfaction” experienced by them while waiting for service. This dissatisfaction is assumed to be a linear function of the waiting and riding times of each customer. Vehicle capacity constraints and special priority rules are part of the problem. A Dynamic Programming approach is developed. The algorithm exhibits a computational effort which, although an exponential function of the size of the problem, is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size. Part II extends this approach to solving the equivalent “dynamic” case. In this case, new customer requests are automatically eligible for consideration at the time they occur. The procedure is an open-ended sequence of updates, each following every new customer request. The algorithm optimizes only over known inputs and does not anticipate future customer requests. Indefinite deferment of a customer's request is prevented by the priority rules introduced in Part I. Examples in both “static” and “dynamic” cases are presented. <s> BIB003 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> This paper modifies the exact Dynamic Programming algorithm developed by the author for the single vehicle many-to-many immediate request Dial-A-Ride problem to solve the problem where each customer has specified upper and lower bounds for his pickup and delivery times and where the objective is to minimize the time needed to service all customers. The major difference between the two algorithms is the substitution of backward recursion with forward recursion. The new algorithm requires the same computational effort as the old one (0( N 2 3 N ) for N customers) and is able to recognize infeasible problem instances. <s> BIB004 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> This paper presents a vehicle dispatching procedure designed to minimize empty vehicle travel and idle time for a demand-responsive transportation system. The method schedules the empty vehicle assignment between passenger drop-off points and passenger pick-up points by examining the times of drop-offs and pick-ups, and the travel times and distance between them. The minimization of empty vehicle travel and idle time is accomplished through the use of a linear programming transportation problem in which supply and demand vectors contain both location and time elements. The service area is divided into zones and the operating hours into time periods; the vehicle movements (loaded and empty) are processed as the movements between zones, and between time periods. The outputs of the model include scheduling instructions for each vehicle (both loaded and empty trips), estimates of vehicle miles and time, fleet size requirements to satisfy the passenger trip requests, and the identification of passenger trips which cannot be met due to fleet size limitation. <s> BIB005 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> Abstract The paper extends the branch and bound algorithm of Little, Murty, Sweeney, and Karel to the traveling salesman problem with pickup and delivery customers, where each pickup customer is required to be visited before its associated delivery customer. The problems considered include single and multiple vehicle cases as well as infinite and finite capacity cases. Computational results are reported. <s> BIB006 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> Abstract This paper formulates the pickup and delivery problem, also known as the dial-a-ride problem, as an integer program. Its polyhedral structure is explored and four classes of valid inequalities developed. The results of a branch-and-cut algorithm based on these constraints are presented. <s> BIB007 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <s> We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), an extension of the well-known Traveling Salesman Problem where each customer to be served is associated with two quantities of goods to be collected and delivered, respectively. A vehicle with given capacity starts at a depot and must visit each customer exactly once. The vehicle capacity must not be exceeded and the total length of the tour must be minimized. We describe new heuristics for TSPPD, the first based on the exact solution of a special case and the second based on tabu search, and we analyze their average performance through extensive computational experiments. ::: ::: ::: Scope and purpose ::: ::: In several industries vehicles must routinely visit customers and make at each visit a pickup and a delivery. Clearly this must be accomplished without ever violating the vehicle capacity. A common example arises in beer or soft drinks delivery where full bottles must be delivered and empty bottles must be collected. We study this problem for the case of a single vehicle. Since the problem is extremely hard to solve to optimality, we have developed a number of heuristics and tested them on a large number of instances exhibiting different characteristics. <s> BIB008 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Exact methods <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> BIB009
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 BIB002 . The test instances solved are adaptations of the ones used in  and BIB008 , containing up to 75 customers. 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. BIB007 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 BIB009 . 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 BIB006 . The branch and bound algorithm described is an extension of the one developed by BIB001 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. BIB009 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. An early exact dynamic programming algorithm for the single vehicle DARP is introduced in BIB003 . Service quality is taken care of by means of maximal position shift constraints compared to a first-come-first-serve visiting policy. The largest instance solved comprises nine requests. In BIB004 a modified version of the above algorithm is presented. Instead of backward recursion forward recursion is used. Also time windows are considered. A forward dynamic programming algorithm for the static SDARP is discussed in . Possible states are reduced by eliminating those that are incompatible with respect to vehicle capacity, precedence, and time window restrictions. User inconvenience in terms of ride times is incorporated into time window construction, resulting in tight time windows at both, origin and destination of the transportation request. The largest instance solved contains 40 transportation requests. BIB005 develops a balanced LP transportation problem for the multi vehicle case, minimizing empty vehicle travel as well as idle times and thus fleet size. In a preprocessing step the service area is divided into zones, the time horizon into time periods. Every request is classified according to an origin and a destination zone as well as a departure and an arrival time period. An example with four zones is presented. Cordeau (2006) proposes a branch and cut algorithm for the static DARP. The algorithm is based on a 3-index mixed-integer problem formulation. New valid inequalities as well as previously developed ones for the PDP and the VRP are employed. The largest instance solved to optimality comprises 36 requests. Two branch and cut algorithms are described in . Instead of a 3-index formulation, two more efficient 2-index problem formulations and additional valid inequalities are used. A 96-request instance is the largest instance solved to optimality. Extensions of the 3-index and the two 2-index based branch and cut algorithms BIB009 to the DARP with heterogeneous fleet and passengers are discussed in  . Exact methods have not been explicitly developed for the dynamic DARP. A possible reason is that, in the context of dynamic routing, the concept of "optimal solutions" becomes debatable. However, in BIB003 ) the static version of his algorithm is adapted to the dynamic case. Transportation requests are ordered according to the time of call. Up to ten customer requests can be handled.