Dynamic robot routing and destination assignment policies for robotic sorting systems

Abstract

Robotic sorting systems (RSSs) use mobile robots to sort items by destination. An RSS pairs high accuracy and flexible capacity sorting with the advantages of a flexible layout. This is why several express parcel and e-commerce retail companies, who face heavy demand fluctuations, have implemented these systems. To cope with fluctuating demand, temporal robot congestion, and high sorting speed requirements, workload balancing strategies such as dynamic robot routing and destination reassignment may be of benefit. We investigate the effect of a dynamic robot routing policy using a Markov decision process (MDP) model and dynamic destination assignment using a mixed integer programming (MIP) model. To obtain the MDP model parameters, we first model the system as a semiopen queuing network (SOQN) that accounts for robot movement dynamics and network congestion. Then, we construct the MIP model to find a destination reassignment scheme that minimizes the workload imbalance. With inputs from the SOQN and MIP models, the Markov decision process minimizes parcel waiting and postponement costs and helps to find a good heuristic robot routing policy to reduce congestion. We show that the heuristic dynamic routing policy is near optimal in small-scale systems and outperforms benchmark policies in large-scale realistic scenarios. Dynamic destination reassignment also has positive effects on the throughput capacity in highly loaded systems. Together, in our case company, they improve the throughput capacity by 35%. Simultaneously, the effect of dynamic routing exceeds that of dynamic destination reassignment, suggesting that managers should focus more on dynamic robot routing than dynamic destination reassignment to mitigate temporal congestion.