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.
Bibliographical notePublisher Copyright:
© 2017, Springer Science+Business Media New York.
Copyright 2017 Elsevier B.V., All rights reserved.
All Science Journal Classification (ASJC) codes
- Decision Sciences(all)
- Management Science and Operations Research