Efficient formulations for the traveling car renter problem and its quota variant

Abstract

In this paper, we study the recently introduced Traveling Car Renter Problem. This latter is a generalization of the well-known traveling salesman problem, where a solution is a set of paths of different colors as well as an orientation of each path in such a way that the union forms a directed Hamiltonian circuit. Considering costs associated with all edges and all ordered pairs of nodes for each color, the cost of a solution is the sum of the costs of its colored oriented paths, the cost of these later being the sum of the edge costs plus the costs of the arcs from their destination to their origin. We also consider the Quota version of this problem where a weight is associated with every node and the circuit formed by a solution may not be Hamiltonian but must cover a subset of nodes whose sum of weights should be greater than or equal to a fixed value. We propose integer linear programming formulations for these problems. We also propose some valid inequalities for strengthening the models and we devise branch-and-cut algorithms for solving these formulations. The computational results show the efficiency of our formulations as we solve to optimality almost all the instances of the literature, and outperform by an order of magnitude all published approaches.

1 Introduction

In this paper, we consider the Traveling Car Renter Problem (CARS). An instance of the CARS is given by an undirected graph $G=(V,E)$ where $V = \{1,\dots , n\}$ indicates a set of nodes and $ij \in E$ is an edge between nodes i and j. A set $K=\{1,\dots ,o\}$ of colors is also given. Moreover, for every color $k \in K$, a cost $d_{e}^k$ is associated with each edge $e \in E$ and a cost $c_{i,j}^k$ is associated with each ordered pair $(i,j) \in V\times V$ (note that c is asymmetric whereas d is symmetric). A solution to the CARS is a set of paths of different colors as well as an orientation of each path in such a way that the union forms a directed Hamiltonian circuit. The cost of a solution is defined as the sum of the costs of the colored oriented paths, where the cost of a st-path P with color k oriented from s to t is defined as $\sum _{e \in P} d_e^k + c_{s,t}^k$. The CARS consists of finding a solution of minimum cost.

The CARS was introduced by Goldbarg et al. [9], and it is directed to the viewpoint of vehicle rental customers. In general, a user of rented vehicles aims at traveling a specific route by minimizing the rental cost. Nowadays, there are several available vehicles, which means that a user may choose the most attractive vehicle for traveling different parts of the intended route. Nevertheless, an extra fee must be paid whenever a vehicle is delivered to a city different from the one it was rented. Hence, this problem corresponds to the CARS: each vehicle corresponds to a color $k \in K$ and a st-path P of color k oriented from s to t in a solution corresponds to renting the vehicle k at city s, traveling with this vehicle through P and delivering it at city t. The total rental cost of a trip is given by the travel cost $\sum _{e \in P} d_e^k$ plus the extra fee $c_{s,t}^k$ of returning the vehicle from t to s. Note that in this context, a specific node corresponding to the initial position of the customer is generally set, and an initial rental is required at this node.

The Quota CARS (QCARS) is a variant of the CARS where a weight $q_i$ is associated with each node $i \in V$, and a quota Q is given, representing the minimum amount of weight that should be collected. In the QCARS, it is not anymore mandatory to visit all the nodes. Indeed, the algorithm can select the subset of nodes it visits under the constraint to reach at least the threshold Q. Therefore, the QCARS aims at finding at minimum cost a set of paths of different colors with orientations in such a way that the union forms a directed circuit covering a subset of nodes U satisfying $\sum _{i \in U} q_i \ge Q$.

The QCARS was introduced in [4] to model the variant of the CARS where the user, a tourist, wants to visit a subset of touristic places to reach a level of satisfaction. The QCARS also models a specific case of the Rapid Transit Networks Design problems that consist of embedding a set of interconnected transit lines within an undirected network. The nodes correspond to population centroids in a city, while the edges correspond to potential connections to be built between node pairs. Let $q_i$ be the population associated with node i, usually defined as the population living within a reasonable walking distance of the node. Let $d_{ij}^k$ be the cost of constructing a link of type k between i and j and let $c^k_{i,j}$ indicate the cost of constructing a depot at the beginning (i.e., node i) and a depot at the ending (i.e., node j) of the transit line of type k. This cost is asymmetric due to the difference in real-estate price in i and j and the different size of the starting and ending depots. Moreover, the cost could be different since the lines could be of different types, such as: buses, metros, light metros, tramways, or fully overground light-rail systems. An objective of a rapid transit system is to minimize the cost while deserving a certain amount of population [11]. In this case, the model locates the stations chosen among a subset of nodes, determines the connections between the stations, and partitions them into different lines. Under the hypotheses that there is only one line of each type and the lines should create a circuit, this is precisely the QCARS.

