The benefits of re-evaluating the real-time fulfillment decisions

An extended abstract of a 2005 winner of the MSOM Society Student Paper Competition. We conjecture that we can reduce the total transportation cost of shipping orders from warehouses by periodically re-evaluating the real-time assignment decisions, subject to the constraint that there are no violations to the estimate-to-ship date expectation for any customer order. We therefore develop efficient and easy-to-implement suboptimal heuristics to solve the reevaluation problem. Given the real-time assignment decisions, we take the natural path to construct an improvement heuristic that starts with a feasible solution and iteratively finds better solutions. We deploy neighborhood search algorithms, and the neighbourhood of our heuristics is exponentially large. Our heuristics consist of two distinct parts. We name the first part order swap as we consider split orders one at a time and examine possible swaps. The second part is SKU exchange as we consider one SKU at a time and examine possible cyclic exchanges. In our implementation, we start with order swap and then proceed to SKU exchange on the remaining split orders. We view order swap as a fast and extremely simple greedy algorithm to exploit the abundance of single-unit orders and unassigned inventory. To incur incremental benefits, we employ the efficient but more time-consuming SKU exchange heuristic. We implement the heuristics on several real data sets from a global e-tailer. For each re-evaluation problem during the off-peak season, we estimate that we can reduce 15 K to 20 K shipments, which corresponds to 40% to 50% of the total number of extra shipments in the real-time assignments. We show on reduced problem sets that the heuristic is near optimal, achieving over 97% of the optimal solution. Our heuristic is relatively easy to implement, as each iteration translates into a series of swaps or cyclic exchanges among a limited set of orders. We can feed these exchanges into the e-tailer's existing order-management systems, and as such, we are optimistic that implementation is possible. We conclude that there is an opportunity to reduce the transportation costs for an e-tailer by means of a re-evaluation of its real-time fulfillment decisions. With preliminary testing on the developed heuristic, we show that e-tailers can make better decisions by utilizing more resources and more information.