dc.contributor.author | Kobeaga Urriolabeitia, Gorka | |
dc.contributor.author | Merino Maestre, María | |
dc.contributor.author | Lozano Alonso, José Antonio | |
dc.date.accessioned | 2024-02-08T09:13:05Z | |
dc.date.available | 2024-02-08T09:13:05Z | |
dc.date.issued | 2017-09-06 | |
dc.identifier.citation | Computers & Operations Research 90 : 42-59 (2018) | es_ES |
dc.identifier.issn | 0305-0548 | |
dc.identifier.issn | 1873-765X | |
dc.identifier.uri | http://hdl.handle.net/10810/64964 | |
dc.description.abstract | This paper deals with the Orienteering Problem, which is a routing problem. In the Orienteering
Problem each node has a profit assigned and the goal is to find the route that maximizes the total
collected profit subject to a limitation on the total route distance. To solve this problem, we propose
an evolutionary algorithm, whose key characteristic is to maintain unfeasible solutions during the
search. Furthermore, it includes a novel solution codification for the Orienteering Problem, a
novel heuristic for node inclusion in the route, an adaptation of the Edge Recombination crossover
developed for the Travelling Salesperson Problem, specific operators to recover the feasibility of
solutions when required, and the use of the Lin-Kernighan heuristic to improve the route lengths.
We compare our algorithm with three state-of-the-art algorithms for the problem on 344 benchmark
instances, with up to 7397 nodes. The results show a competitive behavior of our approach
in instances of low-medium dimensionality, and outstanding results in the large dimensionality
instances reaching new best known solutions with lower computational time than the state-of-theart
algorithms. | es_ES |
dc.description.sponsorship | This research has been partially supported by Spanish Ministry of Economy and Competitiveness
MINECO through the BCAM Severo Ochoa excellence accreditation SEV-2013-0323 and
Project I+D Excellence MTM2015-65317-P; by Spanish Ministry of Science and Innovation through
the project TIN2016-78365-R; by the Basque Government through the BERC 2014-2017, IT609-13
and IT-928-16 programs; and by the University of the Basque Country UPV/EHU through the UFI
BETS 2011 programme. | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Elsevier | es_ES |
dc.relation | info:eu-repo/grantAgreement/MICIN/TIN2016-78365-R | |
dc.relation | info:eu-repo/grantAgreement/MINECO/MTM2015-65317-P | |
dc.rights | info:eu-repo/semantics/openAccess | es_ES |
dc.subject | orienteering problem | es_ES |
dc.subject | travelling sales | |
dc.subject | person problem | |
dc.subject | evolutionary algorithm | |
dc.subject | combinatorial optimization | |
dc.title | An efficient evolutionary algorithm for the orienteering problem | es_ES |
dc.type | info:eu-repo/semantics/preprint | es_ES |
dc.rights.holder | © 2017 Elsevier Ltd. | |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0305054817302241 | es_ES |
dc.identifier.doi | /10.1016/j.cor.2017.09.003 | |
dc.departamentoes | Matemáticas | es_ES |
dc.departamentoeu | Matematika | es_ES |