An Algorithm for the Solution of a Traveling Salesman Problem to Minimize the Average Time to Demand Satisfaction.

Abstract

This paper presents a solution approach for solving a modified traveling salesman problem. In this problem, each city which the salesman must visit contains a quantity of demand (in units) which the salesman must satisfy. The objective of the salesman is to minimize the average time until satisfaction for each unit of demand. The solution approach presented is a branch-and-bound approach in which the total set of feasible tours are broken down into subsets. Lower bounds are the calculated for each subset and compared against a known upper bound to determine if this subset can be fathomed or if a improved upper bound has been found. The solution approach presented ensures optimality. A computer code was created and is presented which implements the solution approach developed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1992
Accession Number
ADA258301

Entities

People

  • James P. Ryan

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Data Sets
  • Engineering
  • Generators
  • Industrial Engineering
  • Industrial Modernization
  • Integer Programming
  • Operations Research
  • Propulsion Systems
  • Travel Time
  • Trees (Data Structures)
  • United States

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design