
Accession Number : AD0709059
Title : A BRANCHANDBOUND 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 branchandbound 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 (n1) 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 stepbystep detail and illustrated by flow chart and examples. A modification for symmetric (r sub (ij)) sup k improves the efficiency of the algorithm. A tradeoff 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