The traveling salesman problem with cumulative costs
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.
- Time‐dependent traveling salesman problem–the deliveryman case
- scientific article; zbMATH DE number 947471
- Time-dependent travelling salesman problem.
- A new generalization of the traveling salesman problem
- Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem
- A classification of formulations for the (time-dependent) traveling salesman problem
- Solving the continuous flow-shop scheduling problem by metaheuristics.
- A branch-and-price algorithm for the minimum latency problem
- A performance study on multi improvement neighborhood search strategy
- Routing problems: A bibliography
- The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach
- A simple and effective metaheuristic for the minimum latency problem
- The multi-depot \(k\)-traveling repairman problem
- Solving the traveling delivery person problem with limited computational time
- The arc-item-load and related formulations for the cumulative vehicle routing problem
- Weighted online minimum latency problem with edge uncertainty
- Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints
- A hybrid reactive GRASP heuristic for the risk-averse \(k\)-traveling repairman problem with profits
- A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem
- A heuristic for cumulative vehicle routing using column generation
- Time-dependent travelling salesman problem.
- A bicriteria scheduling with sequence-dependent setup times
- An online optimization approach for post-disaster relief distribution with online blocked edges
- A new generalization of the traveling salesman problem
- Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem
- The delivery man problem with time windows
- Exact and heuristic solutions to minimize total waiting time in the blood products distribution problem
- Continuous time dependent multilple travelling salesman problem
- Natural and extended formulations for the time-dependent traveling salesman problem
- THE TSP AND THE SUM OF ITS MARGINAL VALUES
- Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
- A new integer programming formulation of the graphical traveling salesman problem
- Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining
- A guided quantum particle swarm optimization approach for the traveling repairman problem
- A dynamic and stochastic cumulative capacitated vehicle routing problem
- Quantum annealing-driven branch and bound for the total weighted tardiness traveling salesman problem on the D-wave quantum computer
- Cost allocation: The traveling salesman, bin packing, and the knapsack
- The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
- An effective memetic algorithm for the cumulative capacitated vehicle routing problem
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)