Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization |
| |
Authors: | Yaroslav Salii |
| |
Institution: | 1. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620219, Russia;2. Ural Federal University, pr. Lenina 51, Yekaterinburg 620083, Russia |
| |
Abstract: | 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 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. |
| |
Keywords: | Dynamic programming Traveling salesman problem Precedence constraints Complexity Time dependence |
本文献已被 ScienceDirect 等数据库收录! |
|