Speeding-Up Routing Schedules on Aisle-Graphs

Abstract

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.

Meeting Name

16th Annual International Conference on Distributed Computing in Sensor Systems, DCOSS 2020 (2020: Jun. 15-17, On-line)

Department(s)

Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research

Second Research Center/Lab

Intelligent Systems Center

International Standard Book Number (ISBN)

978-172814351-4

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2020 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 May 2020

Link to Full Text

Share

 
COinS