The traveling salesman problem with cumulative costs

From MaRDI portal
Publication:5287441





Let \(D= (V, A)\) denote a directed graph with vertex set \(V\) and arc set \(A\). The travelling salesman problem (TSP) is the problem of finding a minimum cost tour (or Hamiltonian circuit) in a directed graph. A generalization of TSP is the time-dependent travelling salesman problem (TDTSP) in which the cost of travelling between cities depends on their location as well as their positions on the tour. In this paper, the authors consider an instance of TDTSP where the objective is to minimize the sum of all distances travelled from the origin to all other vertices. They denote this problem as the TSP with cumulative costs or simply CTSP. The authors develop two exact algorithms incorporating lower bounds provided by a Lagrangean relaxation of an integer programming formulation. Also investigated is a heuristic procedure derived from dynamic programming that is able to evaluate the distance from optimality of the produced solution. Computational results on randomly generated problems with 15 to 60 cities are presented. Problems with up to 35 cities can be solved optimally whilst problems up to 60 cities can be solved within 3\% of optimality.




Cited in
(34)








This page was built for publication: The traveling salesman problem with cumulative costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5287441)