Scenic Routes Now: Efficiently Solving the Time-Dependent Arc Orienteering Problem
Preprint
Abstract
This paper extends the Arc Orienteering Problem (AOP) to large road networks with time-dependent travel times and time-dependent value gain, termed Twofold Time-Dependent AOP or 2TD-AOP for short. In its original definition, the NP-hard Orienteering Problem (OP) asks to find a path from a source to a destination maximizing the accumulated value while not exceeding a cost budget. Variations of the OP and AOP have many practical applications such as mobile crowdsourcing tasks (e.g., repairing and maintenance or dispatching field workers), diverse logistics problems (e.g., crowd control or controlling wildfires) as well as several tourist guidance problems (e.g., generating trip recommendations or navigating through theme parks). In the proposed 2TD-AOP, travel times and value functions are assumed to be time-dependent. The dynamic values model, for instance, varying rewards in crowdsourcing tasks or varying urgency levels in damage control tasks. We discuss this novel problem, prove the benefit of time-dependence empirically and present an efficient approximative solution, optimized for fast response systems. Our approach is the first time-dependent variant of the AOP to be evaluated on a large scale, fine-grained, real-world road network. We show that optimal solutions are infeasible and solutions to the static problem are often invalid. We propose an approximate dynamic programming solution which produces valid paths and is orders of magnitude faster than any optimal solution.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Orienteering Problem: A survey of recent variants, solution approaches and applicationsEuropean Journal of Operational Research, 2016
- Approximation algorithms for the arc orienteering problemInformation Processing Letters, 2015
- An extension of the arc orienteering problem and its application to cycle trip planningTransportation Research Part E: Logistics and Transportation Review, 2014
- A fast solution method for the time-dependent orienteering problemEuropean Journal of Operational Research, 2014
- A survey on algorithmic approaches for solving tourist trip design problemsJournal of Heuristics, 2014
- The planning of cycle trips in the province of East FlandersOmega, 2011
- Privatized rural postman problemsComputers & Operations Research, 2006
- A fast and effective heuristic for the orienteering problemEuropean Journal of Operational Research, 1996
- An efficient four-phase heuristic for the generalized orienteering problemComputers & Operations Research, 1991
- A multifaceted heuristic for the orienteering problemNaval Research Logistics (NRL), 1988