Computationally Efficient Solution of a Multiproduct,Two-Stage Distribution—Location Problem

A two-stage distribution planning problem, in which customers are to be served with different commodities from a number of plants, through a number of intermediate warehouses is addressed. The possible locations for the warehouses are given. For each location, there is an associated fixed cost for opening the warehouse concerned, as well as an operating cost and a maximum capacity. The demand of each customer for each commodity is known, as are the shipping costs from a plant to a possible warehouse and thereafter to a customer. It is required to choose the locations for opening warehouses and to find the shipping schedule such that the total cost is minimized. The problem is modelled as a mixed-integer programming problem and solved by branch and bound. The lower bounds are calculated through solving a minimum-cost, multicommodity network flow problem with capacity constraints. Results of extensive computational experiments are given.     

Optimal model for warehouse location and retailer allocation

Warehouse location and retailer allocation is a high‐level strategic decision problem that is commonly encountered by logisticians and supply chain managers, especially during the supply chain design phase. Considering the product distribution cost and warehouse capital cost trade‐offs, this paper models the warehouse location and retailer allocation problem as a 0–1 integer programming problem and provides an efficient two‐stage set covering heuristic algorithm to solve large‐sized problems. Finally, concluding remarks and some recommendations for further research are also presented. Copyright © 2007 John Wiley & Sons, Ltd.     

Capacity allocation problem with random demands for the rail container carrier

In this paper, we consider the formulation and heuristic algorithm for the capacity allocation problem with random demands in the rail container transportation. The problem is formulated as the stochastic integer programming model taking into account matches in supply and demand of rail container transportation. A heuristic algorithm for the stochastic integer programming model is proposed. The solution to the model is found by maximizing the expected total profit over the possible control decisions under the uncertainty of demands. Finally, we give numerical experiments to demonstrate the efficiency of the heuristic algorithm.     

Solution procedures for sizing of warehouses

In the past, researchers presented a linear programming formulation for the economic sizing of warehouses when demand is highly seasonal and public warehouse space is available on a monthly basis. The static model was extended for the dynamic sizing problem in which the warehouse size is allowed to change over time. By applying simplex routine, the optimal size of the warehouse to be constructed could be determined. In this paper, an alternative and simple method of arriving at an optimal solution for the static problem is given. Three extensions of the static model are given. These extensions involve costs varying over time, economies of scale in capital expenditure and/or operating cost and stochastic version. The dynamic warehouse sizing problem is shown to be a network flow problem which could be solved by using network flow algorithms. The structure of an optimal solution is also given. The concave cost version of the dynamic warehouse sizing problem is also discussed and it is shown that this problem can be solved efficiently using dynamic programming.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Optimal Operations Management and Network Planning of a District Heating System with a Combined Heat and Power Plant

District heating plants are becoming more common in European cities. These systems make it possible to furnish users with warm water while locating the production plants in the outskirts having the double benefit of lowering the impact of pollution on the center of the city and achieving better conversion performances. In order to amortize the costs throughout the year, the system often includes a combined heat and power (CHP) plant, to exploit the energy during the summer as well, when the demand for warm water decreases. A linear programming model for the optimal resource management of such a plant is presented and some results for a real case are reported. A distribution network design problem is also addressed and solved by means of mixed integer linear programming.     

An efficient heuristic approach for a multi-period logistics network redesign problem

In this paper, a multi-period logistics network redesign problem arising in the context of strategic supply chain planning is studied. Several aspects of practical relevance are captured, namely, multiple echelons with different types of facilities, product flows between facilities in the same echelon, direct shipments to customers, and facility relocation. A two-phase heuristic approach is proposed to obtain high-quality feasible solutions to the problem, which is initially modeled as a large-scale mixed-integer linear program. In the first phase of the heuristic, a linear programming rounding strategy is applied to find initial values for the binary location variables. The second phase of the heuristic uses local search to correct the initial variable choices when a feasible solution is not identified, or to improve the initial feasible solution when its quality does not meet given criteria. The results of a computational study are reported for randomly generated instances comprising a variety of logistics networks.     

After-sales services network design of a household appliances manufacturer

