A Two-Index Formulation for the Fixed-Destination Multi-Depot Asymmetric Travelling Salesman Problem and Some Extensions

2.1General Formulations for the FD-mATSP

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 cij be the distance from node i to node j, (i,j)∈N, i≠j and md be the number of salesmen located at depot d∈D. Note that cij, i,j∈D are not defined since flow from a depot to another depot and to itself is not permitted; however, we can let cij=∞, i,j∈D.

We define the following decision variable. Let xij=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:

2.2Compact SECs

Letting ui 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:

Letting yij 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:

2.3Compact FDCs

Let zijd 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):

Letting ki 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):

2.4Proposed FDCs

Letting yij′ 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):

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.

3.1FD-mVRPT

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 qi, where its positive and negative values indicate pickup and delivery customers, respectively. The variable yij 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. k3=1 and k3=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.

Fig. 1

Optimal solution obtained by adapting the compact formulation presented in Bektaş (2012) and in this paper to the FD-mVRPT.

Fig. 2

Optimal solution obtained by adapting the compact formulation presented in Burger et al. (2018) to the FD-mVRPT.

3.1.1General Formulation for the FD-mVRPT

Before we introduce the model, consider the following notation:

Sets and parameters: Parameters:

Let xij be equal to 1 if arc (i,j) is used in the solution, and equals 0 otherwise, ∀i,j∈N, i≠j, and wi be equal to the amount collected from the inventory in location i, ∀i∈P. The formulation is as follows:

(34)

FD-mVRPT:Minimize∑i∈N∑j∈Ncijxij

(35)

subject to∑i∈Cxdi=1,∀d∈D,

(36)

∑i∈Cxid=1,∀d∈D,

(37)

∑j∈Nxji=1,∀i∈E,

(38)

∑j∈Nxij=1,∀i∈E,

(39)

∑i∈Nxij=∑i∈Nxji,∀∈C,

(40)

wi⩽qi∑j∈Nxji,∀i∈P,

(41)

xij∈{0,1},∀i,j∈N,i≠j,

(42)

wi⩾0,∀i∈P,

(43)

SECs and capacity constraints,

(44)

FDCs

The objective function (34) minimizes the total cost, while Constraints (35) and (36) enforce that each vehicle departs and returns to each depot, respectively. Constraints (37) and (38) assure that each delivery customer is visited and departed exactly once, while Constraints (39) are the standard flow conservation constraints. Constraints (40) restrict the amount collected at pickup customers. Constraints (41) and (42) define domains of decision variables. Constraints (43) are the subtour elimination constraints (SECs) and capacity constraints which prohibit disconnected cycles, and Constraints (44) are the fixed-destination constraints.

The KB-SECs cannot be extended to this problem since they are developed on the assumption that each node is visited exactly once; and thus, can lead to a contradiction on the labels assigned to nodes visited more than once. Therefore, we only extend the GG-SECs, which are presented next.

Letting yij be the flow on arc (i,j), i≠j, ∀i,j∈N, then we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows:

(45)

ydi⩽qdxdi,∀d∈D,∀i∈C,

(46)

yij⩽Qxij,∀i,j∈N,

(47)

∑i∈Nyji−∑i∈Nyij=qj,∀j∈E,i≠j,

(48)

∑i∈Nyji−∑i∈Nyij=wj,∀j∈P,i≠j.

Constraints (45) ensure that the flow from each depot does not exceed the initial inventory available, while Constraints (46) enforce the flow variables yij to exist only when there is an arc connecting i and j, and limit the vehicle capacity to Q. Constraints (47) and (48) are the flow conservation constraints at delivery and pick-up customers, respectively.

We adapt FDC1s, FDC2s, FDC3s, Constraints (20)–(24), (25)–(27) and (29)–(33), to enforce vehicles to return to their starting points.

3.2FD-mDCPTP

