A Note on the Convergence of Two Time Window Discretization Methods for Time Constrained Vehicle Routing and Scheduling Problems

In this paper, we discuss the convergence of two time window discretization methods for vehicle routing problems with time windows. The first method provides a feasible solution for the minimization problem while the second, newly developed by the authors, provides a lower bound. Analysis shows that the lower bounding method is guaranteed to converge to the optimal solution while the method used to develop feasible solutions is not. This result reveals an inherent optimality gap that exists in the traditional discretization methods. In addition, we analytically examine conditions under which the traditional discretization method does converge. We further analyze the convergence of the linear programming relaxation of the lower bounding method in order to obtain a lower bound efficiently. We highlight a need to enhance this lower bound by introducing the sub-tour polytope into the formulation. While the problem examined in this paper is the single vehicle traveling salesman problem with time windows, the results apply to a general class of time constrained vehicle routing and scheduling problems