To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order-picking system, each human order picker is accompanied by an AGV during the order-picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot and continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block, parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal [ Ratliff HD, Rosenthal AS (1983) Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Oper. Res. 1(3):507–521], and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective traveling salesman problem (TSP) solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-) optimal fashion, picker walking can be reduced by about 20% compared with a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect so that, in larger warehouses, only about 1.5 AGVs per picker are required to avoid picker waiting. Summary of Contribution: New technologies, such as automatic guided vehicles (AGVs) are currently considered as options to increase the efficiency of the order-picking process in warehouses, which is responsible for a large part of operational warehousing costs. In addition, picker-routing decisions are more and more often based on algorithmic decision support because of their relevance for decreasing unproductive picker walking time. This paper addresses both aspects and investigates routing algorithms for AGV-assisted order picking in parallel-aisle warehouses. We present a dynamic programming routine with polynomial runtime to solve the problem variant in which the sequence of picking orders is fixed. For the variant in which this sequence is a decision, we show that the problem becomes NP-hard, and we propose a greedy heuristic and investigate the use of state-of-the-art exact and heuristic traveling salesman problem solution methods to address the problem. The numerical studies demonstrate the effectiveness of the algorithms and indicate that AGV assistance promises strong improvements in the order-fulfillment process. Because of the practical relevance of AGV-assisted order picking and the presented algorithmic contributions, we believe that the paper is relevant for practitioners and researchers alike.

Abstract Driven by environmental considerations, regulations on vehicle emissions, and the offer of major subsidies, electric commercial vehicles (ECVs) are receiving ever stronger attention in logistics companies. Route planning for ECV fleets requires consideration of the special characteristics of ECVs, like limited driving range and the potential need to recharge en route at dedicated recharging stations. From a practical viewpoint, the number of recharge operations of each vehicle can very often be restricted to one recharge per route because (i) typical route distances in the most important application areas of ECVs, like small package shipping and food or beverage distribution, do not require more than one recharge given the current driving range of ECVs, and (ii) operations managers are very reluctant to plan vehicle routes with two or more recharges because recharging operations are perceived as unproductive idle times. We develop a simple hybrid of large neighborhood search and granular tabu search to solve the resulting electric vehicle‐routing problem with time windows and single recharge (EVRPTWS), considering the possibility of both full and partial recharge. The heuristic works on routes represented as customer sequences, and recharge operations are implicitly considered by determining the recharging position in the route, the recharging station to visit, and the amount to be recharged in optimal fashion. We discuss how our algorithm can be extended to handle nonlinear recharging times, different recharging times per station, and time‐dependent waiting times at stations. In numerical studies on EVRPTWS instances from the literature, the method provides optimal or near‐optimal solutions for instances with up to 100 customers within reasonable runtimes. Additional studies investigate the cost savings potential of partial recharges in comparison to full recharges in the presence of time‐window constraints, and examine the factors that influence this cost saving potential.