Skip to main content
Article
Speeding Up Routing Schedules on Aisle Graphs with Single Access
IEEE Transactions on Robotics
  • Francesco Betti Sorbelli
  • Stefano Carpin
  • Federico Coro
  • Sajal K. Das, Missouri University of Science and Technology
  • Alfredo Navarra
  • Cristina M. Pinotti
Abstract

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.

Department(s)
Computer Science
Keywords and Phrases
  • Orienteering problem (OP),
  • Routing,
  • Submodularity
Document Type
Article - Journal
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 2023 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
2-1-2022
Publication Date
01 Feb 2022
Disciplines
Citation Information
Francesco Betti Sorbelli, Stefano Carpin, Federico Coro, Sajal K. Das, et al.. "Speeding Up Routing Schedules on Aisle Graphs with Single Access" IEEE Transactions on Robotics Vol. 38 Iss. 1 (2022) p. 433 - 447 ISSN: 1941-0468; 1552-3098
Available at: http://works.bepress.com/sajal-das/270/