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

doi:10.1007/978-3-030-92121-7_28

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

Departamento Académico de Ingeniería de Sistemas e Informática

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers
Editors	Dimitris E. Simos, Panos M. Pardalos, Ilias S. Kotsireas
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	364-378
Number of pages	15
ISBN (Print)	9783030921200
DOIs	https://doi.org/10.1007/978-3-030-92121-7_28
State	Published - 2021
Event	15th International Conference on Learning and Intelligent Optimization, LION 15 2021 - Virtual, Online Duration: 20 Jun 2021 → 25 Jun 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12931 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Conference on Learning and Intelligent Optimization, LION 15 2021
City	Virtual, Online
Period	20/06/21 → 25/06/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

Mathematical programming
Metaheuristics
Traveling car renter problem

Access to Document

10.1007/978-3-030-92121-7_28

Cite this

Rios, B. H. O., Casquina, J. C., Añasco, H. H. V., & Paz-Valderrama, A. (2021). Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem. In D. E. Simos, P. M. Pardalos, & I. S. Kotsireas (Eds.), Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers (pp. 364-378). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12931 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-92121-7_28

Rios, Brenner Humberto Ojeda ; Casquina, Junior Cupe ; Añasco, Hossmell Hernan Velasco et al. / Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem. Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers. editor / Dimitris E. Simos ; Panos M. Pardalos ; Ilias S. Kotsireas. Springer Science and Business Media Deutschland GmbH, 2021. pp. 364-378 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b464a8a53b7047f18c6b9cce95738791,

title = "Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem",

abstract = "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.",

keywords = "Mathematical programming, Metaheuristics, Traveling car renter problem",

author = "Rios, {Brenner Humberto Ojeda} and Casquina, {Junior Cupe} and A{\~n}asco, {Hossmell Hernan Velasco} and Alfredo Paz-Valderrama",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 15th International Conference on Learning and Intelligent Optimization, LION 15 2021 ; Conference date: 20-06-2021 Through 25-06-2021",

year = "2021",

doi = "10.1007/978-3-030-92121-7_28",

language = "Ingl{\'e}s",

isbn = "9783030921200",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "364--378",

editor = "Simos, {Dimitris E.} and Pardalos, {Panos M.} and Kotsireas, {Ilias S.}",

booktitle = "Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers",

address = "Alemania",

}

Rios, BHO, Casquina, JC, Añasco, HHV & Paz-Valderrama, A 2021, Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem. in DE Simos, PM Pardalos & IS Kotsireas (eds), Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12931 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 364-378, 15th International Conference on Learning and Intelligent Optimization, LION 15 2021, Virtual, Online, 20/06/21. https://doi.org/10.1007/978-3-030-92121-7_28

Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem. / Rios, Brenner Humberto Ojeda; Casquina, Junior Cupe; Añasco, Hossmell Hernan Velasco et al.
Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers. ed. / Dimitris E. Simos; Panos M. Pardalos; Ilias S. Kotsireas. Springer Science and Business Media Deutschland GmbH, 2021. p. 364-378 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12931 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem

AU - Rios, Brenner Humberto Ojeda

AU - Casquina, Junior Cupe

AU - Añasco, Hossmell Hernan Velasco

AU - Paz-Valderrama, Alfredo

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Mathematical programming

KW - Metaheuristics

KW - Traveling car renter problem

UR - http://www.scopus.com/inward/record.url?scp=85121906852&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-92121-7_28

DO - 10.1007/978-3-030-92121-7_28

M3 - Contribución a la conferencia

AN - SCOPUS:85121906852

SN - 9783030921200

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 364

EP - 378

BT - Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers

A2 - Simos, Dimitris E.

A2 - Pardalos, Panos M.

A2 - Kotsireas, Ilias S.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Conference on Learning and Intelligent Optimization, LION 15 2021

Y2 - 20 June 2021 through 25 June 2021

ER -

Rios BHO, Casquina JC, Añasco HHV, Paz-Valderrama A. Hybrid Meta-heuristics for the Traveling Car Renter Salesman Problem. In Simos DE, Pardalos PM, Kotsireas IS, editors, Learning and Intelligent Optimization - 15th International Conference, LION 15, 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 364-378. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-92121-7_28