Sajal K Das, Stefano Carpin, Federico Coro, Alfredo Navarra, and 2 more February 10, 2021
In this paper, we study the Orienteering Aisle-graphs Single-access Problem
(OASP), a variant of the orienteering problem for a robot moving in a so-called
single-access aisle-graph, i.e., a graph consisting of a set of rows that can
be accessed from one side only. Aisle-graphs model, among others, vineyards or
warehouses. Each aisle-graph vertex is associated with a reward that a robot
obtains when visits the vertex itself. As the robot's energy is limited, only a
subset of vertices can be visited with a fully charged battery. The objective
is to maximize the total reward collected by the robot with a battery charge.
We first propose an optimal algorithm that solves OASP in O(m^2 n^2) time for
aisle-graphs with a single access consisting of m rows, each with n vertices.
With the goal of designing faster solutions, we propose four greedy sub-optimal
algorithms that run in at most O(mn (m+n)) time. For two of them, we guarantee
an approximation ratio of 1/2(1-1/e), where e is the base of the natural
logarithm, on the total reward by exploiting the well-known submodularity
property. Experimentally, we show that these algorithms collect more than 80%
of the optimal reward.
Download PDF159 Views
97 Downloads
Authors
- Sajal K Das
Author
- Stefano Carpin
Author
- Federico Coro
Author
- Alfredo Navarra
Author
- Cristina M Pinotti
Author
- Francesco Betti Sorbelli
Author