The Orienteering Problem with Time Windows Applied to Robotic Melon Harvesting

Moshe Mann (), Boaz Zion, Dror Rubinstein, Rafi Linker and Itzhak Shmulevich
Additional contact information
Moshe Mann: Technion
Boaz Zion: Agricultural Research Organization - the Volcani Center
Dror Rubinstein: Technion
Rafi Linker: Technion
Itzhak Shmulevich: Technion

Journal of Optimization Theory and Applications, 2016, vol. 168, issue 1, No 13, 246-267

Abstract: Abstract The goal of a melon harvesting robot is to maximize the number of melons it harvests given a progressive speed. Selecting the sequence of melons that yields this maximum is an example of the orienteering problem with time windows. We present a dynamic programming-based algorithm that yields a strictly optimal solution to this problem. In contrast to similar methods, this algorithm utilizes the unique properties of the robotic harvesting task, such as uniform gain per vertex and time windows, to expand domination criteria and quicken the optimal path selection process. We prove that the complexity of this algorithm is linearithmic in the number of melons and can be implemented online if there is a bound on the density. The results of this algorithm are demonstrated to be significantly better than the standard heuristic solution for a wide range of harvesting robot scenarios.

Keywords: Harvesting robot; Orienteering; Time windows; Dynamic programming; Combinatorial optimization; 05C85; 68T40; 90C39; 90C27; 68W40 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-015-0767-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:168:y:2016:i:1:d:10.1007_s10957-015-0767-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-015-0767-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().