FINDING A CYCLE IN A GRAPH WITH MINIMUM COST TO TIME RATIO WITH APPLICATION TO A SHIP ROUTING PROBLEM

Abstract

Associated with each arc of a directed graph are two numbers which will be called arc cost and arc time. The problem is to find that cycle in a graph whose ratio of the sum of arc costs to the sum of arc times around the cycle is a minimum. Application of the simplex method reduces to finding a negative cycle in a graph when arc distances are given which may be positive or negative. The algorithm thus may be viewed as a variant of the shortest route algorithm that yields either the shortest route from a starting node to all others or uncovers a negative cycle. This problem arose as a sub-problem of a larger problem in which the decomposition principle was used. The application was to ship routing where there are quantities to be shipped between various parts, and vessels have capacities that depend on the type of vessel and type of arc.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1966
Accession Number
AD0646553

Entities

People

  • George Bernard Dantzig
  • M. R. Rao
  • W. O. Blattner

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Coefficients
  • Computations
  • Contracts
  • Decomposition
  • Equations
  • Heuristic Methods
  • Linear Programming
  • Mathematics
  • Military Research
  • Operations Research
  • Security
  • Simplex Method
  • United States
  • Universities

Readers

  • Life Cycle Cost Analysis
  • Operations Research
  • Plasma Physics.