A reoptimization algorithm for the shortest path problem with time windows (Q1123818)

The shortest path problem with time windows (SPPTW) consists of finding the least cost route between two nodes in a network \(G=(N,A)\), while visiting each chosen node i within a specified time interval \([a_ i,b_ i]\). The problem of finding the set of disjoint paths, covering all the nodes of the network requires the solution of a sequence of SPPTWs, each one providing one path. After solving the k-th problem for a set of nodes \(N^ k\) (the authors propose a dynamic programming algorithm here), the nodes \(S^ k\) belonging to the optimal solution \(X^ k\) are removed from \(N^ k\) to form a set of nodes \(N^{k+1}=(N^ k-S^ k)\), used for the \((k+1)th\) problem. In order to reduce the cost of repeatedly solving the SPPTW, a primal- dual reoptimization algorithm is proposed, reusing in the k-th problem part of the solution of the \((k+1)th\) problem. Implementation issues and the complexity of the reoptimization algorithm, running in pseudo- polynomial time, are discussed. Also numerical results are reported, including the efficiently solved example of a network with 2500 nodes and 250000 arcs.