Variable Neighborhood Search for the Set Orienteering Problem and its application to other Orienteering Problem variants

Robert Pěnička, Jan Faigl and Martin Saska

European Journal of Operational Research, 2019, vol. 276, issue 3, 816-825

Abstract: This paper addresses the recently proposed generalization of the Orienteering Problem (OP), referred to as the Set Orienteering Problem (SOP). The OP stands to find a tour over a subset of customers, each with an associated profit, such that the profit collected from the visited customers is maximized and the tour length is within the given limited budget. In the SOP, the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. Similarly to the OP, the SOP limits the tour cost by a given budget constraint, and therefore, only a subset of clusters can usually be served. We propose to employ the Variable Neighborhood Search (VNS) metaheuristic for solving the SOP. In addition, a novel Integer Linear Programming (ILP) formulation of the SOP is proposed to find the optimal solution for small and medium-sized problems. Furthermore, we show other OP variants that can be addressed as the SOP, i.e., the Orienteering Problem with Neighborhoods (OPN) and the Dubins Orienteering Problem (DOP). While the OPN extends the OP by collecting a profit within the neighborhood radius of each customer, the DOP uses airplane-like smooth trajectories to connect individual customers. The presented computational results indicate the feasibility of the proposed VNS algorithm and ILP formulation, by improving the solutions of several existing SOP benchmark instances and requiring significantly lower computational time than the existing approaches.

Keywords: Routing; Orienteering Problem; Variable Neighborhood Search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719300827
Full text for ScienceDirect subscribers only

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:eee:ejores:v:276:y:2019:i:3:p:816-825

DOI: 10.1016/j.ejor.2019.01.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().