The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
From MaRDI portal
Publication:1146121
zbMath0446.90084MaRDI QIDQ1146121
Jean-Claude Picard, Maurice Queyranne, David J. jun. Houck, R. R. Vemuganti
Publication date: 1980
Published in: Opsearch (Search for Journal in Brave)
travelling salesman problembranch and bound algorithmcomputational experienceconstrained shortest path problemn-path relaxationoptimal vertex penalties
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)
Related Items
A Branch-and-Price Algorithm for Capacitated Arc Routing Problem with Flexible Time Windows, The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem, Freight railway operator timetabling and engine scheduling, Robust Team Orienteering Problem with Decreasing Profits, New techniques for cost sharing in combinatorial optimization games, A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands, A profit-maximization location-routing-pricing problem: a branch-and-price algorithm, A column generation approach to the heterogeneous fleet vehicle routing problem, Column Generation Algorithms for the Capacitated m-Ring-Star Problem, The hazardous orienteering problem, A dynamic programming based algorithm for the crew scheduling problem., A computational study of solution approaches for the resource constrained elementary shortest path problem, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, Convergent duality for the traveling salesman problem, A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands, Formulations and exact algorithms for the vehicle routing problem with time windows, Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Real-time vehicle rerouting problems with time windows, Bounding the optimum for the problem of scheduling the photographs of an agile Earth observing satellite, Lagrangian duality applied to the vehicle routing problem with time windows, A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, A rollout algorithm for the resource constrained elementary shortest path problem, The shortest path problem with forbidden paths, A survey of resource constrained shortest path problems: Exact solution approaches, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, MIP modelling of changeovers in production planning and scheduling problems, A stochastic dynamic traveling salesman problem with hard time windows, An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems, A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, Microcomputer-based algorithms for large scale shortest path problems, Compact formulations of the Steiner traveling salesman problem and related problems
