The Quality Arc Orienteering Problem for Multi-Objective Scenic Route Planning

Abstract

The Quality Arc Orienteering Problem (Quality-AOP) is to find a path in a directed graph subject to a travel cost budget and in which the quality of the path is optimized. Due to our restrictive problem definition and the use of a strong quality measure in the objective function, artifacts such as subtours and detours do not occur in Quality-AOP where they did occur in the Arc Orienteering Problem. The budget interval allows us to find higher quality routes close to the desired costs. We give a polynomial time heuristic for this problem, which is NP-hard. Our algorithm is based on a Greedy Randomized Adaptive Search Procedure. Our experiments show the reduction of artifacts and also improvements on the route’s quality up to 10%.