Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|S1725 - S1746
|02 March 2021
An ils-based heuristic applied to the car renter salesman problem
PESC/Coppe – Federal University of Rio de Janeiro, Rio de Janeiro, Brazil
2 Computing Institute – Fluminense Federal University, Niterói, Brazil
* Corresponding author: email@example.com
Accepted: 17 May 2020
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.
Mathematics Subject Classification: 90C11 / 90C59 / 90B06
Key words: Traveling salesman / heuristics / integer programming / transportation / manufacture processes
© EDP Sciences, ROADEF, SMAI 2021
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.