Pickup-and-Delivery Site

Last update: 28th of March, 2020

This web page is devoted to Pickup-and-Delivery Problems. The main motivation for this page is to upload the random generated instances described in articles of Hipólito Hernández-Pérez, Inmaculada Rodríguez Martín and Juan-José Salazar-González. However, other information are shown also. If you have some question or advice you can write to hhperez@ull.es

Contents

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

Introduction to Pickup-and-Delivery Problems

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.

References

[1] S. Anily and J. Bramel. Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Naval Research Logistics, 46:654-670, 1999.

[2] S. Anily and G. Mosheiov. The traveling salesman problem with delivery and backhauls. Operations Research Letters, 16:11-18, 1994.

[3] R. Baldacci, E. Hadjiconstantinou and A. Mingozzi. An exact algorithm for the traveling salesman problem with deliveries and collections. Networks, 42:26-41, 2003.

[4] P. Chalasani and R. Motwani. Approximating capacitated routing and delivery problems. SIAM Journal on Computing, 28:2133-2149, 1999.

[5] J. F. Cordeau and G. Laporte. The dial-a-ride problem (DARP): Variants, modeling issues and algorithm. 4OR - Quarterly Journal of The Belgian, French and Italian Operations Research Societies, 1:89-101, 2003.

[6] M. Gendreau, G. Laporte, and D. Vigo. Heuristics for the traveling salesman problem with pickup and delivery. Computers & Operations Research, 26:699-714, 1999.

[7] H. Hernández-Pérez and J. J. Salazar-González. The one-commodity pickup-and-delivery traveling salesman problem: inequalities and algorithms. Networks, 4 (2007) 258-272.(Pdf of the technical report)

[8] H. Hernández-Pérez and J. J. Salazar-González. The one-commodity pickup-and-delivery travelling salesman problem. In M. Jünger, G. Reinelt, and G. Rinaldi, editors, Combinatorial Optimization-Eureka, You Shrink!, volume 2570, pages 89-104. Lecture Notes in Computer Science, Springer, 2003.

[9] H. Hernández-Pérez and J. J. Salazar-González. A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Applied Mathematics, 145:126-139, 2004.(The most downloaded article in Discrete Applied Mathematics from January - December 2004)

[10] H. Hernández-Pérez and J. J. Salazar-González. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science, 38(2):245-255, 2004.

[11] G. Mosheiov. The traveling salesman problem with pickup and delivery. European Journal of Operational Research, 79:299-310, 1994.

[12] M. W. P. Savelsbergh and M. Sol. The general pickup and delivery problem. Transportation Science, (29):17-29, 1995.

[13] H. Hernández-Pérez, I. Rodríguez-Martín and J. J. Salazar-González. A hybrid GRASP/VND heuristic for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Computers & Operations Research, 36 - 5, pp. 1639 - 1645. 2009. (Pdf of the technical report)

[14] H. Hernández-Pérez, J. J. Salazar-González. The multi-commodity one-to-one pickup-and-delivery traveling salesman problem. European Journal of Operational Research, 196 (3), pp. 987 - 995, 2009. (Pdf of a revised version)

[15] H. Hernández-Pérez and J. J. Salazar-González. The multi-commodity pickup-and-delivery traveling salesman problem. Networks, 63 (1), pp 46 - 59, 2014. (Pdf of a revised version)

[16] H. Hernández-Pérez, I. Rodríguez-Martín and J. J. Salazar-González. A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem. European Journal of Operational Research, 251 (1), 44 - 52, 2016. (Pdf of a revised version)

[17] F. Zhao, S. Li, J. Sun, and D. Mei. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Computers and Industrial Engineering, 56(4), pp. 1642-1648, 2009.

[18] N. Mladenović, D. Urošević, S. Hanafi, and A. Ilić. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, 220(1), 270-285, 2012.

[19] I. Rodríguez-Martín and J. J. Salazar-González. A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem. Journal of Heuristics, 18(6), pp. 849-867, 2011.

[20] J. J. Salazar-González, B. Santos-Hernández. The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transportation Research Part B: Methodological 75, pp. 58-73, 2015.

[21] D. Chemla, F. Meunier, R. Wolfler-Calvo. Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization 10 (2), 120-146, 2013.

[22] G. Erdogan, M. Battarra, R. Wolfler Calvo. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. European Journal of Operational Research 245, 667–679, 2015.

[23] F. Cruz, B. P. Bruck, A. Subramanian, M. Iori. A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Computers and Operations Research 79, 19–33, 2017.

[24] H. Hernández-Pérez and J. J. Salazar-González. A Branch-and-Cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem. Submitted to Transportation Research Part B: Methodological, 2020.(Pdf of the technical report)


Benchmark Instances and Solutions for 1-PDTSP and TSPPD

Instances Format

The random generated PDTSP and 1-PDTSP instances are divided in three classes:

Benchmark 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.

Solutions Values

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].

Benchmark Instances and Solutions for the one-to-one and many-to-many m-PDTSP

Instances Format

NAME: is the name of the file. All of them have extension .tsp
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
There 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].

Benchmark Instances

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].


Solutions Values

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].

Benchmark Instances and Solutions for the Split Delivery One-Commodity Pickup and Delivery Traveling Salesman problem (SD1PDTSP)

It is also called in the literature Static Bike Rebalance Problem (SBRP).

Benchmark Instances

Instances are the same that the benchmark instances of the 1-PDTSP.

Solutions Values

Solution files Description
TRB_HS_2020_Table2.sol Solution values of Table 2 in [24].
TRB_HS_2020_tables3_6.sol Solution values of Tables 3--6 in [24].

Links

Institutional WEB sites

Personal WEB sites


Valid HTML 4.01 Transitional