Exact solution methods for the multi-period vehicle routing problem with due dates
Revista : Computers & Operations ResearchVolumen : 110
Páginas : 148-158
Tipo de publicación : ISI Ir a publicación
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%.