The travelling salesman problem as a constrained shortest path problem: Theory and computational experience

zbMATH Open0446.90084MaRDI QIDQ1146121FDOQ1146121

Authors: David J. jun. Houck, Jean-Claude Picard, Maurice Queyranne, R. R. Vemuganti 

Publication date: 1980

Published in: Opsearch (Search for Journal in Brave)

zbMATH Keywords

travelling salesman problembranch and bound algorithmconstrained shortest path problemcomputational experiencen-path relaxationoptimal vertex penalties

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35)

Cited In (35)

• A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands
• Column Generation Algorithms for the Capacitated m-Ring-Star Problem
• Compact formulations of the Steiner traveling salesman problem and related problems
• A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem
• An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems
• The hazardous orienteering problem
• A stochastic dynamic traveling salesman problem with hard time windows
• Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems
• The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem
• A rollout algorithm for the resource constrained elementary shortest path problem
• A profit-maximization location-routing-pricing problem: a branch-and-price algorithm
• A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands
• MIP modelling of changeovers in production planning and scheduling problems
• Bounding the optimum for the problem of scheduling the photographs of an agile Earth observing satellite
• A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times
• A column generation approach to the heterogeneous fleet vehicle routing problem
• Real-time vehicle rerouting problems with time windows
• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• The shortest path problem with forbidden paths
• A branch-and-price algorithm for capacitated arc routing problem with flexible time windows
• Convergent duality for the traveling salesman problem
• A computational study of solution approaches for the resource constrained elementary shortest path problem
• A dynamic programming based algorithm for the crew scheduling problem.
• Freight railway operator timetabling and engine scheduling
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Formulations and exact algorithms for the vehicle routing problem with time windows
• Lagrangian duality applied to the vehicle routing problem with time windows
• Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• A survey of resource constrained shortest path problems: exact solution approaches
• Microcomputer-based algorithms for large scale shortest path problems
• Robust Team Orienteering Problem with Decreasing Profits
• New techniques for cost sharing in combinatorial optimization games

This page was built for publication: The travelling salesman problem as a constrained shortest path problem: Theory and computational experience

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