Approximate dynamic programming for the aeromedical evacuation dispatching problem: Value function approximation utilizing multiple level aggregation

Sequential resource allocation decision-making for the military medical evacuation of wartime casualties consists of identifying which available aeromedical evacuation (MEDEVAC) assets to dispatch in response to each casualty event. These sequential decisions are complicated due to uncertainty in casualty demand (i.e., severity, number, and location) and service times. In this research, we present a Markov decision process model solved using a hierarchical aggregation value function approximation scheme within an approximate policy iteration algorithmic framework. The model seeks to optimize this sequential resource allocation decision under uncertainty of how to best dispatch MEDEVAC assets to calls for service. The policies determined via our approximate dynamic programming (ADP) approach are compared to optimal military MEDEVAC dispatching policies for two small-scale problem instances and are compared to a closest-available MEDEVAC dispatching policy that is typically implemented in practice for a large-scale problem instance. Results indicate that our proposed approximation scheme provides high-quality, scalable dispatching policies that are more easily employed by military medical planners in the field. The identified ADP policies attain 99.8% and 99.5% optimal for the 6- and 12-zone problem instances investigated, as well as 9.6%, 9.2%, and 12.4% improvement over the closest-MEDEVAC policy for the 6-, 12-, and 34-zone problem instances investigated.     

供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题

取送货车辆路径问题在多点调拨系统普遍存在,属于NP-hard问题。该问题研究通常需考虑车场数、车型种类、货品种类、客户服务次数等诸多因素,已有文献多假设客户间供需已匹配、单车场、单车型、单货品和取送货需求一次性满足,优化目标多设置为总路径最短。而从企业运营实践来看,运输方案不仅要规划客户间访问路径,还需进行客户间供需匹配;运输成本不仅与运距有关,还涉及运输货品的重量和派车成本;运输网络中多车场、多车型和多货品更加常见,且客户需求量往往大于车辆装载能力。因此,本文首次尝试基于"运距×运量"的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标,建立同时考虑多车场、多车型、多货品、客户间供需未匹配和需求可拆分的取送货车辆路径问题模型,并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解,并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：1）本文提出的算法在求解质量和求解效率方面均优于相关文献中的算法;2）相对人工调拨方案,本文设计的方案能够帮助企业节约33%的运输成本和21%的车次。本研究不仅可拓展取送货车辆路径问题现有理论,而且可为企业实际运营提供决策支持。     

直接配送下随机需求库存-路径问题最优平稳策略及其算法

直接配送策略下随机需求库存-路径问题（Stochastic Demand Inventory Routing Problem with Direct Deliveries, SDIRPDD）由于其需求的不确定性、决策的长期性以及其最优策略形式对求解其他库存-路径问题（IRP）的参考价值,使得对SDIPRDD问题的研究成为物流、供应链优化领域研究的一个热点。文章首先证明了无约束SDIRPDD的最优平稳策略为（s,S）形式,并通过分析车辆数约束对客户单阶段期望成本函数的影响,给出了存在车辆数和客户库存容量约束时SDIRPDD问题的最优平稳策略形式,进而提出了一种求解有约束SDIRPDD问题最优平稳策略的近似算法。最后,通过数值算例验证了算法的有效性并分析了结果的现实意义。     

资源约束下多项目调度的改进遗传算法

针对资源约束下的多项目调度问题,在前人提出的有效的启发式算法研究路径基础上,本文利用遗传算法,结合进度生成机制,提出了多项目调度的改进遗传算法。与其他多项目调度启发式算法相比,该算法在平均项目延迟和最佳解比例方面都表现较好,综合利用优化后的优先规则也使得该算法更适用于不同网络复杂度和不同资源约束程度的多项目调度问题中。     

A Parametric Approach for a Nonlinear Discrete Location Problem

A discrete location problem is formulated for the design of a postal service network. The cost objective of this problem includes a nonlinear concave component. A parametric integer programming algorithm is developed to find an approximate solution to the problem. The algorithm reduces the problem into a sequence of p-median problems and deals with the nonlinear cost by a node-replacement scheme. Preliminary computational results are presented.     

Subcontracting price schemes for order acceptance and scheduling

In this paper we study subcontracting price schemes between a subcontractor and a firm that are engaged in subcontracting of heterogeneous orders with distinct due dates, revenues, and processing times. We assume that the subcontractor proposes the subcontracting pricing and the firm follows by determining the subcontracted orders by solving its order acceptance and scheduling problem. When the subcontractor adopts a linear pricing scheme, we find the firm׳s optimal decisions and develop an algorithm to derive the subcontractor׳s own optimal pricing. We then design a fixed pricing with transfer payment scheme and a quantity discount pricing scheme to coordinate the firm׳s and subcontractor׳s decisions. We examine if the subcontractor can make a higher profit using either of these schemes than the linear pricing scheme, and if they will induce the firm to make decisions that lead to system-wide optimal outcomes.     

