Route Generation For Warehouse Management Using Fast Heuristics

In this research, fast heuristics for a centralized multi-agent route planner are presented and computationally evaluated. We solve a sub-problem of warehouse scheduling involving the routing of intelligent agents as a preliminary step in optimizing the total schedule. The problem involves the generation of routes for automated agents tasked with the transfer of items within a warehouse from storage pallets to a common loading shed. The goal is to minimize the total distance of the routes and the number of routes generated. This constitutes a multiple-objective optimization problem which is NP-hard and hence can take a prohibitively long time to solve using existing search-based techniques. The approach adapted here is to model the system as a Split-Delivery Vehicle Routing Problem (SDVRP) with grid distances and to solve it using heuristics based on tested operations research concepts. Twenty-two such heuristics are tested including the well-known greedy Nearest-Neighbor (NN) heuristic, and the established Savings heuristic of Clarke and Wright. Two SDVRP variations of the NN algorithm are introduced, namely the Nearest-Fill (NF) and Nearest-Fill Farthest-Start (NFFS) heuristics. Existing SDVRP improvement procedures are also considered and generalized to produce numerous heuristic variations. This novel approach of applying fast vehicle routing heuristics to multi-agent routing has the advantag