ACM Transactions on Mathematical Software · 1995 · 109 citations · 12 references
Mathematical ProgrammingBranch-and-bound AlgorithmHeuristic SearchAssignment Problem RelaxationEngineeringExact SolutionComputational ComplexityDiscrete OptimizationBranch-decision TreeOperations ResearchTraveling Salesman ProblemSystems EngineeringDiscrete MathematicsParallel ComputingCombinatorial OptimizationCombinatorial ProblemComputer EngineeringSubtour EliminationComputer ScienceInteger ProgrammingGraph TheoryParallel ProgrammingVehicle Routing ProblemBranch And Bound
A lowest-first, branch-and-bound algorithm for the Asymmetric Traveling Salesman Problem is presented. The method is based on the Assignment Problem relaxation and on a subtour elimination branching scheme . The effectiveness of the algorithm derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree. Large-size, uniformly, randomly generated instances of complete digraphs with up to 2000 vertices are solved on a DECstation 5000/240 computer in less than 3 minutes of CPU time. In addition, we solved on a PC 486/33 no wait flow shop problems with up to 1000 jobs in less than 11 minutes and real-world stacker crane problems with up to 443 movements in less than 6 seconds.
12
Efficient Algorithms for Shortest Paths in Sparse Networks
D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text
Flowshop scheduling with limited temporary storage
Christos H. Papadimitriou, Paris C. Kanellakis · Journal of the ACM · 1980 · 248 citations · Full text