TY - JOUR
T1 - Formulations for the orienteering problem with additional constraints
AU - Palomo Martinez, Pamela Jocelyn
AU - Salazar-Aguilar, M. Angélica
AU - Albornoz, Victor
N1 - Funding Information:
We sincerely thank to CONACYT, UANL-PAICYT 2015, and DGIIP of Universidad Técnica Federico Santa María (Grant USM 28.15.20) for their support to this work. Thanks are due to the anonymous referees for their valuable comments.
Publisher Copyright:
© 2017, Springer Science+Business Media New York.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85011629840&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85011629840&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/4026b17a-f215-3d7b-8e7d-2aac6f08fcad/
U2 - 10.1007/s10479-017-2408-4
DO - 10.1007/s10479-017-2408-4
M3 - Article
SN - 0254-5330
VL - 258
SP - 503
EP - 545
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 2
ER -