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.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

Integrated production and allocation policies with one direct shipping option

We consider a single period inventory problem in which a supplier faces stochastic demands and customer specific waiting costs from multiple customers. The objective is to develop integrated production, allocation, and distribution policies so that the total production and customer waiting costs are minimized. We present an optimal policy for the two customer problem and derive a heuristic for a general problem based on the structural results of the two customer case. We show, numerically, that the heuristic performs very well with error bounds of less than 2% on average, while typical approximations may lead to significant sub-optimality.     

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.     

Optimal inventory threshold for a dynamic service make‐to‐stock system with strategic customers

We consider a make‐to‐stock production system with one product type, dynamic service policy, and delay‐sensitive customers. To balance the waiting cost of customers and holding cost of products, a dynamic production policy is adopted. If there is no customer waiting in the system, instead of shutting down, the system operates at a low production rate until a certain threshold of inventory is reached. If the inventory is empty and a new customer emerges, the system switches to a high production rate where the switching time is assumed to be exponentially distributed. Potential customers arrive according to the Poisson process. They are strategic in the sense that they make decisions on whether to stay for product or leave without purchase on the basis of on their utility value and the system information on whether the number of products is observable to customers or not. The strategic behavior is explored, and a Stackelberg game between production manager and customers is formulated where the former is the game leader. We find that the optimal inventory threshold minimizing the cost function can be obtained by a search algorithm. Numerical results demonstrate that the expected cost function in an observable case is not greater than that in an unobservable case. If a customer's delay sensitivity is relatively small, these two cases are entirely identical. With increasing of delay sensitivity, the optimal inventory threshold might be positive or zero, and hence, a demarcation line is depicted to determine when a make‐to‐stock policy is advantageous to the manager.     

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.     

Control policies for single-stage production systems with perishable inventory and customer impatience

We consider problems of inventory and admission control for make-to-stock production systems with perishable inventory and impatient customers. Customers may balk upon arrival (refuse to place orders) and renege while waiting (withdraw delayed orders) during stockouts. Item lifetimes and customer patience times are random variables with general distributions. Processing, setup, and customer inter-arrival times are however assumed to be exponential random variables. In particular, the paper studies two models. In the first model, the system suspends its production when its stock reaches a safety level and can resume later without incurring any setup delay or cost. In the second model, the system incurs setup delays and setup costs; during stockouts, all arriving customers are informed about anticipated delays and either balk or place their orders but cannot withdraw them later. Using results from the queueing literature, we derive expressions for the system steady-state probabilities and performance measures, such as profit from sales and costs of inventory, setups, and delays in filling customer orders. We use these expressions to find optimal inventory and admission policies, and investigate the impact of product lifetimes and customer patience times on system performance.     

考虑顾客退货和固定成本的联合补货与定价策略

为了吸引更多顾客,许多电子商务零售商允许顾客在一定时间内退货,导致其利润明显减少。同时,在补货时不仅产生依赖补货量的变动成本,而且会产生与补货量无关的固定成本。基于此,以最大化电子商务零售商的利润为目标,建立考虑顾客退货和固定成本的联合补货与定价模型,其中顾客的退货量与满足的需求呈正比。在一般需求情形下,部分刻画多期问题的最优策略;在特殊需求情形下,证明(s,S,p)策略对单期问题最优,并对多期问题的最优策略进行严格刻画。根据已有刻画为多期问题构造启发式策略。数值结果表明启发式策略近似最优;当初始库存水平足够高/低时,最优补货水平和定价随退货率与固定成本单调变化。关键词:联合补货与定价模型;顾客退货;固定成本;随机动态规划;最优策略     

Large scale stochastic inventory routing problems with?split delivery and service level constraints

A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, which determines delivery volumes to the customers that the depot serves in each period, and vehicle routes to deliver the volumes. This paper aims to solve a large scale multi-period SIRP with split delivery (SIRPSD) where a customer??s delivery in each period can be split and satisfied by multiple vehicle routes if necessary. This paper considers SIRPSD under the multi-criteria of the total inventory and transportation costs, and the service levels of customers. The total inventory and transportation cost is considered as the objective of the problem to minimize, while the service levels of the warehouses and the customers are satisfied by some imposed constraints and can be adjusted according to practical requests. In order to tackle the SIRPSD with notorious computational complexity, we first propose an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We then develop a hybrid approach that combines the linearization of nonlinear constraints, the decomposition of the model into sub-models with Lagrangian relaxation, and a partial linearization approach for a sub model. A near optimal solution of the model found by the approach is used to construct a near optimal solution of the SIRPSD. Randomly generated instances of the problem with up to 200 customers and 5 periods and about 400 thousands decision variables where half of them are integer are examined by numerical experiments. Our approach can obtain high quality near optimal solutions within a reasonable amount of computation time on an ordinary PC.     

A heuristic for BILP problems: The Single Source Capacitated Facility Location Problem

In the Single Source Capacitated Facility Location Problem (SSCFLP) each customer has to be assigned to one facility that supplies its whole demand. The total demand of customers assigned to each facility cannot exceed its capacity. An opening cost is associated with each facility, and is paid if at least one customer is assigned to it. The objective is to minimize the total cost of opening the facilities and supply all the customers. In this paper we extend the Kernel Search heuristic framework to general Binary Integer Linear Programming (BILP) problems, and apply it to the SSCFLP. The heuristic is based on the solution to optimality of a sequence of subproblems, where each subproblem is restricted to a subset of the decision variables. The subsets of decision variables are constructed starting from the optimal values of the linear relaxation. Variants based on variable fixing are proposed to improve the efficiency of the Kernel Search framework. The algorithms are tested on benchmark instances and new very large-scale test problems. Computational results demonstrate the effectiveness of the approach. The Kernel Search algorithm outperforms the best heuristics for the SSCFLP available in the literature. It found the optimal solution for 165 out of the 170 instances with a proven optimum. The error achieved in the remaining instances is negligible. Moreover, it achieved, on 100 new very large-scale instances, an average gap equal to 0.64% computed with respect to a lower bound or the optimum, when available. The variants based on variable fixing improved the efficiency of the algorithm with minor deteriorations of the solution quality.     

