The Biobjective Consistent Traveling Salesman Problem

Abstract

This article deals with the problem of designing a route for each day of a time period to minimize the total travel cost and the discrepancy in the service time to customers visited on different days. In this paper we allow waiting times for the vehicle at customer locations. The literature already includes exact and heuristic approaches for the variant where the first objective is minimized and the second objective is constrained by a given threshold. The variant do not allow waiting times at customer locations, and it is known as Consistent Travelling Salesman Problem. We are not aware of any previous algorithm in the literature to tackle the biobjective problem, and this article describes three compact formulations for it. Each formulation is suitable for approaching the problem through the well-known weighted-sum method for multiobjective optimization, where some Pareto optimal solutions are sequentially determined by systematically changing the weights among the objective functions. We perform a computational study applying the formulations to tackle instances adapted from the TSPLIB library.

1 Introduction

The Traveling Salesman Problem (TSP) is an NP-Hard problem that has been extensively studied in the literature. Given a depot and a set of customers, it consists of finding a minimum-cost circuit so that a vehicle visits each customer exactly once. The Consistent Travelling Salesman Problem (CTSP) is a variant of the TSP introduced by [2] where a time period is given (say, a week), each customer requires service on some (known in advance) days, and one TSP must be solved for each day. The novel requirement in the CTSP is that customers desire to be served consistently in time when visited in different days, meaning that the service times should be similar for each customer. For example, giving service to a customer in the early morning on Monday and in the late evening on Thursday is undesirable. In the literature this requirement has been modelled as a hard constraint (see e.g. [7, 8]). Indeed, an input threshold T is given in advance to limit the maximum allowed time inconsistency for each customer visited in several days, and then the routes should be determined to ensure it. While there are articles where waiting times of the vehicle at the customer locations are forbidden before the services start, better solutions are found when waiting times are allowed. For that reason, in this paper, we assume that the vehicle is allowed to wait along the route. Under this assumption the mathematical problem is more complex since a solution is not only a route for each day, but also the waiting time at each customer location served each day.

Given a route for each day and the waiting times at each customer location, we consider two characteristics. One characteristic is the total travel cost of the routes, not including waiting times. The other feature is the maximum of the time difference between the visits in different days to a customer, over all the customers. The CTSP looks for a solution, minimizing the first feature, while it limits the second feature to T with a hard constraint. However the real-world problem has a multicriteria nature and a CTSP solution also admits other characteristics, like the travel cost of the route in each day (perhaps even including the waiting times), or the maximum waiting time between when a vehicle arrives to a customer and when the service starts at the customer. To reduce the complexity of the exposition in this article, we restrict our analysis to two characteristic, thus leading to a bicriteria optimization problem. The models and implementations can be easily adapted to also include the other characteristics.

Since the two characteristics (the total travel cost and the time inconsistency at customers) evolve in different directions, there does not exist a feasible solution that minimizes the two objective functions simultaneously. In this context, solving the bicriteria problem is finding a Pareto optimal solution, which is a set of routes that cannot be improved in any of the objectives without degrading the other objective. Since there may be a huge number of Pareto optimal solutions, we only aim at generating supporting non-dominated Pareto-optimal solutions, i.e., solutions with objective values on the convex hull of the Pareto frontier. As typically followed when approaching a bicriteria optimization problem, our article models and solves a single-objective problem where the two selected characteristics are linearly combined with a generic weight $\alpha$, the standard weighted-sum method in multicriteria optimization to generate some Pareto-optimal solutions (see e.g. [5]). We propose three mathematical programming formulations for the single-objective problem and analyse computational experiments using a modern solver to find optimal solutions. The formulations can also be adapted to work on more sophisticated approaches to generate all the Pareto-optimal solutions (see e.g. [3, 4]).

Fig. 1.

Optimal solution with $\alpha = 0$. Travel cost: 8414. Time inconsistency: 1667

Fig. 2.

Optimal solution with $\alpha = 0.1$. Travel cost: 8415. Time inconsistency: 640

Fig. 3.

Optimal solution with $\alpha = 0.27$. Travel Cost: 8572. Time inconsistency: 211

Fig. 4.

Optimal solution with $\alpha = 0.3$. Travel Cost: 8652. Time inconsistency: 0

2 Problem Definition

