One of the standard approaches for solving time-dependent discrete optimization problems, such as the traveling salesman problem with time-windows or the shortest path problem with time-windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology. Therefore, algorithms for the corresponding time-independent variant become applicable. The downside of this approach is that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion that might contain time infeasible paths often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation is time feasible, an optimal solution can be derived from it, and the algorithm terminates. In this work, we present new ideas that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms, which are based on graph refinement. More precisely, we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations of time-dependent problems that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm, we present numerical results on its application to the shortest path problem with time-windows and the traveling salesman problem with time-windows.
Citation
Cottbus Mathematical Preprint COMP#13 (2020), Brandenburg University of Technology, Platz der Deutschen Einheit 1, 03046 Cottbus, Germany