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

Abstract

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.

Keywords

logistics travelling salesman multiple depot fixed-destination

1 Introduction

Routing problems are combinatorial optimization problems that are concerned with designing a set of routes for a fleet of salesmen or vehicles, in order to satisfy customer demand. These problems have broad applicability in industry and constitute the core of the transportation and logistics companies. Two of the most common routing problems are the travelling salesman problem (TSP) (Lawler et al., 1985; Laporte, 1992a; Reinelt, 1994; Davendra, 2010) and the vehicle routing problem (VRP) (Laporte, 1992b; Toth and Vigo, 2002; Golden et al., 2008; Kumar and Panneerselvam, 2012). They are also two of the most challenging problems to solve.

In recent years, several interesting studies have considered a fleet of salesmen or vehicles to be located at several depots from where requests or distribution of goods to customers is made (Montoya-Torres et al., 2015; Ramos et al., 2020). Multi-depot routing problems can be classified as non-fixed-destination (where the salesmen or vehicles can return to any depot) or as fixed-destination (where the vehicles return to their starting points) (Bektaş, 2012). For a review of work on multi-depot routing problems, please see Montoya-Torres et al. (2015).

The case of fixed-destination in multi-depot routing problems is an important feature that has been studied in different applications. These include the fixed-destination multiple travelling salesman problems (Burger et al., 2018), the symmetric generalized multiple-depot multiple travelling salesman problem (Malik et al., 2007), the postal distribution problem, the less-than-truckload transport operations, and balance billing-cycle vehicle routing problems (Bektaş, 2012).

In this paper, we study the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP), which can be defined as follows: Given a complete graph with vertex set $N = D \cup C$ , where the first $| D |$ nodes of $N = {1, \dots, n}$ comprise a set of depots having $m_{d}$ salesmen located initially at depot $d \in D$ ; and where $C = {| D | + 1, | D | + 2, \dots, n}$ comprises the set of customers to be visited, and given an asymmetric distance matrix $[c_{i j}]$ , find $m = \sum_{d \in D} m_{d}$ tours, with $m_{d}$ tours starting and ending at depot $d \in D$ , while collectively having visited a customer i exactly once, $\forall i \in C$ , such that the total distance travelled is minimized.

Less than a handful of compact formulations for the FD-mATSP are reported in the literature. Typically, these formulations incorporate three components: routing, subtour elimination constraints (SECs), and fixed-destination constraints (FDCs). The first component enforces vehicles to depart and return to the depots after visiting each client exactly once, while the second component prohibits cycles in the solution. The last component ensures that the salesmen return to their origins. Kara and Bektaş (2006) used a set of three-index binary variables to capture the routing and fixed-destination components. Then, Bektaş (2012) introduced a set of two-index binary variables to capture the routing part and a set of three-index continuous variables to model the fixed-destination component. Later, Burger et al. (2018) extended the work presented in Burger (2014) and introduced a set of two-index binary variables to capture the routing of vehicles and an additional novel set of two-index variables to label the nodes in order to identify the ones belonging to the same tour, and thereby enforcing the fixed-destination requirements.

In this paper, we formulate a new model for the FD-mATSP, which exploits the multi-depot aspect of the problem and uses two-index variables to label the arcs in order to enforce the fixed-destination requirement, which was motivated by the work reported in Aguayo (2016). Bektaş et al. (2020) have independently developed this formulation for the FDCs. We call this formulation the “arc labelled formulation” (ALF). Bektaş et al. (2020) also propose a “path labelled formulation” (PLF). However, in this paper, we consider only the ALF because of the inapplicability of the PLF to the variants of the FD-mATSP that we address. For a relative performance of these two formulations to solve the FD-mATSP, see Bektaş et al. (2020). In this paper, we present a computational investigation on the performance of the ALF, the two-index formulation of Burger et al. (2018), and the three-index formulation of Bektaş (2012) to capture the FDCs, along with some underlying insights. The two variants of the FD-mATSP that we consider are as follows. In the first variant, the nodes are split into pick-up customers and delivery customers. Each depot has only one capacitated vehicle available and an initial inventory of a product. The quantities collected from pick-up customers can be supplied to any delivery customer. Also, a transshipment is allowed at pick-up customizer locations, while a delivery customer is visited only once. The problem is to determine vehicle routes to meet customer demands with vehicles not exceeding their respective capacities and returning to their starting depots after incurring minimum total cost. In the second variant, given a set of identical vehicles at each depot, which might differ in number, a set of customers with known quantities of products for pick-up, and a set of transfer points to enable transfer of products among vehicles, the problem is to determine vehicle routes to pick up products from all the customers such that the vehicles return to their starting depots and the total cost incurred is minimized.

The remainder of this paper is organized as follows. In Section 2, we present the existing and proposed formulations for the FD-mATSP. In Section 3, we extend our formulation to two new variants of the FD-mATSP in order to show its versatility. In Section 4, we present results of our computational investigation of the proposed formulation. Concluding remarks are made in Section 5.

2 Mathematical Formulations for the FD-mATSP

In this section, we first present a general formulation for the FD-mATSP in Section 2.1, while in Section 2.2, we present some pertinent polynomial-length subtour elimination constraints (SECs). We present a three-index formulation due to Bektaş et al. (2020) and a two-index formulation due to Burger et al. (2018) for the FD-mATSP in Section 2.3. And finally, we introduce our compact two-index formulation for the FD-mATSP in Section 2.4.

2.1 General Formulations for the FD-mATSP

