A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior

In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. The fundamental idea behind our dynamic programming decomposition method is to allocate the revenue associated with an itinerary among the different flight legs and to solve a single‐leg revenue management problem for each flight leg in the airline network. The novel aspect of our approach is that it chooses the revenue allocations by solving an auxiliary optimization problem that takes the probabilistic nature of the customer choices into consideration. We compare our approach with two standard benchmark methods. The first benchmark method uses a deterministic linear programming formulation. The second benchmark method is a dynamic programming decomposition idea that is similar to our approach, but it chooses the revenue allocations in an ad hoc manner. We establish that our approach provides an upper bound on the optimal total expected revenue, and this upper bound is tighter than the ones obtained by the two benchmark methods. Computational experiments indicate that our approach provides significant improvements over the performances of the benchmark methods.     

Decentralization in Linear Programming Models

This paper proposes a decomposition of a linear programming problem based on the structure of the optimal basis matrix. If this matrix contains a zero matrix of appropriate dimensions, the problem may be decomposed into a price-setting problem and a quantity-setting problem. This decomposition is valid for a set of coefficients of the problem to be determined by parametric programming. It can be applied to problems with common constraints or common variables. An application to dairy production planning is discussed and a comparison with the Dantzig-Wolfe decomposition principle is given.     

基于二阶段随机规划的城市医疗废弃物回收网络设计

城市医疗废弃物日益增加,且回收需求量受诸多因素的影响,难以准确预测,假定回收需求为确定值的医疗废弃物网络优化设计不能与实际需求相匹配。本文考虑了离散随机参数环境下,医疗回收网络设计中选址规划、分配计划及运输规划的协同优化问题,建立了以选址成本、运输成本最小为目标,设施与车辆能力限制为约束的二阶段随机规划模型。根据模型特点,设计了基于Benders decomposition的求解算法,同时,设计了一系列加速技术用于提高算法的求解效率。最后,以国内某城市医疗回收网络为背景设计算例,检验本文模型和求解策略的可行性和有效性。结果表明：相比确定性规划,随机规划的解能够节约总成本,结合一系列加速技术的Benders decomposition方法比CPLEX与纯的Benders decomposition更有优势。     

运输问题时间优化算法

运输问题是线性规划中的一类特殊问题。适用于求解目标函数符合线性叠加关系的费用或距离问题,对于实际运输问题中的运输时间优化问题则难以给出优化解。本文结合科研实践提出了运输问题中有关时间优化的迭代算法模型,此模型可给出整体运输时间最优的运输方案。通过实际检验证明,此算法简便、稳定、计算结果符合实际情况。     

Managing stochastic demand in an Inventory Routing Problem with transportation procurement

We study an Inventory Routing Problem in which the supplier has a limited production capacity and the stochastic demand of the retailers is satisfied with procurement of transportation services. The aim is to minimize the total expected cost over a planning horizon, given by the sum of the inventory cost at the supplier, the inventory cost at the retailers, the penalty cost for stock-out at the retailers and the transportation cost. First, we show that a policy based just on the average demand can have a total expected cost infinitely worse than the one obtained by taking into account the overall probability distribution of the demand in the decision process. Therefore, we introduce a stochastic dynamic programming formulation of the problem that allows us to find an optimal policy in small size instances. Finally, we design and implement a matheuristic approach, integrating a rollout algorithm and an optimal solution of mixed-integer linear programming models, which is able to solve realistic size problem instances. Computational results allow us to provide managerial insights concerning the management of stochastic demand.     

Multimodal hub location and hub network design

Through observations from real life hub networks, we introduce the multimodal hub location and hub network design problem. We approach the hub location problem from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub networks with different possible transportation modes must be designed. In this multimodal hub location and hub network design problem, we jointly consider transportation costs and travel times, which are studied separately in most hub location problems presented in the literature. We allow different transportation modes between hubs and different types of service time promises between origin–destination pairs while designing the hub network in the multimodal problem. We first propose a linear mixed integer programming model for this problem and then derive variants of the problem that might arise in certain applications. The models are enhanced via a set of effective valid inequalities and an efficient heuristic is developed. Computational analyses are presented on the various instances from the Turkish network and CAB data set.     

The total cost bounds of the transportation problem with varying demand and supply

