dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Kreveld, M.J. van | |
dc.contributor.advisor | Bodlaender, H.L. | |
dc.contributor.author | Conté, J.M.W. Le | |
dc.date.accessioned | 2017-05-22T17:52:09Z | |
dc.date.available | 2017-05-22T17:52:09Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/25874 | |
dc.description.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%. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 10916303 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.title | The Quality Arc Orienteering Problem for Multi-Objective Scenic Route Planning | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Arc Orienteering Problem, route planning, scenic path, multi-objective optimization, routing, Greedy Randomized Adaptive Search Procedure, Orienteering Problem, OpenStreetMap, curviness, road network | |
dc.subject.courseuu | Computing Science | |