First, consider the following notation. Let D be the set of depots, D = { 1 , … , | D |}, C be the set of customers to be visited, C = { | D | + 1 , … , n }, where n is the total number of nodes, and N = { 1 , … , n } be the set of nodes, N = { D ∪ C }. Furthermore, let c i j be the distance from node i to node j, ( i , j ) ∈ N, i ≠ j and m d be the number of salesmen located at depot d ∈ D. Note that c i j , i , j ∈ D are not defined since flow from a depot to another depot and to itself is not permitted; however, we can let c i j = ∞, i , j ∈ D.

We define the following decision variable. Let x i j = 1 if arc ( i , j ) is used in the solution, and equal to 0, otherwise, ∀ ( i , j ) ∈ N. The general formulation for the FD-mATSP is as follows: (1) FD-mATSP : Minimize ∑ i ∈ C ∑ j ∈ C , j ≠ i c i j x i j + ∑ d ∈ D ∑ i ∈ C c d i x d i + ∑ i ∈ C ∑ d ∈ D c i d x i d (2) subject to ∑ i ∈ C x d i = m d , ∀ d ∈ D , (3) ∑ i ∈ C x i d = m d , ∀ d ∈ D , (4) x d i + x i d ⩽ 1 , ∀ i ∈ C , ∀ d ∈ D , (5) ∑ j ∈ N x j i = 1 , ∀ i ∈ C , i ≠ j , (6) ∑ j ∈ N x i j = 1 , ∀ i ∈ C , i ≠ j , (7) x i j ∈ { 0 , 1 } , ∀ i , j ∈ N , (8) Subtour elimination constraints (SECs) , (9) Fixed destination constraints (FDCs) . The objective function (1) minimizes the total distance travelled, while Constraints (2) and (3), respectively, enforce that m d salesmen depart and return to depot d, ∀ d ∈ D. Constraints (4) prohibit a tour with a unique customer. Constraints (5) and (6) assure that each customer is visited and departed exactly once, and Constraints (7) define the domain of decision variables. Constraints (8) are the subtour elimination constraints (SECs) which prohibit disconnected cycles, and Constraints (9) are the fixed-destination constraints (FDCs) enforcing the salesmen to return to their starting depots. Next, we present both polynomial-length SECs and FDCs for the FD-mATSP. Exponential-length SECs and FDCs are described in Burger et al. (2018) and Bektaş (2012).

Letting u i indicate a real number representing the order in which a customer i is visited in an optimal tour, Kara and Bektaş (2006) adapt the MTZ-SECs to multi depot travelling salesman problem as follows: (10) KB-SECs : u i − u j + L x i j + ( L − 2 ) x j i ⩽ L − 1 , ∀ i , j ∈ C , i ≠ j , (11) u i + ( L − 2 ) ∑ d ∈ D x d i − ∑ d ∈ D x i d ⩽ L − 1 , ∀ i ∈ C , (12) 1 ⩽ u i ⩽ | C | , ∀ i ∈ C , (13) u i + ∑ d ∈ D x d i + ( 2 − K ) ∑ d ∈ D x i d ⩾ 2 , ∀ i ∈ C . K and L are the minimum and the maximum number of nodes a salesman can visit, respectively. We assume K = 2 and that there is no restriction on L. In this case, we can set L = | C | − 2 ( ∑ d ∈ D m d − 1 ). Constraints (10) are used to break any infeasible subtours. Constraints (11) and (13) collectively impose the bounding limitations.

