A Special Case of the Multiple Traveling Salesmen Problem in End-of-Aisle Picking Systems

Lennart Baardman (), Kees Jan Roodbergen (), Héctor J. Carlo () and Albert H. Schrotenboer ()
Additional contact information
Lennart Baardman: Stephen M. Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109
Kees Jan Roodbergen: Faculty of Economics and Business, Department of Operations, University of Groningen, 9700 AV Groningen, Netherlands
Héctor J. Carlo: Industrial Engineering Department, University of Puerto Rico – Mayagüez, Mayagüez 00680, Puerto Rico
Albert H. Schrotenboer: School of Engineering, Operations, Planning, Accounting, and Control Group, Eindhoven University of Technology, 5600 MB Eindhoven, Netherlands

Transportation Science, 2021, vol. 55, issue 5, 1151-1169

Abstract: This study focuses on the problem of sequencing requests for an end-of-aisle automated storage and retrieval system in which each retrieved load must be returned to its earlier storage location after a worker has picked some products from the load. At the picking station, a buffer is maintained to absorb any fluctuations in speed between the worker and the storage/retrieval machine. We show that, under conditions, the problem of optimally sequencing the requests in this system with a buffer size of m loads forms a special case of the multiple traveling salesmen problem in which each salesman visits the same number of cities. Several interesting structural properties for the problem are mathematically shown. In addition, a branch-and-cut method and heuristics are proposed. Experimental results show that the proposed simulated annealing-based heuristic performs well in all circumstances and significantly outperforms benchmark heuristics. For instances with negligible picking times for the worker, we show that this heuristic provides solutions that are, on average, within 1.8% from the optimal value.

Keywords: automated storage/retrieval systems; multiple traveling salesmen problem; scheduling; warehousing (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1075 (application/pdf)

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:inm:ortrsc:v:55:y:2021:i:5:p:1151-1169

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().