On dynamic programming for Precedence-Constrained TSPs with Profits

Among the diverse TSP varieties there exist “TSPs with profits,” see the review in (Feillet et al. 2005). Their two principal features are as follows: 1.) There are two objective functions; typically, there is a “ cost” associated with moving between the cities (defined on the edges of the corresponding graph) and a “profit” associated with visiting a city (defined on the vertices of the graph). 2.) In contrast with true bicriteria TSPs, one of the objective functions is optimized whereas another one must not exceed a certain threshold, whence the possibility of visiting *only a subset* of cities.
The report will concentrate on solving precedence-constrained TSPs with profits; to the best of the author's knowledge, such statements were not yet considered, however, they might have viable applications. For example, one could consider the the problem of dismantling a decommissioned nuclear power generation unit, where there will be a threshold on costs (read personnel exposure to radiation), whereas the profit from visiting vertices—dismantling the unit's elements— will be maximized; this version of TSP with profits is known as the Orienteering Problem.
Dynamic programming is chosen in spite of the well-established application of MILP to such problems because of its inherent ability to deal with and profit from precedence constraints.
(Feillet et al. 2005) Feillet D., Dejax P., Gendreau M., Traveling Salesman Problems with Profits // Transportation Science, vol. 396 No.2, 1995, pp. 118–205