The traveling salesman problem (TSP) is a particular case of the CARS where only one car is considered, and since the TSP is NP-hard, so is the CARS. However, from a computational point of view, the TSP can be solved up to thousands of nodes [1], whereas the exact existing methods can only solve instances of the CARS with up to 20 nodes and five colors. In this paper, we provide a new integer linear programming formulation for the CARS, and devise a branch-and-cut algorithm able to solve in an exact way almost all the instances of Goldbarg et al. [9], even those containing hundreds of nodes and more than four colors.

Moreover, the proposed formulation and the branch-and-cut algorithm have been adapted to the QCARS, solving to optimality all the instances generated in [4], the vast majority being solved in less than a second.

2 Literature review

Mathematical programming models and approaches for solving the CARS have been scarcely explored. The first formulations for modeling the CARS have been proposed in [7] and in [3]. As pointed out by Rios et al. [13], the formulation in [3] actually models the CARS without an initial rental required on a specific node. Nevertheless, an incomplete integer programming formulation containing nonlinear constraints was previously proposed in the literature [6]. In [8], three different mathematical formulations are proposed and computationally compared. The first model has a quadratic objective function and is based on the TSP formulation viewed as a particular case of the quadratic assignment problem. The assignment variables represent the positions of the nodes in the Hamiltonian circuit. The second model also has a quadratic objective function, but it is based on the Gavish-Grave’s formulation for the TSP. The last proposed model is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP [1] and has quadratic constraints. An experimental comparison of the three linearized formulations is performed. Instances with up to 52 nodes and three colors are solved to optimality. However, when the number of colors increases, the performance worsens dramatically: with five colors, only instances with less than 20 nodes are solved to optimality.

Pedrosa et al. [12] study the CARS for which the rental costs $c_{s,t}^k$ are all equal for any $s,t\in V$ and any color $k\in K$. They propose an $O(log~ n)-$approximation algorithm for the problem based on the randomized rounding of an exponentially large linear relaxation.

Different metaheuristics have been devised for the CARS. Goldbarg et al. [9] devise two greedy randomized adaptive search procedures with variable neighborhood descent. Several evolutionary algorithms have also been developed: memetic algorithms [4, 9], transgenetic algorithms [2, 6] and scientific algorithm [5]. Two hybrid algorithms have also been proposed [3, 13].

The QCARS has also been considered in the literature. Two integer linear programming formulations for the QCARS are presented in [4, 7]. Both formulations are based on the same nonlinear constraints, but differ by the linearization techniques applied. By using these formulations, instances with up to 16 nodes are solved to optimality. da Silva Menezes et al. [4] and Goldbarg et al. [7] also devise evolutionary algorithms to solve the QCARS. Computational experiments based on instances with up to 100 nodes are reported.

A related problem to the CARS is the colorful traveling salesman problem [10, 16], where edges are colored, and the objective is to find a Hamiltonian circuit with the minimum number of distinct colors. The different colors must not be contiguous, and there are no rental costs as in the CARS. Another problem close to the CARS is the traveling salesman problem with flexible coloring [14]. In this problem, nodes belong to various color classes, and the aim is to assign a color to each node to find the shortest Hamiltonian circuit with the particularity that all nodes of the same color must be visited consecutively.

3 Integer linear programming formulations

In this section, we introduce new formulations for the CARS and the QCARS. Moreover, we present valid inequalities to strengthen the formulations and devise branch-and-cut algorithms to solve these formulations. We also discuss some variants of the problems.

To compare our approach with those in the literature (except the one proposed by da Silva and Ochi [3]), we take into account the same assumption: node one must be the extremity of a path. This assumption stems from the fact that a tourist arrives at a specific city (node one) and starts its trip by renting a vehicle.

3.1 CARS formulation

