Show simple item record

dc.contributor.authorKobeaga G.en_US
dc.contributor.authorMerino M.en_US
dc.contributor.authorLozano J.A.en_US
dc.date.accessioned2017-09-07T11:02:39Z
dc.date.available2017-09-07T11:02:39Z
dc.date.issued2017-09-06
dc.identifier.issn0305-0548
dc.identifier.urihttp://hdl.handle.net/20.500.11824/730
dc.description.abstractThis 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-the-art algorithms.en_US
dc.description.sponsorshipMTM2015-65317-P, TIN2016-78365-R, IT-609-13, IT-928-16, UFI BETS 2011en_US
dc.formatapplication/pdfen_US
dc.language.isoengen_US
dc.publisherComputers and Operations Researchen_US
dc.relationES/1PE/SEV-2013-0323en_US
dc.relationEUS/BERC/BERC.2014-2017en_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/3.0/es/en_US
dc.subjectOrienteering Problemen_US
dc.subjectTravelling Salesperson Problemen_US
dc.subjectEvolutionary Algorithmen_US
dc.subjectCombinatorial Optimizationen_US
dc.titleAn efficient evolutionary algorithm for the orienteering problemen_US
dc.typeinfo:eu-repo/semantics/articleen_US
dc.typeinfo:eu-repo/semantics/acceptedVersionen_US
dc.relation.publisherversionhttps://linkinghub.elsevier.com/retrieve/pii/S0305054817302241en_US


Files in this item

Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/openAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/openAccess