The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

Warehouse location with production,inventory, and distribution decisions: a case study in the lube oil industry

In this paper, a supply chain management problem from a real case study is modeled and solved. A company in Pakistan wanted to outsource part of its warehousing activity to a third party logistics (3PL) provider. Consequently, the company had to decide on where to rent space in the 3PL warehouses. Knowing that such a strategic decision is affected by tactical and operational decisions, the problem is presented as a facility location problem integrating production, inventory, and distribution decisions. The problem is formulated as a mixed integer linear programming model which minimizes the total cost composed of location, distribution, production, and inventory costs. Several constraints specific to the situation and policy of the company were considered. A thorough analysis was done on the results obtained with respect to formulation efficiency, sensitivity analysis, and distribution of costs. In addition to the solution of the company problem, a set of 1215 problem instances was generated by varying five types of relevant costs in a full factorial manner. The solution of the generated problems always suggests to open in the same two locations and the integrality gaps averaged 0.062 % with a maximum of 0.102 %. On average, the major components of the total cost are production cost (96.6 %), transportation costs (2.7 %), and inventory holding costs (0.38 %). The total warehouse opening cost accounted for less than 0.05 % of the total costs.     

Sustainable SC through the complete reprocessing of end-of-life products by manufacturers: A traditional versus social responsibility company perspective

Every item produced, transported, used and discarded within a Supply Chain (SC) generates costs and creates an impact on the environment. The increase of forward flows as effects of market globalization and reverse flows due to legislation, warranty, recycling and disposal activities affect the ability of a modern SC to be economically and environmentally sustainable. In this context, the study considers an innovative sustainable closed loop SC problem. It first introduces a linear programming model that aims to minimize the total SC costs. Environmental sustainability is guaranteed by the complete reprocessing of an end-of-life product, the re-use of components, the disposal of unusable parts sent directly from the manufacturers, with a closed loop transportation system that maximizes transportation efficiency. Secondly, the authors consider the problem by means of a parametrical study, by analyzing the economical sustainability of the proposed CLSC model versus the classical Forward Supply Chain model (FWSC) from two perspectives: Case 1, the ‘traditional company perspective’, where the SC ends at the customers, and the disposal costs are not included in the SC, and Case 2, the ‘social responsibility company perspective’, where the disposal costs are considered within the SC. The relative impact of the different variables in the SC structure and the applicability of the proposed model, in terms of total costs, SC structure and social responsibility, are investigated thoroughly and the results are reported at the conclusion of the paper.     

Location-allocation on a line with demand-dependent costs

This paper extends the location-allocation formulation by making the cost charged to users by a facility a function of the total number of users patronizing the facility. Users select their facility based on facility charges and transportation costs. We explore equilibria where each customer selects the least expensive facility (cost and transportation) and where the facility is at a point that minimizes travel costs for its customers. The problem in its general form is quite complex. An interesting special case is studied: facilities and customers are located on a finite line segment and demand is distributed on the line by a given density function.     

The plant location problem with demand-dependent setup costs and centralized allocation

Suppose that customers are situated at the nodes of a transportation network, and a service company plans to locate a number of facilities that will serve the customers. The objective is to minimize the sum of the total setup cost and the total transportation cost. The setup cost of a facility is demand-dependent, that is, it depends on the number of customers that are served by the facility. Centralized allocation of customers to facilities is assumed, that is, the service company makes a decision about allocation of customers to facilities. In the case of a general network, the model can be formulated as a mixed integer programming problem. For the case of a tree network, we develop a polynomial-time dynamic programming algorithm.     

Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.     

Optimal pricing,EOL (end of life) warranty,and spare parts manufacturing strategy amid product transition

We study firm’s strategy to determine its product price and warranty period, and plan the spare parts manufacturing so as to maximize its profit and at the same time to fulfill its commitment to providing the customer with the key part continuously over the relevant decision time horizon, i.e., the product’s life cycle plus its EOL service (warranty) period. To examine the research question, we develop and solve a two-stage optimal control theory model. From the numerical analysis, we infer as follows. It is not always true that the longer the EOL warranty period, the better for the company’s profitability, implying there exists an optimal EOL warranty period that balances all the relevant forces like market demand and cost structures. The relationship between optimal EOL warranty period and failure rate (defect rate) is concave: when the defect rate is moderate, the company has to increase its EOL warranty period as the defect rate increases so as to compensate for the deteriorating quality; but, when the defect rate is beyond a threshold level, the company needs to curtail its EOL warranty commitment as the defect rate increases in order to avoid excessive cost to service the failed parts. By depicting key dynamics in this managerial problem, this paper sheds light on how to make decision for optimal pricing and warranty when the product life cycle is finite and the company is obliged to provide after-sales services to customers for an extended period of time after the current product is no longer produced.     

Multi-source facility location–allocation and inventory problem

We consider a joint facility location–allocation and inventory problem that incorporates multiple sources of warehouses. The problem is motivated by a real situation faced by a multinational applied chemistry company. In this problem, multiple products are produced in several plants. Warehouse can be replenished by several plants together because of capabilities and capacities of plants. Each customer in this problem has stochastic demand and certain amount of safety stock must be maintained in warehouses so as to achieve certain customer service level. The problem is to determine number and locations of warehouses, allocation of customers demand and inventory levels of warehouses. The objective is to minimize the expected total cost with the satisfaction of desired demand weighted average customer lead time and desired cycle service level. The problem is formulated as a mixed integer nonlinear programming model. Utilizing approximation and transformation techniques, we develop an iterative heuristic method for the problem. An experiment study shows that the proposed procedure performs well in comparison with a lower bound.     

Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs

We consider two linear project time–cost tradeoff problems with multiple milestones. Unless a milestone is completed on time, penalty costs for tardiness may be imposed. However, these penalty costs can be avoided by compressing the processing times of certain jobs that require additional resources or costs. Our model describes these penalty costs as the total weighted number of tardy milestone. The first problem tries to minimize the total weighted number of tardy milestones within the budget for total compression costs, while the second problem tries to minimize the total weighted number of tardy milestones plus total compression costs. We develop a linear programming formulation for the case with a fixed number of milestones. For the case with an arbitrary number of milestones, we show that under completely ordered jobs, the first problem is NP-hard in the ordinary sense while the second problem is polynomially solvable.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

Analysis of an industrial component commonality problem

We discuss a case study of an industrial production-marketing coordination problem involving component commonality. For the product line considered, the strategic goal of the company is to move from the current low volume market to a high volume market. The marketing department believes that this can be achieved by substantially lowering the end products’ prices. However, this requires a product redesign to lower production costs in order to maintain profit margins. The redesign decision involves grouping end products into families. All products within one family use the same version of some components. This paper fits in the stream of recent literature on component commonality where the focus has shifted from inventory cost savings to production and development cost savings. Further, we consider both costs and revenues, leading to a profit maximization approach. The price elasticity of demand determines the relationship between the price level and number of units sold. Consequently, we integrate information from different functional areas such as production, marketing and accounting. We formulate the problem as a net-present-value investment decision. We propose a mixed integer nonlinear optimization model to find the optimal commonality decision. The recommendation based on our analysis has been implemented in the company. In addition, the application allows us to experimentally validate some claims made in the literature and obtain managerial insights into the trade-offs.     

Speciality oils supply chain optimization: From a decoupled to an integrated planning approach

We study a problem of tactical planning in a divergent supply chain. It involves decisions regarding production, inventory, internal transportation, sales and distribution to customers. The problem is motivated by the context of a company in the speciality oils industry. The overall objective at tactical level is to maximize contribution and, in order to achieve this, the planning has been divided into two separate problems. The first problem concerns sales where the final sales and distribution planning is decentralized to individual sellers. The second problem concerns production, transportation and inventory planning through refineries, hubs and depots and is managed centrally with the aim of minimizing costs. Due to this decoupling, the solution of the two problems needs to be coordinated in order to achieve the overall objective. In the company, this is pursued through an internal price system aiming at giving the sellers the incentives needed to align their decisions with the overall objective. We propose and discuss linear programming models for the decoupled and integrated planning problems. We present numerical examples to illustrate potential effects of integration and coordination and discuss the advantages and disadvantages of the integrated over the decoupled approach. While the total contribution is higher in the integrated approach, it has also been found that the sellers’ contribution can be considerably lower. Therefore, we also suggest contribution sharing rules to achieve a solution where both the company and the sellers attain a better outcome under the integrated planning.     

Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network

This paper addresses a generalization of the capacitated location-routing problem (CLRP) arising in the design of a collection network for a company engaged in collecting used products from customer zones. The company offers customers a financial incentive per unit of used products. This incentive determines the quantity of used products which are returned by customers. Moreover, it is not necessary for the company to visit all customer zones or to collect all returns in each visited customer zone. The objective is to simultaneously find the location of collection centers, the routes of vehicles, the value of incentive offered and the amount of used products collected from customer zones, so as to maximize the company's overall profit. We develop two mixed integer linear programming formulations of the problem and a heuristic algorithm based on iterated local search. Extensive computational experiments on this problem demonstrate the effectiveness of the proposed algorithm.     

A MIP-based slicing heuristic for three-dimensional bin packing

The mixed-case palletization problem is a common problem in warehousing and logistics where boxes of rectangular shapes are stacked on top of each other to form pallets. The problem shares common features with three-dimensional bin packing but requires boxes to be adequately supported. We propose a mixed integer programming formulation that maximizes the density of the bottom layers and the compactness of the pallet to ensure stability for top layers. We use a relative-position formulation with slicing that minimizes height, maximizes the fill rate of slices, and pushes boxes towards the vertical axis in order to consolidate fragmented space. Apart from common non-overlap and dimension-related constraints, we explicitly model the fill rates and force lower slices to have an equal or higher density than upper slices. As expected, the formulation could only handle small instances. To tackle larger instances, we embedded the formulation in an iterative approach that packs subsets of boxes sequentially. The approach was found to provide stable pallets and to outperform the branch-and-bound approach of Martello et al. (Oper Res 48(2):256–267, 2000).     

On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

Lower bounds for the two-stage uncapacitated facility location problem

In the two-stage uncapacitated facility location problem, a set of customers is served from a set of depots which receives the product from a set of plants. If a plant or depot serves a product, a fixed cost must be paid, and there are different transportation costs between plants and depots, and depots and customers. The objective is to locate plants and depots, given both sets of potential locations, such that each customer is served and the total cost is as minimal as possible. In this paper, we present a mixed integer formulation based on twice-indexed transportation variables, and perform an analysis of several Lagrangian relaxations which are obtained from it, trying to determine good lower bounds on its optimal value. Computational results are also presented which support the theoretical potential of one of the relaxations.     

A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company that provides preventive maintenance services to a set of customers using a fleet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visited each day and the routes followed by the gangs. The objective is to provide improved customer service at minimum operating cost subject to constraints on frequency of visits, service time requirements, customer preferences for visiting on particular days and other routing constraints. The problem is solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The computational implementation of the complete planning model is described with reference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem

We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ringʼs customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm.     

Comparison of policies in dynamic routing problems

We consider a company that has to satisfy customers' pick-up requests arriving over time every day. The overall objective of the company is to serve as many requests as possible at a minimum operational cost. When organizing its business the company has to fix some features of the service that may affect both service quality and operational costs. Some of these features concern the time a request is taken into account to plan its service, the associated deadline and the way requests are managed when the system is overloaded. In this paper we analyse several policies that can be implemented by the management of a carrier company in a multi-period context. For example, a company might reject all the requests that cannot be feasibly scheduled or accept all the requests and rely on a backup service in order to serve requests that are difficult to handle. Another interesting issue considered in this paper is the impact of collaborative service where two or more carrier companies, with their own customers, decide to share customers in order to optimize the overall costs. We set up a general framework to allow comparison of alternative service policies. Extensive computational results evaluating the number of lost requests and the distance travelled provide interesting insights.