Sizing and scheduling for a fleet of reconfigurable mobile robots
研究如何确定可重构机器人车队的规模和调度方案，以最小化投资和运行成本，并针对该NP难问题提出高效启发式算法。
We consider a fleet of elementary robots that transport items within a warehouse. These elementary robots can be connected in different ways to transport loads of different types. The capacity of the resulting poly-robot depends on its configuration and on the load type being transported. For each load type, we have to meet a transportation demand within a given time interval. Several poly-robots may be required either simultaneously or sequentially to meet this demand. We have to decide how to decompose the demand into transportation tasks. A transportation task specifies the load type, the corresponding number of loads and the configuration of the involved poly-robot. The objective is to determine the transportation tasks and schedule them over time, in order to minimise the investment cost (related to the fleet size) and the running costs (related to the use of the fleet). We show that the resulting Multi-Bot problem is strongly NP-hard. We also study several special cases that can be solved in polynomial time and derive from our theoretical results an efficient heuristic for the general case. A numerical study shows that the heuristic algorithm is effective even for large instances.