Variable-Speed Dubins Orienteering Problem

• L. C. Vinícius Faria UFMG
• C. G. Caio Ribeiro UFMG
• Douglas G. Macharet UFMG

Abstract

The class of vehicle routing problems plays an important role in optimizing logistics and transportation strategies across various sectors. In this context, the Orienteering Problem (OP) seeks to determine an optimized path through a set of locations with associated rewards, aiming to maximize the total collected reward while respecting constraints such as time or distance limits. Nonholonomic motion planning, particularly considering Dubins vehicles, is crucial in real-world applications due to its ability to accurately capture the constraints and dynamics of many physical vehicles. In this paper, we extend the Dubins Orienteering Problem (DOP), where unlike the classical Dubins model with constant speed, the vehicle can vary its speed during navigation, enabling the discovery of more effective paths. Experiments comparing both the DOP and our novel formulation show that the VS-DOP achieves higher total collected rewards within the same budget compared to the conventional DOP.

Keywords: Navigation, Vehicle routing, Dynamics, Transportation, Planning, Time factors, Vehicle dynamics, Robots, Logistics, orienteering problem, dubins vehicle, variable speed