A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> In many cities and towns in the Commonwealth of Massachusetts, Councils on Aging are running dial-a-ride services for elderly residents. A survey of these organizations was made to determine the service characteristics of their transportation systems. While the Council on Aging dial-a-rides do not achieve productivities as high as those achieved by public transit dial-a-rides, lower operating costs are achieved on a per hour basis. Thus the costs per passenger trip are very close to those for the public transit systems. The major advantage of the Council on Aging systems is their ability to employ volunteer or inexpensive labor. These systems are thus very attractive in areas with unused volunteer resources. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Demand responsive bus operation generally requires some type of manual dispatching. If the volume of traffic is low and few vehicles are in service, the cost of dispatching relative to the total operating costs will be substantial. Consequently, many operators hesitate to introduce a dial-a-ride system. <s> BIB002 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> This paper presents a preliminary study of the feasibility of checkpoint dial-a-ride systems. Their cost-effectiveness is compared to that of fixed route systems with no transfers and door-to-door dial-a-ride systems. The results are derived for a simple routing strategy, and involve some simplifications which facilitate the comparisons. For high demand levels, the total cost per passenger for fixed route and checkpoint systems is very close. In fact, their optimal configurations are so alike, and the occurrence of route deviations is so rare, that fixed route systems should be preferred, as they can be operated on a schedule and require less dispatching effort. As the demand level decreases, demand responsive systems become relatively more attractive than fixed route systems, and checkpoint systems might possibly become cost-effective. However, by the time demand responsive systems are significantly better than fixed route systems, door-to-door service can be provided at an even lower cost. This appears to limit the situations where checkpoint dial-a-ride systems can be applied efficiently to a small window of demand levels (and special situations) where they only narrowly outperform other systems. <s> BIB003 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Abstract Given the directed G = ( N , A ) and the penalty matrix C , the Sequential Ordering Problem (hereafter, SOP) consists of finding the permutation of the nodes from the set N , such that it minimizes a C -based function and does not violate the precedence relationships given by the set A . Strong sufficient conditions for the infeasibility of a SOP's instance are embedded in a procedure for the SOP's pre-processing. Note that it is one of the key steps in any algorithm that attempts to solve SOP. By dropping the constraints related to the precedence relationships, SOP can be converted in the classical Asymmetric Traveling Salesman Problem (hereafter, ASTP). The algorithm obtains (hopefully) satisfactory solutions by modifying the optimal solution to the related Assignment Problem (hereafter, AP) if it is not a Feasible Sequential Ordering (hereafter, FSO). The new solution ‘patches’ the subtours (if any) giving preference to the patches with zero reduced cost in the linking arcs. The AP-based lower bound on the optimal solution to ATSP is tightened by using some of the procedures given in [1]. In any case, a local search for improving the initial FSO is performed; it uses 3- and 4-changed based procedures. Computational results on a broad set of cases are reported. <s> BIB004 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> The sequential ordering problem (SOP) finds a minimum cost Hamiltonian path subject to certain precedence constraints. The SOP has a number of practical applications and arises, for instance, in production planning for flexible manufacturing systems. This paper presents several 0–1 models of the SOP and reports the authors’ computational experience in finding lower bounds of the optimal solution value of several real-life instances of SOP. One of the most successful approaches is a cutting plane procedure that is based on polynomial time separation algorithms for large classes of valid inequalities for the associated polyhedron. <s> BIB005 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> The household activity pattern problem of analyzing/predicting the optimal path of household members through time and space as they complete a prescribed agenda of out-of-home activities is posed as a variant of the pickup and delivery problem with time windows. The most general case of the model includes provision for vehicle transfer, selective activity participation, and ridesharing options. A series of examples are solved using generic algorithms. The model is purported to remove existing barriers to the operationalization of activity-based approaches in travel behavior analysis. <s> BIB006 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Abstract A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship’s flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem. <s> BIB007 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple constraints directly without increasing computational complexity. An algorithm that combines the SOP-3-exchange with an Ant Colony Optimization algorithm is described, and we present experimental evidence that the resulting algorithm is more effective than existing methods for the problem. The best-known results for many of a standard test set of 22 problems are improved using the SOP-3-exchange with our Ant Colony Optimization algorithm or in combination with the MPO/AI algorithm (Chen and Smith 1996). <s> BIB008 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Abstract This paper considers a real ship scheduling problem that can be considered as a multi-ship pickup and delivery problem with soft time windows (m-PDPSTW). The motivation for introducing soft time windows instead of hard is that by allowing controlled time window violations for some customers, it may be possible to obtain better schedules and significant reductions in the transportation costs. To control the time window violations, inconvenience costs for servicing customers outside their time windows are imposed. An optimisation based approach based on a set partitioning formulation is proposed to solve the problem. First, all (or a number of promising) feasible routes are enumerated. Second, the various possible schedules of each route are computed as well as the corresponding operating and inconvenience costs. Finally, the schedules are given as input to a set partitioning problem. The solution method also determines the optimal speeds for the ships on the various sailing legs. The computational results show that the proposed approach works on the real ship scheduling problem. <s> BIB009 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Dial-a-ride systems are attracting attention as a new style of transportation systems for urban areas. While it has been reported that such systems improve the usability of bus systems when applied in a small town or area, it is not obvious how and under what conditions the systems are effective in comparison to traditional fixed-route bus systems. We conducted two computer simulations of dial-a-ride and fixed-route systems in order to compare the usability and profitability of both systems. Simulation results indicated that: (1) The usability of the dial-a-ride system with a fixed number of buses drops very quickly when the number of requests(demands) increases. (2) When we increase the number of buses proportionally to the number of demand, the usability of the dial-a-ride system is improved more significantly than that of the fixed-route system. (3) When frequency of demands is sufficiently, the dial-a-ride system is a reasonable solution from the both usability and profitability perspectives. <s> BIB010 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Evaluation of scalability and usability of dial-a-ride systems is reported as a case study to assess utilities of ubiquitous mass user support. One of applications of ubiquitous and multi-agent systems is transportation system in urban area. While multi-agent and ubiquitous systems are considered to support next-generation social systems, it is not clear how it provides advantage in usability and benefit. We will show a result of comparison between dial-a-ride bus systems, one of possible multi-agent application of transportation systems, and traditional fixed-route bus systems. We conduct experiments of various situation and show how the advantage of dial-a-ride is robust to the variation of social conditions. For example, when many demands occur from/to a certain point like railway stations or shopping centers, improvement of usability of dial-a-ride systems is better than one of fixed-route systems so that a break-even point between the two systems is reduced. This means that dial-a-ride systems are useful even in 'rush-hour'. Through these experiments, we will figure out the conditions where multi-agent like systems have advantage against traditional systems. <s> BIB011 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Over the past 10 years, operating expenses for demand responsive transit (DRT) have more than doubled as demand for this mandated service has expanded. The DRT systems that we studied consist of dial-a-ride programs that transit agencies use for point-to-point pick-up and delivery of the elderly and handicapped. Many advanced technologies and management practices have been proposed and implemented to improve the efficiency of the service; but, evidence for the effectiveness of these actions has been based upon projections or small pilot studies. We present the results of a nationwide study involving 62 transit agencies. Our analysis indicates that the use of paratransit computer aided dispatching (CAD) system and agency service delivery provide a productivity benefit while the use of financial incentives has a detrimental impact on productivity. Also, the use of advanced communication technology has a beneficial impact on operating cost while the use of financial incentives has a detrimental impact. <s> BIB012 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Car pooling is a transportation service organized by a large company which encourages its employees to pick up colleagues while driving to/from work to minimize the number of private cars travelling to/from the company site. The car pooling problem consists of defining the subsets of employees that will share each car and the paths the drivers should follow, so that sharing is maximized and the sum of the path costs is minimized. The special case of the car pooling problem where all cars are identical can be modeled as a Dial-a-Ride Problem. In this paper, we propose both an exact and a heuristic method for the car pooling problem, based on two integer programming formulations of the problem. The exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the problem. A valid upper bound is obtained by the heuristic method, which transforms the solution of a Lagrangean lower bound into a feasible solution. The computational results show the effectiveness of the proposed methods. <s> BIB013 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> following the difficulty of public transport to adequately cover all passenger transportation needs, different innovative mobility services are emerging. Among those are car pooling services, which are based on the idea that sets of car owners having the same travel destination share their vehicles. Until now these systems have had a limited use due to lack of an efficient information processing and communication support. In this study an integrated system for the organization of a car pooling service is presented, using several current Information and Communication Technologies (ICT's) technologies: web, GIS and SMS. The core of the system is an optimization module which solves heuristically the specific routing problem. The system has been tested in a real-life case study. <s> BIB014 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> The rising auto usage deriving from growth in jobs and residential population is making traffic congestion less tolerable in urban and suburban areas. This results in air pollution, energy waste and unproductive and unpleasant consumption of people’s time. Public transport cannot be the only answer to this increasing transport demand. Car pooling has emerged to be a viable possibility for reducing private car usage in congested areas. Its actual practice requires a suitable information system support and, most important, the capability of effectively solving the underlying combinatorial optimization problem. This paper presents an application of the ANTS approach, one of the approaches which follow the Ant Colony Optimization (ACO) paradigm, to the car pooling optimization problem. Computational results are presented both on datasets derived from the literature about problems similar to car pooling and on real-world car pooling instances. <s> BIB015 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> Demand Responsive Transport Services (DRTS) are a type of public transportation characterized by the fact that the vehicles operate in response to calls from passengers to the transit operator, who then dispatches a vehicle to collect the clients and transport them to their destinations. This article describes the importance of accurate information flows, notably for time factors, for the efficient scheduling of dynamic DRTS. Dynamic systems are designed to handle changing situations such as incoming requests, customer no-shows at pickup points, vehicle breakdowns, or traffic congestion. The authors begin with a literature review on dynamic demand responsive systems, then describe the problem under study and the simulation process they used to solve it. The authors introduce and discuss some temporal parameters that can be seen as attributes of the information inflows of the scheduling process. The authors found that the relationship between the percentage of offline reservations and the number of rejected requests is not monotonic and is dependent on demand patterns. Fare discounts for early reservations have a positive effect on the scheduling efficiency only if they are determined to assume a critical percentage of offline requests. Pricing policies should be considered together with the performances of the scheduling software. The authors conclude that, in a dynamic environment trying to serve all the requests, a DRTS can lead to oversized fleets. If policy regulations do not allow for rejections, then it is more convenient to foresee the possibility of outsourcing a fraction of these to taxicabs. <s> BIB016 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> We study the problem of determining the number of vehicles needed to provide a demand responsive transit service with a predetermined quality for the user in terms of waiting time at the stops and maximum allowed detour. We propose a probabilistic model that requires only the knowledge of the distribution of the demand over the service area and the quality of the service in terms of time windows associated of pickup and delivery nodes. This methodology can be much more effective and straightforward compared to a simulation approach whenever detailed data on demand patterns are not available. Computational results under a fairly broad range of test problems show that our model can provide an estimation of the required size of the fleet in several different scenarios. <s> BIB017 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Related work <s> In this paper we consider a variant to the classical symmetric travelling salesman problem (TSP), the TSP with extra precedence constraints on vertex pairs. We call this problem the pickup and delivery travelling salesman problem (PDTSP). We conduct a polyhedral analysis of the PDTSP. We determine the size of the associated polytope, we propose new valid inequalities, and we identify several classes of inequalities that are facets for the PDTSP polytope. <s> BIB018
Pickup and delivery problems do not only arise in the context of vehicle routing but also in ocean borne transportation. Christiansen and Nygreen (1998a) propose a combined PDPTW and multi inventory model arising in the context of ship routing. It is solved by means of column generation. Similar solution approaches are presented in Nygreen, 1998b, Christiansen, 1999) . Column generation is also used in (Christiansen and Nygreen, 2005) , assuming uncertainties in sailing times and considering inventory constraints to be soft. Another exact solution method for the traditional PDPTW in ship routing is reported in (Christiansen and Fagerholt, 2002) . Brønmo et al. (2007) propose a multi-start local search heuristic. A relaxed version of the multi-ship PDPTW, considering soft time windows, is tackled in BIB009 ). Fagerholt and Christiansen (2000a) study a combined ship scheduling and allocation problem. Optimal solutions are computed for several real life cases. The subproblem, a TSPTW with allocation and precedence constraints, of the combined problem is studied by BIB007 . For an extensive survey on ship routing problems we refer to (Christiansen et al., 2004 ). An interesting extension of the PDPTW was proposed by BIB006 , namely the household activity pattern problem. It involves ridesharing as well as vehicle-switching options. The objective is the minimization of household travel disutility. Recker solved the problem defined by means of a genetic algorithm. Research dedicated to polyhedral analysis is presented in BIB018 for the SPDP. New valid inequalities are discussed. Combinatorially simple pickup and delivery paths are studied in  . These are concatenations of several short patterns. Each pattern consists of visiting at most two requests, BIB008 elaborate on another problem related to the PDP, namely the sequential ordering problem. Its objective is to determine a minimum weight Hamiltonian path in a directed graph, with weights on arcs and vertices, respecting precedence constraints between vertices. In contrast to the PDPTW, one vertex can have multiple predecessors. BIB008 propose an ant colony optimization based approach to solve this problem. Other solution methods involve, e.g. those of BIB004 BIB005 . Dealing with the transportation of people, especially handicapped or elderly, research has also been dedicated to the comparison of dial-a-ride systems with other modes of transportation. Early studies of dial-a-ride transportation systems are reported in (Carlson, 1976, Teixeira and BIB001 . BIB002 tests a robot dispatcher dial-a-ride system in Sweden. BIB003 compares fixed route transit systems with checkpoint dial-a-ride and doorto-door dial-a-ride systems. He concludes that most of the time either a fixed route system or door-to-door transportation is the appropriate choice.  investigate the impact of different operating scenarios on the quality of transportation systems for the handicapped. More recent studies comparing dial-a-ride and traditional bus systems by means of simulation are reported in BIB011 . BIB010 study the usability of dial-a-ride systems in urban areas.  evaluate telematics based demand responsive transport services in Europe. BIB012 analyze the impact of management practices and advanced technologies in the context of demand responsive transport systems. The impact of information flows, e.g. the percentage of real time requests or the length of the interval between the arrival of a new request and its requested pickup TW, is investigated in BIB016 . BIB017 study optimal fleet sizes with respect to predetermined service quality. Research has also been dedicated to possible ways of computation time reduction. Hunsaker and Savelsbergh (2002) A problem class related to the DARP is the car pooling problem. It consists of finding subsets of employees that share a car, the path the driver should follow, and possibly also who should be the driver. In contrast to the DARP either origin or destination are the same for all users depending on whether the trip is from home to the office or back. Two variants can be investigated, either one car pool for both ways or differing to-work and from-work problems. BIB013 propose an exact as well as a heuristic procedure for this problem. A real life application is reported in BIB014 . BIB015 propose an ant colony optimization algorithm for the long-term problem.