.png){kind=icon}
返回
An efficient evolutionary algorithm for the orienteering problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2017.09.003.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 LinKernighan 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. (C) 2017 Elsevier Ltd. All rights reserved.
Keyword:
Orienteering problem
Travelling salesperson problem
Evolutionary algorithm
Combinatorial optimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏Orienteering Problem: A survey of recent variants, solution approaches and applications定向越野问题: 对最新变体，解决方法和应用的调查OAAI
OAAI分享收藏
查看更多内容