In our formulation the orientation of a st-path of color k is represented by the arc from s to t with color k. Then a solution with several colors consists of a union of undirected colored paths and by a directed circuit composed of the orientations of the paths. Note that if the solution contains only one color, then we do not have an orientation of the associated circuit. Figure 1 represents a solution on 14 nodes with three colored paths: one with extremities 1 and 8, one with extremities 8 and 11, and the last one with extremities 11 and 1. The first path is oriented from 1 to 8, the second from 8 to 11, and the last one from 11 to 1.

Fig. 1

An example of a solution of an instance of 14 nodes which uses three colors: red, blue and black (color figure online)

The proposed formulation contains four types of variables. The binary variable $x_e^k$ equals one when the edge $e \in E$ belongs to the path having color $k \in K$. The binary variable $y_{i,j}^k$ equals one when the solution contains a path of color $k \in K$ that has i and j as extremities and that is oriented from i to j, for all $i \ne j \in V\times V$. The binary variable $z_i^k$ equals 1 if node $i \in V$ is adjacent to an edge of color $k \in K$. The binary variable $w^k$ equals 1 if color $k \in K$ is the only color used in the solution. Therefore the CARS can be formulated as follows where $\delta (i)$ is the set of edges of E incident to a node $i \in V$, E[S] is the set of edges having both extremities in a node set $S \subseteq V$ and $x^k(F) =\sum _{e \in F} x^k_e$ for $F \subseteq E$.

$$\begin{aligned}&(CARS)\quad \min \sum _{k\in K} \sum _{e\in E} d^k_e x^k_e + \sum _{k \in K}\sum _{i \ne j \in V}c^k_{i,j} y^k_{i,j} + \sum _{k \in K} c_{1,1}^k w^k \end{aligned}$$

(1)

$$\begin{aligned}&s.t. \sum _{k\in K}x^k(\delta (i)) = 2 \quad i \in V \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{k\in K} x^k(E[S]) \le |S| - 1 \quad S\subseteq V , 2 \le |S| \le \lfloor \frac{n}{2} \rfloor \end{aligned}$$

(3)

$$\begin{aligned}&x^k(\delta (i)) + \sum _{j \in V\setminus \{i\}}\left( y^k_{j,i} + y^k_{i,j}\right) = 2 z^k_i \quad k\in K, i \in V \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{i \ne j \in V} y_{i,j}^k + \sum _{\ell \in K} w^\ell \le 1 \quad k \in K \end{aligned}$$

(5)

$$\begin{aligned}&x^k(\delta (1))= z_1^k + w^k\quad k\in K \end{aligned}$$

(6)

$$\begin{aligned}&\sum _{k \in K}\sum _{j \in V\setminus \{i\}} y_{i,j}^k - \sum _{k \in K}\sum _{j \in V\setminus \{i\}} y_{j,i}^k = 0 \quad i \in V\\&\quad w^k, x^k_{e}, y^k_{i,j}, z^k_{i} \in \{0,1\}\nonumber \end{aligned}$$

(7)

The objective function (1) minimizes the travel cost of the Hamiltonian circuit and the sum of the rental costs. Equations (2) are the degree constraints that force the tour to visit each node once. Constraints (3) are the well-known subtour elimination constraints stating that for each node subset $S \subsetneq V$ the number of edges in the solution having both extremities in S must be less than |S|. By (4), if a node i is colored with $k \in K$ (that is $z^k_i=1$) then it is incident to two edges of the path of color k or it is one of its extremities. Inequalities (5) imply that there is at most one path of each color if the solution contains several colors (i.e., $\sum _{k \in K} w^k = 0$) and if the solution contains only one color ($w^k = 1$ for some $k \in K$), its colored path is a circuit (i.e., $y_{i,j}^k = 0$ for all $i\ne j \in V$, $k \in K$). Equation (6) specifies that node 1 is adjacent to two edges of a same color $k \in K$ only if k is the only color in the solution. Equations (7) are the flow conservation constraints associated with variables y. Consider a binary point $\bar{w}, \bar{x}, \bar{y}, \bar{z}$ satisfying constraints (2)–(7). By (2) and (3), the set of edges satisfying $\sum _{k\in K} \bar{x}_e^k = 1$ corresponds to a Hamiltonian circuit, say C. For a color $k \in K$, let $S^k$ be the set of nodes $i \in V$ with $\bar{z}_i^k = 1$, $E^k$ be the set of edges $e \in E$ with $\bar{x}_e^k = 1$ and $A^k$ be the set of arcs (i, j) such that $\bar{y}_{i,j}^k = 1$. By (4), $E^k \subseteq E[S^k]$ and $i,j \in S^k$ for all $(i,j) \in A^k$. Moreover, $|E^k| + |A^k| = |S^k|$. If $w^k = 1$ for some $k \in K$, then $A^k = \emptyset$ by (5) and $E^k \ne \emptyset$ by (6). Since $|E^k| = |S^k|$, constraints (3) imply that $S^k = V$ and the solution is a Hamiltonian circuit of color k. Suppose now that $w^k = 0$ for all $k \in K$. For each $k \in K$, $E^k$ is not a Hamiltonian circuit by (6). Hence, by (3), $|E^k| \le |S^k| - 1$. This implies that $A^k = \{(s_k,t_k)\}$ and $|E^k| = |S^k| - 1$ by (5). Constraints (2), (3) and (4) ensure that $E^k$ is a $s_kt_k$-path covering $S^k$ which means that C is a union of different colored paths. By (7), their orientation forms a directed Hamiltonian circuit, proving the validity of the formulation.

