Formulations for the orienteering problem with additional constraints

Pamela Jocelyn Palomo Martinez; M. Angélica Salazar-Aguilar; Victor Albornoz

doi:10.1007/s10479-017-2408-4

Formulations for the orienteering problem with additional constraints

Pamela Jocelyn Palomo Martinez, M. Angélica Salazar-Aguilar, Victor Albornoz

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

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.

Original language	English
Pages (from-to)	503-545
Number of pages	43
Journal	Annals of Operations Research
Volume	258
Issue number	2
DOIs	https://doi.org/10.1007/s10479-017-2408-4
Publication status	Published - 1 Nov 2017
Externally published	Yes

Bibliographical note

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.

All Science Journal Classification (ASJC) codes

General Decision Sciences
Management Science and Operations Research

Access to Document

10.1007/s10479-017-2408-4

Cite this

@article{3945b4d479a04f77aa00dc39943ed11c,

title = "Formulations for the orienteering problem with additional constraints",

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.",

author = "{Palomo Martinez}, {Pamela Jocelyn} and Salazar-Aguilar, {M. Ang{\'e}lica} and Victor Albornoz",

note = "Funding Information: We sincerely thank to CONACYT, UANL-PAICYT 2015, and DGIIP of Universidad T{\'e}cnica Federico Santa Mar{\'i}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: {\textcopyright} 2017, Springer Science+Business Media New York.",

year = "2017",

month = nov,

day = "1",

doi = "10.1007/s10479-017-2408-4",

language = "English",

volume = "258",

pages = "503--545",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

number = "2",

}

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 -

Formulations for the orienteering problem with additional constraints

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this