Abstract
To solve routing problems with given constraints, an initial routing solution is obtained in a construction phase and iteratively improved in a subsequent improvement phase. With O(1) time complexity to check for constraint satisfaction per change with p being the total length of all paths changed between a known solution and a new candidate solution, current approaches have O(p²) time and space complexity when replacing the current solution with a new one. This does not scale when routing problems involve paths that have hundreds of nodes. This disclosure describes techniques to perform efficient pre-computations to reduce the time and space complexity to O(p log p), thus significantly saving time and resources. The pre-computations check constraint satisfaction for new candidate solutions generated with small variations from a current solution that is known to respect the constraints. The new candidate solutions are described by the chains of their paths that are changed in comparison to the current solution. The checking and pre-computations are performed with a general algorithm and associated query scheme for each subproblem, and run in linear time in the number of chains. As a result, the time and space complexity of the operation is reduced to O(p log p), where p is the total length of all changed paths in the new solution.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Gay, Steven, "Improved Time-related Checking in Routing Solvers", Technical Disclosure Commons, (February 08, 2023)
https://www.tdcommons.org/dpubs_series/5671