3.2 QCARS formulation

Recall that for this version of the CARS, some nodes may not be visited. Indeed, the model determines the nodes to visit to reach the quota Q at the least cost. Thus, we modify the previous model by introducing additional binary variables: the variable $u_i$ equals one if the node $i \in V$ is visited. To ensure that the collected profit reaches the quota, we consider the following constraint:

$$\begin{aligned} \sum _{i\in V} q_i u_i \ge Q \end{aligned}$$

(8)

We also need to modify inequalities (2) and (3). Equations (2) are replaced by the following:

$$\begin{aligned} \sum _{k\in K}x^k(\delta (i)) = 2 u_i \quad i \in V \end{aligned}$$

(9)

These equations impose that the circuit formed by $\{e \in E: \sum _{k \in K} x_e^k = 1\}$ covers i if and only if i is visited (i.e., $u_i = 1$).

The colored paths may form a circuit that is not Hamiltonian but covers node 1 since some of the other nodes may not be visited. Hence, inequalities (3) are no more valid. We must either restrict inequalities (3) to node subsets not containing node 1 or replace these inequalities by the following generalized subtour inequalities introduced by Wolsey [15]:

$$\begin{aligned} \sum _{k\in K} x^k(E[S]) \le \sum _{j \in S \setminus \{i\}} u_j, \quad S\subseteq V\, \text {such that}\, 1 \notin S, i\in S. \end{aligned}$$

(10)

3.3 Strengthening the linear programming relaxations

In this section, we reinforce the linear relaxations of the CARS and QCARS formulations by strengthening the lower and upper bounds of each variable $z_i^k$ with three inequalities. The efficiency of these new inequalities is experimentally showed in Sect. 4.

The first family gives an upper bound on variables z by ensuring that a node i is adjacent to an edge of color k (i.e., $z_i^k = 1$) only if there exists a path or a circuit of color k (i.e., $\sum _{u \ne v \in V} y_{u,v}^k + w^k = 1$):

$$\begin{aligned} z_i^k \le \sum _{u \ne v \in V} y_{u,v}^k + w^k\quad i \in V, k \in K \end{aligned}$$

(11)

Note that inequalities (5) imply that inequalities (11) dominate $z \le 1$.

The other two families of constraints give a lower bound on variables z. The second family imposes that an edge $e=ij$ is of color k (i.e., $x_e^k = 1$) only if its extremities are incident to an edge of color k (i.e., $z_i^k = 1$ and $z_j^k = 1$).

$$\begin{aligned} x^{k}_{e} \le z^k_i \quad i\in V, e \in \delta (i), k\in K. \end{aligned}$$

(12)

The last family implies that a node $i \in V\setminus \{1\}$ is the extremity of the path of color k (i.e., $\sum _{j \in V \setminus \{i\}} (y_{i,j}^k + y_{j,i}^k) = 1$) only if it is incident to an edge of color k (i.e., $z_i^k = 1$).

$$\begin{aligned} w^k + \sum _{j \in V \setminus \{i\}} \left( y_{i,j}^k + y_{j,i}^k\right) \le z_i^k \quad i\in V\setminus \{1\}, k \in K. \end{aligned}$$

(13)