Race to idle or not: balancing the memory sleep time with DVS for energy minimization

Reducing energy consumption is a critical problem in most of the computing systems today. Among all the computing system components, processor and memory are two significant energy consumers. Dynamic voltage scaling is typically applied to reduce processor energy while sleep mode is usually injected to trim memory’s leakage energy. However, in the memory architecture with multiple cores sharing memory, in order to optimize the system-wide energy, these two classic techniques are difficult to be directly combined due to the complicated interactions. In this work, we explore the coordination of the multiple cores and the memory, and present systematic analysis for minimizing the system-wide energy based on different system models and task models. For tasks with common release time, optimal schemes are presented for the systems both with and without considering the static power of the cores. For agreeable deadline tasks, different dynamic programming-based optimal solutions are proposed for negligible and non-negligible static power of cores. For the general task model, this paper proposes a heuristic online algorithm. Furthermore, the scheme is extended to handle the problem when the transition overhead between the active and sleep modes is considered. The optimality of the proposed schemes for common release time and agreeable deadline tasks are proved. The validity of the proposed heuristic scheme is evaluated through experiments. Experimental results confirm the superiority of the heuristic scheme in terms of the energy saving improvement compared to the most related existing work.     

Pricing and Operational Performance in Discretionary Services

In many services, for example, website or landscape design, the value or quality derived by a customer depends upon the service time, and this valuation differs across customers. Customers procure the service based on the expected value to be delivered, prices charged, and the timeliness of service. We investigate the performance of the optimal pricing scheme as well as two commonly used pricing schemes (fixed fee and time‐based pricing) for such services on important dimensions such as revenue, demand served, and utilization. We propose a novel model that captures the above features and wherein both service rate and demand are endogenous and functions of the pricing scheme. In particular, service time is an outcome of the pricing scheme adopted and the heterogeneous valuations of customers, unlike in the queueing‐based pricing literature. We find that the service system may benefit from a greater variance in consumer valuations, and the performance of pricing schemes is impacted by the shape of the distribution of customers' valuation of service time and the responsiveness desired by customers. Both the fixed fee and time‐based schemes do well relative to the optimal pricing scheme in terms of revenue in many plausible scenarios, but there are substantial differences between the pricing schemes in some important operational metrics. For instance, the fixed fee scheme serves more customers and has higher utilization than the time‐based scheme. We also explore variants of the fixed and time‐based schemes that have better revenue performance and show that the two‐part tariff which is a combination of fixed and time‐based pricing can do as well as the optimal scheme in terms of revenue.     

跨境电商企业海外仓选址多目标优化研究

海外仓作为一带一路战略环境下的一种新型跨境物流模式,具有运输时间短、退换货快等特点。本文在跨境电商的背景下,综合考虑建仓成本、运输费用、运输时间和税费等因素,提出了海外仓选址多目标优化模型,随后基于分层序列法设计了二分搜索-最小费用流算法对该模型进行求解,并证明该算法在多项式时间内可以得到最优解,最后通过算例证实了该模型和算法的有效性和实用性,这为跨境电商海外仓选址提供了理论依据和决策支持。     

基于时差分析的资源均衡问题探究

本文在已有时差概念分析的基础上,提出了三个新时差概念,给出了同一工序不同时差关系,提出了标值算法,算出了不同工序时差传递量。对资源均衡优化问题的初始方案进行研究,给出了随机时标网络图的绘制方式,使网络技术的应用更具灵活性和实用性。在时差传递性的基础上,进一步对有资源限制的资源均衡优化方案进行研究,提出了基于赋值算法的优化调整方式,最后通过算例对该调整方式进行了验证。     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

Clustering and combinatorial optimization in recursive supervised learning

The use of combinations of weak learners to learn a dataset has been shown to be better than the use of a single strong learner. In fact, the idea is so successful that boosting, an algorithm combining several weak learners for supervised learning, has been considered to be the best off the shelf classifier. However, some problems still exist, including determining the optimal number of weak learners and the over fitting of data. In an earlier work, we developed the RPHP algorithm which solves both these problems by using a combination of global search, weak learning and pattern distribution. In this chapter, we revise the global search component by replacing it with a cluster based combinatorial optimization. Patterns are clustered according to the output space of the problem, i.e., natural clusters are formed based on patterns belonging to each class. A combinatorial optimization problem is therefore created, which is solved using evolutionary algorithms. The evolutionary algorithms identify the “easy” and the “difficult” clusters in the system. The removal of the easy patterns then gives way to the focused learning of the more complicated patterns. The problem therefore becomes recursively simpler. Over fitting is overcome by using a set of validation patterns along with a pattern distributor. An algorithm is also proposed to use the pattern distributor to determine the optimal number of recursions and hence the optimal number of weak learners for the problem. Empirical studies show generally good performance when compared to other state of the art methods.     

航空公司机上周转品多基地库存优化模型

