Research Reports from the Department of Operations
Document Type
Report
Publication Date
4-1-1971
Abstract
A formulation of the traveling salesman problem with more than one salesman is offered. The particular formulation has computational advantages over other formulations. Experience is obtained with an exact branch and bound algorithm employing both upper and lower bounds (mean run time for 55 city problems is one minute). Due to the special formulation, certain subtours may satisfy the constraints, thus reducing the search. A very good initial tour and upper bound are employed. The determination of these as well as the pathology of the formulation and the algorithm are discussed. No increase in computation time over the one salesman case is experienced.
Keywords
Operations research, Traveling salesman problem, Combinatorial optimization, Algorithms, Branch and bound algorithms, Computational complexity
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 224
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Svestka, Joseph A. and Huckfeldt, Vaughn E., "Computational Experience with a Traveling Salesmen Algorithm" (1971). Research Reports from the Department of Operations. 85.
https://commons.case.edu/wsom-ops-reports/85