Fix and Relax Heuristic for a Stochastic Lot-Sizing Problem

This paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the problem. The computational experiments carried out on a large set of instances have shown that the approach provides good quality solutions in a reasonable amount of time.     

Convex duality for finite-fuel problems in singular stochastic control

Upon introducing a finite-fuel constraint in a stochastic control system, the convex duality formulation can be set up to represent the original singular control problem as a minimization problem over the space of vector measures at each level of available fuel. This minimization problem is imbedded tightly into a related weak problem, which is actually a mathematical programming problem over a convex,w*-compact space of vector-valued Radon measures. Then, through the Fenchel duality principle, the dual for the finite-fuel control problems is to seek the maximum of smooth subsolutions to a dynamic programming variational inequality. The approach is basically in the spirit of Fleming and Vermes, and the results of this paper extend those of Vinter and Lewis in deterministic control problems to the finite-fuel problems in singular stochastic control. Meanwhile, we also obtain the characterization of the value function as a solution to the dynamic programming variational inequality in the sense of the Schwartz distribution.The author is much indebted to Professor Wendell H. Fleming for his constant support and many helpful discussions during the preparation of this paper.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

Stochastic linear knapsack programming problem and its application to a portfolio selection problem

In this paper a probability maximization model of a stochastic linear knapsack problem is considered where the random variables consist of several groups with mutually correlated ones. We propose a solution algorithm to the equivalent nonlinear fractional programming problem with a simple ranking method. This approach will be effectively applied to one of the portfolio selection problems.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

A stochastic dynamic traveling salesman problem with hard time windows

Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

求解硬时间窗约束下随机需求库存-路径问题的优化算法

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem, SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows, SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。     

Algorithm for minimizing weighted earliness penalty in single-machine problem

In this paper, the problem of minimizing the weighted earliness penalty in a single-machine scheduling problem is addressed. For this problem, every job is assumed to be available at time zero and must be completed before or on its deadline. No tardy job is allowed. Each job has its own earliness penalty and deadline. The paper identifies several local optimality conditions for sequencing of adjacent jobs. A heuristic algorithm is developed based on these local optimality conditions. Sample problems are solved and the solutions obtained from the heuristic are compared to solutions obtained from the heuristics developed by Chand and Schneeberger. Also, comparisons are performed between the solutions obtained from the heuristic and the optimal solutions obtained from a mathematical modeling approach for problems involving 10 and 15 jobs. The results show that the developed heuristic produces solutions close to optimal in small size problems, and it also outperforms the Chand and Schneeberger's method.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

带冲突关系装箱问题的启发式求解算法

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。     

Adaptive dynamic cost updating procedure for solving fixed charge network flow problems

We approximate the objective function of the fixed charge network flow problem (FCNF) by a piecewise linear one, and construct a concave piecewise linear network flow problem (CPLNF). A proper choice of parameters in the CPLNF problem guarantees the equivalence between those two problems. We propose a heuristic algorithm for solving the FCNF problem, which requires solving a sequence of CPLNF problems. The algorithm employs the dynamic cost updating procedure (DCUP) to find a solution to the CPLNF problems. Preliminary numerical experiments show the effectiveness of the proposed algorithm. In particular, it provides a better solution than the dynamic slope scaling procedure in less CPU time. Research was partially supported by NSF and Air Force grants.     

A Solution Method for a Two-dispatch Delivery Problem with Stochastic Customers

We study a vehicle routing problem in which vehicles are dispatched multiple times a day for product delivery. In this problem, some customer orders are known in advance while others are uncertain but are progressively realized during the day. The key decisions include determining which known orders should be delivered in the first dispatch and which should be delivered in a later dispatch, and finding the routes and schedules for customer orders. This problem is formulated as a two-stage stochastic programming problem with the objective of minimizing the expected total cost. A worst-case analysis is performed to evaluate the potential benefit of the stochastic approach against a deterministic approach. Furthermore, a sample-based heuristic is proposed. Computational experiments are conducted to assess the effectiveness of the model and the heuristic.      

The continuity of the optimum in parametric programming and applications to stochastic programming

It is proved a sufficient condition that the optimal value of a linear program be a continuous function of the coefficients. The condition isessential, in the sense that, if it is not imposed, then examples with discontinuous optimal-value function may be found. It is shown that certain classes of linear programs important in applications satisfy this condition. Using the relation between parametric linear programming and the distribution problem in stochastic programming, a necessary and sufficient condition is given that such a program has optimal value. Stable stochastic linear programs are introduced, and a sufficient condition of such stability, important in computation problems, is established.This note is a slightly modified version of a paper presented at the Institute of Econometrics and Operations Research of the University of Bonn, Bonn, Germany, 1972.The author is grateful to G. B. Dantzig and S. Karamardian for useful comments on an earlier draft of this paper. In particular, S. Karamardian proposed modifications which made clearer the proof of Lemma 2.1.     

抽象经济均衡问题解的存在性及其算法

本文首先研究一类新的向量均衡问题,利用截口定理与KKM定理两种不同的工具证明此类均衡问题解的存在性,接着,把这类向量均衡问题推广到更为一般的情形,随后讨论了具有上下界的均衡问题,它是由Isac,Sehgal和Singh于1999年提出的一个公开问题,本文在一定条件下获得了一个新的解的存在性定理,并构造了一个迭代算法,讨论了算法的收敛性。     

Receiver set partitioning and sequencing for multicasting traffic in a WDM lightwave single-hop network

This paper considers a receiver set partitioning and sequencing problem in a wavelength division multiplexing single-hop lightwave network for multicasting traffic. The problem is analysed in the approach of uncapacitated single batch-processing machine scheduling. In the analysis, several solution properties are characterized with respect to a mean flow time measure, based upon which two heuristic algorithms are developed, along with a dynamic programming algorithm. Several numerical experiments show that the heuristic algorithms generate good schedules. The problem is extended to consider two measures simultaneously including the mean flow time and the number of transmissions, for which the proposed algorithms also perform well.     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.