After-sales services have become high-margin businesses that account for larger portions of corporate profits. Delivering the after-sales services is challenging as after-sales services supply chains are significantly different than production–distribution supply chains. The literature provides little guidance on the use of quantitative methods for after-sales services network design. We present a mixed integer linear programming problem formulation to determine warehouse locations, assign repair vendors to facilities and choose mode of transportation while minimizing the total network cost. We transform the large-scale real-life problem of a household appliances manufacturer into a smaller scale to solve optimally in reasonable time. Through a scenario-based approach, we evaluate different configurations of a decentralized network with choices of transportation mode. We test the sensitivity of the solutions. The total cost decreases with additional choices of transportation mode and only slightly increases with the next-day delivery policy while the network solution may change significantly.     

基于航段需求计算网络竞价的近似动态规划方法

竞价控制是收益管理中广泛应用的一种存量控制方法.将网络存量控制问题描述为一个动态规划模型,通过状态向量的一个仿射函数近似动态规划的最优值函数,并且在航段水平上考虑随机需求,最终得到一个计算网络竞价所需的确定性线性规划(DLP),相对于标准的DLP,这个DLP得到了更接近于动态规划最优值的上界.给出了一个列生成算法用于求解这个DLP,并提供了模拟算例,计算结果表明可获得比标准的DLP方法更好的收益.     

Charging scheduling problem of an M-to-N electric vehicle charger

This study investigates a real case of charging scheduling of an electric vehicle charger with multiple ports called M-to-N charger. The charger is designed for a multi-unit dwelling facility and can charge N electric vehicles simultaneously despite the supplied charging capacity being limited to only M electric vehicles. The electric vehicles arrive at the charger randomly and stay for their desired length of time, during which they must be charged as much as possible with minimum electric cost. The scheduling problem considers four objectives: maximizing the total charging amount, minimizing the total charging cost, minimizing the charging completion time, and maximizing the charging balance among the electric vehicles. A mixed-integer linear programming model and a relaxation-based heuristic algorithm are developed. Computational experiment results show that the proposed heuristic algorithm can generate schedules within 8 s for this case study by using an open-source linear programming solver. Compared with the mixed-integer programming algorithm, the proposed heuristic algorithm can provide solutions with less than 7% charging amount gap and 4% price gap. The proposed heuristic algorithm is successfully implemented in a real M-to-N charger.     

A two-phase heuristic approach to the bike repositioning problem

An approach to overcome the bike imbalance problem is to transfer excess bikes to branches with bike shortages. This study develops a constrained mathematical model to deal with a multi-vehicle bike-repositioning problem, and aims to minimize the sum of transportation and unmet demand costs over a planning horizon through bike-transfer strategies under a minimum service requirement. A two-phase heuristic based on linear programming was proposed to solve the problem and produce compromising solutions. In the first phase, the paper developed a linear programming model to quickly develop decisions related to bike inventory, unloading, and loading for all stations for each time slot. In the second phase, this paper proposed an iterative approach through two parameter sensitive mathematical models to sequentially reduce the problem scale to develop decisions related to bike transfers. Computational results show that the proposed approach is superior to a CPLEX optimizer and a hybrid heuristic based on a genetic algorithm. The proposed approach was used to analyze the bicycle system in Taiwan. The impacts of various system parameters on the system were also investigated.     

A two-echelon inventory model for a deteriorating item with stock-dependent demand,partial backlogging and capacity constraints

This study investigates a two-echelon supply chain model for deteriorating inventory in which the retailer’s warehouse has a limited capacity. The system includes one wholesaler and one retailer and aims to minimise the total cost. The demand rate in retailer is stock-dependent and in case of any shortages, the demand is partially backlogged. The warehouse capacity in the retailer (OW) is limited; therefore the retailer can rent a warehouse (RW) if needed with a higher cost compared to OW. The optimisation is done from both the wholesaler’s and retailer’s perspectives simultaneously. In order to solve the problem a genetic algorithm is devised. After developing a heuristic a numerical example together with sensitivity analysis are presented. Finally, some recommendations for future research are presented.     

The EOQ problem with decidable warehouse capacity: Analysis, solution approaches and applications

The Economic Order Quantity (EOQ) problem is a fundamental problem in supply and inventory management. In its classical setting, solutions are not affected by the warehouse capacity. We study a type of EOQ problem where the (maximum) warehouse capacity is a decision variable. Furthermore, we assume that the warehouse cost dominates all the other inventory holding costs. We call this the EOQ-Max problem and the D-EOQ-Max problem, if the product is continuously divisible and discrete, respectively. The EOQ-Max problem admits a closed form optimal solution, while the D-EOQ-Max problem does not because its objective function may have several local minima. We present an optimal polynomial time algorithm for the discrete problem. Construction of this algorithm is supported by the fact that continuous relaxation of the D-EOQ-Max problem provides a solution that can be up to 50% worse than the optimal solution, and this worst-case error bound is tight. Applications of the D-EOQ-Max problem include supply and inventory management, logistics and scheduling.     

