A branch-and-bound algorithm for the solution of sequence dependent routing problems
DeHaemer, Michael Joseph
Schudde, Rex H.
MetadataShow full item record
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 k/ij 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 k/ij) 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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Solution of large-scale multicommodity network flow problems via a logarithmic barrier function decomposition Lange, Heinrich (Monterey, California. Naval Postgraduate School, 1988-03);A new algorithm is presented using a logarithmic barrier function decomposition for the solution of the large-scale multicommodity network flow problem. Placing the complicating joint capacity constraints of the multicommodity ...
Polak, E.; Royset, J.O. (2008);We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is speci_ed in terms of a fractional reduction of the initial cost error. We show that such an approximate ...
New motion planning and real-time localization methods using proximity for autonomous mobile robots Wahdan, Mahmoud A. (Monterey, California. Naval Postgraduate School, 1996-09);One of the most difficult theoretical problems in robotics--motion planning for rigid body robots-- must be solved before a robot can perform real- world tasks such as mine searching and processing. This dissertation ...