Note that inequalities (13) are not defined for node 1 since it is redundant with respect to the Eq. (4) associated with node 1 and Eq. (6).

3.4 Branch-and-cut algorithms

In the previous sections, we proposed integer linear formulations for the CARS and its quota variant. Both formulations contain an exponential number of inequalities in order to prevent the formation of subtours: the subtour elimination constraints (3) for the CARS and the generalized subtour elimination constraints (10) for the QCARS. Note that the other constraints, even those introduced in Sect. 3.3 for strengthening the linear relaxations, are in polynomial number. These formulations cannot be directly solved outside very small instances due to this exponential number of constraints. Hence, we solve these formulations using branch-and-cut algorithms where the (generalized) subtour elimination constraints (3) and (10) are added in a lazy way.

CARS The formulation obtained by adding the strengthening inequalities of Sect. 3.3, but removing the subtour elimination constraints (3), that is, the formulation given by inequalities (2), (4)–(7), (11), (12) and (13) is solved using a branch-and-bound procedure. Each time an integer solution is found, the algorithm checks whether it is feasible for the CARS, that is, whether it satisfies all the subtour elimination constraints (3). If not, the integer point is discarded and a constraint (3) violated by this point is added to the current linear relaxation.

This ckeck procedure, called separation problem associated with the subtour elimination constraints, is performed in linear time using a breadth-first search. When subtours are encountered, only the inequality associated with the smallest subtour is added to the current linear relaxation¹.

QCARS The formulation solved using a branch-and-bound is given by inequalities (4)–(9), (11), (12) and (13). An integer solution of this formulation is feasible for the QCARS if it satisfies all the generalized subtour elimination constraints (10).

The separation problem associated with the generalized subtour elimination constraints is performed in linear time using a breadth-first search. If the solution contains subtours, let S be the smallest subset of nodes inducing a subtour and not containing node 1. In this case, the |S| violated inequalities (10) associated with S are added to the current linear relaxation.

3.5 Variants

The formulations introduced below can be slightly modified to tackle different variants of the CARS and QCARS.

Depot The proposed formulations are based on the assumption that node one is the extremity of a path or the starting node of the Hamiltonian circuit with only one color. However, this assumption may be relaxed by modifying the cost $c_{1,1}^k$ to $\min _{i \in V} c_{i,i}^k$ and by replacing constraints (6) by inequalities (11). Indeed, the modification of the cost ensures that the associated rental cost is minimum when a solution contains only one color. Constraints (11) ensure that if color $k \in K$ is the only used color (i.e., $w^k = 1$), no other color is used (i.e., $z_i^\ell = 0$ for all $i \in V$, $\ell \in K \setminus \{k\}$).

Remark that for the QCARS, node one must still be covered by the circuit.

Symmetric vs. asymmetric costs Accordingly to the instances proposed in the literature, we consider in this paper that the cost matrix c is asymmetric, whereas d is symmetric. However, the proposed formulations can be adapted to all the other cases. If c is symmetric, the formulations may be changed by only using variables $y_{i,j}^k$ with $i < j$ and removing equations (7). If d is asymmetric, one needs to consider directed variables $x_{i,j}^k$ and $x_{j,i}^k$ for all $ij \in E$ and $k \in K$ and add flow conservation constraints similar to (7) for the x variables.

Paths with the same color In a solution to the CARS and QCARS, the paths have different colors. This hypothesis is quite restrictive, and one may consider a variant where several paths with the same color are allowed. This variant can be tackled by adding the following inequalities:

$$\begin{aligned} \sum _{i \in W} \sum _{j \notin W} \left( y_{i,j}^k + y_{j,i}^k\right) \le x^k(\delta (W)) \quad k \in K,~\emptyset \ne W \subsetneq V. \end{aligned}$$

(14)

and replacing (5) by

$$\begin{aligned} y_{i,j}^k + \sum _{\ell \in K} w^\ell \le 1 \quad k \in K, i \ne j\in V. \end{aligned}$$

(15)

Inequalities (14) impose that the number of paths of a color $k \in K$ having one extremity in W is no more than the number of edges of color k in the cut $\delta (W)$, for every $\emptyset \ne W \subsetneq V$. The validity of these inequalities stems from the fact that the paths a the same color are disjoint since the union of all the colored paths forms a Hamiltonian circuit. Note that the complexity of the separation problem associated with inequalities (14) is unknown, but such a model may be solved within a branch-and-cut algorithm by separating these inequalities in a lazy way (that is, for binary points only).

