基于马尔可夫决策过程的医疗检查预约优化模型

医技部门的医疗检查如电子计算机断层扫描（CT）、核磁共振成像设备（MRI）、X射线（X－rays）常常有如下三种病人类型：门诊病人、住院病人和急诊病人。针对不同病人类型的需求特点,运用马尔可夫决策过程原理和动态规划方法,建立了医疗检查设备的预约优化模型,并证明了模型的最优性质,得出了不同病人类型的最优预约策略。数值算例的结果表明：本文的预约策略不仅易于实施,而且,通过该模型获得的最大收益比按传统先来先预约的模式所获得的收益要大。     

面向多检查的门诊患者调度研究

及时的检查对于患者病情诊断和治疗非常重要。然而,患者不同的紧急程度、检查项目的多样性、以及患者的行为因素如失约等,使门诊患者调度问题难以求解。为解决该问题,本文考虑患者对两种检查项目的不同需求,两类不同的紧急程度,以及患者失约和医生加班,建立了有限时域马尔可夫决策过程(MDP)模型,目标是使得患者检查所得的期望收益最大化以及期望加班时间惩罚成本最小化。由于MDP模型复杂,难以用解析方法来分析最优控制策略,因此本文基于MDP模型进行数值实验,观察最优解的结构特征,进一步构造了两种参数化启发式调度策略,并采用遗传算法对调度策略的参数进行优化。数值实验比较了最优控制策略、两种启发式调度策略以及先到先服务规则,实验结果表明本文所提的调度策略性能偏离最优解不超过10%;当工作负荷非常大时,启发式调度策略远远优于先到先服务规则。     

基于随机动态规划的有限库存ATO系统优化控制

本文研究n维组件单一产品,有限库存的ATO系统。通过建立马尔可夫决策过程模型(MDP),构造优化算法,研究组件生产与库存的最优控制策略。最优策路可以表示为状态依赖型库存阈值,系统内任一组件的控制策略受其它组件库存状态的影响。利用最优控制理论动态规划方法和数值计算方法对最优控制策略的存在性、最优值的数值计算进行研究,建立更符合实际生产的ATO系统决策模型,进行相应的理论和实验验证,研究系统参数对最优策略的影响。     

随机服务时间下异质患者门诊预约调度优化

考虑随机服务时间与行为特征互不相同的异质患者,建立随机混合整数规划模型对门诊预约调度问题展开研究。首先在给定服务顺序的假设下求解了两个患者的预约调度问题;在此基础上,设计启发式算法对多个患者预约方案和服务顺序同时进行优化。数值结果表明:当患者服务时间为独立同分布的随机变量时,患者预约时间间隔呈现先增加后减少的圆顶形状;当患者服务时间服从不同分布时,通过与样本平均近似方法对比,验证了启发式算法的计算效率和有效性。     

基于预约模式的移动充电车实时需求响应策略研究

预约模式下移动充电车实时需求响应问题是移动充电行业发展过程中的新问题,该问题包含了两类不同特点、存在动态交替影响关系的需求,不仅有时间窗约束、实时响应性要求,也有动态不确定性的特点。针对以上问题特点,本文以最大化整体收益为目标,提出联动的两阶段实时需求响应策略,引用近似动态规划求解决策未来价值,并融入到以下两阶段中：第一阶段基于多阶段随机动态决策模型与禁忌搜索算法生成了可以动态调整的充电服务方案;第二阶段基于第一阶段提出了针对动态需求的实时响应决策流程。最后,对比实验验证了本策略在不同客户规模与动态度下的有效性,并得出管理启示。本研究可以支持制定移动充电车的实时需求响应策略,对类似具有动态特征的需求响应问题具有启发意义。     

动态规划方法在矩阵连乘积中的应用

动态规划方法虽然对于解决多阶段决策过程的最优化问题是比较有效的，然而它也可以用来解决有些似乎与多阶段决策无关的数学问题，如矩阵连乘问题，我们可以引进“时段”和“状态”，把问题分解成一系列形式上很相似的子问题来解决。     

优化配送中心订单拣取路径的一种动态规划方法

订单拣取过程是配送中心最耗时耗力的作业环节，因此提高拣货作业效率成了大多数配送中心努力的方向。而优化拣货路径则是提高拣货作业效率的有效措施之一，所以本在传统拣货规则的基础上，提出了一种采用动态规划方法优化订单拣取路径的方法。该方法是优化配送中心订单掠取路径的一种新的思路和方法，且其确定的拣货路径是在既定规则下的最优拣货路径。针对不同的拣货单采用不同的拣货路径，能有效缩短拣货行走的距离，对提高配送中心的拣货效率具有现实意义。     

