Accession Number : AD0709059

Title :   A BRANCH-AND-BOUND ALGORITHM FOR THE SOLUTION OF SEQUENCE DEPENDENT ROUTING PROBLEMS.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF

Personal Author(s) : DeHaemer,Michael Joseph

Report Date : APR 1970

Pagination or Media Count : 57

Abstract : A branch-and-bound algorithm, which finds the optimal route through n nodes when a different cost matrix occurs after each arc in the sequence is traversed, is presented. The route may begin at any node and must pass through each of the n nodes exactly once. The objective is to minimize total cost in traversing (n-1) arcs of the route. The cost of traversing each arc is (r sub (ij)) sup k, which is a function of the distance between nodes i and j and a function of the kth position in the sequence of arcs forming the route. The algorithm is presented in step-by-step detail and illustrated by flow chart and examples. A modification for symmetric (r sub (ij)) sup k improves the efficiency of the algorithm. A trade-off between computation time and storage requirements may be accomplished by alternate branching policies. Suboptimal solutions may be obtained with reduced computation. (Author)

Descriptors :   (*TRANSPORTATION, NETWORKS), (*MATHEMATICAL PROGRAMMING, ALGORITHMS), DYNAMIC PROGRAMMING, PROBLEM SOLVING, GRAPHICS, OPTIMIZATION, THESES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE