15/09/2025
The vehicle routing problem with time windows is a well-researched problem in literature. We study the 2-index flow formulation for the problem and propose a relatively little-used approach of polar duality/local cuts to compute new general valid inequalities for the problem. Our method of applying polar duality is quite distinct from and complimentary to an earlier attempt of applying the same idea to this problem and produces significantly better results on instances with tight time windows. On almost all 25-customer Solomon instances with tight time windows, our approach is capable of producing very strong lower bounds that are close to 100% of the optimal solution within reasonable computing time. On larger instances too the lower bounds are significantly better than those reported in the literature. We also present a new version of the previously proposed -path inequalities that are easy to compute as well as effective. These inequalities also lead to a substantial improvement in lower bounds and solution times for some classes of instances. Computational tests performed on benchmark instances indicate significant improvement in computing time and decrease in the number of nodes in the branch-and-bound tree as compared to extant methods that employ the flow formulation for the problem.