  Different retail and e-commerce companies are facing the challenge of
assembling large numbers of time-critical picking orders that include both
single-line and multi-line orders. To reduce unproductive picker working time
as in traditional picker-to-parts warehousing systems, different solutions are
proposed in the literature and in practice. For example, in a mixed-shelves
storage policy, items of the same stock keeping unit are spread over several
shelves in a warehouse; or automated guided vehicles (AGVs) are used to
transport the picked items from the storage area to packing stations instead of
human pickers. This is the first paper to combine both solutions, creating what
we call AGV-assisted mixed-shelves picking systems. We model the new integrated
order batching and routing problem in such systems as an extended multi-depot
vehicle routing problem with both three-index and two-commodity network flow
formulations. Due to the complexity of the integrated problem, we develop a
novel variable neighborhood search algorithm to solve the integrated problem
more efficiently. We test our methods with different sizes of instances, and
conclude that the mixed-shelves storage policy is more suitable than the usual
storage policy in AGV-assisted mixed-shelves systems for both single-line and
multi-line orders (saving up to 67% on driving distances for AGVs). Our
variable neighborhood search algorithm provides close-to-optimal solutions
within an acceptable computational time.
