The M-Travelling Salesmen Problem: A Duality Based Branch-and-Bound Algorithm.

Abstract

This paper presents a new model and branch-and-bound algorithm for the m-travelling salesmen problem. The algorithm uses a Lagrangean relaxation, a subgradient algorithm to solve the Lagrangean dual, a greedy algorithm for obtaining minimal m-trees, penalties to strengthen the lower bounds on candidate problems, and a new concept known as staged optimization. Computational experience for both symmetric and asymmetric problems having up to 100 cities is presented. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1980
Accession Number
ADA092951

Entities

People

  • I. Ali
  • J. Kennington

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Beyond Visual Range Missiles
  • Computer Programming
  • Contracts
  • Core Storage
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Linear Programming
  • Military Research
  • Optimization
  • Plastic Explosives
  • Scientific Research
  • Theses
  • Universities

Fields of Study

  • Computer science

Readers

  • Operations Research