A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static pickup and delivery problem <s> In the real world problems occur that can be regarded as travelling salesman problems in which the solution must have some predescribed structure. For example it can be obligatory that some cities must be visited before others or some cities must be visited contiguously. Exact branch and bound procedures will de described for solving general travelling salesman problems with additional constraints. ::: The travelling salesman problem is expanded to include the following situations. ::: 1. A subset (or subsets) of cities - called a cluster - must be visited contiguously. - 2. Precedence relations are imposed on some points. - 3. Situation 1 and precedence relations are imposed on some clusters.Some real world applications of these constrained travelling salesman problems are mentioned. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static pickup and delivery problem <s> A survey of solution methods for routing problems with time window constraints. Among the problems considered are the traveling salesman problem, the vehicle routing problem, the pickup and delivery problem, and the dial-a-ride problem. Optimization algorithms that use branch and bound, dynamic programming and set partitioning, and approximation algorithms based on construction, iterative improvement and incomplete optimization are presented. <s> BIB002 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static pickup and delivery problem <s> A laminate having particular characteristics is used in securing a protective sheet over the emulsion surface of a photographic element such as negatives, positives, slides, glass plates, microfilm, movie film, etc. The optical and mechanical characteristics of the laminate include a protective sheet of transparent, wear-resistant plastic coated with a pressure-sensitive adhesive so that the total thickness of the protective sheet and the adhesive is less than 0.004 inches. The adhesive transmits a major portion of incident ultra violet light and is non-degradable in ultra violet light, and a release sheet of resin material covers the adhesive coating until application to the photographic element when the release sheet is stripped away. Both the protective sheet and the release sheet have a surface finish of less than 10-millionths of an inch RMS so that both the adhesive surface and the protective sheet surface are very smooth when the release sheet is stripped away. <s> BIB003 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static pickup and delivery problem <s> Transportation on demand (TOD) is concerned with the transportation of passengers or goods between specific origins and destinations at the request of users. Management of a TOD system involves making decisions regarding three main aspects: request clustering, vehicle routing, and vehicle scheduling. The operations research literature contains numerous studies addressing both static and dynamic TOD problems, most of which are generalizations of the vehicle routing problem with pickup and delivery (VRPPD). The aim of this paper is to present the most important results regarding the VRPPD and to survey four areas of application: the dial-a-ride problem, the urban courier service problem, the dial-a-flight (or air taxi charter) problem, and the emergency ambulance dispatch problem. For each area, the paper describes the particular features of the problem and summarizes the main exact and heuristic solution algorithms that have been proposed in the literature. <s> BIB004
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. BIB001 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  , 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 BIB002 . BIB004 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  BIB003 BIB002 . In the following paragraphs the various solution techniques for the static PDP are summarized according to exact, heuristic, and metaheuristic approaches.