Robot scheduling for pod retrieval in a robotic mobile fulfillment system

In order to increase the order picking efficiency, e-commerce retailers have started to implement order picking systems where mobile robots carry inventory pods to pick stations. In pick stations, pickers pick the products from inventory pods and put them in customer bins. In such a robotic mobile fulfillment center, pickers are constantly busy with picking customer orders and avoid non-value adding activities such as walking to reach storage locations. To fulfill customer orders, each robot needs to complete a sequence of missions and each mission includes a set of retrieval requests. We study the operational problem of scheduling a mobile robot fulfilling a set of customer orders from a pick station. The mobile robot needs to bring each pod from a retrieval location to the pick station and return the pod to a storage location. The objective is to minimize the total travel time of the robot which can be considered as a proxy for other objectives such a shorter lead time, higher throughput and less capital investment. We formulate the basic problem as an asymmetric traveling salesman problem. We then extend the model by adding general precedence constraints to give different priorities to customer orders based on their urgency (e.g. same-day, one-day, two-day, and standard orders). We also study a variation of the problem where the pod can be stored in multiple alternative locations. In this case, we model the problem as a generalized asymmetric traveling salesman problem. An adaptive large neighborhood search heuristic is developed to efficiently solve real size instances. The method outperforms the heuristics commonly used in practice.