Exact solution methods for the multi-period vehicle routing problem with due dates

Abstract

•We propose two new exact solution algorithms for the multi-period vehicle routing problem with due dates (MVRPD).•One improves a previously published branch-and-bound algorithm, using optimized valid cuts and an initialization routine.•The second is a VMND algorithm, with local search operators tailored to the MVRPD.•We generate and test instances with up to 100 customers, showing that our VMND dominates the branch-and-bound algorithm.•We test the VMND algorithm on instances with 1, 2 and 3 vehicles, obtaining average optimality gaps of 3.6%, 5.5% and 5.6%.