Letting y i j be the flow on arc ( i , j ), i ≠ j, ∀ i , j ∈ N, we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows: (14) GG-SECs : y d i ⩾ K x d i , ∀ d ∈ D , i ∈ C , (15) y d i ⩽ L x d i , ∀ d ∈ D , i ∈ C , (16) y i j ⩽ ( L − 1 ) x i j , ∀ i , j ∈ C , i ≠ j , (17) ∑ j ∈ N y j i − ∑ j ∈ N y i j = 1 , ∀ i ∈ C , i ≠ j , (18) y d i = 0 , ∀ d ∈ D , i ∈ C , (19) y i j ⩾ 0 , ∀ i , j ∈ N . Constraints (14)–(19) impose the connectivity of the graph induced by the x-variables. Consequently, a path defined by the flow variables y i j exists starting from each depot, d ∈ D, and terminating at that depot after visiting some customers in C. This is achieved by pushing one unit of flow from depots to customers. Constraints (14)–(16), respectively, impose the load balancing restrictions that each path carries at most L and at least K units of flow. Finally, Constraints (17) ensure that each customer appears on a path that start from a depot and converges at it by maintaining the flow of a unit commodity.

Let z i j d be the flow on arc ( i , j ) from depot d, ∀ i , j ∈ N, i ≠ j, ∀ d ∈ D, Bektaş (2012) propose the following FDCs (FDCs1 from now on): (20) FDCs1 : z i j d ⩽ x i j , ∀ i , j ∈ N , ∀ d ∈ D , (21) ∑ i ∈ C z d i d = m d , ∀ d ∈ D , (22) ∑ i ∈ C z i d d = m d , ∀ d ∈ D , (23) ∑ j ∈ N z j i d − ∑ j ∈ N z i j d = 0 , ∀ d ∈ D , ∀ i ∈ C , i ≠ j , (24) z i j d ⩾ 0 , ∀ i , j ∈ N , ∀ d ∈ D . Constraints (20)–(24) impose the fixed-destination feature of the problem by requiring m d units of flow to leave and come back to each depot d using only those arcs for which x i j > 00$]]>.

Letting k i be a variable that indicates the label assigned to customer i, ∀ i ∈ N, Burger et al. (2018) introduce the following FDCs (FDCs2 from now on): (25) FDCs2 : k d = d , ∀ d ∈ D , (26) k i − k j + ( | D | − 1 ) ( x i j + x j i ) ⩽ | D | − 1 , ∀ i , j ∈ N , i ≠ j , (27) k j − k i + ( | D | − 1 ) ( x i j + x j i ) ⩽ | D | − 1 , ∀ i , j ∈ N , i ≠ j , (28) k i ⩾ 0 , ∀ i ∈ N . Constraints (25)–(27) label the nodes visited from each d ∈ D based on the particular index d so that an exchange of salesmen among depots leads to a contradiction. Constraints (28) capture the domain of the decision variables.

Letting y i j ′ be a variable that indicates the label assigned to arc ( i , j ), i ≠ j, ∀ i , j ∈ N, we propose the following FDCs (FDCs3 from now on): (29) FDCs3 : y i j ′ ⩽ | D | x i j , ∀ i , j ∈ N , (30) y d i ′ = d x d i , ∀ d ∈ D , ∀ i ∈ C , (31) y i d ′ = d x i d , ∀ d ∈ D , ∀ i ∈ C , (32) ∑ j ∈ N y j i ′ − ∑ j ∈ N y i j ′ = 0 , ∀ i ∈ C , i ≠ j , (33) y i j ′ ⩾ 0 , ∀ i , j ∈ N . A label d is assigned to all the salesmen leaving from depot d, and this label is used as a flow that is maintained throughout the tours of the salesmen from that depot. To this end, Constraints (29) enforce flow to only occur on arcs for which x i j > 00$]]>. Constraints (30) and (31) enforce d units to depart and return to each base using those arcs for which x d i > 00$]]> and x i d > 00$]]>, ∀ d ∈ D, ∀ i ∈ C, respectively. Constraints (32) are the standard flow conservation constraints, and Constraints (33) represent the domain of the y i j ′ -variables. Note that FDCs2 labels the nodes, while FDCs3 labels the arcs visited by each d ∈ D.

From now on, we will use the following notation to refer to different formulations. Note that in all cases we use the GG-SECs, (14)–19, since they outperform or perform similarly than the other SECs.

MCF: refers to the multi-commodity formulation reported in Bektaş (2012) based on FDCs1; (1)–(7), (14)–(19), (20)–(24).

