Routing automated lane-guided transport vehicles in a warehouse handling returns

Faced with high return rates, many e-commerce retailers are considering novel technical solutions to expedite the processing of returned items in their warehouses. One such solution consists of lane-guided transport (LGT) vehicles. These small, electric vehicles follow optical markers on the floor, picking up boxes of returned items at a depot and dropping them off at workstations, releasing the logistics workers to focus on the productive task of actually processing the items instead of carrying them through the warehouse. These types of systems are simple to set up from a technical perspective; however, the routes on the warehouse floor still need to be carefully planned. This gives rise to the following routing problem. Given a set of stations to be served from multiple depots by a fleet of LGT vehicles, which stations doing what type of work should be visited on what route? Only one route per depot is allowed, but multiple vehicles may use the same route. Moreover, since routes cannot be changed on short notice, we consider an infinite planning horizon where the demand rate of the stations depends on the type of work they are assigned to do (e.g., handling defective items or refurbishing). We develop a decomposition heuristic, which solves instances derived from industry data to near-optimality in less than a minute. We also show that the depot location is rather unimportant for the overall system performance, but that the depot count can have a significant influence.