GRASP with path relinking for the orienteering problem

Vicente Campos, Rafael Martí, Jesús Sánchez-Oro and Abraham Duarte
Additional contact information
Vicente Campos: Universitat de València, València, Spain
Rafael Martí: Universitat de València, València, Spain
Jesús Sánchez-Oro: Universidad Rey Juan Carlos, Mostoles, Spain
Abraham Duarte: Universidad Rey Juan Carlos, Mostoles, Spain

Journal of the Operational Research Society, 2014, vol. 65, issue 12, 1800-1813

Abstract: In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies—for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high-quality solutions employing short computing times.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v65/n12/pdf/jors2013156a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v65/n12/full/jors2013156a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:65:y:2014:i:12:p:1800-1813

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().