The FD-mVRPT can be defined as follows. We have a set of D depots each having exactly one capacitated vehicle with an initial inventory of a product, a set of P pickup customers supplying units of a product, and a set E of delivery customers demanding units of a product. The quantities collected from pickup customers can be supplied to any delivery customer. Furthermore, a transshipment is allowed, i.e. units can be transferred among vehicles at pickup customers, while the delivery customers must be visited exactly once. The problem consists of determining a set of routes so that the total cost is minimized in such a way that the delivery customers receive the amount demanded, the vehicle capacity is never exceeded, and vehicles return to their respective starting points. The FD-mVRPT can be viewed as a variant of diverse routing problems encountered in real-life applications such as the swapping problem wherein vehicles transport objects among customers (Anily and Hassin, 1992), the movement of full and empty containers between warehouses and customers (Zhang et al., 2009), the problem of collaborative transport in the milk industry (Paredes-Belmar et al., 2017), and re-balancing in urban bicycles renting systems (Chira et al., 2014).

We illustrate the FD-mATSP in Fig. 1. It consists of two depots D = { 1 , 2 }, each having one vehicle with a capacity of Q = 190 units each, and available commodity in the amount 20 and 32 units, respectively; six pickup customers, P = { 3 , 4 , 5 , 6 , 7 , 8 }; and two delivery customers, E = { 9 , 10 }. The given amount of the product supplied or demanded is denoted by q i , where its positive and negative values indicate pickup and delivery customers, respectively. The variable y i j indicates the level of the load carried on an arc ( i , j ). The optimal solution displayed in Fig. 1 incurs a cost of 447. Vehicle 1 departs from Depot 1 (solid line) to Pickup Location 3 to leave there 20 units, and then, it returns to its starting point. Vehicle 2 departs from Depot 2 (dotted line) and visits Location 5, picking up 22 units, and then it travels to Customers 3 to pick up 45 units (20 of which were left by Vehicle 1). Then, Vehicle 2 visits Locations 10, 8, 4, 6, 7, and 9; and finally, it returns to its origin. This solution can be obtained by adapting the formulations proposed in Bektaş (2012) and in this paper, which allow visiting pickup customer multiples times to collect items.

However, it is not possible to obtain the solution presented in Fig. 1 by adapting the formulation reported in Burger et al. (2018). In this optimal solution, Vehicles 1 and 2, starting from Depots 1 and 2, respectively, transfer units at Pickup Location 3. The formulation by Burger et al. (2018) does not allow customers to be visited more than once since it would require multiple and different labels to be assigned to a node due to vehicles from different depots visiting that node, which the formulation does not permit. This is evident if we try to label the nodes in Fig. 1, which will result in assigning two different labels to Customer 3 (that is visited by Vehicle 1 and 2), i.e. k 3 = 1 and k 3 = 2. By adapting the formulation presented in Burger et al. (2018), we obtain a sub-optimal solution shown in Fig. 2 having a cost of 484 with a unique visit to pickup Location 3. Besides, in some cases, this formulation might become infeasible if all feasible solutions require transfers among vehicles.

The FD-mDCPTP can be stated as follows. We have a set D of depots with m d vehicles in depot D, each having a capacity of Q, a set of customers, C, with q i units of a product available to collect at customers i ∈ C, and a set of T transfer points used to transfer products among vehicles. The problem involves determining a set of routes so that all units supplied by customers are collected, the vehicle capacity is never exceeded, and the vehicles return to their starting depots. The FD-mDCPTP belongs to a class of transportation problems involving intermediate facilities (Guastaroba et al., 2016). An application of this problem arises in dairy industries for the collection of milk (Lou et al., 2016). Trucks must collect and transport milk from a set of producers belonging to a cooperative to different processing plants, and transfer points are used to reload milk among vehicles to reduce the transportation costs.

We present an example to illustrate the FD-mDCPTP (see Fig. 3). We have two depots, D = { 1 , 2 }, each having two identical vehicles with a capacity of Q = 50 units, three transfer points, T = { 3 , 4 , 5 }, and eleven customers, C = { 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 }. The given amount of the product offered by customers i is denoted by q i , and a variable y i j indicates the level of the load carried in an arc ( i , j ). The optimal solution is displayed in Fig. 3 having a cost of 263, and it uses the Transfer Point 3 to interchange goods between vehicles departing from different depots.

