Accession Number:

AD0646553

Title:

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

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA OPERATIONS RESEARCH HOUSE

Report Date:

1966-11-01

Pagination or Media Count:

16.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE