An Improved Branch-And-Price Algorithm To The Capacitated Vehicle Routing Problem With Time Window

Abstract

Motivated by real-life needs to reduce high operational costs and satisfy growing delivery demand as well as the essence of its NP-hardness, this study aims to construct an effective solution method to the state-of-the-art Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Even though the dynamics of real-world scenarios results in a variety of routing problems with specific settings, these problems are often easy to tailor to meet their requirements. We believe it is significant to study a generic problem and improve its solution approach. We thus decided to study the classic CVRPTW in this project. Two major solution approaches to this problem are exact solution approach and heuristic-based approach. This study centres on a Branch-and-Price (BnP) algorithm that combines both exact solution and heuristic-based approaches via a set-covering formulation and the efficient Column Generation (CG) technique. The BnP algorithm adopts Iterated Local Search (ILS) to improve initial solutions and feed them into the Master Problem (MP). After that, the subproblem is treated as a Shortest Path Problem with Resource Constraints (SPPRC), in which solutions with negative reduced costs are iteratively generated based on the classic labelling algorithm. This study provides a detailed explanation of modeling procedure and provides several numerical examples for illustration. A total of 24 Solomon benchmark instances were tested to attain computational results of the new solution method. Other heuristic and exact methods are also implemented for comparison of solution quality and time complexity. Based on result analysis, it is demonstrated that the meta-heuristic ILS is able to improve initial solution significantly compared to the well-known greedy heuristic, generating more meaningful feedback from the MP for the subproblem. In addition, due to small improvement in labelling approach, the subproblem is also sped up. In the last part of this study, we discuss potential directions for future research on this topic.