Online citations, reference lists, and bibliographies.
← Back to Search

A Hybrid Variable Neighborhood Search For The Orienteering Problem With Mandatory Visits And Exclusionary Constraints

Pamela J. Palomo-Martínez, M. A. Salazar-Aguilar, G. Laporte, A. Langevin
Published 2017 · Mathematics, Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
This paper addresses a variant of the Orienteering Problem in which some constraints related to mandatory visits and incompatibilities among nodes are taken into account. A hybrid algorithm based on a reactive GRASP and a general VNS is proposed. Computational experiments over a large set of instances show the efficiency of the algorithm. Additionally, we also validate the performance of this algorithm on some instances taken from the literature of the traditional Orienteering Problem. HighlightsThis paper addresses the Orienteering Problem (OP) with mandatory visits and exclusionary constraints.An efficient procedure based on a reactive GRASP and a general VNS is proposed.Extensive computational results on artificial instances are analyzed.Additionally, the performance of the proposed procedure is validated on a set of instances taken from the literature of the traditional OP.
This paper references
10.1057/JORS.1984.162
Heuristic Methods Applied to Orienteering
T. Tsiligirides (1984)
10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D
The Orienteering Problem
B. Golden (1987)
10.15807/JORSJ.31.515
AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
S. Kataoka (1988)
10.1016/0167-6377(89)90002-3
A probabilistic heuristic for a computationally difficult set covering problem
T. Feo (1989)
10.1016/0166-218X(90)90100-Q
The selective travelling salesman problem
G. Laporte (1990)
10.1016/0305-0548(94)90065-5
A heuristic for the multiple tour maximum collection problem
Steven E. Butt (1994)
10.1016/0377-2217(94)00289-4
The team orienteering problem
I. Chao (1996)
10.1016/S0305-0548(97)00031-2
Variable neighborhood search
N. Mladenovic (1997)
10.1002/(SICI)1097-0037(199812)32:4<263::AID-NET3>3.0.CO;2-Q
A Branch-and-Cut Algorithm for the Undirected Selective Traveling Salesman Problem
M. Gendreau (1998)
10.1145/276884.276919
Resource-constrained geometric network optimization
E. Arkin (1998)
10.1287/ijoc.10.2.133
Solving the Orienteering Problem through Branch-and-Cut
M. Fischetti (1998)
Effective Approaches for Partial Satisfaction (Over-Subscription) Planning
M. V. D. Briel (2004)
Choosing Objectives in Over-Subscription Planning
David E. Smith (2004)
10.1016/j.cor.2003.11.008
A TABU search heuristic for the team orienteering problem
H. Tang (2005)
Dynamic programming for the orienteering problem with time windows
G. Righini (2006)
10.1007/s10288-008-0086-4
Planning in tourism and public transportation
P. Vansteenwegen (2009)
10.1016/j.cor.2009.03.008
Iterated local search for the team orienteering problem with time windows
P. Vansteenwegen (2009)
10.1016/j.cor.2009.05.012
Heuristics for the multi-period orienteering problem with multiple time windows
Fabien Tricoire (2010)
10.1007/978-3-642-13803-4_19
Hybrid Approach for the Public Transportation Time Dependent Orienteering Problem with Time Windows
A. García (2010)
10.1016/j.eswa.2010.11.085
The City Trip Planner: An expert system for tourists
P. Vansteenwegen (2011)
10.1007/978-3-642-27549-4_58
Solving the Two-Dimensional Bin-Packing Problem with Variable Bin Sizes by Greedy Randomized Adaptive Search Procedures and Variable Neighborhood Search
Andreas M. Chwatal (2011)
10.1007/978-3-642-27549-4_38
Variable Neighborhood and Greedy Randomized Adaptive Search for Capacitated Connected Facility Location
Markus Leitner (2011)
10.1016/j.ejor.2010.03.045
The orienteering problem: A survey
P. Vansteenwegen (2011)
10.1016/j.ejor.2012.01.030
The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search
N. Labadie (2012)
10.1016/j.ejor.2012.01.036
A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem
N. Mladenovic (2012)
10.1016/j.cor.2011.08.022
A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
G. Kirlik (2012)
10.1016/j.eswa.2012.01.024
A variable neighborhood search for the multi-depot vehicle routing problem with loading cost
Yiyo Kuo (2012)
10.1002/9781118731598.CH4
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (2013)
10.1016/j.cor.2012.05.009
Variable neighborhood search for location routing
B. Jarboui (2013)
10.1287/trsc.1110.0377
The Multiconstraint Team Orienteering Problem with Multiple Time Windows
Wouter Souffriau (2013)
10.1057/jors.2013.156
GRASP with path relinking for the orienteering problem
V. Campos (2014)
10.1007/S10470-014-0273-5
Greedy randomized adaptive search procedure for analog test point selection
H. Lei (2014)
10.1007/978-3-662-44736-9_16
A GRASPxELS for Scheduling of Job-Shop Like Manufacturing Systems and CO2 Emission Reduction
Sylverin Kemmoe Tchomte (2014)
10.1007/978-3-319-09584-4_21
GRASP with Path-Relinking for the Maximum Contact Map Overlap Problem
Ricardo Martins (2014)
10.1007/s10732-014-9242-5
A survey on algorithmic approaches for solving tourist trip design problems
D. Gavalas (2014)
10.1016/j.cor.2013.07.026
The multi-district team orienteering problem
M. A. Salazar-Aguilar (2014)
10.1016/j.endm.2014.11.027
A hybrid variable neighborhood search algorithm for targeted offers in direct marketing
T. A. Oliveira (2015)
10.1016/j.ejor.2014.06.042
Multiobjective GRASP with Path Relinking
R. Martí (2015)
10.1016/j.ins.2014.10.010
Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization
A. Duarte (2015)



