Capacitated facility location/network design problems

We introduce a combined facility location/network design problem in which facilities have constraining capacities on the amount of demand they can serve. This model has a number of applications in regional planning, distribution, telecommunications, energy management, and other areas. Our model includes the classical capacitated facility location problem (CFLP) on a network as a special case. We present a mixed integer programming formulation of the problem, and several classes of valid inequalities are derived to strengthen its LP relaxation. Computational experience with problems with up to 40 nodes and 160 candidate links is reported, and a sensitivity analysis provides insight into the behavior of the model in response to changes in key problem parameters.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Capacitated replenishment and disposal planning for multiple products with resalable returns

We consider a replenishment and disposal planning problem (RDPP) that arises in settings where customer returns are in as-good-as-new condition. These returns can be placed into inventory to satisfy future demand or can be disposed of, in case they lead to excess inventory. Our focus is on a multi-product setting with dynamic demands and returns over a finite planning horizon with explicit replenishment and disposal capacities. The problem is to determine the timing of replenishment and disposal setups, along with the associated quantities for the products, so as to minimize the total costs of replenishment, disposal, and inventory holding throughout the planning horizon. We examine two variants of the RDPP of interest both of which are specifically motivated by a spare part kitting application. In one variant, the replenishment capacity is shared among multiple products while the disposal capacity is product specific. In the other variant, both the replenishment and disposal capacities are shared among the products. We propose a Lagrangian Relaxation approach that relies on the relaxation of the capacity constraints and develop a smoothing heuristic that uses the solution of the Lagrangian problem to obtain near-optimal solutions. Our computational results demonstrate that the proposed approach is very effective in obtaining high-quality solutions with a reasonable computational effort.     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

Capacitated Warehouse Location with Concave Costs

The mixed integer-linear models that have been used in most analyses of warehouse location problems fail to capture the potential operating efficiencies associated with large scale facilities. This paper presents an algorithm for finding a minimal cost warehouse system design wherein individual warehouses have limited capacities and exhibit economies of scale. The iterative procedure defines and solves a series of conventional transportation problems in order to converge on the optimal system design. The algorithm is well suited to solving large problems of the type commonly encountered in practice.     

Capacitated transit assignment with loading priorities

In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a users position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution, users are assigned to strategies that minimize their expected delay. This situation is formulated as a variational inequality, whose cost mapping is discontinuous and strongly asymmetric, due to the priority of current passengers over incoming users. We prove that the solution set is nonempty and provide numerical results obtained by an efficient solution algorithm.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds pour la formation de chercheurs et laide à la recherche (FCAR).Mathematics Subject Classification (2000):20E28, 20G40, 20C20Accepted: December 20, 2003     

Balancing U-lines in a multiple U-line facility

U-shaped production lines and facilities consisting of many such lines are important parts of modem manufacturing systems. The problem of balancing and rebalancing U-line facilities is studied in this paper. Like the traditional line balancing problem this problem is NP-hard. The objective is to assign tasks to a minimum number of regular, crossover, and multiline stations while satisfying cycle time, precedence, location, and station-type constraints. A secondary objective is to concentrate the idle time in one station so that improvement efforts can be focused there in accordance with modern just-in-time principles. A reaching dynamic programming algorithm is presented for determining optimal balances. It is effective for balancing and rebalancing facilities with any number of U-lines, provided that individual U-lines do not have more than 22 tasks and do not have wide, sparse precedence graphs.     

The Queueing Maximal availability location problem: A model for the siting of emergency vehicles

The Maximal Availability Location Problem (MALP) has been recently formulated as a probabilistic version of the maximal covering location problem. The added feature in MALP is that randomness into the availability of servers is considered. In MALP, though, it is assumed that the probabilities of different servers being busy are independent. In this paper, we utilize results from queuing theory to relax this assumption, obtaining a more realistic model for emergency systems: the Queueing MALP or Q-MALP. We also consider in this model that travel times or distances along arcs of the network are random variables. We show here how to site limited numbers of emergency vehicles, such as ambulances, in such a way as to maximize the calls for service which have an ambulance available within a time or distance standard with reliability α — using a queueing theory model for server availability. We also propose some extensions to the basic model. Formulations are presented and computational experience is offered.     

Capacitated lot-sizing with extensions: a review

The capacitated lot-sizing problem (CLSP) is a standard formulation for big bucket lot-sizing problems with a discrete period segmentation and deterministic demands. We present a literature review on problems that incorporate one of the following extensions in the CLSP: back-orders, setup carry-over, sequencing, and parallel machines. We illustrate model formulations for each of the extensions and also mention the inclusion of setup times, multi-level product structures and overtime in a study. For practitioners, this overview allows to check the availability of successful solution procedures for a specific problem. For scientists, it identifies areas that are open for future research.      

