Formulations for the orienteering problem with additional constraints
Pamela J. Palomo-Martínez (pamela.palomomrt@gmail.com),
M. Angélica Salazar-Aguilar (maria.salazaragl@uanl.edu.mx) and
Víctor M. Albornoz (victor.albornoz@usm.cl)
Additional contact information
Pamela J. Palomo-Martínez: Universidad Autónoma de Nuevo León
M. Angélica Salazar-Aguilar: Universidad Autónoma de Nuevo León
Víctor M. Albornoz: Universidad Técnica Federico Santa María
Annals of Operations Research, 2017, vol. 258, issue 2, No 15, 503-545
Abstract:
Abstract This paper addresses a variant of the Orienteering Problem taking into account mandatory visits and exclusionary constraints (conflicts among nodes). Five mixed integer linear formulations are adapted from the Traveling Salesman Problem literature in order to provide a robust formulation for this problem. The main difference among these formulations lies in the way they deal with the subtour elimination constraints. The performance of the proposed formulations is evaluated over a large set of instances. Computational results reveal that the model that avoids subtours by means of a single-commodity flow formulation allows to solve to optimality more instances than the other formulations, within a time limit of 1 h.
Keywords: Orienteering problem; Subtour elimination constraints; Exclusionary constraints; Selective traveling salesman problem (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations: View citations in EconPapers (2)
Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2408-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
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:spr:annopr:v:258:y:2017:i:2:d:10.1007_s10479-017-2408-4
Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479
DOI: 10.1007/s10479-017-2408-4
Access Statistics for this article
Annals of Operations Research is currently edited by Endre Boros
More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).