Speeding-up Routing Schedules on Aisle-Graphs

摘要

In this paper, we study the Orienteering Aisle-graphs Single-column Problem (OASP), which is a variant of the route planning problem for an entity/robot moving along a specific aisle-graph consisting of a set of rows connected via just one column at one endpoint of the rows. Such constrained aisle-graph may model, for instance, a vineyard or warehouse, where each vertex is assigned with a reward that a robot gains when visiting it for accomplishing a task. As the robot is energy limited, it must visit a subset of vertices before going back to the depot for recharging, while maximizing the total reward gained. It is known that the OASP for constrained aisle-graphs composed by m rows of length n is polynomially solvable in $mathcal{O}left( {{m^2}{n^2}} ight)$ time, which can be prohibitive for graphs of large dimensions. With the goal of designing more time efficient solutions, we propose four algorithms that iteratively build the solution in a greedy manner. These solutions take at most $mathcal{O}(mn(m + n))$ time, thus improving the optimal solution by a factor of n. Experimentally, we show that these algorithms collect more than 80% of the optimum reward. For two of them, we also guarantee an approximation ratio of $rac{1}{2}left( {1 - rac{1}{e}} ight)$ on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm.