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 Om2n2) 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 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 12(1-1e) on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm.
F. B. Sorbelli et al., "Speeding-Up Routing Schedules on Aisle-Graphs," Proceedings of the 16th Annual International Conference on Distributed Computing in Sensor Systems (2020), pp. 69 - 76, Institute of Electrical and Electronics Engineers (IEEE), May 2020.
The definitive version is available at https://doi.org/10.1109/DCOSS49796.2020.00023
16th Annual International Conference on Distributed Computing in Sensor Systems, DCOSS 2020 (2020: Jun. 15-17, On-line)
Center for High Performance Computing Research
Second Research Center/Lab
Intelligent Systems Center
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2020 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 May 2020