Let $G = (V, A)$ be a complete directed graph where $V = \{0,1,...,n\}$ is the set of nodes, with 0 representing the depot and 1, ..., n representing the customers. Each arc $(i,j)\in A$ is associated with two variables: $c_{ij}$ and $t_{ij}$ representing the travel cost and travel time, respectively, to go from node i to node j. We use $K=\{1,...,m\}$ to represent the time period (for example, the days of a week). Each day $k\in K$ is associated with a subset of nodes $V_k$, representing the customers to be visited in that day, with $0\in V_k$. The day k is also associated with a set of arcs $A_k=\{(i,j): i, j \in V_k, i \not = j\} \subseteq A$. Let $G^k = (V^k, A^k)$ be the graph on which a Hamiltonian circuit must be computed to define the route on day k. We assume that waiting times are allowed between the vehicle arrives at a customer location and before the service starts. To evaluate the two selected characteristics of a problem solution into a single objective function, let $\alpha$ be a given weight in the interval [0, 1] so the cost of the solution is $1-\alpha$ times the travel cost plus $\alpha$ times the maximum time discrepancy over all the customers.

Fig. 5.

Pareto frontier

Figures 1, 2, 3 and 4 show the optimal solutions for different values of $\alpha$ using an instance introduced in [7]. It is the burma14 instance with 13 customers, with travel costs computed from geographic coordinates. Three days are considered (i.e., $|K|=3$) and every customer requires a visit on each day with probability 0.7. In each figure, we use a different colour for each day, and show a pair of numbers near each customer. The left number is the waiting time of the vehicle at the customer before service starts, which is the right number. The tiny number on an arc shows the travel cost of that arc. Figure 1 corresponds to the solution when $\alpha =0$, hence the time inconsistencies are not penalized and the result is equivalent to solving three independent TSPs. Figure 2 shows the optimal solution of the problem when $\alpha =0.1$; the maximum time difference is reduced from 1667 to 640 increasing the travel cost of the routes by only one unit. It is worth mentioning that a solution with the same travel cost could be obtained with the approach in [8] and with any threshold T in the interval [640, 1666]. As expected, the more importance we place on time consistency in the objective function, the smaller the maximum time difference and the higher the total path cost. Figure 3 shows the solution when $\alpha =0.27$, with travel cost equals to 8572 and the maximum time difference reduced to 211. Figure 4 shows the solution for a decision maker accepting a cost of 8652 to reduce the maximum time difference to zero, i.e. there is no inconsistency for any customer. Although $\alpha$ could still be increased to the value 1, no better solution is generated. Figure 5 shows the eight Pareto-optimal points for this bicriteria problem burma14. The four points along the blue line (frontier) correspond to the optimal solutions depicted in the previous figures, which are non-dominated Pareto solutions.

3 Mathematical Formulations

In this section we describe three formulations. The three formulations are based on a binary variable $x_a^k$ which takes the value 1 if the vehicle in day $k \in K$ traverses the arc $a\in A^k$ and 0 otherwise. As standard in the literature, with $S \subseteq V^k$ we define $\delta _k^+(S):= \{(i,j) \in A^k: i \in S, j \notin S \}$ and $\delta _k^-(S):= \{(i,j) \in A^k: j \in S, i \notin S \}$. We denote the successors of a node i in day k as $\delta ^+_k(i)$ instead of $\delta ^+_k(\{i\})$ and the predecessors of node i in day k as $\delta ^-_k(i)$ instead of $\delta ^-_k(\{i\})$, in addition to $x^k(B)$ instead of $\sum _{a \in B} x_a^k$ where $B \subseteq A^k$. We also define a continuous variable T to represent the maximum time inconsistency of any customer. Therefore the objective function is:

$$\begin{aligned} \text { minimize }\qquad (1-\alpha )\cdot \sum _{k \in K} \sum _{a \in A^k} c_ax_a^k + \alpha \cdot T \end{aligned}$$

(1)

Constraints shared by the three formulations are:

$$\begin{aligned} x^{k}(\delta _k^+(i)) = x^{k}(\delta _k^-(i))=1&\qquad&i\in V^k \end{aligned}$$

(2)

$$\begin{aligned} x^{k}_a \in \{0,1\}&\qquad&a\in A^k. \end{aligned}$$

(3)

Formulation 1 uses an additional continuous variable $z_i^k$ to represent the visit time on day k to customer i, and a big value $M^k$ to upper bound the duration of the route in day k. Consequently the problem is formulated as (1)–(3) and

$$\begin{aligned} z_j^k \ge z_i^k + t_{(i,j)}\cdot x^k_{(i,j)} - M^k \cdot (1-x^k_{(i,j)})&\quad&k\in K,\; i,j\in V^k\setminus \{0\},\;i\not =j \end{aligned}$$

(4)

$$\begin{aligned} z_j^k \ge t_{(0,j)} \cdot x^k_{(0,j)}&\quad&k\in K,\; j\in V^k\setminus \{0\} \end{aligned}$$

(5)

$$\begin{aligned} z_i^p - z_i^q \le T&\quad&p,q\in K, \; i\in V^p\cap V^q\setminus \{0\}. \end{aligned}$$

(6)

The constraints (4) are commonly used in vehicle routing problems when dealing with time constraints, they are known as Miller-Tucker-Zemlin inequalities (see, e.g. [1]), and they imply that $z_j^k \ge z_i^k+t_{(i,j)}$ when $x_{(i,j)}^k=1$ with $i, j \in V^k \setminus \{0\}$. Constraints (5) force the same to the depot. Finally time consistency is established with the inequality (6).

Formulation 2 uses a different variable $g^k_{(i, j)}$ with $k \in K$, $(i,j) \in A^k$ to represent the arrival time at customer i on day k only if j is the next location to visit. The expression $\sum _{a \in B} g^k_a$ is abbreviated as $g^k(B)$ for all $B \subseteq A^k$.

$$\begin{aligned} g^k(\delta _k^+(j)) - g^k(\delta _k^-(j)) \ge \sum _{i\in V^k\setminus \{j\}} t_{(i,j)} x^k_{(i,j)} \quad&k\in K, \; j\in V^k\setminus \{0\} \end{aligned}$$

(7)

$$\begin{aligned} 0 \le g^k_a \le M^k \cdot x^k_a \quad&k\in K,\; a\in A^k \setminus \delta _k^+(0) \end{aligned}$$

(8)

$$\begin{aligned} g^p(\delta _p^+(i)) - g^q(\delta _q^+(i)) \le T \quad&p,q\in K,\; i\in V^p \cap V^q\setminus \{0\} \end{aligned}$$

(9)

Constraints (7) imply the duration of the route to customer j to be greater than or equal to the duration of the route to its predecessor i plus the time that the vehicle needs to make the journey from i to j. Equations (8) set the value of $g_a^k$ to zero whenever $x_a^k=0$. The remaining constraints (9) establish just like constraints (6) in the previous formulation, the time consistency. As in the previous formulation, there are big values $M^k$ for all $k \in K$.

Formulation 3 is based on three families of mathematical variables. A first family consider a multi-commodity flow on each day with $f_a^{ik}$ representing the path from the depot 0 to each customer $i\in V_k$ on each day $k \in K$. A second set includes $y_{i}^k$ representing the idle time of the vehicle at customer i on day k. A third family includes $w^{ik}_j$ representing the idle time on the variable $w^{ik}_j$ if j precedes i. Each feasible solution must verify:

$$\begin{aligned} f^{ik}( \delta _k^+(0)) - f^{ik}(\delta _k^-(0)) = \,\;\;1&\qquad&\end{aligned}$$

(10)

$$\begin{aligned} f^{ik}( \delta _k^+(i)) \, - f^{ik}(\delta _k^-(i))\, = -1&\end{aligned}$$

(11)

$$\begin{aligned} f^{ik}( \delta _k^+(j)) - f^{ik}(\delta _k^-(j)) = \,\;\;0&j\in V^k\setminus \{0,i\} \end{aligned}$$

(12)

$$\begin{aligned} 0 \le f^{ik}_a \le x^{k}_a&\qquad&a\in A^k \end{aligned}$$

(13)

$$\begin{aligned} y_j^k - N_j^k \cdot f^{jk}(\delta _k^-(i)) \le w_{j}^{ik} \le N_j^k \cdot f^{ik}(\delta _k^-(j))&\qquad&i,j\in V^k\setminus \{0\} \end{aligned}$$

(14)

$$\begin{aligned} 0 \le w_{j}^{ik} \le y_j^k&\qquad&i,j\in V^k\setminus \{0\} \end{aligned}$$

(15)

$$\begin{aligned} \bigg ( \sum _{a\in A^p} t_a f^{ip}_a + \sum _{j\in V^p\setminus \{0\}} w_{j}^{ip} \bigg ) -\nonumber \\ \bigg ( \sum _{a\in A^q} t_a f^{iq}_a + \sum _{j\in V^q\setminus \{0\}} w_{j}^{iq} \bigg ) \le T&\qquad&\begin{array}{l} p,q\in K\\ i\in V^p\cap V^q\setminus \{0\}.\end{array} \end{aligned}$$

(16)

We take $N^k_j$ as an upper bound on the maximum idle time at customer i in day k. The Eqs. (10)–(13) guarantee the existence of a path from the depot to each customer requiring a visit in each day. Inequalities (14)–(15) force $w^{ik}_j$ to take the value $y_{j}^k$ if j precedes i on day k, and it is zero otherwise. Constraints (16) establish the time consistency.