For the FD-mATSP, we use the first 20 instances presented in Bektaş (2012) and derived from TSPLIB (1997), as displayed in Table 1. The columns of this table denote the instance number (Instance), the ATSP problem from where it was derived (ATSP instance), the number of nodes (n), and the number of depots ( | D |), respectively. The number of nodes varies from 34 to 171, and the number of salesmen at each depot, d ∈ D, is assumed to be two, and thus, a total of 2 | D | salesmen are available.

For the FD-mVRPT, we created two sets of instances. The first set, displayed in Table 2, is based on the instances reported in Table 1 for which sets P and E, as well as the parameters q i and Q, are generated following the steps described below. Step 1:

(Generation of temporal customer demands q ¯ i ). q ¯ i = ⌈ U ( 30 , 100 ) ⌉, ∀ i ∈ C.

For the FD-mDCPTP, we created the set of instances displayed in Tables 4 and 5, which are based on those reported in Tables 2 and 3. We generate the number of transfer points using a uniform distribution, | T | = ⌈ U ( 1 , 2 ) ⌉. The q i values are the same as those used for the FD-mVRPT, and Q = ⌈ ∑ i ∈ C q i ∑ d ∈ D m d × 10 ⌉ × 10. Finally, q j = 0, ∀ j ∈ T. We assume m d = 2 vehicles at each depot.

We report the results obtained for ALF (proposed formulation), NLF (Burger et al., 2018) and MCF (Bektaş, 2012) developed for the FD-mATSP (see Section 2). These results are displayed in Table 6, where, for each formulation, we report the LP relaxation value ( Z l b ) obtained by relaxing integrality on all binary variables, the objective value of the integer solution ( Z i p ), and the computational time in seconds (CPU) or the integer optimality gap (CPU/Gap) reported by CPLEX, respectively (if an optimal solution is found, then we report T; otherwise, we report the %gap value and underline it). For each instance, we have highlighted in bold the minimum CPU/Gap value. NLF obtained the minimum CPU/Gap in 16 out of 20 cases outperforming the other formulations. ALF outperformed MCF by achieving the minimum CPU/Gap in 16 out of 20 cases. For Instances 12 for which ALF outperforms MCF, it also does so against NLF. The average optimality gaps attained for ALF, NLF, MCF are 3.14%, 1.53%, and 8.82%, while their average computational times are 1321.5, 1199.4, and 1768.1, respectively. All the instances were solved to optimality by each formulation except for Instances 19 and 20.

Based on the results presented above, we can make the following remarks:

We report the results obtained by the proposed formulation (ALF) and the one by Bektaş (2012) (MCF) adapted for the FD-mVRPT presented in Section 3.1.1. Recall that the formulation based on NLF (Burger et al., 2018) is only an approximation and does not represent the problem exactly. The results are displayed in Table 7. The columns in this table are identical to those in Table 6, and the sign “–” is used to denote an infeasible solution generated by a formulation. ALF obtained the minimum T/Gap in 33 out of 35 cases, outperforming MCF. The average optimality gaps attained for ALF and MCF are 4.72% and 7.12% with average computational times of 5555.8 and 6275.5, respectively.

From the results presented above, we can infer the following: 1

The proposed formulation (ALF) outperformed (MCF) for the FD-mVRPT.

In Table 8, we present the results obtained by the proposed formulation (ALF) versus the one reported in Bektaş (2012) (MCF) for the FD-mDCPTP (see Section 3.2). The columns in this table are identical to those in Table 6. ALF outperformed MCF in 29 out of 35 cases. The average optimality gap for the former and the latter are 11.17% and 18.76%, respectively, with a maximum gap of 46.51% for the former and 92.31% for the latter. The proposed two-index formulation is therefore more suitable for modelling variations of the fixed-destination routing problems in which transfer locations are used to minimize transportation costs.