4 Computational study

In this section, we present the computational results we obtain for the CARS and the QCARS by using the branch-and-cut algorithms given in Sect. 3.4. We describe the instances of the literature on which our algorithms have been applied and then, we discuss the experimental results we obtain. The instances, the codes and the detailed results can be found in https://doi.org/10.6084/m9.figshare.11959287.

Implementation details The branch-and-cut algorithms presented in Sect. 3.4 were implemented in C++, solved with Gurobi 8.01 with the default parameters, and executed on a MacPro with 3.5 GHz 6-Core Intel Xeon E5 and 32 GB of RAM. The time limit for solving each instance is of 10,000 s, as proposed by Goldbarg et al. [8].

4.1 Instances

CARS We use the benchmark proposed in Goldbarg et al. [8], which is composed of 100 different instances based on complete graphs, divided into two sets of 50 instances each: the Euclidean instances and the non-Euclidean instances. These two sets differ by the way the distance matrices $d^k$, $k\in K$, are obtained.

The symmetric cost matrices $d^k$ are computed from an initial $n\times n$ symmetric matrix $\bar{d}$. This matrix $\bar{d}$ stems from a TSP instance, or it is generated either by considering real distances between some arbitrarily chosen cities or by taking random values.

In the Euclidean instances, $\bar{d}$ is Euclidean and a positive integer $L^k_i$ is randomly generated for all $i \in V$ and for all $k \in K$. The matrix $d^k$, $k \in K$, is then given by $d_{ij}^k = \frac{2L_i^k+3L_j^k}{3} + \bar{d}_{ij}$ for all $i < j$. In the non-Euclidean instances, for each $k \in K$, the matrix $d^k$ is given by $d^k_{ij} = \omega _{ij}^k\bar{d}_{ij}$ for all $i < j$, where $\omega _{ij}^k$ is a random value between [1.4, 2]. In all instances, the asymmetric cost matrices $c^k$ are generated as follows. A positive integer $\alpha _i^k$ is randomly chosen for all $i \in V$ and for all $k \in K$ and $c_{i,j}^k = 6\alpha ^k_i + 2\alpha ^k_j$ for all $i \ne j$.

QCARS We use the benchmark proposed in Goldbarg et al. [7]. These instances are some CARS instances adapted to the QCARS. For this, an integer weight $q_i$ is generated uniformly from [0,100] for all $i \in V$ and the quota is $Q = 0.8 \sum _{i \in V} q_i$. There are 34 Euclidean instances and 33 non-Euclidean.

4.2 Discussion of results

In Tables 1, 2 and 4, we compare the results we obtain with our algorithms with the best exact and heuristic approaches of the literature². All tables contain four sets of columns. The first one describes the instances, and the second reports the results we obtain with our formulation. The last two sets report the best results among the exact and heuristic approaches proposed in the literature, respectively. The first set contains the instance name, the number of nodes |V|, and the number of different colors |K|. For all methods, the column entitled “Sol.” reports the best solution value found, and the column entitled “Time” denotes the computational time in seconds. For exact methods, the column entitled “Gap”³ reports the percentage relative gap between the upper and lower bounds. Column “Col.” indicates the number of colors in the best solution found by our algorithm. Finally, we always report to which paper of the literature we refer to. When it is clear since there is only one paper, we report it as a label over the set of columns. When there are several of them, we add a column entitled “Model” for the exact approach or “Algo” for the heuristic one.

Empty values for a row in any of the last two sets of columns indicate that we could not find computational results for the instance with the corresponding approach. Note that for both CARS and QCARS, there are many instances for which there are neither exact nor heuristic computational results in the literature, to the best of our knowledge.

In all the tables solution values in bold font correspond to the best found solution.

4.2.1 CARS results

We compare our CARS model with the best approaches found in the literature. For exact approaches, DFJ and GG refer to the formulations given in [8] based on the Dantzig-Fulkerson-Johnson’s and Gavish-Grave’s formulations for the TSP, respectively. Since in their paper, the authors run experiments with both Cplex 12.6.3.0 and Gurobi 6.5.2 on a PC with an Intel Core i7 3.45GHz x 8 and 32 Gb of RAM, we precise the solver by adding the letter C (DFJ-C and GG-C) or G (DFJ-G and GG-G) when the result is obtained using Cplex or Gurobi, respectively.