This paper is referenced by
10.1016/j.asoc.2020.107024
A Multi-Start Granular Skewed Variable Neighborhood Tabu Search for the Roaming Salesman Problem
Masoud Shahmanzari (2021)
10.1109/TASE.2019.2928774
Person Finding: An Autonomous Robot Search Method for Finding Multiple Dynamic Users in Human-Centered Environments
S. Mohamed (2020)
10.1007/978-3-030-59747-4_15
Metaheuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Cost Functions
J. L. Manguino (2020)
10.1287/trsc.2019.0927
Building Trust in Home Services - Stochastic Team-Orienteering with Consistency Constraints
Yongjia Song (2020)
A Branch-and-Check Approach for the Tourist Trip Design Problem with Rich Constraints
D. Vu (2020)
10.1016/J.COR.2019.07.012
An adaptive large neighborhood search approach for multiple traveling repairman problem with profits
Mualla Gonca Avci (2019)
10.1016/j.cie.2018.05.016
ADOPT: Combining parameter tuning and Adaptive Operator Ordering for solving a class of Orienteering Problems
Aldy Gunawan (2018)
10.1080/0305215X.2017.1417398
An iterated local search algorithm for the team orienteering problem with variable profits
Aldy Gunawan (2018)
10.1016/J.JCLEPRO.2017.10.249
The Accessibility Vehicle Routing Problem
O. J. Ibarra-Rojas (2018)
10.1016/j.ejor.2018.01.019
A memetic algorithm for the Orienteering Problem with Mandatory Visits and Exclusionary Constraints
Y. Lu (2018)
10.1007/s40815-017-0369-z
Models and Algorithm for the Orienteering Problem in a Fuzzy Environment
Yaodong Ni (2018)
10.1109/LOGISTIQUA.2017.7962868
The bi-objective orienteering problem with budget constraint: GRASP_ILS
H. Rezki (2017)
10.1007/s10479-017-2408-4
Formulations for the orienteering problem with additional constraints
Pamela J. Palomo-Martínez (2017)
10.1016/j.cie.2017.10.020
Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing
Shih-Wei Lin (2017)
Semantic Scholar Logo Some data provided by SemanticScholar