Single vehicle routing with predefined client sequence and multiple warehouse returns: the case of two warehouses

摘要

We examine three interesting cases of the single vehicle routing problem with a predefined client sequence and two load replenishment warehouses. Given the location and demand of the clients, we seek the minimal cost route, which includes optimal load replenishment visits to the warehouses in order to fully satisfy the client demand. The cases studied vary with respect to inventory availability at each warehouse and are of increasing complexity. We have developed solution algorithms that address this complexity, ranging from a standard dynamic programming algorithm for the simplest case, to labeling algorithms and a new partitioning heuristic. The efficiency of these algorithms has been studied by solving a wide range of problem instances, and by comparing the results with those obtained from a state-of-the-art MILP solver.