Formulations 1 and 2 have a weak linear programming relaxation, not only due to the big values involved in the constraint definitions, but also because the well-known subtour elimination constraints are poorly imposed, as [6] demonstrate. Indeed, the two compact formulations can be strengthened by including the following exponential set of inequalities:

$$\begin{aligned} x^{k}(\delta _k^+(S)) \ge 1 \qquad \qquad S\subset V^k\setminus \{0\}. \end{aligned}$$

(17)

These inequalities are already implicit in Formulation 3, which has a better linear-programming relaxation when compared to the ones of Formulations 1 and 2, as computationally confirmed in the next section.

4 Preliminary Computational Results

We have implemented computer codes to solve the formulations using Gurobi 9.1.2 through its Python API on a personal computer with Intel(R) Core(TM) i7-10700 CPU @ 2.90 GHz, 24 GB RAM, and Windows 10 Pro. We tested the computer codes on benchmark instances from [7]. These instances were generated with $|K|=3$ and 5 days, and with a probability for each client to require service on each day of $freq=0.5$, 0.7 or 0.9. For example, an instance generated with $freq=0.5$ means that a customer requires service in about half of the days in the time period K. The instances also include three options for the threshold T to limit the time inconsistency in the CTSP, but it is no longer meaningful in our bicriteria problem. Recall that T is unknown in our problem. Instead, we created three instances by using $\alpha = 0$, 0.1 and 0.3. The magnitude of the inconsistency makes useless to solve the problem with larger values for $\alpha$ on these benchmark instances.

Table 1. Results on ulysses22

Table 2. Results on bays29

Table 3. Results on dantzig42

We created five computer codes. Codes F1, F2 and F3 are associated with Formulations 1, 2 and 3, respectively. Formulations 1 and 2 were extended with the use of the Subtour Elimination Constraints (17), leading to codes F1+SEC and F2+SEC. Recall that Formulation 3 has these inequalities implicitly. We report computational results on tables with results from the five codes on each instance. The tables report three columns with characteristics of the instances. Column Incons shows the value of the maximum time difference obtained in the solution (i.e., the value of T in the best solution found). Column Travel shows the total travel cost of the routes. Column Obj shows the value of the obtained objective function 1 where the penalty $\alpha$ affects. In addition, for each code, each table reports two columns. Column Time shows the number of seconds taken by the MILP solver to solve the formulation with a time limit of one hour. Column %-gap is the difference between Obj and linear programming bound at the root node, divided by Obj and multiplied by 100.

Tables 1, 2 and 3 show how Formulations 1 and 2 benefit significantly from the use of the Subtour Elimination Constraints (17), it can be observed that Formulation 1 reaches the time limit in 21 of the 54 instances, however, applying the subtour elimination in the linear relaxation, the amount of reached time limits is reduced to only 1 case, in addition to reducing the execution time in the remaining cases. Similarly occurs with Formulation 2, where by applying the linear relaxation the number decreases from 31 to 3 time limits reached. In both cases the %-gap is significantly reduced. On the other hand Formulation 3 performs better than Formulations 1 and 2 since it reaches the time limit in 18 instances. However, it does not behave better than Formulations 1 and 2 when the subtour elimination constraints are added (i.e., codes F1+SEC and F2+SEC). Quite interestingly, the codes F1+SEC, F2+SEC and F3 produced the same linear programming bounds, never larger than 2%. In terms of computational times F1+SEC is the clear winner followed by F2+SEC. In overall terms, the problem becomes more difficult to solve regardless of the formulation as |K|, freq or $\alpha$ increases. When the value of days or the number of nodes to visit each day increases, it is simply a bigger problem. On the other hand, increasing the weight $\alpha$ of the inconsistency T in the objective function makes the instance harder to be solved.

5 Conclusions

This article introduces and addresses a bicriteria optimization variant of the Consistent Travelling Salesman Problem. While waiting times are forbidden in the Consistent Travelling Salesman Problem, our variant allows waiting times for the vehicle at customer locations. This paper describes three Integer Linear Programming models that are suitable to enumerate some Pareto solutions using the weighted-sum method known in Multiobjective Optimization. The first and second formulations outperform the third formulation when they are strengthened with the subtour elimination constraints. As a future direction of research, we plan to implement a Benders’ Decomposition Approach for the third formulation. Although in principle generating inequalities also consume time, the advantage of working with a multicriteria problem is that the valid inequalities generated when using a weight $\alpha$ are also valid for a different weight $\alpha '$. This advantage can be used both for the subtour elimination constraints and for the Benders’ cuts, thus potentially saving computational time when solving a sequence of problems.