First, consider the following notation. Let D be the set of depots, $D = {1, \dots, | D |$ }, C be the set of customers to be visited, $C = {| D | + 1, \dots, n}$ , where n is the total number of nodes, and $N = {1, \dots, n}$ be the set of nodes, $N = {D \cup C}$ . Furthermore, let $c_{i j}$ be the distance from node i to node j, $(i, j) \in N$ , $i \neq j$ and $m_{d}$ be the number of salesmen located at depot $d \in D$ . Note that $c_{i j}$ , $i, j \in 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} = \infty$ , $i, j \in 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, $\forall (i, j) \in N$ . The general formulation for the FD-mATSP is as follows: $\begin{aligned} FD-mATSP : \\ Minimize \sum_{i \in C} \sum_{j \in C, j \neq i} c_{i j} x_{i j} + \sum_{d \in D} \sum_{i \in C} c_{d i} x_{d i} + \sum_{i \in C} \sum_{d \in D} c_{i d} x_{i d} \end{aligned}$ (1) $\begin{aligned} subject to \\ \sum_{i \in C} x_{d i} = m_{d}, \forall d \in D, \end{aligned}$ (2) $\begin{aligned} \sum_{i \in C} x_{i d} = m_{d}, \forall d \in D, \end{aligned}$ (3) $\begin{aligned} x_{d i} + x_{i d} ⩽ 1, \forall i \in C, \forall d \in D, \end{aligned}$ (4) $\begin{aligned} \sum_{j \in N} x_{j i} = 1, \forall i \in C, i \neq j, \end{aligned}$ (5) $\begin{aligned} \sum_{j \in N} x_{i j} = 1, \forall i \in C, i \neq j, \end{aligned}$ (6) $\begin{aligned} x_{i j} \in {0, 1}, \forall i, j \in N, \end{aligned}$ (7) $\begin{aligned} Subtour elimination constraints (SECs), \end{aligned}$ (8) $\begin{aligned} Fixed destination constraints (FDCs) . \end{aligned}$ (9) 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, $\forall d \in 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).

