A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract This paper presents an analytic model to predict average waiting and ridingtimes in urban transportation systems (such as dial-a-bus and taxicabs), which provide non-transfer door-to-door transportation with a dynamically dispatched fleet of vehicles. Three different dispatching algorithms are analyzed with a simple deterministic model, which is then generalized to capture the most relevant stochastic phenomena. The formulae obtained have been successfully compared with simulated data and are simple enough for hand calculation. They are, thus, tools which enable analysts to avoid cumbersome simulation models when contemplating implementing or modifying many-to-many demand responsive transportation systems. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> The set partitioning model is used as the basis for an interactive approach for solving a broad class of routing problems. A pricing mechanism is developed which can be used with a variety of methods in generating improving solutions. A version of the approach for delivery problems has been implemented via a colorgraphics display. The human aided optimization procedure was tested on the standard 50-point, 75-point, and 100-point test problems of Eilon, Watson-Gandy, and Christofides [6]. In the case of the first two test problems, the procedure was able to generate the best known solutions. In the 100-point problem, a better solution was generated than the current best known solution. <s> BIB002 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP). The time constraints consist of upper bounds on: (1) the amount of time by which the pick-up or delivery of a customer can deviate from the desired pick-up or delivery time; (2) the time that a customer can spend riding in a vehicle. The algorithm uses a sequential insertion procedure to assign customers to vehicles and to determine a time schedule of pick-ups and deliveries for each vehicle. A flexible objective function balances the cost of providing service with the customers' preferences for pick-up and delivery times close to those requested, and for short ride times. Computational experience with the algorithm is described, including a run with a real database of 2600 customers and some 20 simultaneously active vehicles. The scenario for the application of the algorithm is also discussed in detail. <s> BIB003 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> We consider a single depot and a set of customers with known demands, each of which must be picked up and delivered at specified locations and within given time windows. We seek a route and a schedule for a single vehicle with known capacity, which minimizes the route duration, i.e., the difference between the arrival time and the departure time at the depot. We develop a local search method for this problem based on a variable-depth search, similar to the Lin-Kernighan algorithm for the traveling salesman problem. The method consists of two phases. In the first phase, a feasible route is constructed; in the second phase, it is iteratively improved. In both phases, we use a variable-depth search built up out of seven basic types of arc-exchange procedures. When tested on real-life problems, the method is shown to produce near-optimal solutions in a reasonable amount of computation time. In spite of this, there is the theoretical possibility that the method may end up with a poor or even infeasible solution. As a safeguard against such an emergency, we have developed an alternative algorithm based on simulated annealing. As a rule, it finds high quality solutions in a relatively large computation time. <s> BIB004 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper describes an insertion algorithm for the Vehicle Routing and Scheduling Problem with Time Windows (VRSPTW). This algorithm builds routes in parallel and uses a generalized regret measure over all unrouted customers in order to select the next candidate for insertion. Numerical results on the standard set of problems of Solomon are reported as well as comparisons with his sequential algorithm (Solomon, 1987). <s> BIB005 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract In this paper we propose a cheap yet effective extension to the traditional local improvement algorithm. We present this extension in the context of the Dial-A-Ride Problem, a variant of the Traveling Salesman Problem. This extension, which we call sacrificing , yields significant improvements over its plain local improvement counterpart without adversely affecting the algorithm's running time. <s> BIB006 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set of mini-clusters. Specifically, we present a new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation. To solve this problem we have enhanced an existing optimal algorithm in several ways. First, we present an original network design based on lists of neighboring transportation requests. Second, we have developed a specialized initialization procedure which reduces the processing time by nearly 40%. Third, the algorithm was easily generalized to multi-dimensional capacity. Finally, we have also developed a heuristic to reduce the size of the network, while incurring only small losses in solution quality. This allows the application of our approach to much larger problems. To be able to compare the results of optimization-based and local heuristic mini-clustering, we also present a parallel insertion approach to mini-clustering. Our computational results highlight the success of our approach. On test problems with up to 250 requests, our optimization-based method reduced the travel time within the mini-clusters by an average of 10% over the parallel insertion approach. Furthermore, for an actual problem with 2545 requests, a substantial 5.9% improvement in total traveling time was achieved over the heuristic. <s> BIB007 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface. <s> BIB008 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract This paper introduces a modernized version of many-to-few dial-a-ride called autonomous dial-a-ride transit (ADART), which employs fully-automated order-entry and routing-and-scheduling systems that reside exclusively on board the vehicle. Here, “fully automated” means that under normal operation, the customer is the only human involved in the entire process of requesting a ride, assigning trips, scheduling arrivals and routing the vehicle. There are no telephone operators to receive calls, nor any central dispatchers to assign trips to vehicles, nor any human planning a route. The vehicles' computers assign trip demands and plan routes optimally among themselves, and the drivers' only job is to obey instructions from their vehicle's computer. Consequently, an ADART vehicle fleet covers a large service area without any centralized supervision. In effect, the vehicles behave like a swarm of ants accomplishing their chore without anyone in charge. <s> BIB009 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This article describes a new composite heuristic for the symmetric Traveling Salesman Problem. The heuristic consists of three phases: construction of an initial envelope, insertion of the remaining vertices, and improvement procedure. The heuristic is shown to perform very well both on randomly generated instances and on TSPLIB problems. <s> BIB010 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract In this research, we develop a multiobjective vehicle routing and scheduling heuristic for a pickup and delivery problem. The problem contains time window, advanced request, multi-vehicle and many-to-many transport. In addition, the fleet size is not predetermined, and customers are allowed to transfer between vehicles. The objectives of scheduling are to minimize vehicle expense, tardiness and travel time. We propose a concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more than one customer to a vehicle at a time. It differs from the usual concurrent approach in three aspects: (i) it uses the look-ahead strategy to construct miniroute; (ii) it adopts the head/tail, head, and tail integration techniques; and (iii) it allows interactivity. The procedure takes full advantage of due time and travel time information and is implemented through a computer program. It is a one-phase heuristic that can be reiterated when necessary. We provide detailed programming procedures and present the computational results of the proposed algorithm through the real data. <s> BIB011 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> We present DRIVE (Dynamic Routing of Independent VEhicles), a planning module to be incorporated in a decision support system for the direct transportation at Van Gend and Loos BV. Van Gend and Loos BV is the largest company providing road transportation in the Benelux, with about 1400 vehicles transporting 160,000 packages from thousands of senders to tens of thousands of addressees per day. The heart of DRIVE is a branch-and-price algorithm. Approximation and incomplete optimization techniques as well as a sophisticated column management scheme have been employed to create the right balance between solution speed and solution quality. DRIVE has been tested by simulating a dynamic planning environment with real-life data and has produced very encouraging results. <s> BIB012 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> For a large urban area an alternative to public transportation and private cars is considered in the form of a "free" use of electric cars. Such "free" use of electric cars would require periodic redistribution of the cars among different dropoff/pickup stations by a fleet of finite capacity towtrucks stationed at the various depots on the road network. In this study we examine in detail the electric car redistribution problem. The redistribution activity is modelled as that of less than truck load, pickup and delivery with nonsimple paths, allowing for split pickups and deliveries. We propose a Mixed Integer Programming formulation of the problem and we test several solution which include constraint Programming, Lagrangian relaxation methodology applied to the MIP model, and an AI solution approach with a modified A* heuristic. The solution procedures here are designed to solve large practical instances of the car redistribution problem. <s> BIB013 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Telebus is Berlin’s dial-a-ride system for handicapped people who cannot use the public transportation system. The service is provided by a fleet of about 100 mini-buses and includes assistance in getting in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem is to schedule these requests onto the vehicles such that punctual service is provided while operation costs are minimized. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. <s> BIB014 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In this paper, we analyze algorithms for the online dial-aride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp. average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis. <s> BIB015 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Different versions of the dynamic Dial-A-Ride problem are found in every day practice; transportation of people in low-density areas, transportation of the handicapped and elderly persons and parcel pick-up and delivery service in urban areas. Carrier, which is providing the transportation service, receives calls for transportation. The problem is to assign every new passenger request to one of the vehicles and to design a new route and schedule for this vehicle. This assignment must be done in real time. Two approximate reasoning algorithms are developed in this paper. Using the first approximate reasoning algorithm we make the decision about which vehicle will accept the new request. The second developed approximate reasoning algorithm was used to design the new route and schedule for the vehicle chosen to serve the new request. The model developed has been tested on a greater number of different numerical examples. The results obtained are very promising. <s> BIB016 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> We consider a pickup and delivery vehicle routing problem commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple carriers and multiple vehicle types available to cover a set of pickup and delivery orders, each of which has multiple pickup time windows and multiple delivery time windows. Orders and carrier/vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which carrier/vehicle types and which orders cannot be shipped together. Order loading and unloading sequence must satisfy the nested precedence constraint that requires that an order cannot be unloaded until all the orders loaded into the truck later than this order are unloaded. Each vehicle trip must satisfy the driver's work rules prescribed by the Department of Transportation which specify legal working hours of a driver. The cost of a trip is determined by several factors including a fixed charge, total mileage, total waiting time, and total layover time of the driver. We propose column generation based solution approaches to this complex problem. The problem is formulated as a set partitioning type formulation containing an exponential number of columns. We apply the standard column generation procedure to solve the linear relaxation of this set partitioning type formulation in which the resulting master problem is a linear program and solved very efficiently by an LP solver, while the resulting subproblems are computationally intractable and solved by fast heuristics. An integer solution is obtained by using an IP solver to solve a restricted version of the original set partitioning type formulation that only contains the columns generated in solving the linear relaxation. The approaches are evaluated based on lower bounds obtained by solving the linear relaxation to optimality by using an exact dynamic programming algorithm to solve the subproblems exactly. It is shown that the approaches are capable of generating near-optimal solutions quickly for randomly generated instances with up to 200 orders. For larger randomly generated instances with up to 500 orders, it is shown that computational times required by these approaches are acceptable. <s> BIB017 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In this paper results on the dial-a-ride problem with a single server are presented. Requests for rides consist of two points in a metric space, a source and a destination. A ride has to be made by the server from the source to the destination. The server travels at unit speed in the metric space and the objective is to minimize some function of the delivery times at the destinations. We study this problem in the natural on-line setting. Calls for rides come in while the server is traveling. This models, e.g. the taxi problem, or, if the server has capacity more than a minibus or courier service problem. For the version of this problem in which the server has infinite capacity having as objective minimization of the time the last destination is served, we design an algorithm that has competitive ratio 2. We also show that this is best possible, since no algorithm can have competitive ratio better than 2 independent of the capacity of the server. Besides, we give a simple 2.5-competitive algorithm for the case with finite capacity. Then we study the on-line problem with objective minimization of the sum of completion times of the rides. We prove a lower bound on the competitive ration of any algorithm of 1 + 2 for a server with any capacity and of 3 for a server has infinite capacity and the metric space is the real line. The algorithm has competitive ration 15. Copyright 2001 Elsevier Science B.V. <s> BIB018 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract This paper deals with the pickup and delivery traveling salesman problem. First we show how to adapt some classical traveling salesman heuristics to solve this problem, then we propose a new and efficient composite heuristic. The proposed heuristic is composed of two phases: a solution construction phase including a local optimization component and a deletion and re-insertion improvement phase. To evaluate its performance, the proposed heuristic was compared to the only available heuristic specially designed to solve this problem, to an adaptation of the most efficient heuristic designed to solve the traveling salesman problem with backhaul, to an adaptation of the farthest as well as to an adaptation of the cheapest insertion methods. Each of these heuristics was followed by our deletion and re-insertion procedure which considerably improved their performance. Results based on a new set of test problems show that the proposed heuristic outperforms all these reinforced heuristics. Scope and purpose In several physical distribution problems, goods must be picked at an origin and delivered to a destination. Examples include the transportation of handicapped persons, the pickup and delivery of fast courier, of some medical supplies, etc. This problem differs from classical transportation problems because we have to deal with precedence constraints between the customers to be visited. This article describes a powerful heuristic for this difficult problem. <s> BIB019 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In on-line dial-a-ride problems, servers are traveling in some metric space to serve requests for rides which are presented over time. Each ride is characterized by two points in the metric space, a source, the starting point of the ride, and a destination, the end point of the ride. Usually it is assumed that at the release of such a request complete information about the ride is known. We diverge from this by assuming that at the release of such a ride only information about the source is given. At visiting the source, the information about the destination will be made available to the servers. For many practical problems, our model is closer to reality. However, we feel that the lack of information is often a choice, rather than inherent to the problem: additional information can be obtained, but this requires investments in information systems. In this paper we give mathematical evidence that for the problem under study it pays to invest. <s> BIB020 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract The LITRES-2 modelling system provides a framework for investigating the performance of urban passenger transport systems, with particular attention to demand-responsive transport modes and traveller information technologies. The modes covered include conventional timetabled services (buses, trains etc.), taxis (both single- and multiple-hire), and other demand-responsive services. Tables of estimated aggregate demand are disaggregated so as to produce a stream of fully-articulated travel-requests. Individual requests are resolved as single- or multiple-leg journeys, through the use of request-broking and journey-planning modules that seek to minimise travellers' generalised costs. Journey-legs allocated to demand-responsive modes are handled by a fleet-scheduling module which includes provision for “instantaneous” as well as advance-notice bookings, and for contingent situations such as breakdowns and passenger no-shows. The fleet-scheduling and journey-planning modules are designed as embedded control systems and are intended for use in real-time as well as modelling applications. The paper describes the main analytical and procedural components of LITRES-2, and assesses some methodological issues arising from experience in recent planning studies. The system appears to be well suited for use in modelling situations where the critical issues are concerned with the supply rather than demand side of transportation activity. <s> BIB021 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper deals with a generalisation of the well-knowntraveling salesman problem (TSP) in which cities correspond to customers providing or requiring known amounts of a product, and the vehicle has a given upper limit capacity. Each customer must be visited exactly once by the vehicle serving the demands while minimising the total travel distance. It is assumed that any unit of product collected from a pickup customer can be delivered to any delivery customer. This problem is calledone-commodity pickup-and-delivery TSP (1-PDTSP). We propose two heuristic approaches for the problem: (1) is based on a greedy algorithm and improved with ak-optimality criterion and (2) is based on a branch-and-cut procedure for finding an optimal local solution. The proposal can easily be used to solve the classical "TSP with pickup-and-delivery," a version studied in literature and involving two commodities. The approaches have been applied to solve hard instances with up to 500 customers. <s> BIB022 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In this paper we present a parallel regret insertion heuristic to solve a dial-a-ride problem with time windows. A new route initialization procedure is implemented, that keeps into account both the spatial and the temporal aspects of the problem, and a regret insertion is then performed to serve the remaining requests. The considered operating scenario is representative of a large-scale dial-a-ride program in Los Angeles County. The proposed algorithm was tested on data sets of 500 and 1000 requests built from data of paratransit service in this area. The computational results show the effectiveness of this approach in terms of trading-off solution quality and computational times. The latter measure being especially important in large-scale systems where numerous daily requests need to be processed. <s> BIB023 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> When considering innovative forms of public transport for specific groups, such as demand responsive services, the challenge is to find a good balance between operational efficiency and 'user friendliness' of the scheduling algorithm even when specialized skills are not available. Regret insertion-based processes have shown their effectiveness in addressing this specific concern. We introduce a new class of hybrid regret measures to understand better why the behaviour of this kind of heuristic is superior to that of other insertion rules. Our analyses show the importance of keeping a good balance between short- and long-term strategies during the solution process. We also use this methodology to investigate the relationship between the number of vehicles needed and total distance covered - the key point of any cost analysis striving for greater efficiency. Against expectations, in most cases decreasing fleet size leads to savings in vehicle mileage, since the heuristic solution is still far from optimality. <s> BIB024 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> The Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSP-PD)[1] can be defined on an undirected graph T=(V,E), where V is a set of n vertices and E is a set of edges. A nonnegative weight d(e) is associated with each edge e∈ E to indicate its length. Each vertex is either a pickup point, a delivery point, or a transient point. At each pickup point is a load of unit size that can be shipped to any delivery point which requests a load of unit size. Hence we can use a(v)=1,0,–1 to indicate v to be a pickup, a transient, or a delivery point, and a(v) is referred to as the volume of v. The total volumes for pickups and for deliveries are usually assumed to be balanced, i.e., $\sum_{v\in {\it V}}{\it a}({\it v})=0$, which implies that all loads in pickup points must be shipped to delivery points [1]. Among V, one particular vertex r ∈ V is designated as a depot, at which a vehicle of limited capacity of k ≥ 1 starts and ends. The problem aims to determine a minimum length feasible route that picks up and delivers all loads without violating the vehicle capacity. <s> BIB025 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract In this paper we present a new insertion-based construction heuristic to solve the multi-vehicle pickup and delivery problem with time windows. The new heuristic does not only consider the classical incremental distance measure in the insertion evaluation criteria but also the cost of reducing the time window slack due to the insertion. We also present a non-standard measure, crossing length percentage , in the insertion evaluation criteria to quantify the visual attractiveness of the solution. We compared our heuristic with a sequential and a parallel insertion heuristic on different benchmarking problems, and the computational results show that the proposed heuristic performs better with respect to both the standard and non-standard measures. <s> BIB026 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In the online dial-a-ride problem (OLDARP), objects must be transported by a server between points in a metric space. Transportation requests (rides) arrive online, specifying the objects to be transported and the corresponding source and destination. We investigate the OLDARP for the objective of minimizing the maximum flow time. It has been well known that there can be no strictly competitive online algorithm for this objective and no competitive algorithm at all on unbounded metric spaces. However, the question whether on metric spaces with bounded diameter there are competitive algorithms if one allows an additive constant in the definition competitive ratio, had been open for quite a while. We provide a negative answer to this question already on the uniform metric space with three points. Our negative result is complemented by a strictly 2-competitive algorithm for the Online Traveling Salesman Problem on the uniform metric space, a special case of the problem. <s> BIB027 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In this paper the first results on the Online Dial-A-Ride Problem with Time-Windows (ODARPTW for short) are presented. Requests for rides appearing over time consist of two points in a metric space, a source and a destination. Servers transport objects of requests from sources to destinations. Each request specifies a deadline. If a request is not be served by its deadline, it will be called off. The goal is to plan the motion of servers in an online way so that the maximum number of requests is met by their deadlines. We perform competitive analysis of two deterministic strategies for the problem with a single server in two cases separately, where the server has unit capacity and where the server has infinite capacity. The competitive ratios of the strategies are obtained. We also prove a lower bound on the competitive ratio of any deterministic algorithm of $\frac{2-T}{2T}$ for a server with unit capacity and of $\frac{2-T}{2T} \lceil \frac{1}{T} \rceil$ for a server with infinite capacity, where T denotes the diameter of the metric space. <s> BIB028 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Optimization algorithms for both path and tree topology classes of the one-commodity pickup and delivery travelling salesman problem (1-PDTSP) are proposed in this article, which focus on minimizing the route distance to transport products among pickup and delivery customers by a single vehicle with a limited capacity of k. Each pickup customer provides one unit volume of the product while each delivery customer requires one unit volume of the product. For the path case, we propose an O(n2s min (k,n)) algorithm for any arbitrary k, and two O(n) algorithms for k = 1 and k = ∞. For the tree case, O(n2) and O(n) algorithms are proposed for k = 1 and k = ∞, respectively. Moreover, when k is arbitrary, the problem becomes NP-hard in the strong sense. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 24–35 2006 <s> BIB029 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper examines the effects of constraining order circuity during the course of a dynamic pickup and delivery routing algorithm. Order circuity, the ratio of actual to direct shipping distance, affects shipping performance metrics such as transit time and vehicle utilization. The paper begins by exploring the tradeoff between utilization and order circuity, and then describes the application of circuity controls within an algorithm implemented for automobile shipping. We found that circuity controls are more effective than standard least-cost insertion heuristics alone in producing efficient route solutions with lower frequency of anomalous order routings. <s> BIB030 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In 2001, Caramia and his coauthors introduced a very fast and efficient heuristic for rooting a fleet of vehicles for dynamic combined pickup and delivery services [Caramia, M., Italiano, G.F., Oriolo, G., Pacifici, A., Perugia, A., 2001. Routing a fleet of vehicles for dynamic combined pickup and delivery services. In: Proceedings of the Symposium on Operation Research 2001, Springer-Verlag, Berlin/Heidelberg, pp. 3-8.]. The authors assume that every client names a stretch-factor that denotes the maximal relative deviation from the shortest path between pickup and delivery point. Waiting times are not allowed. As these assumptions are not very realistic, this paper now presents the results of adapting this algorithm to the dynamic pickup and delivery vehicle routing problem with several time windows. Waiting times of vehicles are admitted. Moreover, the computational results are considerably improved by local search techniques making use of free computational capacity. <s> BIB031 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> Abstract This work deals with a dynamic dial-a-ride problem with time window constraints. In particular, new unplanned requests for service may arise at a vehicle stop and the driver must decide in real-time whether to accept or reject them. For this problem, we have developed a two-phase insertion algorithm based on route perturbations: the first phase, which is run off-line when the vehicle moves between two successive stops, aims at creating a feasible neighborhood of the current route; while the second phase, which is run in real-time every time a new request occurs, inserts, when possible, the delivery stop of the new customer in the current route. <s> BIB032 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer. <s> BIB033 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> In this research we present the design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets. In the SDPDTWP each shipment is constrained with the earliest possible pickup time from the origin and the latest acceptable delivery time to a destination. Split-deliveries occur when two or more vehicles service the same origin or destination. The proposed heuristics were applied to both static and real-time data sets. The heuristics computed a solution, in a few seconds, for a static problem from the literature, achieving an improvement of 60% in distance in comparison to the published solution. In the real-time SDPDTWP problems, requests for pickup and delivery of a package, breakdown of a truck or insertion of a truck can occur after the vehicle has left the origin and is enroute to service the customers. Thirty data sets, each consisting of one to seven real-time customer or truck events, were used to test the efficiency of the heuristics. The heuristics obtained solutions to real-time data sets in under five seconds of CPU time. <s> BIB034 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Heuristics <s> This paper studies a dynamic dial-a-ride problem bearing complex constraints on a time-dependent network. A flexible scheduling scheme is proposed to dynamically cope with different stochastic events, such as the travelling time fluctuation, new requests, absences of customers, vehicle breakdowns, cancellations of requests, traffic jams and so on. A fast heuristic is proposed to re-optimize the schedule when a new event occurs. This heuristic consists of a properly organized local search strategy and uses a secondary objective function to drive the search out of local optima. Intensive computational simulations were carried out to evaluate the performance of this scheduling scheme and the influence of different stochastic factors. The simulation results of different scenarios with different percentage of dynamic requests reveal that this scheduling scheme can generate high quality schedules and is capable of coping with various stochastic events. <s> BIB035
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 BIB022 ). 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  , 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 BIB025 . 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 BIB029 . 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, BIB013 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  . Also other solution approaches are briefly 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 BIB004 . First, a feasible initial solution is constructed. Then, this solution is improved by exchange procedures maintaining feasibility at all times.  also propose a construction-improvement algorithm for the same problem. They use a double insertion construction heuristic improved by deletion and reinsertion (4-opt* BIB010 ). BIB019 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. BIB017 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. BIB026 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). (2006) transf., split min. UC TW BIB011 plus improvement heur. Swihart and Papstavrou (1999) solve a stochastic SPDP. They assume that new requests arrive according to a poisson process; pickup and delivery locations are uniformly distributed in the service region; and a single vehicle travels at constant speed in the Euclidean plane. The objective minimized is the expected time the requests remain in the system. They test three routing policies, a sectoring, a nearest neighbor and a stacker crane policy. The stacker crane policy refers to grouping arriving demands into contiguous sets of equal size and serving them according to the first-come-first-serve rule. Lower bounds on the expected time a request remains in the system under light and heavy traffic conditions are computed. Three online algorithms (REPLAN, IGNORE, and SMARTSTART) for a single server PDP are investigated in  . The objective considered is the completion time. In the literature the problem at hand is called online dial-a-ride problem. However, the denotation dial-a-ride problem is not used in the same way as defined in this survey. The term online is used whenever no request is know in advance. By means of competitive analysis, i.e. the online (no knowledge about the future) algorithm is compared to its offline (complete knowledge about the future) counterpart Bent, 2006, Jaillet and  , it can be shown that REPLAN and IGNORE are 5/2 competitive, while SMARTSTART has a competitive ratio of 2. BIB015 discuss the performance of REPLAN and IGNORE under reasonable load. BIB018 devise another 2-competitive algorithm for the same problem. A probabilistic version is investigated in (Coja-Oghlan et al., 2005) , the online problem minimizing maximum flow time in BIB027 . The first heuristic for the dynamic multi vehicle PDP is proposed in BIB012 . Their solution methodology called DRIVE (Dynamic Routing of Independent VEhicles) incorporates a branch and price algorithm based on a set partitioning problem formulation. It generates approximate solutions via incomplete optimization. The problem tackled is a ten days real life simulation. Up to 354 active requests are considered at the various re-optimization runs. BIB020 study the influence of restricted information on the multi server online PDP, i.e. the destination of a request is only revealed after the object has been picked up. Competitive ratios of two deterministic strategies (REPLAN and SMARTCHOICE) for the time window case are computed in BIB028 ). An insertion based heuristic for the dynamic multi vehicle PDP is discussed in BIB030 . It is combined with different types of order circuity control in order to increase the efficient utilization of the vehicle's capacity. Results for test instances with up to 2500 initial orders are reported. BIB031 present an adaptation of a heuristic algorithm to the dynamic PDPTW. It was initially designed for the dynamic DARP by Caramia et al. (2002) . In contrast to Caramia et al., they allow vehicle waiting times. To enhance the procedure an additional local search phase is introduced. This phase is initiated whenever a new request has been inserted and ends when the next request comes in. BIB031 report solutions to instances with up to 1000 requests, arriving at an average rate of one request per minute. BIB034 test their algorithm (see Table 2 ) also in a real-time setting, considering up to 159 requests. Over the last decades, a large number of heuristic algorithms have been proposed for the static DARP. Table 4 gives an overview of the various solution methods reported in chronological order, divided into single and multi vehicle approaches. A heuristic routing and scheduling algorithm for the SDARP using Bender's decomposition is described in (Sexton and Bodin, 1985a,b) . The scheduling problem can be solved optimally; the routing problem is solved with a heuristic algorithm. One of the first heuristic solution procedures for static multi vehicle DARP is discussed in BIB002 . They develop an interactive algorithm that follows the cluster first route second approach. It is based on a set partitioning formulation solved by means of column generation. The location-allocation subproblem is only solved approximately. However, user related constraints or objectives are not explicitly considered. The same applies to the work of BIB006 . BIB003 propose a sequential insertion procedure. First, customers are ordered by increasing earliest time for pickup. Then, they are inserted according to the cheapest feasible insertion criterion. The notion of active vehicle periods used. An optimization based mini-clustering algorithm is presented in BIB007 . It uses column generation to obtain mini-clusters and an enhanced initialization procedure to decrease processing times. As in ) also the case of multiple depots is considered. A multi-objective approach is followed in BIB008 . They discuss an insertion based algorithm called REBUS. The objectives considered are the total driving time, the number of vehicles, the total waiting time, the deviation from promised service times as well as cost. A classical cluster first route second algorithm is proposed in BIB014 . The clustering as well as the routing problem are modeled as set partitioning problems. The clustering problem can be solved optimally while the routing subproblems are solved approximately by a branch and bound algorithm (only a subset of all possible tours is used). Alfa (1986) HF min. RC TW, RT adapted heur. of BIB003 up to 49 req. Psaraftis (  HF min. RC TW, RD improved mini-clustering algorithm of up to 2411 req. Customer satisfaction is taken into account in terms of punctual service. Customer ride times are implicitly considered by means of time windows. A regret insertion algorithm for the static DARP is developed in BIB023 . First, all requests are ranked according to ascending pickup times. Some swaps in this order are allowed, giving preference to requests that might be difficult to insert later on, regarding their spatial location. The first m requests are used as seed customers, with m being the number of vehicles. All the remaining requests are inserted following a regret insertion strategy BIB005 . The regret insertion based process is also subject to analysis in a study by BIB024 ; in order to determine why the performance of this heuristic is superior to that of other insertion rules. Early heuristic algorithms for the dynamic DARP are discussed in BIB001 . Daganzo analyzes three different insertion algorithms. In the first the closest stop is visited next. The second consists in visiting the closest origin or the closest destination in alternating order. The third only allows the insertion of delivery locations after a fixed number of passengers have been picked up. Algorithm two results in higher waiting to ride time ratios than algorithm one. However, it will, in general, generate lower waiting times for equal ride times when compared to algorithm three. The dynamic case of the multi vehicle DARP is also studied in BIB009 . New transportation requests are assigned to clusters according to least cost insertion. Routes are then optimized using dynamic programming. Results for a real life problem instance are reported. BIB016 propose a two-stage fuzzy logic based heuristic algorithm. The first approximate reasoning heuristic decides which vehicle a new request is assigned to. The second heuristic handles the adjustment of the vehicle's route. Results for instances with up to 900 requests are reported. Another cluster first route second algorithm is proposed in (Colorni and Righini, 2001 ). Considering only the most urgent requests, the routing subproblems can be solved to optimality with a branch and bound algorithm. Caramia et al. (2002) use a dynamic programming algorithm to iteratively solve the single vehicle subproblems to optimality. Results for instances with up to 50 clients per hour are reported. Horn (2002a) provide a software environment for fleet scheduling and dispatching of demand responsive services. The system can handle advance as well as immediate requests. New incoming requests are inserted into existing routes according to least cost insertion. A steepest descent improvement phase is run periodically. Also automated vehicle dispatching procedures, to achieve a good combination of efficient vehicle deployment and customer service, are included. The system was tested in the modeling framework LITRES-2 BIB021 , using a 24-hours real life data set of taxi operations with 4282 customer requests. Another simulation environment to test solution methods for the dynamic DARP can be found in  . BIB032 propose a two-phase insertion heuristic. A simple insertion procedure allows for quick answers with respect to inclusion or rejection of a new customer. The initial solution is improved by means of local search using 2-opt arc swaps. Results for instances with a total of up to 50 (unexpected and expected) requests are reported. BIB035 propose a fast heuristic for the dynamic DARP. They consider travel time fluctuations, absent customers, vehicle breakdowns, cancellation of requests, traffic jams etc. To solve this complex problem situation the heuristic proposed in BIB033 is adapted to the dynamic case. For testing purposes several simulations under varying parameter settings are conducted. Up to 610 requests are considered with different proportions of them already known in advance.