Introduction to Pickup-and-Delivery Problems
Benchmark Instances and Solutions for 1-PDTSP and TSPPD
Instances Format
Benchmark Instances
Solutions Values
Benchmark Instances and Solutions for the m-PDTSP
Instances Format
Benchmark Instances
Solutions Values
Benchmark Instances and Solutions for the SD1PDTSP
Benchmark Instances
Solutions Values
Links
The theory of routing problems arose half a century ago, when a mathematical model was proposed for the Traveling Salesman Problem by Dantzig, Fulkerson and Johnson. A particular case of routing problems are the so called pickup-and-delivery problems where quantities of one or various products are moved between different localizations. These problems arise in several real-world applications. The last decades have seen the increase in the use of computers to solve these problems. However, the algorithms used in solving the problems are very important to the objective of obtaining good (or optimal) solutions. This justifies the scientific research dedicated to these algorithms.
In the literature there are many problems related to pickup-and-delivery products but they are different problems because they have different features (one commodity or various commodities, one vehicle or various vehicles, a commodity with a single origin or many origins, etc.). We summary the description of pickup-and-delivery problems in few lines.
The 1-PDTSP is a generalization of the TSP in which cities correspond to customers providing or requiring known amounts of a product, and the vehicle has a given capacity. Each customer must be visited exactly once by the vehicle serving the demands while minimizing the total travel distance. It is assumed that the product collected from the pickup customers can be supplied to the delivery customers and that the initial load of the vehicle coming out from the depot can be chosen to be any quantity. From the construction of this problem, we can observe that it has many practical applications, including an important application in the context of inventory repositioning. It has been introduced by Hernández-Pérez and Salazar-González: a first description of the 1-PDTSP is given in [8], an exact approach to solve instances with up to 50 customers is given in [9], reference [10] shows heuristics procedures, a branch-and-cut algorithm including several separation procedures is described in [7] solving instances with up to 100 customers and reference [13] describes a hybrid algorithm that combines the GRASP and VND metaheuristics. Zhao et al. [17] propose a Genetic Algorithm that on average gives better results. Finally, Mladenović et al. [18] describe a General Variable Neighborhood Search improving the best-known solution for all benchmark instances and solving instances with up to 1000 customers.Chalasani and Motwani [4] study the special case of the 1-PDTSP where the delivery and pickup quantities are all equal to one unit. This problem is called Q-delivery TSP where Q is the capacity of the vehicle. Anily and Bramel [1] consider the same problem and call it the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). Both articles propose worst-case heuristic algorithms for euclidian instances.
A closely related problem is known in literature as the Traveling Salesman Problem with Pickups and Deliveries (TSPPD). As in the 1-PDTSP, there are two types of customers, each one with a given demand and a vehicle with a given capacity originally stationed in the depot. Also travel distances are given. A novelty is that in the TSPPD the product collected from pickup customers is different from the product supplied to delivery customers. Moreover, the total amount of product collected from pickup customers must be delivered only to the depot, and the product collected from the depot must be delivered to the delivery customers. For example, this is the case when empty bottles must be collected from customers and taken to a warehouse and full bottles must be delivered from the warehouse to the customers. The TSPPD was introduced by Mosheiov [11]. Anily and Mosheiov [2] present approximation algorithms for the TSPPD, here renamed TSP with Delivery and Backhauls, and Gendreau, Laporte and Vigo [6] propose several heuristics tested on instances with up to 200 customers. Baldacci, Hadjiconstantinou and Mingozzi [3] deal with the same problem, here named TSP with Delivery and Collection constraints, and present an exact algorithm based on a two-commodity network flow formulation which was able to prove optimality of some TSPPD instances with 200 customers. An important remark is that the TSPPD instances can be transformed in 1-PDTSP instances, hence the algorithms of the 1-PDTSP can be used to solve the TSPPD. Articles [9], [10] and [7] show as these the algorithms of the 1-PDTSP have a good performance over TSPPD instances. Although they are not built specifically for the TSPPD.
The generalization of the 1-PDTSP from one to m commodity is called the multi-commodity Pickup-and-Delivery Traveling Salesman Problem (m-PDTSP). In the m-PDTSP, we cannot divide the set of customers into pickup customers and delivery customers because a customer could collect some units of a product and supply some units of other different products. The m-PDTSP was introduced by Hernández-Pérez and Salazar-González [15]. They proposed a Mixed Integer Linear Programming model and described a branch-and-cut algorithm able to solve instances with up to 30 customers and 3 commodities. Since exact algorithms are only able to cope with small instances, Hernández-Pérez, Rodríguez-Martín and Salazar-González present heuristic approaches in [16] which tackle instances with up 400 customers and 5 products.
The particular problem where each commodity has only one origin and one destination is called one-to-one m-PDTSP. It can be considered as a Dial-a-Ride routing problem without time window requirements. The one-to-one m-PDTSP assumes that the load of the vehicle when leaving the depot is zero, unless the depot is the source of a commodity. Hernández-Pérez and Salazar-González [14] describe an exact algorithm for the one-to-one m-PDTSP solving instances involving up to 24 customers and 15 commodities. Rodríguez-Martín and Salazar-González [19] propose and compare several metaheuristic approaches to solve instances with up to 300 customers and 600 commodities.
Another generalization of the 1-PDTSP allows to visit each location more than once. We have called this problem Split Delivery One-Commodity Pickup-and-Delivery Traveling Salesman Problem (SD1PDTSP) but it is also called in the literature Static Bike Rebalance Problem (SBRP) because of its application to Bike Sharing Systems. However, there are many variants of this problem considering: 1) The number of visits are upper limited or not; 2) locations with zero demand must be visited or only if it is convenience; 3) the initial load of the vehicle is unfixed, bounded or fixed; 4) locations can be used to collects or deliver product temporarily (preemption). Salazar-González and Santos-Hernández [20] introduce SD1PDTSP and present and branch-and-cut algorithm. They consider that the number of visits to each location is limited, locations with zero demand must be visited, the initial load of the vehicle is unfixed and preemption. Chemla et al. [21] introduce another problem called Single Vehicle One-commodity Capacitated Pickup and Delivery Problem (SVOCPDP), very similar to the SD1PDTSP. The difference is in the initial load of the vehicle when leaving the depot, which in the SVOCPDP is assumed to be zero (the depot is assumed to have no commodity when the route starts). They propose effective upper and lower bounding procedures, but did not implement an exact approach. The upper bounding procedure is a tabu search algorithm, the lower bounding procedure is a branch-and-cut algorithm to solve a relaxed model. Erdogan et al. [22] introduce another variant called Static Bicycle Rebalancing Problem (SBRP), where the initial load of the vehicle is unfixed but upper limited by the initial inventory level at the depot. They propose a branch-and-cut algorithm using Combinatorial Benders' cuts solving instances with up to 60 customers, and extended their algorithm to the non-preemptive SBRP, reported in the article to be significantly harder than the SBRP. Cruz et al. [23] describe an iterated local search approach to find heuristic solutions of the SBRP, tested on instances with up to 100 customers. SVOCPDP and SBRP have no limit on the maximum number of visits to a customer, and customers with zero demand are not required to be visited. Hernández-Pérez and Salazar-González [24] present another branch-and-cut-algorithm that is capable of solving the SD1PDTSP and all its variants.They propose a new branch-and-cut algorithm to find optimal solutions. A master problem solves a relaxed Mixed Integer Programming model, i.e. a model allowing all feasible solutions but also some invalid ones. A subproblem checks the feasibility of the master solutions and generates valid cuts when they are infeasible. Computational results on benchmark instances demonstrate the good performance of the algorithm compared with others in the literature. In particular, this algorithm has much better results than the exact algorithm proposed in [20] and [22].
There are another many pickup-and-delivery problems described in the literature. We reference two surveys. Savelsbergh and Sol [12] present a survey of articles about pickup-and-delivery problems until 1995. Courdeau and Laporte [5] present a recent survey where articles which deal with Dial-A-Ride Problems (DARP) are classified. In the DARP there is a one-to-one correspondence between pickup customers and delivery customers (typically, the commodities transported in the DARP are people). The DARP have many variants depending on the different requirements, features and optimization functions.
NAME: is the name of the file. For example, for a 1-PDTSP instance n50q20A.tsp (50 is the number of customers (including the depot), 20 is the vehicle capacity and letter A depends of the seed). For the PDTSP instances the depot is duplicated (it is the first and the last nodes), hence, the name n50mosA.tsp is the same instance that the above but letters mos reference a PDTSP instance with the tightest capacity. All of them have extension .tsp
COMMENT: is a comment.
DIMENSION: is the number of vertices of the problem.
CAPACITY: is the vehicle capacity.
EDGE_WEIGHT_TYPE: is the type the norm used (in these instances EUC_2D).
NODE_COORD_SECTION: specifies the coordinates of the vertices.
DISPLAY_DATA_SECTION: can be ignored.
DEMAND_SECTION: specifies the quantities required from (negative values) or given to (positive values) the vehicle. The demands are random integer numbers in [-10,+10]
They are grouped into three collections (derived from the VRP, random Euclidean TSPPD and random symmetric TSPPD). They depend on an input parameter beta. See [5], for details on how these instances are generated, and in particular for the meaning of beta
We thank Daniele Vigo for providing us these instances.
| Instances | Description |
| TS2004t2.zip | Class 1. 1-PDTSP and TSPPD instances of Table 2 in [10] and 1-PDTSP instances of Table 1 in [13]. Small and medium instances (n=20,..,60). |
| TS2004t3.zip | Class 1. 1-PDTSP and TSPPD instances of Table 3 in [10] and 1-PDTSP instances of Table 2 in [13]. Large instances (n=100,...,500). |
| 1pdtspexaple1mos.zip | Class 1. 1-PDTSP and TSPPD instances of Table 1 in [7]. Note that there is a typo when the data of Example 1 of Mosheiov was transcribed. Customer 7 has coordinates (445.724, -383.012) instead of (455.724, -383.012). |
| N2005t3.zip | Class 1. 1-PDTSP and TSPPD instances of Table 3 in [7]. |
| eil.zip | Class 2. 1-PDTSP instances derived from the CVRP of Table 4 in [7]. |
| v_PDTSP.zip (TSPLIB format) vrp_Vigo.zip (Vigo´s format) |
Class 3. TSPPD instances derived form the VRP. They are used in the values of Tables 1 and 2 in Gendreau, Laporte, Vigo [6], Tables 1 and 4 in Baldacci, Hadjiconstantinou and Mingozzi [3], Table 4 in Hernández and Salazar [10], and Table 5 in Hernández and Salazar [7]. |
| e_PDTSP.zip (TSPLIB format) e_Vigo.zip (Vigo´s format) |
Class 3. Euclidian TSPPD instances generated by Gendreau, Laporte, Vigo [6]. They are used in Tables 3 and 4 in Gendreau, Laporte, Vigo [6], Tables 2 and 5 in Baldacci, Hadjiconstantinou and Mingozzi [3], Table 5 in Hernández and Salazar [10], and Table 6 in Hernández and Salazar [7]. |
| s_PDTSP.zip (TSPLIB format) s_Vigo.zip (Vigo´s format) |
Class 3. Symmetric TSPPD instances generated by Gendreau, Laporte, Vigo [6]. They are used in Tables 5 and 6 in Gendreau, Laporte, Vigo [6], Tables 3 and 6 in Baldacci, Hadjiconstantinou and Mingozzi [3], and Table 7 in Hernández and Salazar [7]. |
Instances of article Hernández and Salazar [9] have been generated with the same random generators, therefore, they have not been uploaded in this site.
| Solution files | Description |
| TS2004t2.sol | 1-PDTSP and TSPPD heuristic solutions of Table 2 in [10]. |
| TS2004t3.sol | 1-PDTSP and TSPPD heuristic solutions of Table 3 in [10]. |
| TS2004t4.sol | TSPPD heuristic solutions of Table 4 in [10]. |
| TS2004t5.sol | TSPPD heuristic solutions of Table 5 in [10]. |
| N2005t3.sol | 1-PDTSP and TSPPD optimal solutions of Table 3 in [7]. |
| N2005t4.sol | 1-PDTSP optimal solutions of Table 4 in [7]. |
| N2005t5.sol | TSPPD optimal solutions of Table 5 in [7]. |
| N2005t6.sol | TSPPD optimal solutions of Table 6 in [7]. |
| N2005t7.sol | TSPPD optimal solutions of Table 7 in [7]. |
| COR2008t1.sol | 1-TSPPD solutions of hybrid heuristic of Table 1 in [13]. |
| COR2008t2.sol | 1-TSPPD solutions of hybrid heuristic of Table 2 in [13]. |
NAME: is the name of the file. All of them have extension .tspThere are three classes of instances for the one-to-one m-PDTSP described in [14] and there are two classes of instances for the many-to-many m-PDTSP described in [15]. Large instances of the second class (for the many-to-many m-PDTSP) are used in [16].
COMMENT: is a comment.
DIMENSION: is the number of vertices (nodes) of the problem.
CAPACITY: is the vehicle capacity.
EDGE_WEIGHT_TYPE: is the type the norm used (EUC_2D, EXPLICIT, etc.).
DEMAND_DIMENSION: is the number of different products (i.e., m) NODE_COORD_SECTION: specifies the coordinates of the vertices.
DEMAND_SECTION: specifies the quantities required from (negative values) or given to (positive values) the vehicle of the m commodities. Each column k corresponds with a commodity for k = 1 ... m
| Instances | Description |
| 1to1class1.zip | one-to-one Class 1. Instances of Tables 1 and 4 in [14]. |
| 1to1class2.zip | one-to-one Class 2. Instances of Tables 2 and 5 in [14]. |
| 1to1class3.zip | one-to-one Class 3. Instances of Tables 3 and 6 in [14]. |
| example1mosheiov.zip | many-to-many Example 1 of Mosheiov. Instances of Table 2 in [15] and Table 5 in [16]. Note that there is a typo when the data of Example 1 of Mosheiov was transcribed. Customer 7 has coordinates (445.724, -383.012) instead of (455.724, -383.012). | mPDTSP_class1.zip | many-to-many Class 1. Instances of Table 3 in [15]. Intances with n=30 are used in Table 4 in [16] |
| mPDTSP_class2.zip | many-to-many Class 2. Instances of Table 4 in [15]. Intances with n=30 are used in Table 4 in [16] |
| mediummpdtsp.zip | many-to-many medium sizes. Instances of Table 3 in [16]. |
| largempdtsp.zip | many-to-many large sizes. Instances of Table 6 in [16]. |
| Solution files | Description |
| 1to1class1.sol | one-to-one Class 1. Solution values of Table 4 in [14]. |
| 1to1class2.sol | one-to-one Class 2. Solution values of Table 5 in [14]. |
| 1to1class3.sol | one-to-one Class 3. Solution values of Table 6 in [14]. |
| Network_mpdtsp_2014.sol | many-to-many Class 1 and 2. Solution values of Tables 2 and 3 in [15]. |
It is also called in the literature Static Bike Rebalance Problem (SBRP).
Instances are the same that the benchmark instances of the 1-PDTSP.
| Solution files | Description |
| EJOR_HS_2020_Table2.sol | Solution values of Table 2 in [24]. |
| EJOR_HS_2020_tables3_6.sol | Solution values of Tables 3--6 in [24]. |