Speeding up Routing Schedules on Aisle-Graphs with Single Access
Skip to main content
eScholarship
Open Access Publications from the University of California

UC Merced

UC Merced Previously Published Works bannerUC Merced

Speeding up Routing Schedules on Aisle-Graphs with Single Access

  • Author(s): Sorbelli, Francesco Betti
  • Carpin, Stefano
  • Coro, Federico
  • Das, Sajal K
  • Navarra, Alfredo
  • Pinotti, Cristina M
  • et al.
Abstract

In this paper, we study the Orienteering Aisle-graphs 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 visits the vertex itself. As the robot's energy 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 OASP in O(m^2 n^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 sub-optimal 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 submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View