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_{ij}}]$, find $m={\textstyle\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_{ij}}$ be the distance from node i to node j, $(i,j)\in N$, $i\ne j$ and ${m_{d}}$ be the number of salesmen located at depot $d\in D$. Note that ${c_{ij}}$, $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_{ij}}=\infty $, $i,j\in D$.
We define the following decision variable. Let ${x_{ij}}=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:
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).
(1)
\[\begin{aligned}{}& \textbf{FD-mATSP}:\\ {} & \text{Minimize}\hspace{2.5pt}\sum \limits_{i\in C}\sum \limits_{j\in C,j\ne i}{c_{ij}}{x_{ij}}+\sum \limits_{d\in D}\sum \limits_{i\in C}{c_{di}}{x_{di}}+\sum \limits_{i\in C}\sum \limits_{d\in D}{c_{id}}{x_{id}}\end{aligned}\](2)
\[\begin{aligned}{}& \text{subject to}\\ {} & \sum \limits_{i\in C}{x_{di}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\](3)
\[\begin{aligned}{}& \sum \limits_{i\in C}{x_{id}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\](4)
\[\begin{aligned}{}& {x_{di}}+{x_{id}}\leqslant 1,\hspace{1em}\forall i\in C,\hspace{2.5pt}\forall d\in D,\end{aligned}\](5)
\[\begin{aligned}{}& \sum \limits_{j\in N}{x_{ji}}=1,\hspace{1em}\forall i\in C,\hspace{2.5pt}i\ne j,\end{aligned}\]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:
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({\textstyle\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.
(10)
\[\begin{aligned}{}& \textbf{KB-SECs}:\\ {} & {u_{i}}-{u_{j}}+L{x_{ij}}+(L-2){x_{ji}}\leqslant L-1,\hspace{1em}\forall i,j\in C,\hspace{2.5pt}i\ne j,\end{aligned}\](11)
\[\begin{aligned}{}& {u_{i}}+(L-2)\sum \limits_{d\in D}{x_{di}}-\sum \limits_{d\in D}{x_{id}}\leqslant L-1,\hspace{1em}\forall i\in C,\end{aligned}\]Letting ${y_{ij}}$ be the flow on arc $(i,j)$, $i\ne j$, $\forall i,j\in N$, we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows:
Constraints (14)–(19) impose the connectivity of the graph induced by the x-variables. Consequently, a path defined by the flow variables ${y_{ij}}$ 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.
(14)
\[\begin{aligned}{}& \textbf{GG-SECs}:\\ {} & {y_{di}}\geqslant K{x_{di}},\hspace{1em}\forall d\in D,\hspace{2.5pt}i\in C,\end{aligned}\](15)
\[\begin{aligned}{}& {y_{di}}\leqslant L{x_{di}},\hspace{1em}\forall d\in D,\hspace{2.5pt}i\in C,\end{aligned}\](16)
\[\begin{aligned}{}& {y_{ij}}\leqslant (L-1){x_{ij}},\hspace{1em}\forall i,j\in C,\hspace{2.5pt}i\ne j,\end{aligned}\](17)
\[\begin{aligned}{}& \sum \limits_{j\in N}{y_{ji}}-\sum \limits_{j\in N}{y_{ij}}=1,\hspace{1em}\forall i\in C,\hspace{2.5pt}i\ne j,\end{aligned}\]2.3 Compact FDCs
Let ${z_{ij}^{d}}$ be the flow on arc $(i,j)$ from depot d, $\forall i,j\in N$, $i\ne j$, $\forall d\in D$, Bektaş (2012) propose the following FDCs (FDCs1 from now on):
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_{ij}}>0$.
(20)
\[\begin{aligned}{}& \textbf{FDCs1}:\\ {} & {z_{ij}^{d}}\leqslant {x_{ij}},\hspace{1em}\forall i,j\in N,\hspace{2.5pt}\forall d\in D,\end{aligned}\](21)
\[\begin{aligned}{}& \sum \limits_{i\in C}{z_{di}^{d}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\](22)
\[\begin{aligned}{}& \sum \limits_{i\in C}{z_{id}^{d}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\]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):
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.
(25)
\[\begin{aligned}{}& \textbf{FDCs2}:\\ {} & {k_{d}}=d,\hspace{1em}\forall d\in D,\end{aligned}\](26)
\[\begin{aligned}{}& {k_{i}}-{k_{j}}+\big(|D|-1\big)({x_{ij}}+{x_{ji}})\leqslant |D|-1,\hspace{1em}\forall i,j\in N,\hspace{2.5pt}i\ne j,\end{aligned}\]2.4 Proposed FDCs
Letting ${y^{\prime }_{ij}}$ be a variable that indicates the label assigned to arc $(i,j)$, $i\ne j$, $\forall i,j\in N$, we propose the following FDCs (FDCs3 from now on):
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_{ij}}>0$. Constraints (30) and (31) enforce d units to depart and return to each base using those arcs for which ${x_{di}}>0$ and ${x_{id}}>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^{\prime }_{ij}}$-variables. Note that FDCs2 labels the nodes, while FDCs3 labels the arcs visited by each $d\in D$.
(29)
\[\begin{aligned}{}& \textbf{FDCs3}:\\ {} & {y^{\prime }_{ij}}\leqslant |D|{x_{ij}},\hspace{1em}\forall i,j\in N,\end{aligned}\](30)
\[\begin{aligned}{}& {y^{\prime }_{di}}=d{x_{di}},\hspace{1em}\forall d\in D,\hspace{2.5pt}\forall i\in C,\end{aligned}\](31)
\[\begin{aligned}{}& {y^{\prime }_{id}}=d{x_{id}},\hspace{1em}\forall d\in D,\hspace{2.5pt}\forall i\in C,\end{aligned}\]Proof.
We prove this claim by verifying the equivalence between FDCs1 and FDCs3. If we let ${y^{\prime }_{ij}}={\textstyle\sum _{d\in D}}d{z_{ij}^{d}}$, $\forall i,j\in N$, then, ${y^{\prime }_{ij}}$, $\forall i,j\in N$, satisfy Constraints (29)–(33). Similarly, a feasible path for a d in FDCs3 is equivalent to setting ${z_{ij}^{d}}=1$, $\forall i,j$, on this path, and ${z_{ij}^{d}}=0$, otherwise, $\forall d\in D$. Consequently, ${z_{ij}^{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.
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_{lp}}$), 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_{ij}}$ 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_{ij}}$ be equal to 1 if arc $(i,j)$ is used in the solution, and equals 0 otherwise, $\forall i,j\in N$, $i\ne 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:
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.
(34)
\[\begin{aligned}{}& \textbf{FD-mVRPT}:\\ {} & \text{Minimize}\hspace{1em}\sum \limits_{i\in N}\sum \limits_{j\in N}{c_{ij}}{x_{ij}}\end{aligned}\](35)
\[\begin{aligned}{}& \text{subject to}\\ {} & \sum \limits_{i\in C}{x_{di}}=1,\hspace{1em}\forall d\in D,\end{aligned}\](36)
\[\begin{aligned}{}& \sum \limits_{i\in C}{x_{id}}=1,\hspace{1em}\forall d\in D,\end{aligned}\](37)
\[\begin{aligned}{}& \sum \limits_{j\in N}{x_{ji}}=1,\hspace{1em}\forall i\in E,\end{aligned}\](38)
\[\begin{aligned}{}& \sum \limits_{j\in N}{x_{ij}}=1,\hspace{1em}\forall i\in E,\end{aligned}\](39)
\[\begin{aligned}{}& \sum \limits_{i\in N}{x_{ij}}=\sum \limits_{i\in N}{x_{ji}},\hspace{1em}\forall \in C,\end{aligned}\](40)
\[\begin{aligned}{}& {w_{i}}\leqslant {q_{i}}\sum \limits_{j\in N}{x_{ji}},\hspace{1em}\forall i\in P,\end{aligned}\]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_{ij}}$ be the flow on arc $(i,j)$, $i\ne j$, $\forall i,j\in N$, then we can adapt the single commodity flow-based SECs proposed by Gavish and Graves (1978) as follows:
Constraints (45) ensure that the flow from each depot does not exceed the initial inventory available, while Constraints (46) enforce the flow variables ${y_{ij}}$ 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.
(45)
\[\begin{aligned}{}& {y_{di}}\leqslant {q_{d}}{x_{di}},\hspace{1em}\forall d\in D,\hspace{2.5pt}\forall i\in C,\end{aligned}\]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_{ij}}$ 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.
3.2.1 General Formulation for the FD-mDCPTP
Sets: 
Parameters:
Let ${x_{ij}}$ be equal to 1 if arc $(i,j)$ is used in the solution, and equal to 0, otherwise, $\forall i,j\in N$, $i\ne 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:
(49)
\[\begin{aligned}{}& \textbf{FD-mDCPTP}:\\ {} & \text{Minimize}\hspace{2.5pt}\sum \limits_{i\in N}\sum \limits_{j\in N}{c_{ij}}{x_{ij}}\end{aligned}\](50)
\[\begin{aligned}{}& \text{subject to:}\\ {} & \sum \limits_{i\in T\cup C}{x_{di}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\](51)
\[\begin{aligned}{}& \sum \limits_{i\in T\cup C}{x_{id}}={m_{d}},\hspace{1em}\forall d\in D,\end{aligned}\](52)
\[\begin{aligned}{}& \sum \limits_{j\in N}{x_{ji}}=1,\hspace{1em}\forall i\in C,\end{aligned}\](53)
\[\begin{aligned}{}& \sum \limits_{j\in N}{x_{ij}}=1,\hspace{1em}\forall i\in C,\end{aligned}\](54)
\[\begin{aligned}{}& \sum \limits_{i\in N}{x_{ij}}-\sum \limits_{i\in N}{x_{ji}}=0,\hspace{1em}\forall j\in T\cup C,\hspace{2.5pt}i\ne j,\end{aligned}\](55)
\[\begin{aligned}{}& {x_{ij}}\leqslant {v_{j}},\hspace{1em}\forall i\in N,\hspace{2.5pt}\forall j\in T,\end{aligned}\]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_{ij}}$ be the flow on arc $(i,j)$, $i\ne j$, $\forall i,j\in N$, we can adapt the single commodity flow-based SECs as follows:
(61)
\[\begin{aligned}{}& {y_{dj}}=0,\hspace{1em}\forall d\in D,\hspace{2.5pt}\forall j\in D,\end{aligned}\](62)
\[\begin{aligned}{}& {y_{ij}}\leqslant Q\ast {x_{ij}},\hspace{1em}\forall i,j\in N,\end{aligned}\](63)
\[\begin{aligned}{}& \sum \limits_{i\in N}{y_{ij}}-\sum \limits_{i\in N}{y_{ji}}={q_{j}},\hspace{1em}\forall j\in C,\hspace{2.5pt}i\ne j,\end{aligned}\]Constraints (61) prohibit to send products between depots, while Constraints (62) enforce the flow variables ${y_{ij}}$ 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_{ij}}$, $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_{ij}}=\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 |
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.
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}^{\ast }}$, $i\in C$, where ${q_{i}^{\ast }}$ is the demand in the original instance. Furthermore, in Step 4, we compute $Q=\max \big\{{Q^{\ast }},\big\lceil \displaystyle\frac{{\textstyle\sum _{i\in E}}{q_{i}}}{D\ast 10}\big\rceil \big\}\ast 10$, where ${Q^{\ast }}$ is the original vehicle capacity reported in Cordeau (2007).
-
Step 1: (Generation of temporal customer demands ${\bar{q}_{i}}$). ${\bar{q}_{i}}=\lceil U(30,100)\rceil $, $\forall i\in C$.
-
Step 2: (Generation of P and E). We first determine an integer $m=\big\lceil \displaystyle\frac{{\textstyle\sum _{i\in C}}{\bar{q}_{i}}}{2}\big\rceil $. Then, the first set of customers in J, $J\subset C$, such that ${\textstyle\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 ${\textstyle\sum _{i\in P}}{\bar{q}_{i}}+F={\textstyle\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=\big\lceil \displaystyle\frac{{\textstyle\sum _{i\in E}}{q_{i}}}{|D|\times 10}\big\rceil \times 10$. Note that expression $\displaystyle\frac{{\textstyle\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$.
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|=\lceil U(1,2)\rceil $. The ${q_{i}}$ values are the same as those used for the FD-mVRPT, and $Q=\big\lceil \displaystyle\frac{{\textstyle\sum _{i\in C}}{q_{i}}}{{\textstyle\sum _{d\in D}}{m_{d}}\times 10}\big\rceil \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_{lb}}$) obtained by relaxing integrality on all binary variables, the objective value of the integer solution (${Z_{ip}}$), 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_{lp}}$ | ${Z_{ip}}$ | CPU/Gap | ${Z_{lp}}$ | ${Z_{ip}}$ | CPU/Gap | ${Z_{lp}}$ | ${Z_{ip}}$ | 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
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.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_{lp}}$ | ${Z_{ip}}$ | CPU/Gap | ${Z_{lp}}$ | ${Z_{ip}}$ | 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% |
† Infeasible solution.
Table 8
Results for the FD-mDCPTP.
| ALF | MCF | ||||||
| Instance | Name | ${Z_{lp}}$ | ${Z_{ip}}$ | CPU/Gap | ${Z_{lp}}$ | ${Z_{ip}}$ | 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.