基于动态分时电价的虚拟电厂双层优化调度研究

针对虚拟电厂(virtual power plant,VPP)中供给侧与负荷侧价格传导问题,考虑能源侧新能源出力不确定性、大电网购电价格、各类机组运行成本,文章提出了一种VPP厂内部动态分时电价策略,并综合考虑了负荷侧综合需求响应提出了EV接入的VPP双层经济调度模型,以保证VPP的低碳经济运行.上层考虑能源侧成本,以VPP运营商供能成本最小为目标函数,并将碳捕集系统(carbon capture system,CCS)作为灵活性资源,提出一种充分利用新能源与电网低谷电量的碳捕集装置运行模式.下层考虑包括EV在内的负荷侧用能成本,以用能成本最小为目标函数.最后,通过算例结果验证了所提策略的有效性.结果表明,相较于采用大电网分时电价机制,文章所提动态分时电价机制可节约51.8%的能源供给成本,且可降低81.62%的CO₂排放量,有效提升了VPP经济性与低碳性.     

公交车动态调度模型研究

本文通过对照车辆行车时刻表与实际运行到达各站的偏差 ,建立动态调度模型 ,对车辆实施动态调度 ,以保证线路的行车间隔和车辆载客量均匀 ,提高公交服务质量     

基于整数规划的驾驶员调度系统-TRACS II

本阐述一个世界名的成功的公共交通驾驶员调度系统-TRACSⅡ。该系统的核心算法是基于整数规划的“生成与选择”方法。本首先对驾驶员调度同题以及TRACS⒓系统的研发背景和主要功能进行简要介绍;然后,重点阐述该系统的整数规划模型和求解方法;最后,举出几个成功应用的实例,并归纳出该系统存在的局限性,为进一步研究指出方向。     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

考虑存在取消预约情形的门诊预约能力分配策略

在现实的门诊预约问题中,已经预约的患者在接收医疗服务之前,有可能取消先前的预约,这会对医院的收益造成负面影响,如何在考虑患者存在取消预约的情形下,设计合理有效的能力分配策略来保证医院的收益,是一个值得研究的问题.本文针对具有提前预约和当天预约的门诊预约能力分配问题,在考虑提前预约患者可能存在取消预约行为的情形下,提出了一种提前预约患者和当天预约患者的最优能力分配策略。文中首先以医院的期望收益最大作为决策目标,建立了存在取消预约患者的医疗预约问题的马尔科夫过程模型,并给出了该模型的相关性质;基于所建立模型的特征,证明了对于任意的提前预约时段,存在提前预约患者的最佳数量,进而给出了提前预约患者和当天预约患者的最优能力分配策略以及确定该策略的精确算法;最后,通过数值试验说明了本文所提出的能力分配策略的适用性和有效性。     

Intensional dynamic programming. A Rosetta stone for structured dynamic programming

We present intensional dynamic programming (IDP), a generic framework for structured dynamic programming over atomic, propositional and relational representations of states and actions. We first develop set-based dynamic programming and show its equivalence with classical dynamic programming. We then show how to describe state sets intensionally using any form of structured knowledge representation and obtain a generic algorithm that can optimally solve large, even infinite, MDPs without explicit state space enumeration. We derive two new Bellman backup operators and algorithms. In order to support the view of IDP as a Rosetta stone for structured dynamic programming, we review many existing techniques that employ either propositional or relational knowledge representation frameworks.     

Sensitivity analysis in discrete dynamic programming

The problem of characterizing the minimum perturbations to parameters in future stages of a discrete dynamic program necessary to change the optimal first policy is considered. Lower bounds on these perturbations are derived and used to establish ranges for the reward functions over which the optimal first policy is robust. A numerical example is presented to illustrate factors affecting the tightness of these bounds.     

Dynamic multi-appointment patient scheduling for radiation therapy

Seeking to reduce the potential impact of delays on radiation therapy cancer patients such as psychological distress, deterioration in quality of life and decreased cancer control and survival, and motivated by inefficiencies in the use of expensive resources, we undertook a study of scheduling practices at the British Columbia Cancer Agency (BCCA). As a result, we formulated and solved a discounted infinite-horizon Markov decision process for scheduling cancer treatments in radiation therapy units. The main purpose of this model is to identify good policies for allocating available treatment capacity to incoming demand, while reducing wait times in a cost-effective manner. We use an affine architecture to approximate the value function in our formulation and solve an equivalent linear programming model through column generation to obtain an approximate optimal policy for this problem. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the BCCA.     

Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.