A Procedure for Computing the <i>K</i> Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

A general procedure is presented for computing the best, 2nd best,…, Kth best solutions to a given discrete optimization problem. If the number of computational steps required to find an optimal solution to a problem with n(0, 1) variables is c(n), then the amount of computation required to obtain the if best solutions is O(K nc (n)). The procedure specializes to published procedures of Murty and of Yen for the assignment problem and the shortest path problem, respectively. A method is presented for reducing the required amount of storage by a factor of n, compared with the algorithms of Murty and of Yen. It is shown how the K shortest (loopless) paths in an n-node network with positive and negative arcs can be computed with an amount of computation which is O(Kn 3 ). This represents an improvement by a factor of n, compared with Yen's algorithm.

• 저널Management Science · 18(7) · 401–405
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.18.7.401
• 저자Eugene L. Lawler