Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem

Brenner Humberto Ojeda Rios, Junior Cupe Casquina, Hossmell Hernan Velasco Añasco, Alfredo Paz-Valderrama

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

Resumen

The Traveling Car Renter Problem (CaRS) is a generalization of the classic Traveling Salesman Problem (TSP), where the tour of visits can be broken down into contiguous paths that can be traveled with different rental cars. The objective is to determine the Hamiltonian circuit that has a final minimum cost, considering the penalty paid for each vehicle change on tour. The penalty is the cost of returning the car to the city where it was rented. CaRS is classified as an NP-hard problem. The research focuses on hybrid procedures that combine meta-heuristics and methods based on Linear Programming to deal with CaRS. The hybridized algorithms are scientific algorithms (ScA), variable neighborhood descent (VND), adaptive local search procedure (ALSP), and a new ALSP variant called iterative adaptive local search procedure (IALSP). The following techniques are proposed to deal with the CaRS: ScA+ALSP, ScA+IALSP, and ScA+VND+IALSP. A mixed integer programming model is proposed for the CaRS, which is used in ALSP and IALSP. Nonparametric tests are used to compare the algorithms in a set of instances in the literature.

Idioma originalInglés
Título de la publicación alojadaLearning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers
EditoresDimitris E. Simos, Panos M. Pardalos, Ilias S. Kotsireas
EditorialSpringer Science and Business Media Deutschland GmbH
Páginas364-378
Número de páginas15
ISBN (versión impresa)9783030921200
DOI
EstadoPublicada - 2021
Evento15th International Conference on Learning and Intelligent Optimization, LION 15 2021 - Virtual, Online
Duración: 20 jun. 202125 jun. 2021

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen12931 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia15th International Conference on Learning and Intelligent Optimization, LION 15 2021
CiudadVirtual, Online
Período20/06/2125/06/21

Nota bibliográfica

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Huella

Profundice en los temas de investigación de 'Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem'. En conjunto forman una huella única.

Citar esto