Application of Mathematical Programming to a Large-scale Agricultural Production and Distribution System

This paper addresses an actual production planning problem for a large seed corn production company. Various scenarios are included in different mathematical programming models in order to help the management make production decisions. A linear programming package and a mixed-integer programming package are combined by a designed heuristic program to solve the problem. The solutions obtained and an accompanying sensitivity analysis provide the management with insight into the system's operation and potentials of cost savings.     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

Another heuristic for minimizing total average cycle stock subject to practical constraints

This paper considers the setting of reorder intervals of a population of items for minimizing the total average cycle stock subject to a limit on the total number of replenishments per unit time, and a restricted set of possible intervals. Silver and Moon have investigated the problem with the use of dynamic programming, and they also proposed a heuristic for solving it. This paper presents a new 0-1 linear programming approach to the problem. Based upon the solution of the relaxed 0-1 linear programming formulation, a simple heuristic is proposed to solve the reorder problem. Limited numerical results using realistic test examples indicate that the new heuristic performed very well for each example.     

Different Approaches to Advertising Media Selection

Research groups on both sides of the Atlantic are attempting to use the power of mathematics to aid the decision-maker in dealing with the complex media scheduling problem. This paper reviews, compares and critiques several possible approaches. The approaches reviewed are: linear programming, dynamic programming, marginal analysis, heuristic programming and simulation. At least one particular model of each approach is discussed in detail.     

A two-echelon inventory system with transportation capacity constraint

Consider a one-warehouse multi-retailer system under constant and deterministic demand, which is subjected to transportation capacity for every delivery period. To search for the best stationary zero inventory ordering (ZIO) policy, or the best power-of-two policy, or the best nested policy, the problem is formulated as a 0–1 integer linear program in which the objective function comprises of a fixed transportation cost whenever a delivery is made and the inventory costs for both the warehouse and retailers. To overcome the transportation capacity limitation, we extend the policies to allow for staggering deliveries. It is shown that with transportation capacity constraint the non-staggering policy can have its effectiveness close to 0% from the best staggering policy and the power-of-two policy with staggering allowed can have its effectiveness close to 0% from the optimal policy. Nevertheless in general, the power-of-two policy fairs well on a number of randomly generated problems. To solve the large distribution network problem, an efficient heuristic based on the power-of-two policy with staggering of deliveries is suggested.     

The warehouse-inventory-transportation problem for supply chains

Warehouses play a vital role in mitigating variations in supply and demand, and in providing value-added services in a supply chain. However, our observation of supply chain practice reveals that warehousing decisions are not included when developing a distribution plan for the supply chain. This lack of integration has resulted in a substantial variation in workload (42–220%) at our industry partner’s warehouse costing them millions of dollars. To address this real-world challenge, we introduce the warehouse-inventory-transportation problem (WITP) of determining an optimal distribution plan from vendors to customers via one or more warehouses in order to minimize the total distribution cost. We present a nonlinear integer programming model for the WITP considering supply chains with multiple vendors, stores, products, and time-periods, and one warehouse. The model also considers worker congestion at the warehouse that could affect worker productivity. A heuristic based on iterative local search is developed to solve industry-sized problems with up to 500 stores and 1000 products. Our experiments indicate that the distribution plans obtained via the WITP, as compared to a sequential approach, result in a substantial reduction in workload variance at the warehouse, while considerably reducing the total distribution cost. These plans, however, are sensitive to aisle configuration and technology at the warehouse, and the level and productivity of temporary workers.     

Connectivity-and-hop-constrained design of electricity distribution networks

This paper addresses the problem of designing the configuration of an interconnected electricity distribution network, so as to maximize the minimum power margin over the feeders. In addition to the limitation of feeder power capacity, the distance (as hop count) between any customer and its allocated feeder is also limited for preventing power losses and voltage drops. Feasibility conditions are studied and a complexity analysis is performed before introducing a heuristic algorithm and two integer linear programming formulations for addressing the problem. A cutting-plane algorithm relying on the generation of two classes of cuts for enforcing connectivity and distance requirements respectively is proposed for solving the second integer linear programming formulation. All the approaches are then compared on a set of 190 instances before discussing their performances.