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

Lacroix M.;Rios-Solis Y. A.;Roberto Wolfler Calvo

2021-01-01

---

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.