2.2 Compact SECs

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: $\begin{aligned} KB-SECs : \\ u_{i} - u_{j} + L x_{i j} + (L - 2) x_{j i} ⩽ L - 1, \forall i, j \in C, i \neq j, \end{aligned}$ (10) $\begin{aligned} u_{i} + (L - 2) \sum_{d \in D} x_{d i} - \sum_{d \in D} x_{i d} ⩽ L - 1, \forall i \in C, \end{aligned}$ (11) $\begin{aligned} 1 ⩽ u_{i} ⩽ | C |, \forall i \in C, \end{aligned}$ (12) $\begin{aligned} u_{i} + \sum_{d \in D} x_{d i} + (2 - K) \sum_{d \in D} x_{i d} ⩾ 2, \forall i \in C . \end{aligned}$ (13) 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 (\sum_{d \in 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 \neq j$ , $\forall i, j \in N$ , we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows: $\begin{aligned} GG-SECs : \\ y_{d i} ⩾ K x_{d i}, \forall d \in D, i \in C, \end{aligned}$ (14) $\begin{aligned} y_{d i} ⩽ L x_{d i}, \forall d \in D, i \in C, \end{aligned}$ (15) $\begin{aligned} y_{i j} ⩽ (L - 1) x_{i j}, \forall i, j \in C, i \neq j, \end{aligned}$ (16) $\begin{aligned} \sum_{j \in N} y_{j i} - \sum_{j \in N} y_{i j} = 1, \forall i \in C, i \neq j, \end{aligned}$ (17) $\begin{aligned} y_{d i} = 0, \forall d \in D, i \in C, \end{aligned}$ (18) $\begin{aligned} y_{i j} ⩾ 0, \forall i, j \in N . \end{aligned}$ (19) 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 \in 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.

2.3 Compact FDCs

Let $z_{i j}^{d}$ be the flow on arc $(i, j)$ from depot d, $\forall i, j \in N$ , $i \neq j$ , $\forall d \in D$ , Bektaş (2012) propose the following FDCs (FDCs1 from now on): $\begin{aligned} FDCs1 : \\ z_{i j}^{d} ⩽ x_{i j}, \forall i, j \in N, \forall d \in D, \end{aligned}$ (20) $\begin{aligned} \sum_{i \in C} z_{d i}^{d} = m_{d}, \forall d \in D, \end{aligned}$ (21) $\begin{aligned} \sum_{i \in C} z_{i d}^{d} = m_{d}, \forall d \in D, \end{aligned}$ (22) $\begin{aligned} \sum_{j \in N} z_{j i}^{d} - \sum_{j \in N} z_{i j}^{d} = 0, \forall d \in D, \forall i \in C, i \neq j, \end{aligned}$ (23) $\begin{aligned} z_{i j}^{d} ⩾ 0, \forall i, j \in N, \forall d \in D . \end{aligned}$ (24) 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} > 0$ .

Letting $k_{i}$ be a variable that indicates the label assigned to customer i, $\forall i \in N$ , Burger et al. (2018) introduce the following FDCs (FDCs2 from now on): $\begin{aligned} FDCs2 : \\ k_{d} = d, \forall d \in D, \end{aligned}$ (25) $\begin{aligned} k_{i} - k_{j} + (| D | - 1) (x_{i j} + x_{j i}) ⩽ | D | - 1, \forall i, j \in N, i \neq j, \end{aligned}$ (26) $\begin{aligned} k_{j} - k_{i} + (| D | - 1) (x_{i j} + x_{j i}) ⩽ | D | - 1, \forall i, j \in N, i \neq j, \end{aligned}$ (27) $\begin{aligned} k_{i} ⩾ 0, \forall i \in N . \end{aligned}$ (28) Constraints (25)–(27) label the nodes visited from each $d \in 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.

2.4 Proposed FDCs

Letting $y_{i j}^{'}$ be a variable that indicates the label assigned to arc $(i, j)$ , $i \neq j$ , $\forall i, j \in N$ , we propose the following FDCs (FDCs3 from now on): $\begin{aligned} FDCs3 : \\ y_{i j}^{'} ⩽ | D | x_{i j}, \forall i, j \in N, \end{aligned}$ (29) $\begin{aligned} y_{d i}^{'} = d x_{d i}, \forall d \in D, \forall i \in C, \end{aligned}$ (30) $\begin{aligned} y_{i d}^{'} = d x_{i d}, \forall d \in D, \forall i \in C, \end{aligned}$ (31) $\begin{aligned} \sum_{j \in N} y_{j i}^{'} - \sum_{j \in N} y_{i j}^{'} = 0, \forall i \in C, i \neq j, \end{aligned}$ (32) $\begin{aligned} y_{i j}^{'} ⩾ 0, \forall i, j \in N . \end{aligned}$ (33) 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} > 0$ . Constraints (30) and (31) enforce d units to depart and return to each base using those arcs for which $x_{d i} > 0$ and $x_{i d} > 0$ , $\forall d \in D$ , $\forall i \in 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 \in D$ .

Lemma 1.

FDCs3 is equivalent to FDCs1.

Proof.

We prove this claim by verifying the equivalence between FDCs1 and FDCs3. If we let $y_{i j}^{'} = \sum_{d \in D} d z_{i j}^{d}$ , $\forall i, j \in N$ , then, $y_{i j}^{'}$ , $\forall i, j \in N$ , satisfy Constraints (29)–(33). Similarly, a feasible path for a d in FDCs3 is equivalent to setting $z_{i j}^{d} = 1$ , $\forall i, j$ , on this path, and $z_{i j}^{d} = 0$ , otherwise, $\forall d \in D$ . Consequently, $z_{i j}^{d}$ , $\forall i, j \in N$ , $\forall d \in D$ , will satisfy Constraints (20)–(24). Hence, FDCs1 and FDCs3 are equivalent. □

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

NLF: indicates the node-labelling formulation presented in Burger et al. (2018) based on FDCs2; (1)–(7), (14)–(19), (25)–(28).

ALF: denotes the arc-labelling formulation introduced in this paper based on FDCs3; (1)–(7), (14)–(19), (29)–(33).

We establish the following analytical comparison between these formulations in terms of the strength of their linear programming (LP) relaxations. Lemma 2.

The (LP) relaxation of none of the formulations ALF, NLF, and MCF is tighter than the other.

Proof.

We prove this claim by showing that any of these formulations dominates the other depending upon the problem instance considered. We refer to the LP relaxation results for these formulations presented in Table 6. For Instance ftv47, ( $Z_{l p}$ ), the LP bound of NLF is strictly larger than that of ALF. However, for Instance ft53, the LP bound of ALF is strictly larger than that of NLF.

Regarding ALF and MCF, for Instance ftv47, the LP bound of MCF is strictly larger than that of ALF. However, for Instance ftv55 the LP bound of ALF is strictly larger than of MCF.

As regards MCF and NLF, again for Instance ftv47, the LP bound of MCF is strictly larger than that of NLF. However, for Instance ftv55 the LP bound of NLF is strictly larger than that of MCF. □

3 Extensions of the FD-mATSP

In this section, we present two extensions of the FD-mATSP to illustrate the versatility and computational effectiveness of the two-index compact formulation (ALF) compared with the ones reported in the literature. To that end, we consider the fixed-destination multiple-vehicle routing problem with transshipment (FD-mVRPT), and the fixed-destination multi-depot collection problem with transfer points (FD-mDCPTP).

3.1 FD-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 $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.

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.1 General Formulation for the FD-mVRPT

Before we introduce the model, consider the following notation:

Sets and parameters: Parameters:

Let $x_{i j}$ be equal to 1 if arc $(i, j)$ is used in the solution, and equals 0 otherwise, $\forall i, j \in N$ , $i \neq j$ , and $w_{i}$ be equal to the amount collected from the inventory in location i, $\forall i \in P$ . The formulation is as follows: $\begin{aligned} FD-mVRPT : \\ Minimize \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j} \end{aligned}$ (34) $\begin{aligned} subject to \\ \sum_{i \in C} x_{d i} = 1, \forall d \in D, \end{aligned}$ (35) $\begin{aligned} \sum_{i \in C} x_{i d} = 1, \forall d \in D, \end{aligned}$ (36) $\begin{aligned} \sum_{j \in N} x_{j i} = 1, \forall i \in E, \end{aligned}$ (37) $\begin{aligned} \sum_{j \in N} x_{i j} = 1, \forall i \in E, \end{aligned}$ (38) $\begin{aligned} \sum_{i \in N} x_{i j} = \sum_{i \in N} x_{j i}, \forall \in C, \end{aligned}$ (39) $\begin{aligned} w_{i} ⩽ q_{i} \sum_{j \in N} x_{j i}, \forall i \in P, \end{aligned}$ (40) $\begin{aligned} x_{i j} \in {0, 1}, \forall i, j \in N, i \neq j, \end{aligned}$ (41) $\begin{aligned} w_{i} ⩾ 0, \forall i \in P, \end{aligned}$ (42) $\begin{aligned} SECs and capacity constraints, \end{aligned}$ (43) $\begin{aligned} FDCs \end{aligned}$ (44) 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 $y_{i j}$ be the flow on arc $(i, j)$ , $i \neq j$ , $\forall i, j \in N$ , then we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows: $\begin{aligned} y_{d i} ⩽ q_{d} x_{d i}, \forall d \in D, \forall i \in C, \end{aligned}$ (45) $\begin{aligned} y_{i j} ⩽ Q x_{i j}, \forall i, j \in N, \end{aligned}$ (46) $\begin{aligned} \sum_{i \in N} y_{j i} - \sum_{i \in N} y_{i j} = q_{j}, \forall j \in E, i \neq j, \end{aligned}$ (47) $\begin{aligned} \sum_{i \in N} y_{j i} - \sum_{i \in N} y_{i j} = w_{j}, \forall j \in P, i \neq j . \end{aligned}$ (48) Constraints (45) ensure that the flow from each depot does not exceed the initial inventory available, while Constraints (46) enforce the flow variables $y_{i j}$ 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.2 FD-mDCPTP

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 \in 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.

Fig. 3

An illustration of the FD-mDCPTP.

3.2.1 General Formulation for the FD-mDCPTP

Sets: Parameters:

Let $x_{i j}$ be equal to 1 if arc $(i, j)$ is used in the solution, and equal to 0, otherwise, $\forall i, j \in N$ , $i \neq j$ , and $v_{i}$ 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: $\begin{aligned} FD-mDCPTP : \\ Minimize \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j} \end{aligned}$ (49) $\begin{aligned} subject to: \\ \sum_{i \in T \cup C} x_{d i} = m_{d}, \forall d \in D, \end{aligned}$ (50) $\begin{aligned} \sum_{i \in T \cup C} x_{i d} = m_{d}, \forall d \in D, \end{aligned}$ (51) $\begin{aligned} \sum_{j \in N} x_{j i} = 1, \forall i \in C, \end{aligned}$ (52) $\begin{aligned} \sum_{j \in N} x_{i j} = 1, \forall i \in C, \end{aligned}$ (53) $\begin{aligned} \sum_{i \in N} x_{i j} - \sum_{i \in N} x_{j i} = 0, \forall j \in T \cup C, i \neq j, \end{aligned}$ (54) $\begin{aligned} x_{i j} ⩽ v_{j}, \forall i \in N, \forall j \in T, \end{aligned}$ (55) $\begin{aligned} \sum_{i \in N} x_{i j} ⩾ 2 * v_{j}, \forall j \in T, i \neq j, \end{aligned}$ (56) $\begin{aligned} v_{i} \in {0, 1}, \forall i \in T, \end{aligned}$ (57) $\begin{aligned} x_{i j} \in {0, 1}, \forall i, j \in N, \end{aligned}$ (58) $\begin{aligned} SECs and capacity constraints, \end{aligned}$ (59) $\begin{aligned} Fixed destination constraints (FDCs) . \end{aligned}$ (60)

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 ( $v_{j} = 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 $y_{i j}$ be the flow on arc $(i, j)$ , $i \neq j$ , $\forall i, j \in N$ , we can adapt the single commodity flow-based SECs as follows: $\begin{aligned} y_{d j} = 0, \forall d \in D, \forall j \in D, \end{aligned}$ (61) $\begin{aligned} y_{i j} ⩽ Q * x_{i j}, \forall i, j \in N, \end{aligned}$ (62) $\begin{aligned} \sum_{i \in N} y_{i j} - \sum_{i \in N} y_{j i} = q_{j}, \forall j \in C, i \neq j, \end{aligned}$ (63) $\begin{aligned} \sum_{i \in N} y_{i j} - \sum_{i \in N} y_{j i} = 0, \forall j \in T, i \neq j, \end{aligned}$ (64) $\begin{aligned} y_{i j} ⩾ 0, \forall i, j \in N . \end{aligned}$ (65)

Constraints (61) prohibit to send products between depots, while Constraints (62) enforce the flow variables $y_{i j}$ 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 $c_{i j}$ , $i, j \in D$ are not defined as a flow from one depot to another depot and to itself are not permitted; i.e. we can define $c_{i j} = \infty$ , $i, j \in 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 Computational Results

In this section, we compare the results obtained for the proposed two-index formulation with those obtained for the formulations reported in the literature on the FD-mATSP. We also present the results of this compact formulation extended to the FD-mVRPT and the FD-mDCPTP. All formulations were solved directly in OPL using CPLEX version 12.8.0, with default parameters using a computer with an Intel Xeon(R) CPU E5-2623 v4 @2.60GHZx8 with 62.8 GB of RAM. A time limit of 10,800 seconds was set for all runs.

4.1 Instances

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 $\in D$ , is assumed to be two, and thus, a total of $2 | D |$ salesmen are available.

Table 1
Instances for the FD-mATSP used in Bektaş (2012).

Instance Name n $| D |$

1 ftv33.tsp 34 2

2 ftv35.tsp 36 2

3 ftv38.tsp 39 2

4 p43.tsp 43 2

5 ftv44.tsp 45 2

6 ftv47.tsp 48 2

7 ry48p.tsp 48 2

8 ft53.tsp 53 2

9 ftv55.tsp 56 2

10 ftv55.tsp 56 3

11 ftv64.tsp 65 2

12 ftv64.tsp 65 3

13 ft70.tsp 70 2

14 ft70.tsp 70 3

15 ftv70.tsp 71 2

16 ftv70.tsp 71 3

17 kro124p.tsp 100 2

18 kro124p.tsp 100 3

19 ftv170.tsp 171 5

20 ftv170.tsp 171 5

Instance	Name	n	$\| D \|$
1	ftv33.tsp	34	2
2	ftv35.tsp	36	2
3	ftv38.tsp	39	2
4	p43.tsp	43	2
5	ftv44.tsp	45	2
6	ftv47.tsp	48	2
7	ry48p.tsp	48	2
8	ft53.tsp	53	2
9	ftv55.tsp	56	2
10	ftv55.tsp	56	3
11	ftv64.tsp	65	2
12	ftv64.tsp	65	3
13	ft70.tsp	70	2
14	ft70.tsp	70	3
15	ftv70.tsp	71	2
16	ftv70.tsp	71	3
17	kro124p.tsp	100	2
18	kro124p.tsp	100	3
19	ftv170.tsp	171	5
20	ftv170.tsp	171	5

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 ${\bar{q}}_{i}$ ). ${\bar{q}}_{i} = ⌈ U (30, 100) ⌉$ , $\forall i \in C$ .

