A column generation approach for the location-routing problem with time windows

摘要

The location-routing problem with time windows consists of opening a subset of depots, assigning customers to depots, and determining routes within allowable times such that the sum of depot opening, vehicle usage, and traveling costs is minimized. Customers have to be visited only once during their time windows and depot capacities and load limits of vehicles cannot be violated. In order to find the exact solution to the problem, we propose a branch-and-price algorithm based on set-partitioning approach. The pricing problem is solved using dynamic programming. We introduce several strategies to improve the lower and upper bounds as well as acceleration techniques to generate improving columns more rapidly. Computational results show the higher performance of the proposed method on a set of small and medium size instances in the literature and demonstrate its efficiency in solving generated large size instances. (C) 2017 Elsevier Ltd. All rights reserved.