The precedence constrained traveling salesman problem (TSP-PC), or the sequential ordering problem (SOP), consists of finding an optimal TSP tour that will also satisfy the namesake precedence constraints, typically specified as a partial order or a directed acyclic graph. Its dynamic programming (DP) solution was proposed as early as 1979, however, by late 1990s, it mostly fell out of use in plain TSP-PC. Revisiting this method, we are able to close one of the long-standing TSPLIB SOP problem instances, ry48p.3.sop, and provide improved bounds on its time complexity. Harnessing the “omnivorous” nature of DP, we prove the validity of DP optimality principle for TSP-PC with both (i) abstract cost aggregation function, which may be the arithmetic + operation as in “ordinary” TSP or max as in Bottleneck TSP, or any other left-associative nondecreasing in the first argument operation and (ii) travel cost functions depending on the set of pending tasks (“sequence dependence”). Using the latter generalization, we close several TD-SOP (time-dependent TSP-PC) instances based on TSPLIB SOP as proposed by Kinable et al., including rbg253a.sop. Through the restricted DP heuristic, which was originally formulated for time-dependent TSP by Malandraki and Dial, we improve the state-of-the-art upper bounds for all yet unsolved TSPLIB-based TD-SOP instances, including those with more than 100 cities. We also improve worst-case complexity estimates for DP in TSP-PC.
https://doi.org/10.1016/j.ejor.2018.06.003Cite as:
@article{Salii_2019,
doi = {10.1016/j.ejor.2018.06.003},
url = {https://doi.org/10.1016%2Fj.ejor.2018.06.003},
year = 2019,
month = {jan},
publisher = {Elsevier {BV}},
volume = {272},
number = {1},
pages = {32--42},
author = {Yaroslav Salii},
title = {Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization},
journal = {European Journal of Operational Research}
}