Enumeration and Search Procedures for a Hub Location Problem with Economies of Scale

Within a communications or transportation network, in which a number of locations exchange material or information, hubs can be used as intermediate switching points. In this way, traffic can be consolidated on inter-hub links and, thus, achieve economies of scale in transport costs. Recently, O'Kelly and Brian in 1998 proposed a model (termed the FLOWLOC model) that treats these economies of scale by means of piecewise-linear concave cost functions on the interhub arcs. We show that, for a fixed set of hubs, the FLOWLOC model can be solved using the classic Uncapacitated Facility Location Problem (UFLP). This observation then motivates an optimal enumeration procedure for the FLOWLOC model, as well as some search heuristics that are based upon tabu search and greedy random adaptive search procedures (GRASP). These search procedures would be especially applicable for large-sized problems. Some computational experience is described.     

An Inventory-Location Model: Formulation, Solution Algorithm and Computational Results

We introduce a distribution center (DC) location model that incorporates working inventory and safety stock inventory costs at the distribution centers. In addition, the model incorporates transport costs from the suppliers to the DCs that explicitly reflect economies of scale through the use of a fixed cost term. The model is formulated as a non-linear integer-programming problem. Model properties are outlined. A Lagrangian relaxation solution algorithm is proposed. By exploiting the structure of the problem we can find a low-order polynomial algorithm for the non-linear integer programming problem that must be solved in solving the Lagrangian relaxation subproblems. A number of heuristics are outlined for finding good feasible solutions. In addition, we describe two variable forcing rules that prove to be very effective at forcing candidate sites into and out of the solution. The algorithms are tested on problems with 88 and 150 retailers. Computation times are consistently below one minute and compare favorably with those of an earlier proposed set partitioning approach for this model (Shen, 2000; Shen, Coullard and Daskin, 2000). Finally, we discuss the sensitivity of the results to changes in key parameters including the fixed cost of placing orders. Significant reductions in these costs might be expected from e-commerce technologies. The model suggests that as these costs decrease it is optimal to locate additional facilities.     

A combinatorial approach to level of repair analysis

This paper presents an approach to optimise level of repair decisions taking into account submodular properties of standard life cycle cost functions, which include fixed and variable costs. It proposes an integer programming formulation to solve level of repair problems for multi-echelon multi-indenture level systems. The method converges quickly to the optimum solution relying on heuristics to obtain tight bounds for a subsequent branch-and-bound procedure. A software package called level of repair optimisation model (LOROM) was developed to implement the branch-and-bound method that does not rely on linear programming relaxations. This approach is rather generic and can be applied to a wide class of problems with convex total cost functions such as plant location problems or transportation problems with fixed costs.     

Location of slaughterhouses under economies of scale

The facility location problem described in this paper comes from an industrial application in the slaughterhouse industry of Norway. Investigations show that the slaughterhouse industry experiences economies of scale in the production facilities. We examine a location-allocation problem focusing on the location of slaughterhouses, their size and the allocation of animals in the different farming districts to these slaughterhouses. The model is general and has applications within other industries that experience economies of scale.We present an approach based on linearization of the facility costs and Lagrangean relaxation. We also develop a greedy heuristic to find upper bounds. We use the method to solve a problem instance for the Norwegian Meat Co-operative and compare our results to previous results achieved using standard branch-and-bound in commercial software.     

Two-level evolutionary approach to the survivable mesh-based transport network topological design

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be NP\mathcal{NP} -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

No-wait flowshops with bicriteria of makespan and total completion time

We consider the m-machine no-wait flowshop scheduling problem with the objective of minimizing a weighted sum of makespan and total completion time. For the two-machine problem, we develop a dominance relation and embed it within a proposed branch-and-bound algorithm. For the m-machine problem, we propose a heuristic. Computational experiments show that the proposed heuristic outperforms the best existing multi-criteria heuristics and the best single criterion heuristics for makespan and total completion time. The efficiency of the dominance relation and branch-and-bound algorithm is also investigated and shown to be effective.     

凹整数规划的分枝定界解法

凹整数规划是一类重要的非线性整数规划问题，也是在经济和管理中有着广泛应用的最优化问题．本文主要研究用分枝定界方法求解凹整数规划问题，这一方法的基本思想是对目标函数进行线性下逼近，然后用乘子搜索法求解连续松弛问题．数值结果表明，用这种分枝定界方法求解凹整数规划是有效的．     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Heuristics for convex mixed integer nonlinear programs

In this paper, we describe the implementation of some heuristics for convex mixed integer nonlinear programs. The work focuses on three families of heuristics that have been successfully used for mixed integer linear programs: diving heuristics, the Feasibility Pump, and Relaxation Induced Neighborhood Search (RINS). We show how these heuristics can be adapted in the context of mixed integer nonlinear programming. We present results from computational experiments on a set of instances that show how the heuristics implemented help finding feasible solutions faster than the traditional branch-and-bound algorithm and how they help in reducing the total solution time of the branch-and-bound algorithm.     

Search Heuristics for Box Decomposition Methods