The FD-mDCPTP can be stated as follows. We have a set D of depots with md vehicles in depot D, each having a capacity of Q, a set of customers, C, with qi 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 qi, and a variable yij 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.

Fig. 3

An illustration of the FD-mDCPTP.

3.2.1General Formulation for the FD-mDCPTP

Sets: Parameters:

Let xij be equal to 1 if arc (i,j) is used in the solution, and equal to 0, otherwise, ∀i,j∈N, i≠j, and vi be equal to 1 if the transfer point i is used to transfer goods between two or more vehicles, and equal to 0, otherwise. The formulation is as follows:

(49)

FD-mDCPTP:Minimize∑i∈N∑j∈Ncijxij

(50)

subject to:∑i∈T∪Cxdi=md,∀d∈D,

(51)

∑i∈T∪Cxid=md,∀d∈D,

(52)

∑j∈Nxji=1,∀i∈C,

(53)

∑j∈Nxij=1,∀i∈C,

(54)

∑i∈Nxij−∑i∈Nxji=0,∀j∈T∪C,i≠j,

(55)

xij⩽vj,∀i∈N,∀j∈T,

(56)

∑i∈Nxij⩾2∗vj,∀j∈T,i≠j,

(57)

vi∈{0,1},∀i∈T,

(58)

xij∈{0,1},∀i,j∈N,

(59)

SECs and capacity constraints,

(60)

Fixed destination constraints (FDCs).

The objective function (49) minimizes the total cost, while Constraints (50) and (51) enforce that each vehicle departs and returns to its depot, respectively. Constraints (52) and (53) ensure that each costumer is visited exactly once, while Constraints (54) are the standard flow conservation constraints. Constraints (55) capture if the transfer location is used, while Constrains (56) enforce that if the transfer location is open (vj=1), then at least two vehicles must visit this location. Constraints (57) and (58) define the domains of decision variables. Constraints (59) are the subtour elimination constraints (SECs) and capacity constraints, which prohibit disconnected cycles, and Constraints (60) are the fixed-destination constraints.

Letting yij be the flow on arc (i,j), i≠j, ∀i,j∈N, we can adapt the single commodity flow-based SECs as follows:

(61)

ydj=0,∀d∈D,∀j∈D,

(62)

yij⩽Q∗xij,∀i,j∈N,

(63)

∑i∈Nyij−∑i∈Nyji=qj,∀j∈C,i≠j,

(64)

∑i∈Nyij−∑i∈Nyji=0,∀j∈T,i≠j,

(65)

yij⩾0,∀i,j∈N.

Constraints (61) prohibit to send products between depots, while Constraints (62) enforce the flow variables yij to exist when there is an arc connecting i and j, and they also limit the vehicle capacity to Q. Constraints (63) and (64) are the flow conservation constraints at customers and transfer points, respectively. Constraints (63) ensure that the total amount supplied by customer i is collected, and Constraints (64) prohibit inventory at transfer points. Constraints (65) define domain of the decision variables. Note that cij, i,j∈D are not defined as a flow from one depot to another depot and to itself are not permitted; i.e. we can define cij=∞, i,j∈D.

We use FDC1s and FDC3s, Constraints (20)–(24) and (29)–(33), respectively, as fixed-destination constraints. FDC2s will generate restrictive solutions and may not be able to even find a feasible solution. Consequently, we will not investigate the performance of FDC2s in our computational experiments.

4.1Instances

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 qi and Q, are generated following the steps described below.

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 qi values are the same as those used for the FD-mVRPT, and Q=⌈∑i∈Cqi∑d∈Dmd×10⌉×10. Finally, qj=0, ∀j∈T. We assume md=2 vehicles at each depot.

4.2Results for FD-mATSP

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 (Zlb) obtained by relaxing integrality on all binary variables, the objective value of the integer solution (Zip), 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:

4.3Results for FD-mVRPT

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:

4.4Results for FD-mDCPTP

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.