![](https://d3ilqtpdwi981i.cloudfront.net/JQM68TczYa1PaiNpzl4akUajXkY=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/3c/75/ff/3c75ff82-5ca4-4021-9a88-96a99fab592a/thumbnail_8015fe60-41a6-4dd5-a374-c695b21664af.jpg)
In this article, we study the orienteering aisle-graph 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 it visits the vertex itself. As the energy of the robot 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 the OASP in O (m 2n 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 suboptimal 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 sub modularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.
- Orienteering problem (OP),
- Routing,
- Submodularity
Available at: http://works.bepress.com/sajal-das/270/