A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem

A Branch-and-cut algorithm for the One-commodity Pickup and Delivery Location Routing Problem Bencomo Dom´ınguez-Mart´ın1,a, Hip´olito Hern´andez-P´erez2,a, Jorge Riera-Ledesma3,b, Inmaculada Rodr´ıguez-Mart´ın4,a,∗ 1b[email protected] 2hhp[email protected] 3[email protected] 4[email protected] aDepartamento de Matem´aticas, Estad´ıstica e Investigaci´on Operativa, Universidad de La Laguna, Spain bDepartamento de Ingenier´ıa Inform´atica y de Sistemas, Universidad de La Laguna, Spain ∗Corresponding Author: Inmaculada Rodr´ıguez-Mart´ın Departamento de Matem´aticas, Estad´ıstica e Investigaci´on Operativa Facultad de Ciencias, Universidad de La Laguna P.O. box 456, 38200 La Laguna, Tenerife, Spain Tel: +34 922 31 91 85 Email: [email protected] Abstract This paper introduces a new problem that combines characteristics of the Location and Routing Problem and the One-commodity Pickup and Delivery Traveling Salesman Problem. We are given a set of customers that provide or demand given amounts of a product, and a set of potential facility locations that can be opened or not in order to give service to the customers. Each facility has an opening cost and is the depot of a vehicle with capacity Q. The problem consists in deciding which facilities to open, assigning customers to open facilities, and designing the routes that connect each facility with its customers. The objective is to minimize the sum of the cost of the routes and the facilities. This NP-hard problem has not been previously studied. We propose for it two mathematical formulations, compare them, and present a branch-and-cut algorithm able to solve instances with up to 100 nodes. Keywords: Routing, location, pickup and delivery, branch-and-cut 1 Introduction This paper addresses a problem that combines aspects of two classical optimization problems: the Location and Routing Problem and the One-commodity Pickup and Delivery Traveling Salesman Problem. In particular, the One-commodity Pickup and Delivery Location Routing Problem (1-PDLRP) studied in this paper is defined as follows. We are given a set of potential site locations where a facility, consisting of a depot or base for a capacitated vehicle, can be established, and a set of customers that provide or demand certain amounts of a commodity. Establishing a facility at a certain location has a fixed cost. In order to serve the customers, each of them must be assigned to an open facility and it must be in the route of the vehicle based at that facility. All customers have to be visited exactly once, and the commodity collected at a customer can be supplied to another. The objective of the problem is to decide the facilities to open and to design the routes of the vehicles, so that all customers demands are satisfied and the sum of the routing costs and facility costs is minimized. To further illustrate the problem, we show in Figure 1 the optimal solution of the 1-PDLRP for a particular instance named n20 with 20 nodes located in the plane, 15 customers (nodes 0 to 14) and 5 potential facility locations (nodes 15 to 19). The number next to a customer node represents its demand, the routing costs are equal to the rounded Euclidean distances, the opening cost for all the facilities is 100, and all vehicles have capacity 20. We can see that only two facilities are open in the optimal solution (18 and 19). The load of the vehicle that traverses an arc is the figure next to the arc. Figure 2 shows the optimal solution for the same instance when the capacity of the vehicles is set to 10. In this case, we observe that three facilities have to be open in order to serve the customers (16, 17, and 18), and that there is an increment of around 7.3% in the solution cost. Note also the effect of the capacity restrictions on the routes. The 1-PDLRP is an extension of the One-commodity Pickup and Delivery Traveling Salesman Problem in which not one but several potential facility locations are considered. So it can have similar applications, i.e., applications in transportation problems where only one type of commodity is transported, and the cargo collected at pickup customers can be delivered to delivery customers. The typical example is encountered in a bike sharing system (see Dell’Amico et al. (2014)), and nowadays it could comprise also an electric scooters sharing system. In any 1 case, consider, for example, a situation where a company in this sector operates in a large city. The company has many small parking places for its bikes/scooters distributed all over the city. The users have to choose through a web site or app where they want to collect and drop off a bike or scooter, usually at least a day before using the service, so this information is known in advance by the company. It may happen that, at the beginning of the day, some parking places need to be provided with extra units in order to cover the demand of that day, while in some other parking places there are more units than requested. The units have then to be transported from some parking places to others using a vehicle. Let us suppose that the company has a main depot, maybe in an industrial area outside the city, and a fleet of small vehicles, such as vans, to transport the bikes/scooters. In a large city, it may be convenient to send the vans directly to certain locations early in the morning, so that each van can then make a route from that point to serve the parking places in the area. The cost of sending a van directly from the central depot to a location can be considered the cost of establishing a facility in that point. The objective is to decide to which points to send the vans, assign the parking places to the vans, and design the routes for the vans, so that all the parking places are provided with the necessary number of bikes/scooters to satisfy the users that day, at minimum cost. As the technology advances, other applications for the 1-PDLRP will for sure appear, for example, in transportation systems with aerial drones (see Kim et al. (2017)), where drone bases and routes have to be determined, or in the transportation of goods with automatic guided vehicles or robots inside a factory (see Almeida et al. (2010)). 1.1 Related literature As commented before, the 1-PDLRP is an extension of the One-commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP) that combines the features of this problem and the Location and Routing Problem (LRP). The One-commodity Pickup and Delivery Traveling Salesman Problem is a well known routing problem where each customer provides or requires given amounts of a single product, and these demands must be served by a capacitated vehicle located at a depot. The product collected at pickup customers can be delivered to delivery customers. The objective is to design a minimum cost Hamiltonian route for the vehicle such that all the demands are satisfied. This problem was introduced in Hern´andez-P´erez and Salazar-Gonz´alez (2004a), where a branch-andcut algorithm capable of solving to optimality instances with up to 60 customers was presented. This branch-and-cut algorithm was enhanced in Hern´andez-P´erez and Salazar-Gonz´alez (2007) including new valid inequalities. On the other hand, heuristic algorithms for the 1-PDTSP have been proposed in Hern´andez-P´erez and Salazar-Gonz´alez (2004b), Zhao et al. (2009) and Mladenovi´c et al. (2012). Several recent papers have studied a generalization of the 1-PDTSP consisting in allowing to visit each location more than once. This problem, known as the Split-Demand 1-PDTSP, has also been applied to rebalancing bike sharing systems (see Dell’Amico et al. (2014), Chemla et al. (2013), Erdo˘gan et al. (2015), Salazar-Gonz´alez and Santos-Hern´andez (2015), and Cruz et al. (2017)), and has several variants depending, for example, on whether customers can be used to temporarily store product (see Hern´andez-P´erez and Salazar-Gonz´alez (2022)). 2 0 -7 1-3 2 -3 3 -1 4 10 5 6 6 3 7 -5 81 9 110 9 11 4 12 -3 13 -6 14 4 15 16 17 18 19 0 1 5 8 4 13 17 16 13 14 11 8 3 13 7 0 6 Figure 1: Optimal solution of instance n20 with Q= 20 (cost: 3587) 3 0 -7 1-3 2 -3 3 -1 4 10 5 6 6 3 7 -5 81 9 110 9 11 4 12 -3 13 -6 14 4 15 16 17 18 19 2 8 5 0 10 4 1 9 0 1 5 8 0 4 1 2 1 10 Figure 2: Optimal solution of instance n20 with Q= 10 (cost: 4141) 4 Another variant of the 1-PDTSP is the single-vehicle Two-Echelon One-Commodity Pickup and Delivery Problem, where not all customers need to be visited by the vehicle but, instead, they can be allocated to visited customers (see Hern´andez-P´erez et al. (2021)). More variants of pickup and delivery problems can be found in the extensive reviews by Berbeglia et al. (2007), Parragh et al. (2008a), Parragh et al. (2008b), Battarra et al. (2014), and Ko¸c et al. (2020). On the other hand, the Location and Routing Problem is another classical optimization problem where, given a set of potential facility locations with opening costs, a fleet of identical vehicles, and a set of customers with known demands, the objective is to open a subset of facilities, assign customers to them, and determine vehicle routes, in order to minimize the sum of the costs of the routes and the open facilities. The version of this problem with a single vehicle at each facility was studied by Labb´e et al. (2004), who presented an exact branch-andcut algorithm to solve the case with unit demands, and by Albareda-Sambola et al. (2005), who developed a heuristic method. Many other different variants of the LRP can be found in the literature, and we refer the interested reader to the surveys by Nagy and Salhi (2007) and Prodhon and Prins (2014). In the literature, we have found only one problem that combines simultaneous pickup and delivery and LRP. This problem is the Location-Routing Problem with Simultaneous Pickup and Delivery (LRPSPD) introduced by Karaoglan et al. (2011). The LRPSPD is a LRP where each customer has a pickup and a delivery demand, simultaneously, and both demands have to be satisfied by the vehicle visiting the customer. It can be considered that each customer demands a given product, and supplies another product. The classic example given in the literature relates to the distribution of a drink, in which full bottles have to be delivered and empty bottles have to be collected. Another example arises in a rural area where a vehicle from a local store distributes liquid plant fertilizer to the farms, and collects vegetables from them, simultaneously. In any case, note that in the LRPSPD two different types of products have to be transported: one of the products is transported from the depots to the customers, and the other one is collected at the customers and transported to the depots. However, in the 1-PDLRP there is a single type of commodity to be transported, and the product collected at pickup customers can be supplied to delivery customers. Karaoglan et al. (2011) proposed an exact branch-andcut algorithm to tackle the LRPSPD. In a second paper, Karaoglan et al. (2012) presented two other mathematical formulations for the problem, and described a two-phase heuristic approach based on simulated annealing. Neither of the two problems, the LRPSPD and the 1-PDLRP, is a special case of the other. To see this, consider a simple case with a single depot and a vehicle of capacity 5, and three customers: customer 1 demands 5 units of product, customer 2 supplies 5 units, and customer 3 demands 5 units. If the product collected and supplied is the same, and it can be taken from pickup to delivery customers, that is, if the problem is a 1-PDLRP, then a feasible solution is a route in which the vehicle leaves the depot with 5 units of product, and visits customers 1, 2, and 3, in that order, before returning to the depot. The vehicle is empty after visiting customer 1, full loaded after visiting customer 2, and empty again after visiting customer 3. However, if we consider that the product to be collected is different from the product to be delivered (that is, if the problem to be solved is the LRPSPD), then there is no feasible solution for this example. So, the 1-PDLRP can not be transformed into the LRPSPD. 5 The particular case of the LRPSPD with a single vehicle is known in the literature as the Traveling Salesman Problem with Pickup and Delivery or TSPPD (see Mosheiov (1994)). Hern´andez-P´erez and Salazar-Gonz´alez (2004a) showed that the TSPPD can be transformed into the 1-PDTSP (the special case of the 1-PDLRP with one vehicle). The key point in this transformation is that, in the TSPPD, the total amount of demand that has to be delivered by the vehicle, and the total amount of demand that has to be collected, are known. However, in the general LRPSPD, this information is not known since there are several vehicles, and the customers to be visited by each of them are ignored in advance. Therefore, it is not possible to use the same mechanism to transform the LRPSPD into the 1-PDLRP. 1.2 Contribution To the best of our knowledge, the 1-PDLRP, as stated in this paper, has not been studied before, although related problems appear in the literature. In this sense, the study of the 1-PDLRP contributes to close the research gap in a field, the transportation and distribution of goods, which is undoubtedly of great interest. We present in this paper two mathematical models for the problem, a classical one that uses continuous flow variables as well as integer routing variables, and an alternative one based only on the integer variables. We show that the second model is the best option to develop an exact branch-and-cut algorithm. The 1-PDLRP can be seen as a simplified version of more realistic problems, but the development of good models and efficient exact algorithms for it can serve to provide good approximations to more complex problems, and can help to asses the effectiveness of heuristic algorithms capable of dealing with larger instances. 1.3 Organization The remainder of this paper is organized as follows. First, in Section 2 we formally describe the problem and present two mathematical formulations, one with continuous flow variables and integer variables, and another one with only integer variables, as well as valid inequalities for them. In Section 3 we describe a branch-and cut algorithm to solve the problem. We report the results of our computational experiments in Section 4. Finally, the paper ends with conclusions in Section 5. 2 Mathematical models In order to formally describe the 1-PDLRP, we need to introduce some notation. Let V=I∪J be the set of locations, with Ibeing the set of customers’ locations and Jthe set of potential facility locations. Let E={(i, j) : i, j ∈V, i < j}be the set of edges linking all possible pairs of locations in V. The 1-PDLRP is defined on the undirected graph G= (V, E). The cost of traversing an edge e∈Eis denoted by ce. Each customer i∈Irequires or supplies qiunits of the commodity: if qi>0, the customer is a pickup customer (i.e., a customer where the vehicle picks up product), and if qi<0, the customer is a delivery customer (i.e., a customer where the vehicle delivers product). All customers must be visited by a vehicle. Each potential facility 6 location j∈Jhas an associated opening cost dj, and it can serve customers using a vehicle with capacity Q. We also use some additional notation. For each subset S⊆V,δ(S) is the set of edges with one endpoint in Sand the other one in V\S, and E(S) is the set of edges with both endpoints in S. If S={i}, we simply use δ(i). For brevity in notation, we write x(E′) = Pe∈E′xefor all E′⊆E. The aim of the one-commodity Pickup and Delivery Location Routing Problem is to decide which facilities to open, to assign each customer to an open facility, and to design vehicle routes to serve the customers assigned to each facility. We assume that only one vehicle is available at each facility, each vehicle route starts and ends at the same facility, and each customer must be visited by exactly one vehicle. The objective is to find a feasible solution which minimizes the sum of the routing costs and the opening costs. The 1-PDLRP can be mathematically formulated by defining the following variables. For each facility location j∈J, let yjbe a binary variable that takes value 1 if the facility at location jis opened, and 0 otherwise. For each edge e∈E, variable xetakes value 1 if a vehicle traverses e, and 0 otherwise. For each customer i∈Iand each facility j∈Ja binary variable zij takes value 1 if i∈Iis assigned to j∈J, and value 0 otherwise. Moreover, let fabe a positive real flow variable associated with each ordered pair of nodes or arc a= [i, j], with i, j ∈V,i=j. We can model our problem using these variables as follows: (Pflow) min X j∈J djyj+X e∈E cexe(1) s.t. x(δ(i)) = 2 ∀i∈I(2) x(δ(j)) = 2yj∀j∈J(3) X j∈J zij = 1 ∀i∈I(4) zij ≤yj∀i∈I, j ∈J(5) x(δ(S)) ≥2∀S⊆I(6) xij ≤zij ∀i∈I, j ∈J(7) xii′+zij +zi′j′≤2∀i, i′∈I, i =i′,∀j, j′∈J, j =j′(8) xe∈ {0,1} ∀e∈E(9) yj∈ {0,1} ∀j∈J(10) zij ∈ {0,1} ∀i∈I, j ∈J(11) X j∈V\{i} f[i,j]−X j∈V\{i} f[j,i]=qi∀i∈I(12) 0≤f[i,j]≤Q 2x(i,j)∀i, j ∈V, i < j ∈V(13) 0≤f[i,j]≤Q 2x(j,i)∀i, j ∈V, i > j ∈V(14) The objective function (1) to minimize is the total cost of the solution. Constraints (2) and (3) are the degree constraints for the customers and facilities, respectively. They ensure that 7 each customer is visited by exactly one vehicle, and that the same happens to facilities but only if they are open. Constraints (4) enforce each customer ito be assigned to exactly one facility, and constraints (5) avoid that a customer is assigned to a closed facility. Constraints (6) are connectivity constraints, similar to the subtour elimination constraints for the TSP (see Padberg and Rinaldi (1991)). They ensure that at least a vehicle must enter and leave each set of customers S⊆I. Constraints (7) state that, if a customer iis not assigned to a facility j, then the edge (i, j) can not be routed. Constraints (8) forbid customers assigned to different facilities to be in the same vehicle route. Constraints (12) are the flow conservation conditions for the customers. Finally, (9)-(11) and (13)-(14) are the value restrictions for the different kinds of variables. We will refer to model (1)-(14) as Pflow. Note that the upper bound for variables f[i,j]is Q 2x(i,j), and not Qx(i,j), in constraints (13), and Q 2x(j,i), not Qx(j,i), in constraints (14). As explained in Hern´andez-P´erez and SalazarGonz´alez (2004a), variables f[i,j]do not represent the load of the vehicle when traversing arc [i, j], but are instead a certificate that guarantees that the variables xedefine a feasible 1-PDLPR solution. Anyway, it is possible to calculate the load of the vehicle traversing an arc [i, j] from the values of the favariables as f[i,j]+Q 2−f[j,i]. Note as well that the initial load of a vehicle when leaving a facility is unfixed, and so it can be any value between 0 and Q. It is possible to derive an alternative model for the 1-PDLRP by using Benders’ decomposition to project the continuous flow variables fain model (1)-(14) into the space of the binary variables, as was done in Hern´andez-P´erez et al. (2021). By doing so we obtain the following constraints, which are similar to the rounded fractional capacity inequalities for the Capacitated VRP (Gouveia (1995)): x(δ(S)) ≥2|Pi∈Sqi| Q∀S⊆I. (15) Hence, constraints (1)-(11) together with (15) provide a valid and pure integer linear programming formulation for the 1-PDLRP. We will refer to this model as model PILP . 2.1 Valid inequalities We present next two families of valid inequalities that help to strengthen the linear relaxation of the models described in the former section for the 1-PDLRP. They are both taken from the literature, and validity proofs are omitted as they are very similar to the ones that appear in the cited references. The first family of inequalities were used in Rodr´ıguez-Mart´ın et al. (2014) to solve the Hub Location and Routing Problem: xii′≤X j∈J\S zij +X j′∈S zi′j′∀i, i′∈I, i =i′,∀S⊂J. (16) These inequalities say that, if customer iis assigned to a facility in S, and customer i′is assigned to a facility in J\S, then the edge (i, i′) can not be in a vehicle’s route. Note as well that (16) dominate (8) since they can be rewritten, using (4), as 8 B&Cflow B&C0B&C1B&C2 Q Name Time %-gap Time %-gap Time %-gap Time %-gap 10 A 236.31 9.94 2.00 3.02 1.14 2.49 1.30 2.47 B 161.05 9.10 6.38 3.34 0.81 3.34 0.78 3.34 C 64.30 8.12 2.45 1.73 1.28 1.71 1.02 1.71 D 26.92 10.04 2.98 3.77 0.73 3.57 0.73 3.57 E 14.44 6.83 3.06 18.79 0.47 18.79 0.77 2.14 F 265.72 9.65 3.27 2.52 1.64 4.45 1.75 4.45 G 855.48 9.28 20.64 11.21 5.22 2.29 2.17 2.29 H 192.47 10.06 7.95 4.77 8.83 4.44 2.75 4.44 I 34.05 9.65 1.31 2.94 0.36 2.00 0.33 2.00 J 271.88 11.71 1.38 3.75 1.13 3.75 1.11 3.75 Aver 212.26 9.44 5.14 5.58 2.16 4.68 1.27 3.02 20 A 13.98 6.46 0.39 2.56 0.34 2.56 0.33 2.56 B 3.34 2.77 0.13 0.00 0.06 0.73 0.06 0.00 C 2.23 4.13 0.70 3.26 0.41 3.26 0.42 3.26 D11.30 6.86 0.61 3.51 0.44 3.51 0.47 3.51 E 2.52 3.85 0.47 2.06 0.25 2.06 0.33 1.63 F 17.55 4.98 0.28 2.57 0.16 2.57 0.17 2.57 G 258.22 9.14 0.98 3.19 0.73 3.19 1.05 2.90 H 6.14 5.08 3.09 4.61 2.34 3.86 0.53 3.86 I 0.38 0.00 0.03 0.00 0.03 0.00 0.03 0.00 J 49.58 4.69 0.08 0.00 0.08 0.00 0.08 0.00 Aver 36.52 4.80 0.68 2.18 0.48 2.17 0.35 2.03 40 A 0.36 0.00 0.08 0.92 0.06 0.92 0.06 0.92 B 0.28 0.00 0.03 0.00 0.02 0.00 0.02 0.00 C 0.34 0.00 0.13 0.00 0.06 0.00 0.06 0.00 D 0.31 0.00 0.03 0.00 0.02 0.00 0.02 0.00 E 0.63 1.80 0.20 1.46 0.17 1.46 0.17 0.82 F 1.11 2.71 0.36 2.19 0.20 2.19 0.20 2.19 G 6.30 5.06 0.27 1.85 0.30 1.85 0.30 1.85 H 0.80 1.74 0.06 0.00 0.05 0.00 0.05 0.00 I 0.25 0.00 0.06 0.00 0.05 0.00 0.03 0.00 J 1.14 2.64 0.23 2.40 0.14 2.40 0.14 2.40 Aver 1.15 1.40 0.15 0.88 0.11 0.88 0.10 0.82 Table 1: Model comparison for instances with n= 30, |J|= 5, and dj= 100 15 n Q Name OptVal nOpen Time BBnodes %-gap %-fgap nCuts (6) (15) (16) (18) %-uncapa 30 10 A 5703 3 1.30 87 2.47 0.00 561 4.63 40.11 41.89 13.37 25.32 B 5356 3 0.78 106 3.34 0.00 560 5.89 37.68 56.43 0.00 21.28 C 5420 3 1.02 106 1.71 0.00 580 4.83 39.48 52.59 3.10 22.75 D 6120 3 0.73 87 3.57 0.00 476 4.62 38.45 56.93 0.00 27.63 E 5760 3 0.77 4 2.14 0.00 574 5.92 22.30 12.72 59.06 17.57 F 5660 3 1.75 186 4.45 0.00 902 3.44 35.81 58.09 2.66 24.17 G 8125 3 2.17 156 2.29 0.00 806 3.23 32.75 55.46 8.56 44.02 H 6118 4 2.75 468 4.44 0.00 1101 2.27 27.88 66.58 3.27 27.13 I 4976 2 0.33 25 2.00 0.00 232 9.48 55.17 35.34 0.00 16.44 J 5896 4 1.11 105 3.75 0.00 736 5.84 41.03 53.13 0.00 29.46 Aver 3.10 1.27 133.00 3.02 0.00 652.80 5.02 37.07 48.92 9.00 25.58 20 A 4606 1 0.33 25 2.56 0.00 262 7.63 49.62 42.75 0.00 7.53 B 4479 1 0.06 0 0.00 0.00 68 11.76 19.12 1.47 67.65 5.87 C 4377 2 0.42 21 3.26 0.00 144 18.75 32.64 48.61 0.00 4.34 D 4827 1 0.47 35 3.51 0.00 214 12.15 47.20 40.65 0.00 8.25 E 4837 3 0.33 14 1.63 0.00 240 9.17 13.75 25.83 51.25 1.84 F 4483 1 0.17 9 2.57 0.00 139 14.39 33.81 51.80 0.00 4.26 G 5758 2 1.05 87 2.90 0.00 573 4.54 34.03 23.04 38.39 21.01 H 4800 2 0.53 52 3.86 0.00 344 4.94 15.41 43.90 35.76 7.13 I 4158 1 0.03 0 0.00 0.00 3 100.00 0.00 0.00 0.00 0.00 J 4436 1 0.08 0 0.00 0.00 58 22.41 77.59 0.00 0.00 6.24 Aver 1.50 0.35 24.30 2.03 0.00 204.50 20.57 32.32 27.80 19.30 6.65 40 A 4259 1 0.06 2 0.92 0.00 37 40.54 0.00 59.46 0.00 0.00 B 4216 1 0.02 0 0.00 0.00 4 100.00 0.00 0.00 0.00 0.00 C 4187 1 0.06 0 0.00 0.00 101 12.87 0.00 0.00 87.13 0.00 D 4429 1 0.02 0 0.00 0.00 4 100.00 0.00 0.00 0.00 0.00 E 4748 1 0.17 21 0.82 0.00 49 24.49 0.00 75.51 0.00 0.00 F 4308 3 0.20 57 2.19 0.00 157 15.29 2.55 82.17 0.00 0.37 G 4715 2 0.30 58 1.85 0.00 194 14.95 11.86 73.20 0.00 3.54 H 4466 1 0.05 0 0.00 0.00 15 93.33 6.67 0.00 0.00 0.18 I 4158 1 0.03 0 0.00 0.00 3 100.00 0.00 0.00 0.00 0.00 J 4159 1 0.14 9 2.40 0.00 49 38.78 4.08 57.14 0.00 0.00 Aver 1.30 0.10 14.70 0.82 0.00 61.30 54.02 2.52 34.75 8.71 0.41 40 10 A 6565 3 6.06 692 3.54 0.00 1561 3.72 33.82 45.48 16.98 25.58 B 5877 2 2.30 144 5.05 0.00 899 4.23 40.49 44.16 11.12 17.03 C 7305 2 14.34 474 30.77 0.00 2694 3.82 47.25 48.92 0.00 35.62 D 6108 1 0.47 2 1.49 0.00 273 12.09 49.45 38.46 0.00 14.03 E 6554 4 41.83 3194 6.34 0.00 3424 2.75 27.92 39.52 29.82 20.20 F 6875 4 22.39 1424 4.57 0.00 2727 2.82 40.92 49.06 7.19 30.76 G 6216 2 11.06 919 4.78 0.00 2314 4.24 39.33 51.30 5.14 16.38 H 6519 2 8.03 551 3.59 0.00 1838 4.30 43.53 51.09 1.09 26.42 I 6697 3 7.31 494 30.34 0.00 1931 4.71 37.86 50.28 7.15 28.48 J 6051 1 28.95 3173 5.08 0.00 2616 4.28 39.37 44.84 11.51 23.05 Aver 2.40 14.28 1106.70 9.56 0.00 2027.70 4.69 39.99 46.31 9.00 23.75 20 A 5139 2 0.63 10 0.73 0.00 283 13.07 23.32 63.60 0.00 4.92 B 4974 2 0.27 8 1.44 0.00 84 14.29 1.19 84.52 0.00 1.97 C 5523 1 2.41 324 3.13 0.00 921 6.19 48.75 41.80 3.26 14.85 D 5269 1 0.22 0 0.00 0.00 179 8.38 1.68 20.67 69.27 0.34 E 5374 2 1.56 162 2.98 0.00 848 10.85 31.25 47.88 10.02 2.68 F 5023 1 0.77 105 3.14 0.00 379 11.61 34.30 54.09 0.00 5.24 G 5266 2 0.34 5 1.07 0.00 136 14.71 25.00 60.29 0.00 1.29 H 5033 1 4.27 466 2.29 0.00 1489 7.25 22.83 69.91 0.00 4.69 I 5135 2 0.13 4 9.15 0.00 140 10.71 50.00 39.29 0.00 6.72 J 4773 1 0.03 0 0.00 0.00 35 17.14 82.86 0.00 0.00 2.45 Aver 1.50 1.06 108.40 2.39 0.00 449.40 11.42 32.12 48.21 8.26 4.51 40 A 4886 1 0.14 2 0.26 0.00 11 100.00 0.00 0.00 0.00 0.00 B 4876 2 0.17 0 0.00 0.00 78 6.41 0.00 50.00 43.59 0.00 C 4703 1 0.06 0 0.00 0.00 5 100.00 0.00 0.00 0.00 0.00 D 5251 1 0.05 0 0.00 0.00 13 100.00 0.00 0.00 0.00 0.00 E 5236 1 0.33 29 0.68 0.00 144 27.78 2.08 70.14 0.00 0.11 F 4760 1 0.16 0 0.00 0.00 12 100.00 0.00 0.00 0.00 0.00 G 5198 1 0.27 26 1.34 0.00 139 33.09 0.00 66.91 0.00 0.00 H 4797 1 0.14 4 1.09 0.00 68 44.12 5.88 50.00 0.00 0.00 I 4796 2 0.22 7 2.73 0.00 143 25.17 1.40 73.43 0.00 0.13 J 4656 1 0.05 0 0.00 0.00 6 100.00 0.00 0.00 0.00 0.00 Aver 1.20 0.16 6.80 0.61 0.00 61.90 63.66 0.94 31.05 4.36 0.02 Table 2: Branch-and-cut results for medium-sized instances 16 n Q Name OptVal nOpen Time BBnodes %-gap %-fgap nCuts (6) (15) (16) (18) %-uncapa 50 10 A 6263 2 1.14 16 0.48 0.00 532 8.83 76.50 14.66 0.00 11.32 B 9034 2 126.13 1478 4.17 0.00 6897 3.15 47.14 46.70 3.02 36.44 C 8066 2 71.52 1577 3.82 0.00 3860 3.03 59.07 31.48 6.42 35.26 D 8946 2 26.63 849 3.43 0.00 2963 4.22 46.03 42.02 7.73 33.22 E 8434 4 110.41 2101 3.40 0.00 5840 1.76 42.31 50.50 5.43 30.19 F 7695 2 54.56 1188 8.46 0.00 4051 2.64 51.67 35.57 10.12 29.89 G 6818 2 10.33 582 2.60 0.00 1983 4.74 34.90 60.36 0.00 17.53 H 8200 3 147.25 3881 6.16 0.00 6082 2.76 34.97 50.35 11.92 31.82 I 7510 2 46.09 2126 29.91 0.00 3504 3.40 44.04 51.20 1.37 26.80 J 7519 2 43.50 1687 3.68 0.00 3098 3.03 52.68 34.67 9.62 26.04 Aver 2.30 63.75 1548.50 6.61 0.00 3881.00 3.76 48.93 41.75 5.56 27.85 20 A 5713 1 0.47 23 2.72 0.00 232 17.24 27.16 55.60 0.00 2.78 B 6745 2 11.02 655 3.18 0.00 1834 6.71 45.58 44.00 3.71 14.87 C 6221 1 22.94 967 4.56 0.00 2676 4.07 44.39 50.45 1.08 16.06 D 6782 3 13.53 851 4.45 0.00 2217 5.28 48.22 46.19 0.32 11.91 E 6292 2 2.27 58 0.62 0.00 655 6.56 43.66 49.77 0.00 6.42 F 5891 3 3.61 246 2.72 0.00 1272 7.55 32.31 60.14 0.00 8.42 G 5861 2 1.61 235 4.07 0.00 721 11.37 17.75 70.87 0.00 4.06 H 6033 1 6.63 218 2.41 0.00 1713 5.31 35.32 53.59 5.78 7.33 I 6014 1 8.00 658 12.47 0.00 1729 7.17 25.45 57.32 10.06 8.60 J 5764 1 1.27 169 2.38 0.00 488 11.27 29.30 59.43 0.00 3.52 Aver 1.70 7.13 408.00 3.96 0.00 1353.70 8.25 34.91 54.74 2.10 8.40 40 A 5554 1 0.22 7 0.68 0.00 30 100.00 0.00 0.00 0.00 0.00 B 5825 2 0.66 6 1.22 0.00 80 30.00 61.25 8.75 0.00 1.42 C 5449 1 0.80 67 1.77 0.00 311 15.43 10.29 74.28 0.00 4.17 D 6096 1 0.78 69 2.18 0.00 425 16.00 8.00 76.00 0.00 2.00 E 5888 3 0.44 0 0.00 0.00 129 20.93 6.20 72.87 0.00 0.00 F 5396 1 0.17 0 0.00 0.00 14 92.86 7.14 0.00 0.00 0.02 G 5623 1 0.27 16 1.17 0.00 39 89.74 5.13 5.13 0.00 0.00 H 5620 1 0.94 78 2.30 0.00 350 16.86 11.43 71.71 0.00 0.52 I 5497 1 3.28 360 4.24 0.00 1381 8.25 0.58 84.58 6.59 0.00 J 5561 1 0.13 0 0.00 0.00 17 100.00 0.00 0.00 0.00 0.00 Aver 1.30 0.77 60.30 1.36 0.00 277.60 49.01 11.00 39.33 0.66 0.81 60 10 A 8043 2 t.l. 41789 9.21 2.74 17266 1.92 48.20 24.35 25.52 24.07 B 8322 2 33.31 647 3.34 0.00 3053 4.06 42.29 49.66 4.00 23.32 C 8861 2 36.20 428 3.84 0.00 3252 3.57 42.19 47.54 6.70 29.36 D 11011 3 t.l. 38351 8.05 1.71 17587 2.16 50.56 31.46 15.83 40.88 E 9565 3 1733.70 15040 4.85 0.00 13663 1.81 45.03 38.07 15.10 33.02 F 8733 3 943.69 7497 5.82 0.00 12690 2.06 44.98 41.89 11.06 32.38 G 8579 3 1304.33 10085 6.27 0.00 11879 1.83 47.14 38.69 12.34 28.06 H 7827 3 44.63 1283 21.52 0.00 3618 3.79 42.87 52.18 1.16 24.06 I 9458 4 t.l. 30330 8.30 1.90 17729 1.55 39.09 30.66 28.69 37.75 J 8261 1 1685.47 9769 22.52 0.00 16222 4.22 46.64 44.91 4.22 22.24 Aver 2.60 2738.13 15521.90 9.37 0.63 11695.90 2.70 44.90 39.94 12.46 29.51 20 A 6603 1 91.77 5527 5.20 0.00 4035 5.75 31.13 55.61 7.51 7.51 B 6648 2 30.44 826 3.09 0.00 3589 5.74 44.55 47.53 2.17 4.02 C 6868 2 38.33 964 2.07 0.00 3869 5.20 41.79 52.47 0.54 8.87 D 7784 1 61.77 2385 3.91 0.00 3670 5.59 43.51 47.79 3.11 16.37 E 7336 1 117.33 5483 3.68 0.00 4853 4.10 41.15 50.53 4.22 12.66 F 6589 2 73.30 2243 2.00 0.00 4845 4.95 35.11 56.84 3.10 10.38 G 6651 2 23.13 647 2.20 0.00 3091 5.53 32.97 61.50 0.00 7.20 H 6404 2 5.91 544 2.70 0.00 1380 7.25 23.70 66.30 2.75 7.18 I 7105 2 2829.42 30076 6.96 0.00 14311 2.31 45.28 26.58 25.83 17.13 J 6719 2 13.08 416 1.90 0.00 2247 8.14 34.53 57.32 0.00 4.39 Aver 1.70 328.45 4911.10 3.37 0.00 4589.00 5.46 37.37 52.25 4.92 9.57 40 A 6110 1 0.98 131 2.02 0.00 267 27.34 10.86 61.80 0.00 0.05 B 6381 1 0.67 61 0.63 0.00 59 74.58 25.42 0.00 0.00 0.00 C 6271 1 0.30 2 0.51 0.00 178 17.42 25.84 56.74 0.00 0.19 D 6589 1 0.72 29 2.09 0.00 227 27.31 16.74 55.95 0.00 1.20 E 6415 2 0.33 22 1.15 0.00 154 26.62 24.03 49.35 0.00 0.12 F 6033 2 2.05 245 2.20 0.00 577 15.42 36.05 48.53 0.00 2.12 G 6276 1 1.45 163 1.69 0.00 545 11.19 7.16 81.65 0.00 1.66 H 5945 1 0.36 18 0.74 0.00 94 51.06 5.32 43.62 0.00 0.02 I 6029 2 32.06 2615 4.12 0.00 3014 13.24 20.24 66.52 0.00 2.34 J 6431 1 0.31 19 0.42 0.00 34 82.35 17.65 0.00 0.00 0.11 Aver 1.30 3.92 330.50 1.56 0.00 514.90 34.65 18.93 46.42 0.00 0.78 Table 3: Branch-and-cut results for large instances 17 n Q Name OptVal nOpen Time BBnodes %-gap %-fgap nCuts (6) (15) (16) (18) %-uncapa 100 10 A B 17614 3 t.l. 6402 32.30 30.95 25986 2.48 70.05 23.80 3.67 56.10 C D 16488 4 t.l. 8557 20.42 18.33 23044 2.14 53.32 38.25 6.29 52.06 E 11810 3 t.l. 8336 8.51 6.59 27046 1.62 55.86 38.92 3.59 32.95 F 19040 2 t.l. 12229 44.38 43.29 25493 2.40 67.91 26.76 2.92 58.92 G H 19284 4 t.l. 8790 38.95 37.54 24810 2.57 67.42 27.59 2.42 59.62 I 18159 4 t.l. 9261 31.69 30.11 27267 2.11 57.37 36.09 4.42 56.78 J Aver 3.33 t.l. 8929.17 29.38 27.80 25607.67 2.22 61.99 31.90 3.89 52.74 20 A 8628 1 t.l. 12072 4.27 1.36 28159 3.98 52.72 42.16 1.14 9.90 B 12959 3 t.l. 16822 33.31 31.81 25577 3.19 72.37 21.82 2.63 40.33 C 9150 3 t.l. 32800 4.00 0.65 20311 2.87 46.88 34.43 15.81 13.33 D 9591 3 2978.23 11738 3.64 0.00 17034 3.23 55.70 39.12 1.95 17.59 E 9567 3 t.l. 17322 12.60 11.14 22930 2.89 62.02 28.09 7.00 17.23 F 9008 1 t.l. 10201 8.09 6.40 27144 4.86 52.97 39.73 2.44 13.18 G 8600 1 2260.05 18394 4.05 0.00 11024 4.91 70.44 23.58 1.08 10.37 H I 9735 3 t.l. 13055 5.62 3.36 24326 3.87 54.48 39.30 2.35 19.37 J 9509 2 t.l. 20200 10.93 9.19 19590 3.78 61.55 24.98 9.69 19.34 Aver 2.22 6182.03 16956.00 9.61 7.10 21788.33 3.73 58.79 32.58 4.90 17.85 40 A 7947 1 24.69 962 1.21 0.00 1406 17.99 33.57 48.44 0.00 2.18 B 8053 1 865.34 15675 2.78 0.00 7057 7.65 56.38 29.08 6.89 3.97 C 8137 1 94.45 2492 2.54 0.00 4041 9.30 29.92 58.62 2.15 2.54 D 8127 1 19.16 356 1.43 0.00 1870 9.20 47.49 43.32 0.00 2.74 E 7982 1 759.25 2997 1.86 0.00 14081 6.38 19.52 73.08 1.01 0.79 F 7949 1 701.98 20357 2.87 0.00 7162 12.33 26.64 57.46 3.57 1.61 G 7872 1 46.06 2332 2.74 0.00 2399 10.46 26.30 63.23 0.00 2.08 H 8005 1 56.05 665 1.69 0.00 3036 9.29 64.99 25.72 0.00 2.72 I 8240 2 298.80 4275 1.82 0.00 6121 10.31 35.27 50.73 3.69 4.75 J 8066 2 624.39 13183 2.77 0.00 7679 9.32 31.01 54.66 5.01 4.91 Aver 1.20 349.02 6329.40 2.17 0.00 5485.20 10.22 37.11 50.43 2.23 2.83 Table 4: Branch-and-cut results for very large instances 18 dj= 0 dj= 100 dj= 1000 |J|Name OptVal nOpen Time OptVal nOpen Time OptVal nOpen Time 5 A 6063 2 0.28 6263 2 1.14 7304 1 3.78 B 8834 2 7.75 9034 2 126.13 10043 1 27.19 C 7866 2 49.66 8066 2 71.52 9073 1 88.28 D 8656 4 67.13 8946 2 26.63 10746 2 47.92 E 8034 4 72.95 8434 4 110.41 10684 2 875.80 F 7493 3 24.84 7695 2 54.56 9470 1 1931.36 G 6492 4 9.89 6818 2 10.33 8618 2 5.48 H 7857 4 93.55 8200 3 147.25 10068 2 56.70 I 7310 2 15.47 7510 2 46.09 8459 1 7.50 J 7319 2 22.30 7519 2 43.50 8717 1 89.69 Aver 2.90 36.38 2.30 63.75 1.40 313.37 10 A 6097 4 356.67 6497 4 422.48 10097 4 812.72 B 6732 5 67.17 7156 4 23.17 9341 2 42.89 C 6117 6 49.36 6482 3 63.39 8064 1 36.59 D 5914 7 10.38 6422 4 29.66 8434 2 6.44 E 6846 5 72.72 7280 3 39.77 8679 1 66.06 F 6479 7 42.36 7118 6 717.91 9390 2 1695.81 G 5920 7 5.31 6543 5 46.95 7554 1 3.23 H 6910 3 14.30 7210 3 7.36 8261 1 27.05 I 6642 4 35.08 7035 3 44.67 7946 1 4.84 J 6669 5 648.88 7071 2 160.67 8871 2 59.94 Aver 5.30 130.22 3.70 155.60 1.70 275.56 Table 5: Results for instances with n= 50, Q= 10, |J|∈{5,10}, and different opening costs Almeida, F. L., Terra, B. M., Dias, P. A., and Gon¸calves, G. M. (2010). Transport with automatic guided vehicles in the factory of the future. In 2010 IEEE 15th Conference on Emerging Technologies & Factory Automation (ETFA 2010), pages 1–4. IEEE. Battarra, M., Cordeau, J. F., and Iori, M. (2014). Chapter 6: pickup-and-delivery problems for goods transportation. In Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 161–191. SIAM. Berbeglia, G., Cordeau, J. F., Gribkovskaia, I., and Laporte, G. (2007). Static pickup and delivery problems: a classification scheme and survey. TOP, 15:1–31. Chemla, D., Meunier, F., and Wolfler-Calvo, R. (2013). Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization, 10(2):120–146. Cruz, F., Subramanian, A., Bruck, B. P., and Iori, M. (2017). A heuristic algorithm for a single vehicle static bike sharing rebalancing problem. Computers & Operations Research, 79:19–33. Dell’Amico, M., Hadjicostantinou, E., Iori, M., and Novellani, S. (2014). The bike sharing rebalancing problem: Mathematical formulations and benchmark instances. Omega, 45:7–19. Erdo˘gan, G., Battarra, M., and Wolfler-Calvo, R. (2015). An exact algorithm for the static rebalancing problem arising in bicycle sharing systems. European Journal of Operational Research, 245:667–679. 19 Gouveia, L. (1995). A result on projection for the vehicle routing problem. European Journal of Operational Research, 85(3):610–624. Hern´andez-P´erez, H., Landete, M., and Rodr´ıguez-Mart´ın, I. (2021). The single-vehicle twoechelon one-commodity pickup and delivery problem. Computers & Operations Research, 127:105152. Hern´andez-P´erez, H., Rodr´ıguez-Mart´ın, I., and Salazar-Gonz´alez, J.-J. (2009). A hybrid grasp/vnd heuristic for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Operations Research, 36:1639–1645. Hern´andez-P´erez, H. and Salazar-Gonz´alez, J.-J. (2004a). A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Applied Mathematics, 145:126– 139. Hern´andez-P´erez, H. and Salazar-Gonz´alez, J.-J. (2004b). Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science, 38:245–255. Hern´andez-P´erez, H. and Salazar-Gonz´alez, J.-J. (2007). The one-commodity pickup-anddelivery traveling salesman problem: Inequalities and algorithms. Networks, 50(4):258–272. Hern´andez-P´erez, H. and Salazar-Gonz´alez, J.-J. (2022). A branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, 297(2):467–483. Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2011). A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European Journal of Operational Research, 211(2):318–332. Karaoglan, I., Altiparmak, F., Kara, I., and Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4):465–477. Kim, S., Lim, G., Cho, J., and Cˆot´e, M. (2017). Drone-aided healthcare services for patients with chronic diseases in rural areas. Journal of Intelligent & Robotic Systems, 88:163–180. Ko¸c, C¸., Laporte, G., and T¨ukenmez, ˙ I. (2020). A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research, 122:104987. Labb´e, M., Rodr´ıguez-Mart´ın, I., and Salazar-Gonz´alez, J.-J. (2004). A branch-and-price algorithm for the plant-cycle location problem. Journal of the Operational Research Society, 55:513–520. Mladenovi´c, N., Uroˇsevi´c, D., Hanafi, S., and Ili´c, A. (2012). A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research, 220:270–285. Mosheiov, G. (1994). The travelling salesman problem with pick-up and delivery. European Journal of Operational Research, 79(2):299–310. 20 Nagy, G. and Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2):649–672. Padberg, M. W. and Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev., 33:60–100. Parragh, S., Doerner, K., , and Hartl, R. (2008a). A survey on pickup and delivery problems: Part i: Transportation between customers and depot. Journal f¨ur Betriebswirtschaft, 58:21– 51. Parragh, S., Doerner, K., and Hartl, R. (2008b). A survey on pickup and delivery problems: Part ii: Transportation between pickup and delivery locations. Journal f¨ur Betriebswirtschaft, 58:81–117. Prodhon, C. and Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1):1–17. Rodr´ıguez-Mart´ın, I., Salazar-Gonz´alez, J.-J., and Yaman, H. (2014). A branch-and-cut algorithm for the hub location and routing problem. Computers & Operations Research, 50:161– 174. Salazar-Gonz´alez, J. J. and Santos-Hern´andez, B. (2015). The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transportation Research Part B: Methodological, 75(0):58 – 73. Zhao, F., Li, S., Sun, J., and Mei, D. (2009). Genetic algorithm for the one-commodity pickupand-delivery traveling salesman problem. Computers & Industrial Engineering, 56(4):1642– 1648. 21 A Appendix In this appendix we show the results given by the branch-and-cut algorithm on our whole set of benchmark instances. For each instance and each facility opening cost dj∈ {0,100,1000}, Tables 6 to 10 display the characteristics of the instance (|J|,Q, and Name), and the following information:  OptVal: Optimal solution value.  nOpen: Number of opened facilities.  Time: Total computation time, in seconds.  %-uncapa: Percentage difference between the optimal solution of the 1-PDLRP and the optimal solution of the uncapacitated version of the problem. Blank cells in the tables indicate that the algorithm was unable to find a feasible solution within the time limit of two hours. 22 dj= 0 dj= 100 dj= 1000 |J|QName OptVal nOpen Time %-uncapa OptVal nOpen Time %-uncapa OptVal nOpen Time %-uncapa 5 10 A 5324 4 0.50 21.88 5703 3 1.30 25.32 6736 1 1.56 23.41 B 5056 3 0.86 18.59 5356 3 0.78 21.28 7232 2 1.13 29.26 C 5120 3 0.89 20.72 5420 3 1.02 22.75 6390 1 0.42 20.39 D 5735 5 1.44 24.52 6120 3 0.73 27.63 8181 2 2.02 34.86 E 5386 4 0.38 16.84 5760 3 0.77 17.57 6998 1 0.91 19.29 F 5360 3 5.05 25.22 5660 3 1.75 24.17 7757 2 4.78 32.24 G 7825 3 9.28 44.17 8125 3 2.17 44.02 9291 1 1.25 41.36 H 5718 4 3.56 24.94 6118 4 2.75 27.13 9718 4 3.11 44.87 I 4752 4 0.66 14.60 4976 2 0.33 16.44 5946 1 0.64 14.93 J 5496 4 0.55 26.15 5896 4 1.11 29.46 7135 1 4.02 29.10 Aver 3.70 2.32 23.76 3.10 1.27 25.58 1.60 1.98 28.97 20 A 4453 2 0.52 6.60 4606 1 0.33 7.53 5506 1 0.23 6.30 B 4379 1 0.20 6.01 4479 1 0.06 5.87 5379 1 0.05 4.89 C 4177 2 0.27 2.82 4377 2 0.42 4.34 5301 1 0.27 4.04 D 4718 3 0.64 8.25 4827 1 0.47 8.25 5727 1 0.41 6.95 E 4537 3 0.05 1.28 4837 3 0.33 1.84 5802 1 0.23 2.65 F 4247 3 0.30 5.63 4483 1 0.17 4.26 5383 1 0.09 2.36 G 5468 3 0.64 20.10 5758 2 1.05 21.01 6849 1 0.69 20.46 H 4526 3 0.64 5.17 4800 2 0.53 7.13 6600 2 1.13 18.82 I 4058 1 0.02 0.00 4158 1 0.03 0.00 5058 1 0.02 0.00 J 4336 1 0.38 6.39 4436 1 0.08 6.24 5336 1 0.08 5.19 Aver 2.20 0.36 6.22 1.50 0.35 6.65 1.10 0.32 7.17 40 A 4159 1 0.08 0.00 4259 1 0.06 0.00 5159 1 0.05 0.00 B 4116 1 0.03 0.00 4216 1 0.02 0.00 5116 1 0.02 0.00 C 4059 2 0.08 0.00 4187 1 0.06 0.00 5087 1 0.09 0.00 D 4329 1 0.03 0.00 4429 1 0.02 0.00 5329 1 0.03 0.00 E 4479 3 0.03 0.00 4748 1 0.17 0.00 5648 1 0.08 0.00 F 4008 3 0.05 0.00 4308 3 0.20 0.37 5277 1 0.08 0.40 G 4515 2 0.14 3.23 4715 2 0.30 3.54 5697 1 0.11 4.37 H 4292 2 0.03 0.00 4466 1 0.05 0.18 5366 1 0.06 0.15 I 4058 1 0.03 0.00 4158 1 0.03 0.00 5058 1 0.03 0.00 J 4059 1 0.17 0.00 4159 1 0.14 0.00 5059 1 0.09 0.00 Aver 1.70 0.07 0.32 1.30 0.10 0.41 1.00 0.06 0.49 10 10 A 4434 3 1.52 15.45 4734 3 0.41 17.24 7434 3 0.20 35.19 B 4146 2 0.56 6.08 4346 2 0.22 6.99 6146 2 0.28 19.59 C 4693 4 0.78 18.41 5041 3 0.66 20.71 6728 1 1.47 27.21 D 4519 6 0.08 17.17 5040 4 0.66 23.75 7228 2 6.22 34.38 E 5190 5 0.77 22.85 5607 3 1.86 25.02 7745 2 2.89 31.57 F 4842 7 3.23 20.53 5370 5 5.78 22.76 8213 3 22.95 37.66 G 6377 5 1.14 37.60 6877 5 1.00 39.23 9173 2 1.34 42.78 H 4485 3 0.69 10.48 4785 3 0.23 14.00 7485 3 0.23 33.00 I 4139 5 1.22 6.62 4524 3 1.17 10.15 5612 1 0.58 10.44 J 4036 5 0.83 24.03 4438 4 2.08 24.16 5796 1 0.27 19.27 Aver 4.50 1.08 17.92 3.50 1.41 20.40 2.00 3.64 29.11 20 A 3928 3 1.77 4.56 4214 2 0.70 7.02 6014 2 1.06 19.89 B 3894 2 0.06 0.00 4042 1 0.20 0.00 4942 1 0.19 0.00 C 3892 2 0.36 1.62 4092 2 0.30 2.32 5360 1 1.16 8.64 D 4022 4 0.19 6.94 4252 1 0.53 9.62 5152 1 0.28 7.94 E 4244 2 0.30 5.66 4444 2 0.20 5.40 5557 1 0.09 4.62 F 4124 3 3.30 6.69 4424 3 2.38 6.24 6288 2 1.52 18.58 G 4599 3 0.23 13.48 4899 3 0.39 14.70 6203 1 0.84 15.38 H 4186 2 1.75 4.09 4386 2 1.45 6.18 6186 2 1.59 18.93 I 3865 2 0.05 0.00 4065 2 0.48 0.00 5026 1 0.39 0.00 J 3231 3 0.53 5.11 3531 3 0.47 4.67 4868 1 0.86 3.88 Aver 2.60 0.85 4.81 2.10 0.71 5.62 1.30 0.80 9.79 40 A 3749 2 0.11 0.00 3919 1 0.27 0.03 4819 1 0.14 0.02 B 3894 2 0.05 0.00 4042 1 0.22 0.00 4942 1 0.17 0.00 C 3829 2 0.06 0.00 3997 1 0.67 0.00 4897 1 0.64 0.00 D 3743 1 0.05 0.00 3843 1 0.09 0.00 4743 1 0.05 0.00 E 4004 2 0.05 0.00 4204 2 0.06 0.00 5300 1 0.33 0.00 F 3848 3 0.03 0.00 4148 3 0.31 0.00 5120 1 0.39 0.00 G 4029 2 0.39 1.24 4229 2 0.33 1.18 5264 1 0.16 0.28 H 4015 1 0.09 0.00 4115 1 0.08 0.00 5015 1 0.06 0.00 I 3865 2 0.05 0.00 4065 2 0.45 0.00 5026 1 0.38 0.00 J 3066 3 0.06 0.00 3366 3 0.30 0.00 4687 1 0.28 0.17 Aver 2.00 0.09 0.12 1.70 0.28 0.12 1.00 0.26 0.05 Table 6: Results for instances with n= 30 and different values of Q,|J|, and dj 23 dj= 0 dj= 100 dj= 1000 |J|QName Sol nOpenF Time %-uncapa Sol nOpenF Time %-uncapa Sol nOpenF Time %-uncapa 5 10 A 6265 3 7.88 23.61 6565 3 6.06 25.58 7988 1 15.20 27.57 B 5619 3 8.23 16.78 5877 2 2.30 17.03 7130 1 11.30 17.97 C 7045 5 6.03 34.66 7305 2 14.34 35.62 8240 1 6.38 32.00 D 6008 1 6.30 15.78 6108 1 0.47 14.03 7008 1 4.55 12.23 E 6098 5 14.77 16.40 6554 4 41.83 20.20 8391 2 15.02 26.95 F 6389 5 9.44 27.06 6875 4 22.39 30.76 7934 1 15.47 28.66 G 6016 2 2.30 16.66 6216 2 11.06 16.38 7121 1 0.98 14.37 H 6232 4 4.75 24.63 6519 2 8.03 26.42 8319 2 4.72 31.52 I 6397 3 3.06 28.83 6697 3 7.31 28.48 8545 2 11.30 31.32 J 5758 3 22.81 20.88 6051 1 28.95 23.05 6951 1 1.83 20.07 Aver 3.40 8.56 22.53 2.40 14.28 23.75 1.30 8.67 24.26 20 A 4939 2 0.61 3.10 5139 2 0.63 4.92 6275 1 0.88 7.79 B 4774 2 0.05 2.05 4974 2 0.27 1.97 5967 1 0.34 1.98 C 5346 2 4.30 13.90 5523 1 2.41 14.85 6423 1 3.08 12.77 D 5164 3 0.28 2.01 5269 1 0.22 0.34 6169 1 0.08 0.29 E 5165 3 1.22 1.30 5374 2 1.56 2.68 6326 1 0.63 3.10 F 4912 2 0.69 5.13 5023 1 0.77 5.24 5923 1 0.44 4.44 G 5066 2 0.42 1.03 5266 2 0.34 1.29 6246 1 0.27 2.37 H 4866 2 1.17 3.47 5033 1 4.27 4.69 5933 1 0.42 3.98 I 4935 2 0.34 7.74 5135 2 0.13 6.72 6153 1 0.16 4.62 J 4673 1 0.06 2.50 4773 1 0.03 2.45 5673 1 0.06 2.06 Aver 2.10 0.91 4.22 1.50 1.06 4.51 1.00 0.63 4.34 40 A 4786 1 0.14 0.00 4886 1 0.14 0.00 5786 1 0.14 0.00 B 4676 2 0.05 0.00 4876 2 0.17 0.00 5849 1 0.09 0.00 C 4603 1 0.05 0.00 4703 1 0.06 0.00 5603 1 0.03 0.00 D 5060 2 0.06 0.00 5251 1 0.05 0.00 6151 1 0.06 0.00 E 5098 4 0.56 0.00 5236 1 0.33 0.11 6136 1 0.22 0.10 F 4660 1 0.11 0.00 4760 1 0.16 0.00 5660 1 0.14 0.00 G 5014 3 0.17 0.00 5198 1 0.27 0.00 6098 1 0.19 0.00 H 4697 1 0.11 0.00 4797 1 0.14 0.00 5697 1 0.13 0.00 I 4553 3 0.08 0.00 4796 2 0.22 0.13 5869 1 0.17 0.00 J 4556 1 0.05 0.00 4656 1 0.05 0.00 5556 1 0.05 0.00 Aver 1.90 0.14 0.00 1.20 0.16 0.02 1.00 0.12 0.01 10 10 A 5827 5 10.25 20.65 6192 3 3.38 23.71 7454 1 2.70 24.55 B 4749 4 1.95 10.42 5072 3 1.13 12.18 6645 1 6.91 16.79 C 5812 5 4.61 24.66 6270 4 4.38 28.56 7651 1 4.23 29.70 D 5660 6 11.50 17.39 6026 3 15.84 17.57 8726 3 1.95 32.62 E 5509 8 3.94 14.79 6000 3 9.02 18.43 7533 1 4.77 22.63 F 5549 4 1.72 23.19 5949 4 2.78 24.58 7966 2 6.69 32.19 G 5222 6 1.45 10.26 5615 2 1.70 11.42 6699 1 2.22 12.27 H 5462 7 3.61 18.53 5910 3 6.81 20.76 8610 3 4.47 35.16 I 5389 5 1.61 22.56 5836 4 4.06 23.85 6869 1 1.28 21.69 J 5140 4 5.88 15.31 5370 1 8.77 15.79 6270 1 2.41 13.52 Aver 5.40 4.65 17.78 3.00 5.79 19.69 1.50 3.76 24.11 20 A 4695 3 0.52 1.51 4972 1 1.05 4.99 5872 1 0.78 4.22 B 4254 2 0.03 0.00 4454 2 0.09 0.00 5638 1 0.31 1.93 C 4566 2 0.94 4.10 4766 2 2.56 6.02 6157 1 1.30 12.64 D 4821 3 0.94 3.01 5073 2 0.61 2.09 6873 2 0.48 14.45 E 4819 3 0.89 2.59 5090 2 0.50 3.85 6147 1 0.53 5.19 F 4294 3 0.08 0.75 4535 1 2.22 1.06 5435 1 0.55 0.61 G 4766 3 1.08 1.68 5000 2 0.67 0.52 5978 1 0.17 1.69 H 4591 3 0.05 3.07 4820 2 0.27 2.84 6620 2 0.36 15.66 I 4504 4 0.22 7.35 4743 1 0.44 6.30 5643 1 0.22 4.68 J 4403 4 0.39 1.14 4635 1 0.72 2.44 5535 1 0.53 2.04 Aver 3.00 0.51 2.52 1.60 0.91 3.01 1.20 0.52 6.31 40 A 4624 1 0.22 0.00 4724 1 0.27 0.00 5624 1 0.14 0.00 B 4254 2 0.06 0.00 4454 2 0.08 0.00 5529 1 0.25 0.00 C 4379 1 0.47 0.00 4479 1 0.27 0.00 5379 1 0.25 0.00 D 4676 3 0.06 0.00 4967 2 0.70 0.00 5884 1 0.36 0.07 E 4694 2 0.09 0.00 4894 2 0.20 0.00 5828 1 0.20 0.00 F 4262 3 0.08 0.00 4487 2 0.80 0.00 5402 1 0.56 0.00 G 4686 3 0.33 0.00 4974 2 0.45 0.00 5877 1 0.17 0.00 H 4450 3 0.06 0.00 4683 1 0.45 0.00 5583 1 0.42 0.00 I 4173 4 0.13 0.00 4444 2 0.42 0.00 5379 1 0.17 0.00 J 4353 4 0.72 0.00 4522 1 0.52 0.00 5422 1 0.36 0.00 Aver 2.60 0.22 0.00 1.60 0.42 0.00 1.00 0.29 0.01 Table 7: Results for instances with n= 40 and different values of Q,|J|, and dj 24