A generalized threshold algorithm for the shortest path problem with time windows
Warren B. Powell, Zhilong Chen · DIMACS series in discrete mathematics and theoretical computer science · 1998
Abstract: In this paper, we present a new labeling algorithm for the shortest path problem with time windows (SPPTW). It is generalized from the threshold algorithm for the unconstrained shortest path problem. Our computational experiments show that this generalized threshold algorithm outperforms a label setting algorithm for the SPPTW on a set of randomly generated test problems. The average running time of the new algorithm is about 40 % less than the label setting algorithm, which istoday the best algorithm based on published experimental evidence. 1 The shortest path problem with time windows (SPPTW) is a generalization of the classical (unconstrained) shortest path problem (SPP) involving the added complexity of time windows. The SPPTW can be described as follows. Let G =(V�A) be a directed graph where V = N [fp � qg is the set of nodes with source node p and sink node q, A is the set of arcs. Each nodei2V has a time window [ai�bi] within which nodeican be visited. Each arc (i � j) has a positive duration tij