Formulations for the orienteering problem with additional constraints

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

Research output: Contribution to journalArticlepeer-review

5 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 languageEnglish
Pages (from-to)503-545
Number of pages43
JournalAnnals of Operations Research
Volume258
Issue number2
DOIs
Publication statusPublished - 1 Nov 2017
Externally publishedYes

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

  • Decision Sciences(all)
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Formulations for the orienteering problem with additional constraints'. Together they form a unique fingerprint.

Cite this