Step 2:

(Generation of P and E). We first determine an integer $m = ⌈ \frac{\sum_{i \in C} {\bar{q}}_{i}}{2} ⌉$ . Then, the first set of customers in J, $J \subset C$ , such that $\sum_{i \in J} {\bar{q}}_{i} < m$ , form the set P, and the set $E = C - P$ .

Step 3:

(Checking Feasibility). Given the partitioned sets P and E, it is possible that the resulting supply is less than the demand. Therefore, we determine F units, such that $\sum_{i \in P} {\bar{q}}_{i} + F = \sum_{j \in E} {\bar{q}}_{j}$ , and distribute them evenly among the depots (1 to $| D |$ ).

Step 4:

(Generating vehicle capacity.) We assume a unique vehicle to be present in each depot for both set of instances. We determine the capacity of each vehicle as $Q = ⌈ \frac{\sum_{i \in E} q_{i}}{| D | \times 10} ⌉ \times 10$ . Note that expression $\frac{\sum_{i \in E} q_{i}}{| D |}$ gives a vehicle capacity. We round this number to the next highest 10 by dividing this number by 10 and rounding to the nearest integer, and then multiply it by 10 again.

Step 5:

(Generation of $q_{i}$ ). $q_{i} = {\bar{q}}_{i}$ , $\forall i \in P$ , and $q_{i} = - {\bar{q}}_{i}$ , $\forall i \in E$ .

The second set of instances for the FD-mVRPT, displayed in Table 3, is based on the multi-depot vehicle routing problem (MDVRP) instances proposed in Cordeau (2007). We adapt these instances following the steps described above, except for Step 1, in which we make

{\bar{q}}_{i} = q_{i}^{*}

i \in C

, where

q_{i}^{*}

is the demand in the original instance. Furthermore, in Step 4, we compute