A simple greedy algorithm for a class of shuttle transportation problems

Greedy algorithms for combinatorial optimization problems are typically direct and efficient, but hard to prove optimality. The paper presents a special class of transportation problems where a supplier sends goods to a set of customers, returning to the source after each delivery. We show that these problems with different objective functions share a common structural property, and therefore a simple but powerful generic greedy algorithm yields optimal solutions for all of them.     

Production planning and pricing policy in a make-to-stock system with uncertain demand subject to machine breakdowns

We consider a make-to-stock system served by an unreliable machine that produces one type of product, which is sold to customers at one of two possible prices depending on the inventory level at the time when a customer arrives (i.e., the decision point). The system manager must determine the production level and selling price at each decision point. We first show that the optimal production and pricing policy is a threshold control, which is characterized by three threshold parameters under both the long-run discounted profit and long-run average profit criteria. We then establish the structural relationships among the three threshold parameters that production is off when inventory is above the threshold, and that the optimal selling price should be low when inventory is above the threshold under the scenario where the machine is down or up. Finally we provide some numerical examples to illustrate the analytical results and gain additional insights.     

一类多对多物流系统的运送频率选择优化问题研究

多供应商多客户物流系统的周期运送库存决策问题是一个非常复杂的问题,但它在供应链管理中又极其重要.本文主要考虑一个由多个供应商、一个联运中心和多个客户组成的三级物流系统的运送频率选择优化问题.假定两级库存均采用周期补货策略,且补货周期满足二次幂(POT)策略,每个客户处的产品需求为确定性需求.假设给定一套可行频率的情况下,选择使整个系统总的长期平均成本最小化的联运中心的补货策略和联运中心到各客户的配送策略.分为单频率配送和多频率配送两种情况分别建立了数学模型,并设计了相应的近似算法——基于支配性的邻域搜索启发式算法和基于饱和性的邻域搜索启发式算法.计算试验显示,本文所设计的近似算法对于求解多对多配送这样的大型组合优化问题是有效的.     

A GRASP for the biquadratic assignment problem

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). It is a nonlinear integer programming problem where the objective function is a fourth degree multivariable polynomial and the feasible domain is the assignment polytope. BiQAP problems appear in VLSI synthesis. Due to the difficulty of this problem, only heuristic solution approaches have been proposed. In this paper, we propose a new heuristic for the BiQAP, a greedy randomized adaptive search procedure (GRASP). Computational results on instances described in the literature indicate that this procedure consistently finds better solutions than previously described algorithms.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

Managing stochastic inventory systems with free shipping option

In many industries, customers are offered free shipping whenever an order placed exceeds a minimum quantity specified by suppliers. This allows the suppliers to achieve economies of scale in terms of production and distribution by encouraging customers to place large orders. In this paper, we consider the optimal policy of a retailer who operates a single-product inventory system under periodic review. The ordering cost of the retailer is a linear function of the ordering quantity, and the shipping cost is a fixed constant K whenever the order size is less than a given quantity – the free shipping quantity (FSQ), and it is zero whenever the order size is at least as much as the FSQ. Demands in different time periods are i.i.d. random variables. We provide the optimal inventory control policy and characterize its structural properties for the single-period model. For multi-period inventory systems, we propose and analyze a heuristic policy that has a simple structure, the (s, t, S) policy. Optimal parameters of the proposed heuristic policy are then computed. Through an extensive numerical study, we demonstrate that the heuristic policy is sufficiently accurate and close to optimal.     

Kernel search for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is among the most studied problems in the OR literature. Each customer demand has to be supplied by one or more facilities. Each facility cannot supply more than a given amount of product. The goal is to minimize the total cost to open the facilities and to serve all the customers. The problem is $\mathcal{NP}$ -hard. The Kernel Search is a heuristic framework based on the idea of identifying subsets of variables and in solving a sequence of MILP problems, each problem restricted to one of the identified subsets of variables. In this paper we enhance the Kernel Search and apply it to the solution of the CFLP. The heuristic is tested on a very large set of benchmark instances and the computational results confirm the effectiveness of the Kernel Search framework. The optimal solution has been found for all the instances whose optimal solution is known. Most of the best known solutions have been improved for those instances whose optimal solution is still unknown.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

Managing Dynamic Inventory Systems with Product Returns: A Markov Decision Process

This paper presents a Markov decision process for managing inventory systems with Markovian customer demand and Markovian product returns. Employing functional analysis, we prove the existence of the optimal replenishment policies for the discounted-cost and average-cost problems when demand, returns, and cost functions are of polynomial growth. Our model generalizes literature results by integrating Markovian demand, Markovian returns, and positive replenishment lead times. In particular, the optimality of the reorder point, order-up-to policies is proved when the order cost consists of fixed setup and proportional cost components and the inventory surplus cost is convex. We then make model extensions to include different cost components and to differentiate returned products from new ones. Finally, we derive managerial insights for running integrated closed-loop supply chains. At the aggregate level, returns reduce effective demand while many structural characteristics of inventory models are intact. A simple heuristic for managing systems with returns is to still utilize literature results without returns, but effective demand is lower than customer demand.