Integrated Order Picking and Vehicle Routing with Due Dates

Supermarkets typically order their goods from a centrally located distribution center (warehouse). Each order that the warehouse receives is characterized by the requested items, the location of the respective supermarket and a due date by which the items have to be delivered. For processing an order, a human operator (order picker) retrieves the requested items from their storage locations in the warehouse first. The items are then available for shipment and loaded on the vehicle which performs the tour including the respective location of the supermarket. Whether and to which extent a due date is violated (tardiness) depends on the composition of the tours, the corresponding routes and the start dates of the tours (vehicle routing subproblem). The start date of a tour, however, is also affected by the assignment of orders to pickers and the sequence according to which the orders are processed by the pickers (order picking subproblem). Although both subproblems are closely interconnected, they have not been considered simultaneously in the literature so far. In this paper, an iterated local search algorithm is designed for the simultaneous solution of the subproblems. By means of extensive numerical experiments, it is shown that the proposed approach is able to generate high-quality solutions even for large instances. Furthermore, the economic benefits of an integrated solution are investigated. Problem classes are identified, where the sequential solution of the subproblems leads to acceptable results, and it is pointed out in which cases an integrated solution is inevitable.