Q = max {Q^{*}, ⌈ \frac{\sum_{i \in E} q_{i}}{D * 10} ⌉} * 10

, where

Q^{*}

is the original vehicle capacity reported in Cordeau (2007).

Table 2

Modified instances derived from the TSPLIB (1997) for FD-mVRPT.

Instance	Name	n	$\| C \|$	$\| D \|$	$\| P \|$	$\| E \|$	Q
1	ftv33.tsp	34	32	2	16	16	560
2	ftv35.tsp	36	34	2	18	16	590
3	ftv38.tsp	39	37	2	18	19	630
4	p43.tsp	43	41	2	22	19	720
5	ftv44.tsp	45	43	2	21	22	760
6	ftv47.tsp	48	46	2	24	22	780
7	ry48p.tsp	48	46	2	24	22	730
8	ft53.tsp	53	51	2	24	27	820
9	ftv55.tsp	56	54	2	28	26	840
10	ftv55.tsp	56	53	3	26	27	650
11	ftv64.tsp	65	63	2	33	30	1070
12	ftv64.tsp	65	62	3	30	32	650
13	ft70.tsp	70	68	2	34	34	1190
14	ft70.tsp	70	67	3	33	34	730
15	ftv70.tsp	71	69	2	34	35	1200
16	ftv70.tsp	71	68	3	34	34	750
17	kro124p.tsp	100	98	2	47	51	1680
18	kro124p.tsp	100	97	3	50	47	1100
19	ftv170.tsp	171	166	5	86	80	1040
20	ftv170.tsp	171	166	5	84	82	1090

Table 3

Modified instances derived from the MDVRP (Cordeau, 2007) for FD-mVRPT.

Instance	Name	n	$\| C \|$	$\| D \|$	$\| P \|$	$\| E \|$	Q
21	p01	54	50	4	27	23	100
22	p02	54	50	4	27	23	160
23	p03	80	75	5	42	33	140
24	p04	108	100	8	50	50	370
25	p05	102	100	2	50	50	370
26	p06	103	100	3	50	50	250
27	p07	104	100	4	50	50	190
28	p12	82	80	2	41	39	110
29	p13	82	80	2	41	39	200
30	p14	82	80	2	41	39	180
31	pr01	52	48	4	83	61	230
32	pr02	100	96	4	21	23	200
33	pr03	148	144	4	48	44	195
34	pr04	196	192	4	96	96	320
35	pr07	78	72	6	35	37	200

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 = ⌈ \frac{\sum_{i \in C} q_{i}}{\sum_{d \in D} m_{d} \times 10} ⌉ \times 10$ . Finally, $q_{j} = 0$ , $\forall j \in T$ . We assume $m_{d} = 2$ vehicles at each depot.

Table 4

Modified instances derived from the TSPLIB (1997) for the FD-mDCPTP.

Instance	Name	n	$\| C \|$	$\| D \|$	$\| T \|$	Q
1	ftv33.tsp	34	30	2	2	510
2	ftv35.tsp	36	31	2	3	530
3	ftv38.tsp	39	35	2	2	570
4	p43.tsp	43	39	2	2	690
5	ftv44.tsp	45	41	2	2	710
6	ftv47.tsp	48	44	2	2	780
7	ry48p.tsp	48	43	2	3	730
8	ft53.tsp	53	49	2	2	820
9	ftv55.tsp	56	52	2	2	840
10	ftv55.tsp	56	50	3	3	650
11	ftv64.tsp	65	61	2	2	1020
12	ftv64.tsp	65	59	3	3	620
13	ft70.tsp	70	66	2	2	1160
14	ft70.tsp	70	65	3	2	710
15	ftv70.tsp	71	66	2	3	1120
16	ftv70.tsp	71	66	3	2	730
17	kro124p.tsp	100	96	2	2	1650
18	kro124p.tsp	100	94	3	3	1050
19	ftv170.tsp	171	163	5	3	1020
20	ftv170.tsp	171	163	5	3	1070

Table 5

Modified instances derived from the MDVRP (Cordeau, 2007) for the FD-mDCPTP.

Instance	Name	n	$\| C \|$	$\| D \|$	$\| T \|$	Q
21	p01	54	47	4	3	100
22	p02	54	48	4	2	100
23	p03	80	73	5	2	140
24	p04	108	97	8	3	360
25	p05	102	98	2	2	370
26	p06	103	97	3	3	240
27	p07	104	97	4	3	180
28	p12	82	77	2	3	100
29	p13	82	78	2	2	110
30	p14	82	78	2	2	110
31	pr01	52	45	4	3	80
32	pr02	100	94	4	2	160
33	pr03	148	142	4	2	220
34	pr04	196	189	4	3	310
35	pr07	78	69	6	3	80

4.2 Results 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 ( $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:

1
NLF outperformed the other two compact formulations for the FD-mATSP, whereas ALF outperformed MCF.
2
From an analytical comparison, none of the formulations dominates the other in terms of the strength of their LP relaxations.
3
From the practitioners’ viewpoint, we recommend using the formulations in the order: NLF, ALF and MCF.

Table 6
Results for the ALF, NLF, and MCF-based formulations on the FD-mATSP.

ALF NLF (Burger et al., 2018) MCF (Bektaş, 2012)

Instance Name $Z_{l p}$ $Z_{i p}$ CPU/Gap $Z_{l p}$ $Z_{i p}$ CPU/Gap $Z_{l p}$ $Z_{i p}$ CPU/Gap

1 ftv33.tsp 1424.75 1579 62.39 1425.36 1579 26.79 1426.13 1579 52.69

2 ftv35.tsp 1590.35 1669 6.12 1600.43 1669 4.39 1593.23 1669 6.07

3 ftv38.tsp 1640.77 1730 20.48 1647.12 1730 10.51 1643.55 1730 16.41

4 p43.tsp 2092.18 5695 99.38 2092.16 5695 36.61 2092.25 5695 1565.15

5 ftv44.tsp 1709.92 1802 12.31 1715.66 1802 4.62 1715.24 1802 13.37

6 ftv47.tsp 1848.25 1975 30.13 1862.57 1975 27.47 1862.73 1975 53.5

7 ry48p.tsp 15218.09 15864 47.94 15219.05 15864 36.59 15218.09 15864 109.45

8 ft53.tsp 6733.17 7396 17.83 6715.23 7396 36.41 6793.2 7396 12.97

9 ftv55.tsp 1642.58 1797 204.65 1647.44 1797 147.66 1550.73 1797 531.34

10 ftv55tsp 1865.66 2013 81.03 1869.5 2013 9.06 1879.31 2013 380.31

11 ftv64.tsp 1889.29 1992 104.5 1896.4 1992 40.96 1899.13 1992 150.38

12 ftv64.tsp 1928.62 2062 78.95 1924.88 2062 365.66 1961.76 2062 1297.76

13 ft70.tsp 40788.65 41105 224.95 40803.28 41105 35.76 40803.52 41105 373.86

14 ft70.tsp 41726.99 42272 664.24 41759.79 42272 471.79 41731.58 42272 1016.82

15 ftv70.tsp 1968.26 2074 76.74 1980.55 2074 41.56 1982.31 2074 197.39

16 ftv.70.tsp 2099.75 2296 2600.35 2102.01 2296 778.26 2114.43 2295.99 6180.85

17 fro124p.tsp 36329.11 37407 245.53 36329.11 37407 144.62 36329.11 37407 659.36

18 kro124p.tsp 36874.41 38076 252.7 36774.28 38076 169.92 36792.4 38076 1144.4

19 ftv170.tsp 3121.47 4087 20.13% 3122.63 3920 16.26% 3134.22 26751 88.14%

20 ftv170.tsp 2093.78 5696.99 42.61% 3095.11 3833.999 14.39% 3107.31 26596 88.15%

4.3 Results for FD-mVRPT

		ALF	NLF (Burger et al., 2018)	MCF (Bektaş, 2012)
1	ftv33.tsp	1424.75	1579	62.39	1425.36	1579	26.79	1426.13	1579	52.69
2	ftv35.tsp	1590.35	1669	6.12	1600.43	1669	4.39	1593.23	1669	6.07
3	ftv38.tsp	1640.77	1730	20.48	1647.12	1730	10.51	1643.55	1730	16.41
4	p43.tsp	2092.18	5695	99.38	2092.16	5695	36.61	2092.25	5695	1565.15
5	ftv44.tsp	1709.92	1802	12.31	1715.66	1802	4.62	1715.24	1802	13.37
6	ftv47.tsp	1848.25	1975	30.13	1862.57	1975	27.47	1862.73	1975	53.5
7	ry48p.tsp	15218.09	15864	47.94	15219.05	15864	36.59	15218.09	15864	109.45
8	ft53.tsp	6733.17	7396	17.83	6715.23	7396	36.41	6793.2	7396	12.97
9	ftv55.tsp	1642.58	1797	204.65	1647.44	1797	147.66	1550.73	1797	531.34
10	ftv55tsp	1865.66	2013	81.03	1869.5	2013	9.06	1879.31	2013	380.31
11	ftv64.tsp	1889.29	1992	104.5	1896.4	1992	40.96	1899.13	1992	150.38
12	ftv64.tsp	1928.62	2062	78.95	1924.88	2062	365.66	1961.76	2062	1297.76
13	ft70.tsp	40788.65	41105	224.95	40803.28	41105	35.76	40803.52	41105	373.86
14	ft70.tsp	41726.99	42272	664.24	41759.79	42272	471.79	41731.58	42272	1016.82
15	ftv70.tsp	1968.26	2074	76.74	1980.55	2074	41.56	1982.31	2074	197.39
16	ftv.70.tsp	2099.75	2296	2600.35	2102.01	2296	778.26	2114.43	2295.99	6180.85
17	fro124p.tsp	36329.11	37407	245.53	36329.11	37407	144.62	36329.11	37407	659.36
18	kro124p.tsp	36874.41	38076	252.7	36774.28	38076	169.92	36792.4	38076	1144.4
19	ftv170.tsp	3121.47	4087	20.13%	3122.63	3920	16.26%	3134.22	26751	88.14%
20	ftv170.tsp	2093.78	5696.99	42.61%	3095.11	3833.999	14.39%	3107.31	26596	88.15%

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.
2
From the practitioners’ viewpoint, our proposed formulation is effective in modelling logistics problems having fixed-destinations in which customers can be visited more than once as in FD-mVRPT.

4.4 Results 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.

Table 7
Results for FD-mVRPT.

ALF MCF

Instance Name $Z_{l p}$ $Z_{i p}$ CPU/Gap $Z_{l p}$ $Z_{i p}$ CPU/Gap

1 ftv33.tsp 909.63 1401 20.16 899.47 1401 43.93

2 ftv35.tsp 1006.67 1560 19.63 1006.63 1560 45.74

3 ftv38.tsp 1045.32 1623 36.22 1045.24 1623 79.52

4 p43.tsp 2612.14 5630 181.22 2612.14 5630 127.07

5 ftv44.tsp 1114.05 1710 75.48 1114.05 1710 95.59

6 ftv47.tsp 1194.56 1834 45.32 1194.56 1834 70.69

7 ry48p.tsp 9229.94 15049 234.5 9229.94 15049 162.4

8 ft53.tsp 4411.48 7103 101.13 4407.62 7103 178.45

9 ftv55.tsp 1146.70 1666 88.18 1145.27 1666 202.99

10 ftv55tsp 1240.06 1713 80.98 1229.19 1713 292.06

11 ftv64.tsp 1272.95 1905 145.71 1269.72 1905 284.33

12 ftv64.tsp 1332.10 1932 197.17 1322.52 1932 645.91

13 ft70.tsp 23483.95 39924 0.13% 23469.02 40124 1.12%

14 ft70.tsp 24869.02 40293 0.68% 23869.02 40752 2.74%

15 ftv70.tsp 1255.34 1995 247.54 1254.21 1995 481.88

16 ftv.70.tsp 1384.61 2058 354.41 1384.61 2058 1218.66

17 fro124p.tsp 23255.89 37280 6618.4 23255.89 37905 4.17%

18 kro124p.tsp 23418.21 37444 1.79% 23418.21 38375 4.84%

19 ftv170.tsp 2319.22 3376 16.29% 2319.22 7674 67.32%

20 ftv170.tsp 2300.82 3742 25.16% 2300.82 – † 10800

21 p01 271.34 449 1697.67 278.97 449 3057.51

22 p02 263.11 445 573.872 263.11 445 1354.55

23 p03 340.18 558 1.51% 340.28 561 2.63%

24 p04 338.96 641 6.91% 348.20 644 9.55%

25 p05 335.15 623 3.20% 343.37 642 11.40%

26 p06 342.23 649 5.82% 357.92 644 6.63%

27 p07 347.45 676 9.21% 371.079 923 40.38%

28 p12 817.43 1616 9.65% 1100.66 1642 11.21%

29 p13 925.21 1617 9.74% 1100.66 1626 10.35%

30 p14 817.43 1617 9.74% 1100.66 1626 10.40%

31 pr01 510.19 867 102.17 510.19 867 725.11

32 pr02 546.88 1174 2.61% 546.88 1239 10.6%

33 pr03 762.99 1821 21.01% 823.77 2054 37.7%

34 pr04 998.14 2288 40.16% 1018.13 – † 10800

35 pr07 625.90 1074 1.44% 625.90 1100 5.80%

		ALF	MCF
1	ftv33.tsp	909.63	1401	20.16	899.47	1401	43.93
2	ftv35.tsp	1006.67	1560	19.63	1006.63	1560	45.74
3	ftv38.tsp	1045.32	1623	36.22	1045.24	1623	79.52
4	p43.tsp	2612.14	5630	181.22	2612.14	5630	127.07
5	ftv44.tsp	1114.05	1710	75.48	1114.05	1710	95.59
6	ftv47.tsp	1194.56	1834	45.32	1194.56	1834	70.69
7	ry48p.tsp	9229.94	15049	234.5	9229.94	15049	162.4
8	ft53.tsp	4411.48	7103	101.13	4407.62	7103	178.45
9	ftv55.tsp	1146.70	1666	88.18	1145.27	1666	202.99
10	ftv55tsp	1240.06	1713	80.98	1229.19	1713	292.06
11	ftv64.tsp	1272.95	1905	145.71	1269.72	1905	284.33
12	ftv64.tsp	1332.10	1932	197.17	1322.52	1932	645.91
13	ft70.tsp	23483.95	39924	0.13%	23469.02	40124	1.12%
14	ft70.tsp	24869.02	40293	0.68%	23869.02	40752	2.74%
15	ftv70.tsp	1255.34	1995	247.54	1254.21	1995	481.88
16	ftv.70.tsp	1384.61	2058	354.41	1384.61	2058	1218.66
17	fro124p.tsp	23255.89	37280	6618.4	23255.89	37905	4.17%
18	kro124p.tsp	23418.21	37444	1.79%	23418.21	38375	4.84%
19	ftv170.tsp	2319.22	3376	16.29%	2319.22	7674	67.32%
20	ftv170.tsp	2300.82	3742	25.16%	2300.82	– †	10800
21	p01	271.34	449	1697.67	278.97	449	3057.51
22	p02	263.11	445	573.872	263.11	445	1354.55
23	p03	340.18	558	1.51%	340.28	561	2.63%
24	p04	338.96	641	6.91%	348.20	644	9.55%
25	p05	335.15	623	3.20%	343.37	642	11.40%
26	p06	342.23	649	5.82%	357.92	644	6.63%
27	p07	347.45	676	9.21%	371.079	923	40.38%
28	p12	817.43	1616	9.65%	1100.66	1642	11.21%
29	p13	925.21	1617	9.74%	1100.66	1626	10.35%
30	p14	817.43	1617	9.74%	1100.66	1626	10.40%
31	pr01	510.19	867	102.17	510.19	867	725.11
32	pr02	546.88	1174	2.61%	546.88	1239	10.6%
33	pr03	762.99	1821	21.01%	823.77	2054	37.7%
34	pr04	998.14	2288	40.16%	1018.13	– †	10800
35	pr07	625.90	1074	1.44%	625.90	1100	5.80%

† Infeasible solution.

Table 8

Results for the FD-mDCPTP.

		ALF			MCF
Instance	Name	$Z_{l p}$	$Z_{i p}$	CPU/Gap	$Z_{l p}$	$Z_{i p}$	CPU/Gap
1	ftv33.tsp	1368.13	1595	167.96	1368.62	1595	822.57
2	ftv35.tsp	1519.53	1690	85.63	1519.72	1690	162.11
3	ftv38.tsp	1556.56	1760	740.09	1556.56	1760	1170.64
4	p43.tsp	2883.29	5728	0.15%	2883.29	5728	0.10%
5	ftv44.tsp	1713.88	1869	336.69	1713.88	1869	737.34
6	ftv47.tsp	1794.81	2084	8.21%	1811.23	2134	6.43%
7	ry48p.tsp	14497.04	16967	2.96%	14497.04	16919	4.27%
8	ft53.tsp	6788.11	7812	2.16%	6849.43	7812	7730.61
9	ftv55.tsp	1599.02	1870	3.68%	1619.74	1863	2.15%
10	ftv55tsp	1828.73	2085	1577.87	1849.92	2085	1932.86
11	ftv64.tsp	1912.83	2090	3.26%	1914.87	2117	4.28%
12	ftv64.tsp	2042.2	2558	10.14%	2055.966	2600	14.91%
13	ft70.tsp	39886.53	40924	0.20%	39886.9	41328	2.53%
14	ft70.tsp	40989.59	45312	4.87%	40993.4	44616	6.69%
15	ftv70.tsp	1960.52	2246	1.84%	1962.43	2243	4.24%
16	ftv.70.tsp	2192.5	2652	8.93%	2194.64	2514	5.43%
17	fro124p.tsp	35875.4	51698	11.32%	35875.4	48613	23.11%
18	kro124p.tsp	37538.71	58555	24.77%	37561.039	58324	32.87%
19	ftv170.tsp	3549.63	7452	36.15%	3551.57	6277	42.25%
20	ftv170.tsp	3579.12	7229	40.42%	3580.48	47485	92.31%
21	p01	416.68	514	7.63%	416.68	532	11.80%
22	p02	427.10	524	8.88%	427.10	540	12.38%
23	p03	532.53	667	12.64%	532.53	928	37.64%
24	p04	581.51	638	2.28%	581.51	748	17.05%
25	p05	574.00	667	7.40%	574.00	672	8.31%
26	p06	587.22	732	14.51%	587.22	867	27.93%
27	p07	606.61	819	21.31%	606.64	977	34.59%
28	p12	968.16	1229	1.71%	968.16	1314	10.43%
29	p13	973.42	1222	0.93%	973.42	1222	1.20%
30	p14	973.42	1222	1.76%	973.42	1222	1.21%
31	pr01	846.45	1059	8.36%	846.45	1105	12.05%
32	pr02	1048.51	1563	23.14%	1048.51	2736	56.43%
33	pr03	1346.24	2784	44.48%	1346.24	3848	60.21%
34	pr04	1366.37	3041	46.51%	1366.37	4861	66.78%
35	pr07	1016.39	1679	31.73%	1016.39	2588	57.04%

5 Concluding Remarks

We have presented a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP), wherein m salesmen depart from D depots and return to their origins after collectively visiting a set of customers exactly once. The proposed compact formulation labels an arc based on the depot from where the salesman visits that arc. This label is used as a flow that is maintained throughout the tour of a salesman from that depot. We show that the proposed and existing formulations for the FD-mATSP do not dominate each other in terms of the strength of their linear programming relaxations. The proposed formulation was demonstrated to be more versatile and effective to solve other variations of this problem. We have demonstrated this by applying it to the solution of two important extensions of the FD-mATSP, namely, the fixed-destination multiple vehicle routing problems with transshipment (FD-mVRPT), and the fixed-destination multi-depot collection problem with transfer points (FD-mDCPTP). The proposed formulation outperformed a three-index formulation due to Bektaş (2012) and a two-index formulation due to Burger et al. (2018) when adapted to both problems. Hence, the proposed compact formulation has the potential to effectively solve various routing and logistics problems with applicability in contemporary logistics and manufacturing management environments. For future work, we propose to extend the proposed formulation to other routing problems as well as design more effective exact algorithms based on a polyhedral analysis of the model that exploits the underlying flow-based structure.

References

Aguayo

M.M.

(2016). Modeling, Analysis, and Exact Algorithms for Some Biomass Logistics Supply Chain Design and Routing Problems. PhD thesis, Virginia Polytechnic Institute and State University.

Anily

Hassin

(1992). The swapping problem. Networks, 22(4), 419–433.

Bektaş

(2012). Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing. European Journal of Operational Research, 216(1), 83–93.

Bektaş

Gouveia

Santos

(2020). Compact formulations for multi-depot routing problems: theoretical and computational comparisons. Computers & Operations Research, 124, 105084.

Burger

(2014). Exact and compact formulation of the fixed-destination travelling salesman problem by cycle imposement through node currents. In: Huisman

L.I.W.A.D.

(Ed.), Operations Research Proceedings 2013. Springer, Cham.

Burger

Schutter

B.D.

(2018). A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem. European Journal of Operational Research, 265(2), 463–477.

Chira

Sedano

Villar

J.R.

Cámara

Corchado

(2014). Urban bicycles renting systems: Modelling and optimization using nature-inspired search methods. Neurocomputing, 135, 98–106.

Cordeau (2007). Multiple Depot VRP Instances. http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/.

Davendra

(2010). Traveling Salesman Problem: Theory and Applications. BoD–Books on Demand.

10.

Gavish

Graves

S.C.

(1978). The travelling salesman problem and related problems. Working paper GR-078-78. Cambridge, MA: Operation Research Center, Massachusetts Institute of Technology.

11.

Golden

B.L.

Raghavan

Wasil

E.A.

(2008). The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York.

12.

Guastaroba

Speranza

M.G.

Vigo

(2016). Intermediate facilities in freight transportation planning: a survey. Transportation Science, 50(3), 763–789.

13.

Kara

Bektaş

(2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3), 1449–1458.

14.

Kumar

S.N.

Panneerselvam

(2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4(03), 66.

15.

Laporte

(1992a). The traveling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231–247.

16.

Laporte

(1992b). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358.

17.

Lawler

E.L.

Lenstra

J.K.

Rinnooy Kan

A.H.

Shmoys

D.B.

(1985). The traveling salesman problem; a guided tour of combinatorial optimization. Journal of the Operational Research Society.

18.

Lou

Luo

Dai

(2016). Study on multi-depot collaborative transportation problem of milk-run pattern. In: MATEC Web of Conferences, Vol. 81, 01004. EDP Sciences.

19.

Malik

Rathinam

Darbha

(2007). An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters, 35(6), 747–753.

20.

Montoya-Torres

J.R.

Franco

J.L.

Isaza

S.N.

Jiménez

H.F.

Herazo-Padilla

(2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.

21.

Paredes-Belmar

Lüer-Villagra

Marianov

Cortés

C.E.

Bronfman

(2017). The milk collection problem with blending and collection points. Computers and Electronics in Agriculture, 134, 109–123.

22.

Ramos

T.R.P.

Gomes

M.I.

Póvoa

A.P.B.

(2020). Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications, 23(2), 103–120.

23.

Reinelt

(1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag, Berlin.

24.

Toth

Vigo

(2002). The Vehicle Routing Problem. SIAM, Philadelphia.

25.

TSPLIB (1997). A Library of traveling salesmen and related problem instances. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/atsp/index.html.

26.

Zhang

Yun

W.Y.

Moon

(2009). A reactive tabu search algorithm for the multi-depot container truck transportation problem. Transportation Research Part E: Logistics and Transportation Review, 45(6), 904–914.

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

Abstract

Keywords

1 Introduction

2 Mathematical Formulations for the FD-mATSP

2.1 General Formulations for the FD-mATSP

3.1 FD-mVRPT

4.1 Instances

1 The proposed formulation (ALF) outperformed (MCF) for the FD-mVRPT. 2 From the practitioners’ viewpoint, our proposed formulation is effective in modelling logistics problems having fixed-destinations in which customers can be visited more than once as in FD-mVRPT. 4.4 Results for FD-mDCPTP

References

1
The proposed formulation (ALF) outperformed (MCF) for the FD-mVRPT.
2
From the practitioners’ viewpoint, our proposed formulation is effective in modelling logistics problems having fixed-destinations in which customers can be visited more than once as in FD-mVRPT.

4.4 Results for FD-mDCPTP