A shortest path problem on the network with AGV-type time-windows

This paper deals with a shortest path problem on a network with time-windows. The concept of time-windows is recently introduced by Desrosiers et al as a subproblem of the traveling salesman problem involving time constraints. Authors consider another type of time-windows, which we name the AGV-type time-window, and define a shortest path problem on the network with the AGV-type time-windows. The authors verify that this problem has a structure similar to the conventional shortest path problem without time-windows and propose several methods to solve the problem with such time-windows. The method consists of two procedures: first, they divide the main problem into subproblems, and then solve these subproblems using the dynamic programming or the branch and bound method. Numerical experiments are carried out to compare the computational performance of the proposed algorithms.