A transportation problem is a linear programming problem based on a network structure consisting of a finite numbers of nodes and arcs attached to them. In real world applications, the supply and demand quantities in the transportation problem are sometimes hardly specified precisely because of changing economic conditions. This paper investigates the transportation problem when the demand and supply quantities are varying. A pair of mathematical programs is formulated to calculate the objective value. The derived result is also in range, where the total transportation cost would appear. In addition to allowing for simultaneous changes in supply and demand values, the total cost bounds are calculated directly. Due to the structure of the transportation problem, the largest total transportation cost may not occur at the highest total quantities shipped. Since the total cost bounds are derived, it would be beneficial to decision-making.     

Distribution planning of bulk lubricants at BP Turkey

We address the distribution planning problem of bulk lubricants at BP Turkey. The problem involves the distribution of different lube products from a single production plant to industrial customers using a heterogeneous fleet. The fleet consists of tank trucks where each tank can only be assigned to a single lube. The objective is to minimize total transportation related costs. The problem basically consists of assigning customer orders to the tanks of the trucks and determining the routes of the tank trucks simultaneously. We model this problem as a 0–1 mixed integer linear program. Since the model is intractable for real-life industrial environment we propose two heuristic approaches and investigate their performances. The first approach is a linear programming relaxation-based algorithm while the second is a rolling-horizon threshold heuristic. We propose two variants of the latter heuristic: the first uses a distance priority whereas the second has a due date priority. Our numerical analysis using company data shows that both variants of the rolling horizon threshold heuristic are able to provide good results fast.     

ON USING LINEAR PROGRAMMING IN DISCRIMINANT PROBLEMS

This commentary evaluates the usefulness of the Freed and Glover [6] linear programming approach to the discriminant problem, relates linear programming to other parametric and nonparametric approaches, and evaluates the linear programming approach.     

考虑长期运力合同的班轮收益管理运输路径优化模型

基于收益管理的方法,文章对随机需求环境下班轮运力分配和路径优化问题进行了定量研究。首先针对海运收益管理的特征,建立了考虑长期运力合同、空箱调运的轮运力分配和路径选择随机规划模型,然后应用稳健优化方法对此模型进行求解。最后,通过数值仿真得到了优化的舱位分配方案,比较发现稳健优化模型取得了较确定性规划模型更好的收益,显示了模型和方法对于集装箱海运企业的收益管理问题具有应用价值。     

PORTFOLIO MODELING IN MULTIPLE-CRITERIA SITUATIONS UNDER UNCERTAINTY: COMMENT

In a recent issue of Decision Sciences, Muhlemann, Lockett, and Gear [8] developed a multiple-objective, stochastic linear programming formulation of the multiperiod portfolio selection problem under uncertainty. The purpose of this note is to offer some extensions to their multicriteria approach which is otherwise viewed as an excellent attempt at modeling realistic aspects of the portfolio selection problem. Further, integer goal programming combined with simulation is suggested as an alternate approach for solving the dynamic multiple-objective problem.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

合理制定铁路客票价格的优化模型及算法

在充分考虑出行者和铁路客运部门两方面的利益情况下 ,提出一个双层规划模型以得到在多种交通方式竞争条件下的铁路客票价格制定的最优策略 .既保障了出行者使自己的广义出行费用最小 ,又能使铁路客运部门在运输市场竞争中取得的经济效益最大 .并且给出了求解该模型的 SAB算法。最后用一个简单的算例说明了模型及算法的应用     

MODIFIED STEPPING-STONE METHOD AS A TEACHING AID FOR CAPACITATED TRANSPORTATION PROBLEMS

This paper extends the standard stepping-stone method to the case of capacitated transportation problems. The purpose is to offer an alternative to network-oriented or simplex-based methods (such as the out-of-kilter and upper-bounding techniques) often used in handling the capacitated transportation problem but generally beyond the scope of introductory decision sciences courses. The proposed procedure is based on the simple stepping-stone method and requires only a few modifications in the cost/assignment matrix and some alterations in the pivoting rules. As such, it is much easier to understand and apply than the above-mentioned solution algorithms. It therefore can serve as an effective tool for teaching capacitated transportation problems. Two numerical examples illustrate applications of the proposed method, procedures for sensitivity analysis, and comparisons with linear programming.     

Simultaneous production and logistics operations planning in semicontinuous food industries

The production and logistics operations planning in real-life single- or multi-site semicontinuous food industries is addressed in this work. A discrete/continuous-time mixed integer programming model, based on the definition of families of products, is developed for the problem in question. A remarkable feature of the proposed approach is that in the production planning problem timing and sequencing decisions are taken for product families rather than for products. However, material balances are realized for every specific product, thus permitting the detailed optimization of production, inventory, and transportation costs. Changeovers are also explicitly taken into account and optimized. Moreover, alternative transportation modes are considered for the delivery of final products from production sites to distribution centers. The efficiency and the applicability of the proposed approach is demonstrated by solving to optimality two industrial-size case studies, for an emerging real-life Greek dairy industry.     

Coordinated Capacitated Lot‐Sizing Problem with Dynamic Demand: A Lagrangian Heuristic

Coordinated replenishment problems are common in manufacturing and distribution when a family of items shares a common production line, supplier, or a mode of transportation. In these situations the coordination of shared, and often limited, resources across items is economically attractive. This paper describes a mixed‐integer programming formulation and Lagrangian relaxation solution procedure for the single‐family coordinated capacitated lot‐sizing problem with dynamic demand. The problem extends both the multi‐item capacitated dynamic demand lot‐sizing problem and the uncapacitated coordinated dynamic demand lot‐sizing problem. We provide the results of computational experiments investigating the mathematical properties of the formulation and the performance of the Lagrangian procedures. The results indicate the superiority of the dual‐based heuristic over linear programming‐based approaches to the problem. The quality of the Lagrangian heuristic solution improved in most instances with increases in problem size. Heuristic solutions averaged 2.52% above optimal. The procedures were applied to an industry test problem yielding a 22.5% reduction in total costs.     

可变车道的道路交通网络设计优化方法

城市交通流的潮汐性特点造成上、下班高峰期内,道路资源利用的不合理现象:部分道路一个方向交通严重拥挤,而另一个方向几乎没有交通流量。为了合理利用道路资源,缓解交通拥挤,本文提出了双向流量不平衡道路的车道调整方法,并建立了离散双层规划模型,其中处于上层的交管部门通过调整双向道路的车道分配方案,使得整个城市交通网络的系统总阻抗最小。然后本文给出了该双层规划模型的混沌优化方法,最后以经典的SiouxFalls网络为例验证了本文所提方法的有效性。     

Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches.     

An integrated modelling approach for raw material management in a steel mill

An integrated modelling approach combining optimisation models with simulation is proposed for coordinated raw material management at steel works throughout the whole supply chain management process. The integrated model is composed of three components: ship scheduling, yard operation simulation and material blending models. The ship scheduling model determines which brands, how much and when they should be arrived, and the problem is modelled as mixed integer linear programming. The simulation model is used to simulate the whole processes from ships’ arrivals to the retrieval of the materials through the berthing and unloading the raw materials. Finally, the raw material blending model is developed for determining the brand and quantity of raw materials to be used. The proposed integrated modelling approach for raw material management has been successfully implemented and applied at steelwork to provide shipping schedules and predict future inventory levels at stock yards. By coordinating all the activities throughout the entire raw material supply chain management process, this article proposes an integrated approach to the problem and suggests a guideline by the appropriate simplification. The quantitative nature of the optimisation model and simulation facilitates an assessment of the risk factors in the supply chain, leading to an evaluation of a wide variety of scenarios and the development of multiple contingency plans. Further research is expected to supplement the ship scheduling models with heuristics for the idiosyncratic constraints of maritime transportation.     

Interactive fuzzy goal programming for multi-objective transportation problems

This paper presents an interactive fuzzy goal programming approach to determine the preferred compromise solution for the multi-objective transportation problem. The proposed approach considers the imprecise nature of the input data by implementing the minimum operator and also assumes that each objective function has a fuzzy goal. The approach focuses on minimizing the worst upper bound to obtain an efficient solution which is close to the best lower bound of each objective function. The solution procedure controls the search direction via updating both the membership values and the aspiration levels. An important characteristic of the approach is that the decision maker's role is concentrated only in evaluating the efficient solution to limit the influences of his/her incomplete knowledge about the problem domain. In addition, the proposed approach can be applied to solve other multi-objective decision making problems. The performance of this solution approach is evaluated by comparing its results with that of the two existing methods in the literature.