A branch-and-bound algorithm for the solution of sequence dependent routing problems
Loading...
Authors
DeHaemer, Michael Joseph
Subjects
Routing
Sequencing
Traveling salesman
Branch-and-bound
Algorithm
Shortest route
Sequencing
Traveling salesman
Branch-and-bound
Algorithm
Shortest route
Advisors
Schudde, Rex H.
Date of Issue
1970-04
Date
April 1970
Publisher
Monterey, California; Naval Postgraduate School
Language
en_US
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 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.
Type
Thesis
Description
Series/Report No
Department
Department of Operations Analysis
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.