Concerning the heuristics, TA and MA refer to the transgenetic heuristic and memetic algorithm proposed by Goldbarg et al. [6] and implemented on an Intel Xeon QuadCore W3520 2.8 GHz, 8 GB RAM, running Scientific Linux 5.5 with 64 bits and coded in C++. EALSP reports the result achieved by the evolutionary algorithm hybridized with an adaptive local search procedure presented in [3] on a notebook with i7 3630-QM 2.4 GHz processor, 8GB RAM and Windows 8.0 64-bits using CPLEX 12.6.1.

Finally, ScS+ALSP gives the result obtained with the scientific heuristic also hybridized with the adaptive local search procedure proposed by Rios et al. [13] and tested on a PC with an Intel Core i5-2450M, CPU 2.50GHz x4, 3.8 Gb of RAM which ran Ubuntu.

Table 1 reports the computational results for the CARS on Euclidean instances. Our approach is able to solve to optimality all the instances except three. Moreover, 86% of the instances are solved to optimality in less than a minute. Note that the proposed approach outperforms the best exact ones by at least one order of magnitude of computational time. Moreover, it is competitive with heuristics in terms of computational time. Our algorithm is outperformed by the heuristics for only two instances. However, it improves the best known solution for five instances.

Table 1 The CARS formulation tested on the Euclidean instances and compared with other mathematical formulations and heuristic approaches of the literature

Table 2 reports the results obtained for the non-Euclidean instances for the CARS. Our algorithm solves all the instances except the one with 300 nodes and five colors. Moreover, 79% of the instances are solved to optimality in less than a minute. Note that our exact approach is in general at least one order of magnitude faster than the algorithms proposed in the literature including the heuristics. For 14 instances, our algorithm finds a solution better than the best solution reported in the literature.

Table 2 The CARS formulation tested on the non-Euclidean instances and compared with other mathematical formulations and heuristic approaches of the literature

Table 3 The QCARS formulation compared on the Euclidean instances with the mathematical formulations and heuristic approach of Goldbarg et al. [7]

Table 4 The QCARS formulation compared on the non-Euclidean instances with the mathematical formulations and heuristic approach of Goldbarg et al. [7]

4.2.2 QCARS results

In Tables 3 and 4 we compare our QCARS model with the exact formulation and the evolutionary algorithm proposed in [7]. One instance presents inconsistencies (reported by I in the table) in the solution (the heuristic finds a solution whose value is better than the optimum). Table 3 summarizes the results obtained for the QCARS on the Euclidean instances. All instances except one are solved in less than 9 s. The latter one is solved in 182 s, but it seems to be a hard instance since the model proposed in Goldbarg et al. [7] finds a gap of 38.12% after 80,000 s while for all the others the gap is less than 0.3%. Table 4 summarizes the results obtained for the QCARS on the non-Euclidean instances. All instances are solved in less than 4 s except one which is solved in less than 8 s.

The proposed algorithm is really more efficient than the exact approach proposed in [7]. Some instances that were unsolved in 80,000 s are now solved within few seconds. Moreover, our algorithm is faster than their heuristic approach. However, note that it is difficult to compare our running times with those of the literature since the algorithms have been executed on different environments. In particular, the mathematical solver used in [7] is not competitive with the state of the art.

It is worth notice that the percentage of used colors by the QCARS solutions is around 55% of the available ones, which is less than for the CARS instances. This result is probably due to the fact that not all the nodes are chosen in the optimal solution.

4.2.3 Further analysis of the results

In Tables 5 and 6 we evaluate the impact of inequalities (11), (12), and (13) in our formulations for the CARS and the QCARS, respectively. We have solved all the instances of the CARS and the QCARS with every combination of these families of inequalities.

