Re-evaluation in Dynamic Tree-Search with Backtracking from Known Solutions

In dynamic environments, solutions may become invalid during or after the execution of an optimization algorithm due to changing circumstances, requiring the adaptation or creation of new solutions. This paper uses the hot-storage area of a steel processing plant as a dynamic environment, where the optimization task involves creating lot-assignments of steel slabs for efficient transportation. The lot-assignment problem is represented as a search tree, where slabs are gradually assigned to new or existing lots as the tree is traversed. Unforeseen events in the dynamic hot-storage area can render existing lot-assignments invalid or make them less effective. Instead of completely re-running a tree-search algorithm in response to such dynamic events, we propose a backtracking strategy that uses information from outdated solutions. This strategy involves constructing a backtracking chain to check the validity of the lot-assignments used to construct the outdated solution and to identifying potential restart points for partial search spaces. Through experiments, we show the performance and reliability of various tree-search algorithms under different runtime budgets, with and without backtracking-based restart strategies. Our results strongly suggest that using information from a previous solution significantly enhances algorithm performance to identify valid solutions compared to a complete rerun. Additionally, using backtracking within the same runtime budget as a complete rerun can also improve solution quality.