An ils-based heuristic applied to the car renter salesman problem
RAIRO. Operations Research, Tome 55 (2021), pp. S1725-S1746

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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020053
Classification : 90C11, 90C59, 90B06
Keywords: Traveling salesman, heuristics, integer programming, transportation, manufacture processes 
@article{RO_2021__55_S1_S1725_0,
     author = {Dias, S\'avio S. and Simonetti, Luidi G. and Ochi, Luiz Satoru},
     title = {An ils-based heuristic applied to the car renter salesman problem},
     journal = {RAIRO. Operations Research},
     pages = {S1725--S1746},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020053},
     mrnumber = {4223139},
     zbl = {1472.90110},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020053/}
}
TY  - JOUR
AU  - Dias, Sávio S.
AU  - Simonetti, Luidi G.
AU  - Ochi, Luiz Satoru
TI  - An ils-based heuristic applied to the car renter salesman problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S1725
EP  - S1746
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020053/
DO  - 10.1051/ro/2020053
LA  - en
ID  - RO_2021__55_S1_S1725_0
ER  - 
%0 Journal Article
%A Dias, Sávio S.
%A Simonetti, Luidi G.
%A Ochi, Luiz Satoru
%T An ils-based heuristic applied to the car renter salesman problem
%J RAIRO. Operations Research
%D 2021
%P S1725-S1746
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020053/
%R 10.1051/ro/2020053
%G en
%F RO_2021__55_S1_S1725_0
Dias, Sávio S.; Simonetti, Luidi G.; Ochi, Luiz Satoru. An ils-based heuristic applied to the car renter salesman problem. RAIRO. Operations Research, Tome 55 (2021), pp. S1725-S1746. doi: 10.1051/ro/2020053

T. Bektas, The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34 (2006) 209–219. | DOI

J. A. Chisman, The clustered traveling salesman problem. Comput. Oper. Res. 2 (1975) 115–119. | DOI

A. R. V. Da Silva and L. S. Ochi, An effcient hybrid algorithm for the Traveling Car Renter Problem. Expert Syst. App. 64 (2016) 132–140. | DOI

M. Da Silva Menezes, M. C. Goldbarg and E. F. Goldbarg, A memetic algorithm for the prize-collecting Traveling Car Renter Problem. In: 2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, New York, NY (2014) 3258–3265. | DOI

M. Edelstein and M. Melnyk, The pool control system. Interfaces 8 (1977) 21–36. | DOI

T. A. Feo and M. G. C. Resende, A probabilistic heuristic for a computational diffcult set covering problem. Oper. Res. Lett. 8 (1989) 67–71. | MR | Zbl | DOI

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Co., New York, NY (1979). | Zbl

D. K. George and C. H. Xia, Fleet-sizing and service availability for a vehicle rental system via closed queueing networks. Eur. J. Oper. Res. 211 (2011) 198–207. | MR | Zbl | DOI

Global Industry Analysts, Inc., Car rental business – global strategic business report, Tech. Rep. 338373, research and markets. http://www.researchandmarkets.com/reports/338373/car_rental_business_global_strategic_business (2014).

M. C. Goldbarg, P. H. Asconavieta and E. F. G. Goldbarg, Memetic algorithm for the traveling car renter problem: an experimental investigation. Memet. Comput. 4 (2012) 89–108. | DOI

M. C. Goldbarg, E. F. Goldbarg, P. H. Asconavieta, M. D. S. Menezes, H. P. Luna, A transgenetic algorithm applied to the Traveling Car Renter Problem. Expert Syst. App. 40 (2013) 6298–6310. | DOI

M. C. Goldbarg, E. F. Goldbarg, H. P. Luna, M. S. Menezes and L. Corrales, Integer programming models and linearizations for the Traveling Car Renter Problem. Optim. Lett. 12 (2018) 743–761. | MR | Zbl | DOI

A. Hertz, D. Schindl and N. Zufferey, A solution method for a car fleet management problem with maintenance constraints. J. Heuristics 15 (2009) 425–450. | Zbl | DOI

K. Ilavarasi and K. S. Joseph, Variants of travelling salesman problem: a survey. In: International Conference on Information Communication and Embedded Systems (ICICES2014). IEEE, New York, NY (2014) 1–7.

Z. Li and F. Tao, On determining optimal fleet size and vehicle transfer policy for a car rental company. Comput. Oper. Res. 37 (2010) 341–350. | Zbl | DOI

M. López-Ibánez, J. Dubois-Lacoste, T. Stützle and M. Birattari, The irace package, iterated race for automatic algorithm configuration, Oper. Res. Perspect. 3 (2011). DOI: | DOI | MR

H. R. Lourenco, O. C. Martin and T. Stützle, Iterated local search: framework and applications. In: Handbook of Metaheuristics. Vol 146 of International Series in Operations Research & Management Science. Springer, New York, NY (2010) 363–397.

N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl | DOI

I. H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41 (1993) 421–451. | Zbl | DOI

J. E. Pachon, E. Iakovou, C. Ip and R. Aboudi, A synthesis of tactical fleet planning models for the car rental industry. IIE Trans. 35 (2003) 907–916. | DOI

PassMark, Passmark Software Pty Ltd – CPU benchmarks. [Accessed October 24, 2016 by https://www.cpubenchmark.net] (2016).

P. H. V. Penna, A. Subramanian and L. S. Ochi, An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. J. Heuristics 19 (2013) 201–232. | DOI

S. Seay and A. Narsing, Transitioning to a lean paradigm: a model for sustainability in the leasing and rental industries. Acad. Strategic Manage. J. 12 (2013) 113.

M. M. Silva, A. Subramanian, T. Vidal and L. S. Ochi, A simple and effective metaheuristic for the minimum latency problem. Eur. J. Oper. Res. 221 (2012) 513–520. | Zbl | DOI

C. Steinhardt and J. Gönsch, Integrated revenue management approaches for capacity control with planned upgrades. Eur. J. Oper. Res. 223 (2012) 380–391. | Zbl | DOI

A. Subramanian and M. Battarra, An iterated local search algorithm for the Travelling Salesman Problem with Pickups and Deliveries. J. Oper. Res. Soc. 64 (2013) 402–409. | DOI

P. Vansteenwegen, W. Souffriau and K. Sörensen, The travelling salesperson problem with hotel selection. J. Oper. Res. Soc. 63 (2012) 207–217. | DOI

Y. Xiong, B. Golden and E. Wasil, The colorful traveling salesman problem. In: Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Springer, New York, NY (2007) 115–123. | Zbl

Cité par Sources :