Optimal recharge sequencing in multi-AGV systems: A mixed ILP approach

Battery level is a critical issue in AGV transportation systems, as AGVs cannot run out of power while operating. Hence, at some point they will be forced to stop and recharge at any of the charging stations available in the warehouse. The question that immediately arises is where, and when, to recharge in an optimal way. Assuming that an AGV has already been assigned a task sequence consisting of visiting a number of working stations, stops at charging stations should be optimally inserted. Here, we do so by minimizing the total tour time, including recharges. Recently, this problem was cast as a mixed integer nonlinear program that also included linear and nonlinear constraints. We recast this problem into a mixed integer linear program under linear constraints, which allows to find an exact solution. Moreover, we derive a procedure to reduce the number of variables of the problem. We also show that, when a charging station is visited, bringing the level of charge to the maximum allowed is optimal except for the case where the tour can be completed without other stops. Finally, we present a stochastic formulation of the problem to consider the presence of multiple AGVs in the layout, which may affect the time spent by AGVs at charging stations due to queuing and, consequently, the optimal solution. Interestingly, the linear formulation of the problem allows to fully characterize the optimal solution as a function of the expected occupancies of the charging stations. • A mixed ILP approach for optimal recharge sequencing in multi-AGV systems is presented. • A procedure to reduce the number of variables of the problem is derived. • It is shown that fully recharging to the maximum allowed is optimal. • A stochastic formulation is used to model the presence of multiple AGVs in the layout. • The proposed technique is validated via numerical simulations.