The first column of Tables 5 and 6 indicates whether the results are reported for Euclidean instances (first eight lines marked with “E”) or non-Euclidean instances (last eight lines marked with “NE”). Thus, each line of the table shows the average results over the 50 instances for the CARS and over 34 or 33 for the QCARS. The three following columns labeled with (11), (12), and (13) are check-marked if the corresponding family of inequalities is considered in the model. Columns entitled “Gap %”, “Nodes”, and “Time” (in s) are the average values of those retrieved at the end of the branch-and-cut algorithm of the integer linear solver Gurobi. The “Lazy callbacks” column reports the average number of subtour elimination constraints added to the model. The “Root” column reports the average value of the continuous relaxations without subtour elimination constraints. The column “Int. S. %”, gives the percentage of instances for which a feasible solution could be found by the solver. Note that the instances for which the solver could not find an integer solution within the time limit are not included in the computation of the gap. The last column indicates the percentage of instances solved to optimality within the time limit. Bold values are the best ones.

Table 5 Performance of the CARS integer linear model enhanced by inequalities (11), (12), and (13)

Table 6 Performance of the QCARS integer linear model enhanced by inequalities (11), (12), and (13)

The results reported in Table 5 confirm the quality of the model without valid inequalities presented in Sect. 3.1 which correspond to the rows of the table without check-marks. Indeed, we are able to solve to optimality 80% of the instances, and the running time is around 1200 s for the Euclidean instances and 3000 s for the Non-Euclidean. However, when inequalities (11), (12), and (13) are added for strengthening the model, the number of instances solved to optimality increases up to 96 % and the computational time is almost divided by two for the Euclidean instances and by 10 for the Non-Euclidean. These results show, experimentally, the usefulness of these strengthening inequalities. More precisely, inequalities (11) have the most significant impact, since alone, they are able to divide the computational time by at least 1.7 for the Euclidean instances and around 10 times for the non-Euclidean instances. Similarly, the number of nodes of the branch-and-cut tree is divided by 2 and by more than 300, respectively. Note that for the Euclidean instances considering inequalities (11) and (13) to strengthen the model is the best configuration since the computational time is the smallest, the number of instances solved to optimality is the greatest and last, but not least, the solver is able to find at least a feasible solution for all instances. The best configuration for the non-Euclidean instances is when the three families of inequalities are added. Even if there is one instance in this configuration for which no feasible solution is found, the running time is better than in any other configuration as well as the linear relaxation. Remark that if inequalities (11) have the most significant impact, it is not this family that increases the most the value of the linear relaxation for the Euclidean instances. Indeed, inequalities (12) is the family impacting the most the value of the linear relaxation for these instances. Finally, note that the number of added lazy violated subtour inequalities behaves similarly to the number of nodes in the branch-and-cut tree. Without the three families of valid inequalities, several instances could not be solved. There are ten instances where the optimum cannot be found without the three families of valid inequalities in 10,000 s. When the valid inequalities enforce the model, nine out of ten are solved to optimality in less than 600 s. For example, the Euclidean instance Belem300e reaches the time limit without having found a feasible solution when solved with the model without the strengthening inequalities, but it is solved to optimality in ten minutes with them.

The results reported in Table 6 confirm that the model reported in Sect. 3.2 is useful for solving the QCARS, since it is able to solve to optimality 58 instances over 68 with an average running time of 3000 s. Moreover, when inequalities (11), (12), and (13) are added for strengthening the model, the number of instances solved to optimality increases up 100%, the computational time is divided by 500, and the number of nodes by more than 300. These results show, experimentally, the usefulness of these strengthening inequalities. The results reported in Table 6 confirms the importance of valid inequality (11) also for the QCARS instances. Indeed the computational time for non-Euclidean instances is four orders of magnitudes higher when inequalities (11) are not included. Notice that for the Euclidean instances, the combination of (11), (12) and (13) is the most effective, while for non-Euclidean instances the most effective combination is of (11) with (13).

5 Conclusions

In this paper, we have proposed two integer linear programming formulations for the CARS and the QCARS. We have reinforced these formulations using a polynomial number of inequalities and have devised branch-and-cut algorithms for solving these formulations. The experimental results show the effectiveness of our approach to solve these problems. We were able to solve to optimality all the instances found in the literature but four, and our algorithms clearly outperform the existing approaches. Moreover, the experimental results also show the usefulness of reinforcing the models. The efficiency of our model and its strengthening inequalities deeply relies on the assumption that there exists at most one path of each color in a solution. The variant without this assumption seems far more difficult. However, it is more realistic from an application point of view, especially in the rapid transit network design field, and deserves to be studied. A starting point could be to evaluate the quality of the formulation we propose for this variant.