In this paper we study search heuristics for box decomposition methods that solve problems such as global optimization, minimax optimization, or quantified constraint solving. For this we unify these methods under a branch-and-bound framework, and develop a model that is more convenient for studying heuristics for such algorithms than the traditional models from Artificial Intelligence. We use the result to prove various theorems about heuristics and apply the outcome to the box decomposition methods under consideration. We support the findings with timings for the method of quantified constraint solving developed by the author.     

Strategic planning in LTL logistics – increasing the capacity utilization of trucks

A “less than truckload” (LTL) network organises the transport of small shipping volumes by truck between given depots. To be cost-efficient it is necessary to bundle and unbundle goods on their way, using depots as so-called hubs. Our aim is to develop a strategic plan which is cost-optimal for given average shipping volumes. We consider transshipment and transport costs; to give a realistic estimate of the economies of scale, we charge each truck on a specific route equally, whether it is full or (nearly) empty.Real-sized problems become too hard for standard solvers so that we develop a combination of heuristic strategies (which can, in the end, be combined with solvers like CPLEX). We consider the problem in two flavours: MAPIT requires to transport unsplit goods from one depot to another, using at most two intermediate depots as hubs. IO-MAPIT furthermore considers the circulation of trucks.     

A survey of algorithms for the generalized assignment problem

This paper surveys algorithms for the well-known problem of finding the minimum cost assignment of jobs to agents so that each job is assigned exactly once and agents are not overloaded. All approaches seem to be based on branch-and-bound with bound supplied through heuristics and through relaxations of the primal problem formulation. From the survey one can select building blocks for the design of one's own tailor-made algorithm. The survey also reveals that although just about every mathematical programming technique was tried on this problem, there is still a lack of a representative set of test problems on which competing enumeration algorithms can be compared, as well as a shortage of effective heuristics.     

A Lagrangian Based Branch-and-Bound Algorithm for Production-transportation Problems

We propose a branch-and-bound algorithm of Falk–Soland's type for solving the minimum cost production-transportation problem with concave production costs. To accelerate the convergence of the algorithm, we reinforce the bounding operation using a Lagrangian relaxation, which is a concave minimization but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the algorithm can solve fairly large scale problems.     

Facility location with increasing production costs

Facility location models determine the set of locations on a network that minimize the sum of the costs of investment, production, and distribution to meet a known set of demands. In this paper, we introduce a new type of facility location model, which combines aspects of the well-studied simple uncapacitated and capacitated facility location problems. Its distinctive feature is that unit production costs are modeled as increasing with scale of output. Such cost functions have practical value in handling cases in which capacity can be “stretched” by incurring some additional cost (e.g., by adding workers). Indeed, it is shown that average total costs are minimized at a point where average production costs are rising. Four different formulations for this problem are proposed. Using linear programming plus branch-and-bound as a solution method, the four formulations are tested and compared on a set of 216 problems with randomly generated data.     

基于线路“异质性”假设的轴辐式公共交通网络优化研究

特大城市公共交通局部静态拥堵问题日益成为制约公共交通网络运行效率提高的关键。针对这一问题改变线路“同质性”假设,在线路“异质性”假设的基础上,提出了将轴辐式网络设计运用到公共交通领域中来,综合考虑居民采用公共交通方式出行的单位运输可变成本、不变成本、枢纽换乘成本等要素,将枢纽间大型客车干线运输所带来的规模经济效应进行量化,构建了基于单分配、多枢纽、混合式网络结构特征的轴辐式公共交通网络优化模型,旨在多重约束下通过枢纽布局降低网络运输成本,提高公共交通网络站点的可达性。最后根据模拟退火算法对模型进行求解,并通过算例分析与讨论的方式验证了模型的有效性。     

Minimizing maximum lateness in a flow shop subject to release dates

We consider the problem of minimizing the maximum lateness in a m-machine flow shop subject to release dates. The objective of this paper is to develop a new branch-and-bound algorithm to solve exactly this strongly NP-hard problem. The proposed branch-and-bound algorithm encompasses several features including a procedure for adjusting heads and tails, heuristics, and a lower bounding procedure, which is based on the exact solution of the two-machine flow shop problem with time lags, ready times, and delivery times. Extensive computational experiments show that instances with up to 6000 operations can be solved exactly in a moderate CPU time.     

A theoretical justification of the set covering greedy heuristic of Caprara et al.

Large scale set covering problems have often been approached by constructive greedy heuristics, and much research has been devoted to the design and evaluation of various greedy criteria for such heuristics. A criterion proposed by Caprara et al. (1999) is based on reduced costs with respect to the yet unfulfilled constraints, and the resulting greedy heuristic is reported to be superior to those based on original costs or ordinary reduced costs.We give a theoretical justification of the greedy criterion proposed by Caprara et al. by deriving it from a global optimality condition for general non-convex optimisation problems. It is shown that this criterion is in fact greedy with respect to incremental contributions to a quantity which at termination coincides with the deviation between a Lagrangian dual bound and the objective value of the feasible solution found.     

Heuristics for the fixed cost median problem

We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem.