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.     

碳税政策下生产和销售的选址问题

本文考虑碳税政策下一个生产型企业生产和销售的选址问题。消费者分布在一条直线上,运输成本是线性的,企业除承担自身产品的运输费用外还承担消费者的运输成本。本文建立了利润最大化模型,分析了利润函数的性质,给出了求解方法。通过数值实验证明了求解方法的有效性,同时得出,即使消费者分布是中心对称的,最优的选址也不一定中心对称,这纠正了人们的错觉。增加碳税可使销售点靠近自己的消费者,增加企业的费用,但不一定起到减排的作用,只有通过灵活的碳税政策才有可能达到减排的目的。     

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.     

Environmentally friendly facility location with market competition

Many traditional facility location models assume spatial monopoly where market competition is ignored. Since facility locations affect the firm’s market exposure and subsequently its profit, accounting for the impact of the location decisions on customers while anticipating the reaction of competitor firms is essential. In this paper, we introduce a competitive facility location problem where market prices and production costs are determined through the economic equilibrium while explicitly considering competition from other firms. In order to accommodate for the growing efforts on limiting carbon emissions, the presented model includes constraints on the amount of carbon emissions that are due to transportation, while allowing carbon trading. The problem is formulated as a mixed integer non-linear model. Through numerical examples, we illustrate the effect of market competition on the location decisions and discuss the impact of emission limits and carbon trading on customers.     

Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities

We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the primary customers are served by a primary subtree that is embedded into the secondary subtree. In addition, besides fixed link installation costs, facility opening costs, associated to each node where primary and secondary subtree connect, have to be paid. The problem is called the Two Level Network Design Problem with Transition Facilities (TLNDF).     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

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.     

A dynamic inventory model with supplier selection in a serial supply chain structure

Considering the inherent connection between supplier selection and inventory management in supply chain networks, this article presents a multi-period inventory lot-sizing model for a single product in a serial supply chain, where raw materials are purchased from multiple suppliers at the first stage and external demand occurs at the last stage. The demand is known and may change from period to period. The stages of this production–distribution serial structure correspond to inventory locations. The first two stages stand for storage areas for raw materials and finished products in a manufacturing facility, and the remaining stages symbolize distribution centers or warehouses that take the product closer to customers. The problem is modeled as a time-expanded transshipment network, which is defined by the nodes and arcs that can be reached by feasible material flows. A mixed integer nonlinear programming model is developed to determine an optimal inventory policy that coordinates the transfer of materials between consecutive stages of the supply chain from period to period while properly placing purchasing orders to selected suppliers and satisfying customer demand on time. The proposed model minimizes the total variable cost, including purchasing, production, inventory, and transportation costs. The model can be linearized for certain types of cost structures. In addition, two continuous and concave approximations of the transportation cost function are provided to simplify the model and reduce its computational time.     

The \alpha -cost minimization model for capacitated facility location-allocation problem with uncertain demands

Facility location-allocation problem aims at determining the locations of some facilities to serve a set of spatially distributed customers and the allocation of each customer to the facilities such that the total transportation cost is minimized. In real life, the facility location-allocation problem often comes with uncertainty for lack of the information about the customers’ demands. Within the framework of uncertainty theory, this paper proposes an uncertain facility location-allocation model by means of chance-constraints, in which the customers’ demands are assumed to be uncertain variables. An equivalent crisp model is obtained via the \(\alpha \) -optimistic criterion of the total transportation cost. Besides, a hybrid intelligent algorithm is designed to solve the uncertain facility location-allocation problem, and its viability and effectiveness are illustrated by a numerical example.     

Characterization of facility assignment costs for a location-inventory model under truckload distribution

We consider a two-stage distribution system, where the first stage consists of potential distribution centres (DCs) and the second stage consists of geographically dispersed existing retailers. Our goal is to determine the set of open DCs and assignment of open DCs to retailers simultaneously with inventory decisions of retailers. In addition to the DC-specific fixed facility location costs, we explicitly model the inventory replenishment and holding costs at the retailers and truckload transportation costs between the DCs and the retailers. The transportation costs are subject to truck/cargo capacity, leading to an integrated location-inventory problem with explicit cargo costs. We develop a mixed-integer nonlinear model and analyse its structural properties leading to exact expressions for the so-called implied facility assignment costs and imputed per-unit per-mile transportation costs. These expressions analytically demonstrate the interplay between strategic location and tactical inventory/transportation decisions in terms of resulting operational costs. Although both the theory and practice of integrated logistics have recognized the fact that strategic and tactical decisions are interrelated, to the best of our knowledge, our paper is the first to offer closed-form results demonstrating the relationship explicitly. We propose an efficient solution approach utilizing the implied facility assignment costs and we demonstrate that significant savings are realizable when the inventory decisions and cargo costs are modelled explicitly for facility location purposes.     

Optimal pricing for service facilities with self-optimizing customers

Many service industries (e.g., walk-in clinics, vehicle inspection facilities, and data-processing centers) have customers who choose among congested facilities, and select the facility with the lowest combination of travel cost plus congestion cost at the facility. In general, customers over-utilize attractive facilities, causing higher costs than if customers were assigned to facilities to minimize total costs. Optimal facility prices induce customers to select facilities that minimize total cost. We find optimal facility prices and show they equal charging customers for the impact (net costs and benefits) they cause for others. We explore a rich flexibility that allows a range of optimal prices, useful when negotiating the implementation of facility fees. Facility prices can be positive or negative (price discounts), and can be adjusted to be all positive, or to provide net subsidy or net revenue. We contribute to unifying and generalizing several disparate streams of research.     

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

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

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

Free mobility and taste-homogeneity of jurisdiction structures

We consider a population of agents distributed on the unit interval. Agents form jurisdictions in order to provide a public facility and share its costs equally. This creates an incentive to form large entities. Individuals also incur a transportation cost depending on their location and that of the facility which makes small jurisdictions advantageous. We consider a fairly general class of distributions of agents and generalize previous versions of this model by allowing for non-linear transportation costs. We show that, in general, jurisdictions are not necessarily homogeneous. However, they are if facilities are always intraterritory and transportation costs are superadditive. Superadditivity can be weakened to strictly increasing and strictly concave when agents are uniformly distributed.     

Effective methods for a container packing operation

Since China started its economic reform, many Hong Kong companies have moved to China. While reducing labor costs, the move has also increased transportation costs. In some cases, transportation cost can reach 30% of total product cost.This work is based on the cargo loading operation of a Hong Kong manufacturer that uses standard containers to ship its products from China, and then onto its customers abroad. Its cargo loading problem is complicated by certain operational constraints. We present several heuristics to solve the problem. Computational tests on the company's actual data indicate an annual saving of over HK$3,000,000, which corresponds to 10.58% of the transportation cost. More importantly, our methods can change the management of the loading operation from the current experience-based system into a systematic, accurate, reliable, and efficient system.     

Minimizing the Total Cost in an Integrated Vendor—Managed Inventory System

In this paper we consider a complex production-distribution system, where a facility produces (or orders from an external supplier) several items which are distributed to a set of retailers by a fleet of vehicles. We consider Vendor-Managed Inventory (VMI) policies, in which the facility knows the inventory levels of the retailers and takes care of their replenishment policies. The production (or ordering) policy, the retailers replenishment policies and the transportation policy have to be determined so as to minimize the total system cost. The cost includes the fixed and variable production costs at the facility, the inventory costs at the facility and at the retailers and the transportation costs, that is the fixed costs of the vehicles and the traveling costs. We study two different types of VMI policies: The order-up-to level policy, in which the order-up-to level quantity is shipped to each retailer whenever served (i.e. the quantity delivered to each retailer is such that the maximum level of the inventory at the retailer is reached) and the fill-fill-dump policy, in which the order-up-to level quantity is shipped to all but the last retailer on each delivery route, while the quantity delivered to the last retailer is the minimum between the order-up-to level quantity and the residual transportation capacity of the vehicle. We propose two different decompositions of the problem and optimal or heuristic procedures for the solution of the subproblems. We show that, for reasonable initial values of the variables, the order in which the subproblems are solved does not influence the final solution. We will first solve the distribution subproblem and then the production subproblem. The computational results show that the fill-fill-dump policy reduces the average cost with respect to the order-up-to level policy and that one of the decompositions is more effective. Moreover, we compare the VMI policies with the more traditional Retailer-Managed Inventory (RMI) policy and show that the VMI policies significantly reduce the average cost with respect to the RMI policy.     

Last in line

Queueing is a common praxis in banks, hospitals and transportation, just to name a few. One common performance metric is the mean sojourn time. However, humans experience waiting time in a more complex manner — they dislike being the last in line. We study queueing systems subject to such a cost structure. For the single M/G/1 queue, we derive the corresponding mean costs, value functions and admission costs, which are then applied to route customers to parallel servers.     

Consolidation of customer orders into truckloads at a large manufacturer

We describe the development and operation of an interactive system based on a mathematical optimisation model which is used by a major US manufacturer to consolidate customer orders into truckloads. Dozens of users employ the system daily for planning delivery of orders from manufacturing plants to customers by truckload carriers, saving numerous hours of the users' time and reducing transportation costs.     

Location and allocation for distribution systems with transshipments and transportion economies of scale

Locating transshipment facilities and allocating origins and destinations to transshipment facilities are important decisions for many distribution and logistic systems. Models that treat demand as a continuous density over the service region often assume certain facility locations or a certain allocation of demand. It may be assumed that facility locations lie on a rectangular grid or that demand is allocated to the nearest facility or allocated such that each facility serves an equal amount of demand. These assumptions result in suboptimal distribution systems. This paper compares the transportation cost for suboptimal location and allocation schemes to the optimal cost to determine if suboptimal location and allocation schemes can produce nearly optimal transportation costs. Analytical results for distribution to a continuous demand show that nearly optimal costs can be achieved with suboptimal locations. An example of distribution to discrete demand points indicates the difficulties in applying these results to discrete demand problems.