Solid-Waste Disposal with Intermediate Transfer Stations: An Application of the Fixed-Charge Location Problem

This paper examines the problem of urban solid-waste disposal by landfill. In such disposal, intermediate transfer stations are often used for processing before transport to the landfill. Located at the periphery of waste-generating areas, these transfer stations can compact or recover reusable materials, or merely transfer the waste to heavier and more efficient transporters for the longer, final leg of the trip to the disposal site. The model presented here optimizes disposal costs by trading off transportation costs against the capital and operating costs of introducing the transfer stations. A branch-and-bound procedure is used to obtain the optimum, and an imbedded simplex code serves to provide the solution at each branch.     

A Simple Algorithm for Solving Small,Fixed-Charge Transportation Problems

The solution of the classical transportation problem (as generally presented) can be mastered very quickly. The fixed-charge problem is another matter. The reason is that the introduction of fixed costs in addition to variable costs results in the objective function being a step function. Fixed-charge problems are usually solved, therefore, by using sophisticated computer software. This paper deviates from that approach. It presents a low-tech. algorithm for the solution of small, fixed-charge problems.     

An Algorithm for the Vehicle-dispatching Problem

The vehicle-scheduling problem involves the design of several vehicle tours to meet a given set of requirements for customers with known locations, subject to a capacity constraint for the vehicles and a distance (or time) constraint for vehicle tours. Three methods of solution are considered in this paper:

1. a
   A branch-and-bound approach.
    
2. b
   The "savings" approach.
    
3. c
   The 3-optimal tour method.
    

The excessive computation time and computer storage required for the first method renders it impracticable for large problems. Ten problems are examined and the results suggest that method C is superior to the other two methods.     

An Algorithm for the Allocation Problem

This paper* sets out a procedure for solving allocation problems, on different lines from procedures based on linear programming.     

求解运输问题的一种算法

文章给出了运输问题的一种算法,该算法计算过程容易掌握,求解具有一次终止性     

求解运输问题的一个算法

给出一个求解问题的数值算法，证明了算法的理论依据，并举例说明算法的应用。     

求解指派问题的一个算法

为了便于建立与指派问题有关的决策支持系统，本给出了一个求解指派问题的数值算法，证明了算法的理论依据。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

An Efficient Genetic Algorithm for the p-Median Problem

We propose a new genetic algorithm for a well-known facility location problem. The algorithm is relatively simple and it generates good solutions quickly. Evolution is facilitated by a greedy heuristic. Computational tests with a total of 80 problems from four different sources with 100 to 1,000 nodes indicate that the best solution generated by the algorithm is within 0.1% of the optimum for 85% of the problems. The coding effort and the computational effort required are minimal, making the algorithm a good choice for practical applications requiring quick solutions, or for upper-bound generation to speed up optimal algorithms.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

An Improved Algorithm for the Non-Guillotine-Constrained Cutting-Stock Problem

A personal-computer-based algorithm to solve the non-guillotine-constrained two-dimensional cutting-stock problem is developed. The problem is constrained to single-sized rectangles placed orthogonally on a larger containing rectangle. The algorithm uses the linear combination of box lengths and widths that minimizes waste along the cutting stock's length and width to determine an optimal layout. The algorithm's performance is evaluated using two sets of test cases and compared to the results of other algorithms.     

运输问题的一种图上解法

把运输问题转化成图的问题，给出了求解运输问题的一种图上算法。通过实例，验证了这是一个有效，可行的方法。     

An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.     

An Improved Algorithm for the Multi-commodity Location Problem

Distribution systems designs commonly require the optimal location decisions of regional ware-houses or distribution centers which function as intermediate facilities between plants and customers. This paper deals with such a location problem in which the facilities can handle one of several commodities. We term this problem the multi-commodity facility location problem. A branch and bound algorithm is proposed for solving this problem. Improved bounds are developed for increasing the efficiency of the algorithm. Computational results are provided.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

An Improved Algorithm for the Capacitated Facility Location Problem

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.     

Kth最短路径的Bellman改进算法

基于对Bellm an算法的改进,得到了求解k th最短路的新算法.改进算法的优势在于从Bellm an算法只能解决最短路问题拓展到求解k th最短路问题,而且可以考虑权重为负数的情况.与传统算法相比,新算法更易于理解.     

求解最大利润流问题的一个算法

为了便于建立与最大利润流问题有关的决策支持系统，本给出了一个交易网络中求最大利润流的数值算法，证明了算法的理论依据，并举例了说明算法的应用。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

An Algorithm for Solving a Resource Allocation Problem

The paper discusses the solution of a resource allocation problem and a new method for solving a special case of the problem. An algorithm for solving the general problem is presented, and computational experience comparing it with existing methods is given.     

离线k-服务器问题算法的改进

阐述了在k-服务器猜想的证明中改进经典的离线k-服务器问题算法的必要性,从而对经典算法进行了改进,设计了一种新算法,其复杂度由原来的O(m(nk)2)下降为O(mk2).