On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem

DOI10.1111/j.1475-3995.1995.tb00023.xzbMath0860.90121OpenAlexW4242523418MaRDI QIDQ5688010

Mauro Dell'Amico, Peter Värbrand, Francesco Maffioli

Publication date: 6 January 1997

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.1995.tb00023.x

zbMATH Keywords

Lagrangean relaxationlower boundstravelling salesmanprize-collectingprofitable tour problemasymmetric version

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Notes on the single route lateral transhipment problem, The probabilistic travelling salesman problem with crowdsourcing, Exact algorithms for budgeted prize-collecting covering subgraph problems, The vehicle routing problem with service level constraints, Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems, The time-dependent capacitated profitable tour problem with time windows and precedence constraints, PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems, Multiperiod integrated spare parts and tour planning for on-site maintenance activities with stochastic repair requests, Systematic reviews as a metaknowledge tool: caveats and a review of available options, FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM, A revisited branch-and-cut algorithm for large-scale orienteering problems, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, Hybridized evolutionary local search algorithm for the team orienteering problem with time windows, Column Generation Algorithms for the Capacitated m-Ring-Star Problem, Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio, The hazardous orienteering problem, A primal-dual approximation algorithm for the asymmetric prize-collecting TSP, The selective traveling salesman problem with emission allocation rules, A stabilized column generation scheme for the traveling salesman subtour problem, A unified matheuristic for solving multi-constrained traveling salesman problems with profits, Multi-objective meta-heuristics for the traveling salesman problem with profits, Exact methods for solving the elementary shortest and longest path problems, An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits, The online prize-collecting traveling salesman problem, Multi-objective vehicle routing problems, A branch-and-cut-and-price approach for the capacitated \(m\)-ring-star problem, Unnamed Item, Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics, A branch-and-cut algorithm for the capacitated profitable tour problem, Heuristics for multi-attribute vehicle routing problems: a survey and synthesis

Cites Work

• Unnamed Item
• A note on the prize collecting traveling salesman problem
• The selective travelling salesman problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• On Some Generalizations of the Travelling-Salesman Problem
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Validation of subgradient optimization