An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems

DOI10.1287/OPRE.34.5.698zbMath0612.90099OpenAlexW2066558813MaRDI QIDQ3753823

Kizhanatham Srikanth, Bezalel Gavish

Publication date: 1986

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.34.5.698

zbMATH Keywords

sensitivity analysisLagrangean relaxationbranch-and-boundsubgradient optimizationdegree-constrained minimal spanning treeMultiple traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (27)

Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ TSP race: minimizing completion time in time-sensitive applications ⋮ Hybrid search with neighborhood reduction for the multiple traveling salesman problem ⋮ Integration of equipment planning and project scheduling ⋮ Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations ⋮ Routing problems: A bibliography ⋮ Minimization of the total traveling distance and maximum distance by using a transformed-based encoding EDA to solve the multiple traveling salesmen problem ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ MineReduce: an approach based on data mining for problem size reduction ⋮ Modeling and optimization of multiple traveling salesmen problems: an evolution strategy approach ⋮ Transformation of multidepot multisalesmen problem to the standard travelling salesman problem ⋮ The coastal seaspace patrol sector design and allocation problem ⋮ A branch-and-bound approach for a vehicle routing problem with customer costs ⋮ Classification of travelling salesman problem formulations ⋮ Graphical-structure-based models for routing problems ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Selection and sequencing heuristics to reduce variance in gas turbine engine nozzle assemblies ⋮ The multiagent planning problem ⋮ Algorithms for the design of network topologies with balanced disjoint rings ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Integer linear programming formulations of multiple salesman problems and its variations ⋮ On the shortest path problem with negative cost cycles ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ Fictitious upper bounds in an algorithm for the symmetric traveling salesman problem ⋮ New lower bounds for the symmetric travelling salesman problem ⋮ Topological design of ring networks ⋮ A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

This page was built for publication: An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems