Search

The well-known Steiner problem on networks is an NP-complete problem for which there are many deterministic algorithms and heuristics. In this paper a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. Two different types of cooling algorithms are tailored to the Directed Steiner Problem. Computations are done on a test bed of 480 random graphs in order to study the performance of these algorithms. In addition to the quality of the final answers, the study looks at the distribution of first occurrences during the execution of the cooling schedules of answers that are within 3% of the optimum. The study suggests that these near-optimal answers appear according to an approximately exponential distribution and that they can be obtained in polynomial time. Experiments also indicate that for random graphs annealing usually gives near-optimal answers in less time than does branch and bound. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper introduces the Multi-Terminal Sweep Algorithm, a heuristic algorithm for obtaining an approximate solution to the multiple terminal vehicle-dispatch problem. The procedure determines a set of routes by which vehicles from two or more terminals can service a collection of demand points so that the total distance traveled is kept near to the minimum. This solution also satisfies constraints on the vehicle load and on the length of each route. Application of the algorithm to eleven multiple terminal vehicle-dispatch problems shows that near-optimal solutions to large-scale problems can be found in a reasonable amount of computer time.

A branch and bound algorithm is designed to solve the general integer linear programming problem with parametric right-hand sides. The right-hand sides have the form b + θd where b and d are comformable vectors, d consists of nonnegative constants, and θ varies from zero to one. The method consists of first determining all possible right-hand side integer constants and appending this set of integer constants to the initial tableau to form an expanded problem with a finite number of family members. The implicit enumeration method gives a lower bound on the integer solutions. The branch and bound method is used with fathoming tests which allow one family member possibly to fathom other family members. A cutting plane option applies a finite number of cuts to each node before branching. In addition, the cutting plane method is invoked whenever some members are feasible at a node and others are infeasible. The branching and cutting process is repeated until the entire family of problem has been solved.

This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems with load and distance constraints for each vehicle. The locations that are used to make up each route are determined according to the polar-coordinate angle for each location. An iterative procedure is then used to improve the total distance traveled over all routes. The algorithm has the feature that the amount of computation required increases linearly with the number of locations if the average number of locations for each route remains relatively constant. For example, if the average number of locations per route is 7.5, the algorithm takes approximately 75 seconds to solve a 75-location problem on an IBM 360/67 and approximately 115 seconds to solve a 100-location problem. In contrast, the time to solve a problem with a fixed number of locations increases quadratically with the average number of locations per route. The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell's and is slightly less so than Christofides and Eilon's.

The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model.

The major problem in “layout” is to determine the most economical relative location of facilities. MAT is a construction technique utilizing the distances between all pairs of locations and the loads transported between all pairs of facilities per unit time to approximate the optimal allocation of the facilities to the locations. The MAT general algorithm, an example problem and a theorem relating the MAT solution to the optimal solution are given. A computer program has been written that will apply MAT to the allocation problem for a maximum of 40 facilities.

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.