A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> Abstract In the transportation and distribution sector, the task of dispatching and controlling vehicles in real time is becoming increasingly complex. The task requires complex perceptual and cognitive abilities that are often applied under a high level of stress. At the same time, the task has never been so important for the economic viability and efficiency of many transportation companies, including freight transportation, courier services, emergency vehicle dispatching, transportation of handicapped persons, and many others. In this context, the development of an expert consultant for an advanced computer-aided dispatching system is essential. This paper proposes learning by examples as a means to uncover the human expertise in this domain. We investigate and compare two techniques based on linear programming and neural network models. Experimental results are reported on real data from a courier service company. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> Abstract Ejection chain procedures are based on the notion of generating compound sequences of moves, leading from one solution to another, by linked steps in which changes in selected elements cause other elements to be “ejected from” their current state, position or value assignment. This paper introduces new ejection chain strategies designed to generate neighborhoods of compound moves with attractive properties for traveling salesman problems. These procedures derive from the principle of creating a reference structure that coordinates the options for the moves generated. We focus on ejection chain processes related to alternating paths, and introduce three reference structures, of progressively greater scope, that produce both classical and non-standard alternating path trajectories. Theorems and examples show that various rules for exploiting these structures can generate moves not available to customary neighborhood search approaches. We also provide a reference structure that makes it possible to generate a collection of alternating paths that precisely expresses the symmetric difference between two tours. In addition to providing new results related to generalized alternating paths, in directed and undirected graphs, we lay a foundation for achieving a combinatorial leverage effect, where an investment of polynomial effort yields solutions dominating exponential numbers of alternatives. These consequences are explored in a sequel. <s> BIB002 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> We examine the problem of determining an optimal schedule for a fleet of vehicles used to cover the trips required to transport handicapped persons in an urban area. The problem is a generalization of the well-known Pickup and Delivery Problem with Time Windows since, due to the high level of service required by this kind of transport, many additional operational constraints must be considered. We describe fast and effective local search refining procedures, based on trip movements and exchanges, which can be used to improve within acceptable computing time the solutions of large-size instances obtained by using a parallel insertion heuristic algorithm. The procedures have been successfully applied to a set of large real-life problems for the town of Bologna, involving about 300 trips each, showing the effectiveness of the proposed approach. <s> BIB003 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> This paper presents a novel approach to solving the single-vehicle pickup and delivery problem with time windows and capacity constraints. While dynamic programming has been used to find the optimal routing to a given problem, it requires time exponential in the number of tasks. Therefore, it often fails to find the solutions under real-time conditions in an automated factory. This research explores anytime problem solving using genetic algorithms. By utilizing optimal but possibly partial solutions from dynamic programming, the hybrid genetic algorithms can produce near-optimal solutions for problems of sizes up to 25 percent bigger than what can be solved previously. This paper reports the experimental results of the proposed hybrid approach with four different crossover operators as well as three mutation operators. The experiments demonstrated the advantages of the hybrid approach with respect to dynamic task requests. <s> BIB004 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> In this article we present a new solution approach for a specific online pickup and delivery problem as it occurs in a real-world dispatching task of electric monorail load carriers. The presented optimization module adapts the communication structure of the respective IT components of the warehouse system to facilitate an easy integration. Numerical results are presented comparing steepest descent as well as reactive tabu search and simulated annealing with the dispatching system used so far. Tests are performed on the basis of a detailed simulation model of the entire warehouse and show a clear superiority for this approach. <s> BIB005 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> In the Dial-a-Ride problem (DARP) users specify transportation requests between origins and destinations to be served by vehicles. In the dynamic DARP, requests are received throughout the day and the primary objective is to accept as many requests as possible while satisfying operational constraints. This article describes and compares a number of parallel implementations of a Tabu search heuristic previously developed for the static DARP, i.e., the variant of the problem where all requests are known in advance. Computational results show that the proposed algorithms are able to satisfy a high percentage of user requests. <s> BIB006 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> Purpose – To propose and to evaluate a new genetic algorithm (GA) for solving the dynamic pickup and delivery problem with time windows (DPDPTW).Design/methodology/approach – First, a grouping genetic algorithm (GGA) for the (static) PDPTW is described. In order to solve the dynamic problem, the GGA then is embedded in a rolling horizon framework. Special updating mechanisms are provided which assure that reusable solution knowledge is preserved over the plan revisions. The approach is evaluated using a large number of test instances with varying degrees of dynamism.Findings – The experimental results have demonstrated that the proposed approach is able to find high‐quality solutions when compared with two comparative heuristics.Research limitations/implications – Future research will be dedicated to the following issues: testing the proposed method using larger problem instances, using more sophisticated objective functions in order to further improve and evaluate the approach, integrating fast local sea... <s> BIB007 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> This paper proposes neighborhood search heuristics to optimize the planned routes of vehicles in a context where new requests, with a pick-up and a delivery location, occur in real-time. Within this framework, new solutions are explored through a neighborhood structure based on ejection chains. Numerical results show the benefits of these procedures in a real-time context. The impact of a master–slave parallelization scheme, using an increasing number of processors, is also investigated. <s> BIB008 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> Metaheuristics <s> The vehicle routing problem with pickup and delivery and time windows (VRPPDTW) is one of the prominent members studied in the class of rich vehicle routing problems and it has become one of the challenges for developing heuristics which are accurate and fast at the same time. Indirect local search heuristics are ideally suited to flexibly handle complex constraints as those occurring in rich combinatorial optimization problems by separating the problem of securing feasibility of solutions from the objective-driven metaheuristic search process using simple encodings and appropriate decoders. In this paper we show that the approach of indirect local search with greedy decoding (GIST) is not only flexible and simple but when applied to the VRPPDTW it also gives results which are competitive with state-of-the-art VRPPDTW-methods by Li and Lim, as well as Pankratz. <s> BIB009
A two-stage hybrid algorithm for the static PDPTW is presented in . The first phase uses simulated annealing to decrease the number of vehicles needed. The second phase consists of a large neighborhood search algorithm in order to reduce total travel cost. BIB009 discuss an indirect (evolutionary) local search heuristic for the same problem. In indirect search solutions are encoded such that the problem of securing feasibility is separated from the metaheuristic search process. Here a greedy decoding is used. A population based metaheuristic approach, namely a hybrid genetic algorithm, for the dynamic SPDP with TW is proposed in BIB004 . It is called hybrid, as the genetic algorithm is combined with a dynamic programming algorithm. The data sets used for testing purposes consist of up to 50 requests. Early research on dynamic multi vehicle PDP is conducted in and . Both articles focus on neural networks with learning capabilities to support vehicle dispatchers in real-time. In the neural network based learning techniques are compared to a linear programming based method. Real life data sets with 200 and 140 requests are used in , respectively, to assess the performance of their algorithms. BIB001 conclude that the neural network performed better than the linear programming model. The first neighborhood based metaheuristic solution method for the dynamic multi vehicle PDPTW is presented in  . The neighborhood used is of the request-to-vehicle-assignment type. To accelerate the search an elimination matrix is used. It memorizes the compatibility of two requests. Thus, only promising moves are considered. The proposed procedure is tested on some adapted instances of . A two-phase solution procedure for the dynamic PDPTW is described in . In the first phase an initial solution is constructed via cheapest insertion. This solution is improved by means of a tabu search algorithm. In the second phase different waiting strategies are used to schedule the requests. The waiting strategies tried are referred to as drive first, wait first, dynamic waiting, and advanced dynamic waiting. They differ regarding the vehicle's location when waiting occurs. In the drive first strategy, the vehicle leaves every vertex as early as possible. If it arrives too early at the subsequent stop it waits there until service is viable. When using the wait first strategy, the vehicle leaves every vertex as late as possible with respect to time windows of subsequent vertices. Dynamic waiting refers to a strategy where customers are clustered according to time windows. The vehicle waits as long as possible before moving on to the first customer of the next cluster. Advanced dynamic waiting denotes a strategy where waiting time before visiting the first cluster depends on the latest possible time to begin service at the last cluster, without violating time windows at intermediate clusters. report solutions to problem instances with a total of up to 1000 requests, all occurring during the service period. The results indicate that the advanced dynamic waiting strategy is the most efficient. Advanced dynamic waiting is also used by in a double horizon based heuristic. The routing part is solved by means of a construction heuristic improved by tabu search. Scheduling is conducted according to advanced dynamic waiting. Routes are segmented. The first segment corresponds to the short term horizon, the remainder of the route to the long term horizon. Also the case of several depots is considered. Again instances with a total of up to 1000 requests are solved. BIB005 compare a steepest descent, a reactive tabu search, and a simulated annealing algorithm. They solve the dynamic PDP on an electric monorail system. The best results are obtained with the tabu search algorithm. In BIB007 ) a grouping genetic algorithm for the static PDP is embedded in a rolling horizon framework in order to solve the dynamic PDPTW. It is tested on data sets with different degrees of dynamism. Another tabu search algorithm for the dynamic multi vehicle PDPTW was proposed by BIB008 . It uses an ejection chain neighborhood BIB002 , i.e. one request is removed from its current route and inserted into another route, forcing the ejection of a request on this route to a third route, and so on. A lateness criterion is incorporated into the objective function. To speed up the optimization procedure a parallel implementation is conducted. The resulting program is tested on simulations over 7.5 hours with 20 vehicles and 23 requests per hour, and over four hours with ten vehicles and 33 requests per hour. Also metaheuristic solution methods have been developed for the static DARP. Table 5 provides an overview of the different algorithms proposed. For each reference the same information as in the previous tables is given. Toth and Vigo (1997) describe a local search based metaheuristic, i.e. a tabu thresholding algorithm, for the static multi vehicle DARP. It employs the neighborhoods defined in BIB003 . Initial solutions are constructed using parallel insertion. Cordeau and Laporte (2003b) develop a tabu search algorithm. Time windows are considered at either origin or destination depending on the type of request (inbound or outbound). The neighborhood used is defined by moving one request to another route. The best possible move serves to generate a new incumbent solution. Reverse moves are declared tabu. However, an aspiration criterion is defined, such that tabu moves that provide a better solution, with respect to all other solutions already constructed by the same move, can constitute a new incumbent solution.  Metaheuristic solution methods have not been explicitly developed for the dynamic DARP, since short response times are necessary in dynamic settings. Only one algorithm developed for the static version has been used to solve the dynamic case. The tabu search of Cordeau and Laporte (2003b) is adapted to the dynamic DARP by means of parallelization BIB006 . Different parallelization strategies are tested on instances with up to 144 requests.