A Transportation model with multiple criteria and multiple constraint levels

In this paper, a transportation model with multiple criteria and multiple constraint levels (MC²) is formulated by using the framework of MC² linear programming. An algorithm is developed to solve such MC² transportation problems. In this algorithm, the traditional northwest corner rule is adopted to find an initial basic feasible solution for a given MC² transportation problem. Then the MC²-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the supply and demand parameter for the MC² transportation problem. A numerical example is illustrated to demonstrate the applicability of the algorithm in solving the MC² transportation problems.     

Price-only contracts with backup supply

This paper studies a supply chain in which a manufacturer holds backup supply with extra cost to satisfy demand unmet by a retailer. We provide a simple threshold condition for when the manufacturer should hold backup supply. We also study how the backup supply affects the supply chain performance.     

Capacitated Multiple Item Ordering with Incremental Quantity Discounts

This paper presents a heuristic algorithm for determining order quantities for multiple items given incremental quantity discounts and a single resourse constraint. The heuristic is based on Lagrangian relaxation. The performance of the heuristic is compared, for small problems, with a procedure that generates optimal solutions. Results from computational experiments are given that demonstrate the quality and computational efficiency of the heuristic algorithm.     

Capacitated transportation problem with bounds on RIM conditions

Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory.     

Online facility location with facility movements

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than \({(\sqrt{13}+1)/4\approx 1.1514}\) exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.     

Assortment and inventory decisions with multiple quality levels

We consider the assortment and inventory decisions of a retailer under a locational consumer choice model where products can be differentiated both horizontally (e.g., color of a product) and vertically (e.g., quality of a product). The assortment and quantity decisions affect customer choice and, hence, the demand and sales for each product. In this paper, we investigate two different environments where product availability and assortment affect consumer choice and demand in different ways: make-to-order (MTO) and make-to-stock (MTS). In the MTO environment, customers order and purchase their most preferred product; that is, stockouts do not occur. In the MTS model, customers buy their most preferred product if it is in stock or do not buy if it is out of stock. In both environments we find conditions under which it is optimal to carry assortments of only a single quality level. In the MTS case, we show that an assortment of mixed quality levels can be optimal only within a narrow range of parameters.     

Reliability problems in multiple path-shaped facility location on networks

In this paper we study a location problem on networks that combines three important issues: (1) it considers that facilities are extensive, (2) it handles simultaneously the location of more than one facility, and (3) it incorporates reliability aspects related to the fact that facilities may fail. The problem consists of locating two path-shaped facilities minimizing the expected service cost in the long run, assuming that paths may become unavailable and their failure probabilities are known in advance. We discuss several aspects of the computational complexity of problems of locating two or more reliable paths on graphs, showing that multifacility path location–with and without reliability issues–is a difficult problem even for 2 facilities and on very special classes of graphs. In view of this, we focus on trees and provide a polynomial time algorithm that solves the 2 unreliable path location problem on tree networks in $O\left(n^2\right)$ time, where $n$ is the number of vertices.     

Mixture modeling of data with multiple partial right-censoring levels

Advances in Data Analysis and Classification - In this paper, a new flexible approach to modeling data with multiple partial right-censoring points is proposed. This method is based on finite...     

弱偏好序下带容量房屋匹配混合模型的机制设计

研究弱偏好序下, 带容量房屋市场混合模型(CHMTeT)的机制设计问题, 并针对该模型提出了一类算法机制, 该机制是TTC算法机制的推广, 称之为剔除筛选算法(简记为CTTC)机制. 此外, 证明了CHMTeT模型应用CTTC算法得到的这一类机制(即CTTC机制)满足个人理性、帕累托有效性和防策略操纵性, 并得出CTTC算法的时间复杂度为O(n_{1}^{2}\\(n_{1}n_{2}+n_{2}^{2})), 其中n_{1}为参与人数, n_{2}为房子数.     

遗传算法求解带容量限制的最小费用流问题

研究了带容量限制的带固定费用和可变费用的最小费用流问题,发现该问题是混合0-1整数规划问题,不存在多项式算法.在研究了最优解的结构后,结合最优解的结构特点为之设计了遗传算法,然后构造了一个100个节点的特殊网络,用计算机做了100例计算,验证了该算法具有很好的近似比和很快的收敛速度.