AN EXACT ALGORITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS AND RELEASE DATES

This work addresses the Vehicle Routing Problem with Time Windows and Release Dates (VRPTW-RD), an extension of the classic VRPTW in which each customer has a release date. This feature introduces an additional decision related to the timing of the vehicles' departure. To solve the problem exactly, a branch-cut-and-price algorithm based on a set partitioning formulation is proposed. The pricing sub-problem is modeled as a Shortest Path Problem with Resource Constraints (RCSPP), solved through a labeling algorithm that incorporates specific states to handle time windows, capacity, and release dates, as well as efficient dominance rules. The method was evaluated on 81 instances derived from the classic Solomon instances with 100 clients. The results indicate that the approach is robust, being able to solve 69 of the 81 instances optimally in competitive computational times.