在民航业日益激烈的市场竞争环境下，航空公司对成本控制的精细化管理显得尤为重要。本文基于航空公司的实际背景，针对为旅客提供的机上周转品，建立了一个多基地库存系统的库存优化模型。该模型以系统的总库存成本最小为目标，在考虑需求、回收、调运、安全库存等因素下，决策一个订货周期内的订货及调运方案。基于最优解的分析，在成本参数满足一定条件下，可以得到系统最优的期初订货量；在此基础上，可以将该模型转化为一个网络流模型，参考最小费用最大流算法，设计了一个多项式求解算法来求解该网络流模型，进而得到各基地之间的最优调运量，并证明该算法的最优性；此外，根据期初订货量可行解的范围，设计了一个求解原库存模型的启发式算法。通过实例分析，验证了该模型与两种算法的有效性。     

Allocation and Pricing of Substitutable Goods: Theory and Algorithm

Motivated by the thriving market of online display advertising, we study a problem of allocating numerous types of goods among many agents who have concave valuations (capturing risk aversion) and heterogeneous substitution preferences across types of goods. The goal is both to provide a theory for optimal allocation of such goods, and to offer a scalable algorithm to compute the optimal allocation and the associated price vectors. Drawing on the economic concept of Pareto optimality, we develop an equilibrium pricing theory for heterogeneous substitutable goods that parallels the pricing theory for financial assets. We then develop a fast algorithm called SIMS (standardization‐and‐indicator‐matrix‐search). Extensive numerical simulations suggest that the SIMS algorithm is very scalable and is up to three magnitudes faster than well‐known alternative algorithms. Our theory and algorithm have important implications for the pricing and scheduling of online display advertisement and beyond.     

A genetic algorithm-based decomposition approach to solve an integrated equipment-workforce-service planning problem

We develop a new genetic algorithm to solve an integrated Equipment-Workforce-Service Planning problem, which features extremely large scales and complex constraints. Compared with the canonical genetic algorithm, the new algorithm is innovative in four respects: (1) The new algorithm addresses epistasis of genes by decomposing the problem variables into evolutionary variables, which evolve with the genetic operators, and the optimization variables, which are derived by solving corresponding optimization problems. (2) The new algorithm introduces the concept of Capacity Threshold and calculates the Set of Efficient and Valid Equipment Assignments to preclude unpromising solution spaces, which allows the algorithm to search much narrowed but promising solution spaces in a more efficient way. (3) The new algorithm modifies the traditional genetic crossover and mutation operators to incorporate the gene dependency in the evolutionary procedure. (4) The new algorithm proposes a new genetic operator, self-evolution, to simulate the growth procedure of an individual in nature and use it for guided improvements of individuals. The new genetic algorithm design is proven very effective and robust in various numerical tests, compared to the integer programming algorithm and the canonical genetic algorithm. When the integer programming algorithm is unable to solve the large-scale problem instances or cannot provide good solutions in acceptable times, and the canonical genetic algorithm is incapable of handling the complex constraints of these instances, the new genetic algorithm obtains the optimal or close-to-optimal solutions within seconds for instances as large as 84 million integer variables and 82 thousand constraints.     

遗传算法在活动网络有限资源分配问题中的应用

有限资源合理分配是网络计划中一个复杂的组合优化问题。应用遗传算法,本文建立了描述有限资源合理分配问题的染色体结构和适应度函数,设计了问题的遗传运算,并举例说明了该遗传算法的有效性。这一工作对于处理工程项目施工安排问题具有重要意义。     

One-machine scheduling to minimize mean tardiness with minimum number tardy

In this paper the one-machine scheduling problem with the objective of minimizing the mean tardiness subject to maintaining a prescribed number of tardy jobs is analysed. An algorithm for solving this problem is presented. It is proved that the schedule generated by the proposed algorithm is indeed optimal.     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

A minimized-rule based approach for improving data currency

Repairing obsolete data items to the up-to-date values faces great challenges in the area of improving data quality. Previous methods of data repairing are based on either quality rules or statistical techniques, but both of the two types of methods have their limitations. To overcome the shortages of the previous methods, this paper focuses on combining quality rules and statistical techniques to improve data currency. (1) A new class of currency repairing rules (CRR for short) is proposed to express both domain knowledge and statistical information. Domain knowledge is expressed by the rule pattern, and the statistical information is described by the conditional probability distribution corresponding to each rule. (2) The problem of generating minimized CRRs is studied in both static and dynamic world. In the static world, the problem of generating minimized CRR patterns is proved to be NP-hard, and two approximate algorithms are provided to solve the problem. In dynamic world, methods are provided to update the CRRs without recomputing the whole CRR set in case of data being changed. In some special cases, the updates can be finished in \(O(1)\) time. In both cases, the methods for learning conditional probabilities for each CRR pattern are provided. (3) Based on the CRRs, the problems of finding optimal repairing plans with and without cost budget is studied, and methods are provided to solve them. (4) The experiments based on both real and synthetic data sets show that the proposed methods are efficient and effective.     

等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.