An ils-based heuristic applied to the car renter salesman problem

¹ PESC/Coppe – Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
² Computing Institute – Fluminense Federal University, Niterói, Brazil

^* Corresponding author: sdias@cos.ufrj.br

Received: 26 August 2019
Accepted: 17 May 2020

Abstract

The present paper tackles the Car Renter Salesman Problem (CaRS), which is a Traveling Salesman Problem variant. In CaRS, the goal is to travel through a set of cities using rented vehicles at minimum cost. The main aim of the current problem is to establish an optimal route using rented vehicles of different types to each trip. Since CaRS is N P-Hard, we herein present a heuristic approach to tackle it. The approach is based on a Multi-Start Iterated Local Search metaheuristic, where the local search step is based on the Random Variable Neighborhood Descent methodology. An Integer Linear Programming Formulation based on a Quadratic Formulation from literature is also proposed in the current study. Computational results for the proposed heuristic method in euclidean instances outperform current state-of-the-art results. The proposed formulation also has stronger bounds and relaxation when compared to others from literature.