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

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

服务型制造网络资源整合决策优化模型

服务型制造是制造业发展的新模式,服务型制造的顺利开展依赖于对服务型制造网络中各种资源的整合及优化.分析服务型制造网络的运作特征, 在此基础上将决定网络和个体运作水平的硬环境因素和软环境因素作为服务型制造网络资源整合的主导因素,提出基于主导因素评判的资源整合决策模式,构建出优化整合决策的数学模型,搭建了改进的蚁群寻优算法来求解整合决策的优化过程,最后借助算例仿真验证算法的有效性与可行性。     

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

回收量不确定的垃圾回收网络优化模型及算法

考虑到实际垃圾回收网络中回收中心日回收量的不确定性特征,以及经城市垃圾处理中心处理后的垃圾被再利用的可能性,建立了一类新的日回收量不确定的垃圾回收处理网络优化模型,分别就全部或部分垃圾能够被再利用两种情形,在假定日回收量为三角模糊量的条件下,利用模糊机会约束规划的方法推导了所建立的不确定性优化模型的确定型等价类.对给定的置信水平,利用LINGO软件能够直接求解所得到的确定性模型.案例研究证实了模型和方法的有效性,应用参数的灵敏度分析得到:目标和不同约束的置信水平对最优运输方案和最小运输成本均具有不同影响.     

基于一种灰色综合关联模型的区域客运结构优化研究

为实现客运结构总体区域优化,运用灰色系统理论中的灰色综合关联分析模型,以珠三角地区客运结构为研究对象进行实证研究,建立了各种客运方式的旅客周转量与相关经济社会主要指标间的灰色综合关联矩阵,对客运结构系统特征及相关影响因素作优势分析.研究结论表明:城市化程度对客运结构影响最大;其次是人均可支配收入,再次是人均生产总值;人口总数对客运结构影响小,但对客运总量影响大.珠三角地区在中短途客运方面,应大力发展城市轨道交通(城际铁路和地下铁道);在长途客运方面,应大力发展高速铁路和民航.     

基于模拟植物生长算法的协作研发网络决策优化模型

在协作研发网络决策中,合理的投资组合可使企业获得理想的收益。企业协作研发网络的投资组合是多方博弈后的结果,利用模拟植物生长算法构建的优化模型可以分析企业在网络中投资组合的博弈过程。通过模拟植物生长算法计算得到的全局最优解和局部最优解是企业协作研发决策投资组合的最优决策集。企业可以根据策略集调整自身的投资方式,制定最优的决策方案。     

基于滚动计划的动态企业资源优化模型

由于传统MRP逻辑存在固有的缺陷,ERP系统中的生产计划模块往往不能满足企业快速发展的需要。为此,文章提出了一个可以实时推进的,能够实现企业资源优化配置的新型企业资源规划系统。系统的核心是一个基于滚动计划的动态企业资源优化模型。文章讨论了将滚动周期理论引入企业资源优化模型的方法和优势。基于该模型的新系统构建更加灵活,应用范围更加广阔,生成的生产计划更加符合企业生产实际。     

区间数型多目标联运路线优化问题的模型与算法

联运路线优化问题直接关系到货物运输的费用、时间和运输质量.首先分析了联运路线优化问题的数学模型及虚拟运输网络图;其次,将区间数排序的思想及属性值为区间数的多属性决策方法引入适应度函数的设计中,提出了一种求解区间数型联合运输路线优化问题的混合型遗传算法,给出了染色体编码、遗传算子设计、适应度函数定义及群体多样性控制的方法;最后用示例对算法的有效性进行了验证.     

多周期多设备冰蓄冷系统的优化模型、算法及应用

本文以多周期多设备冰蓄冷系统运行的动态过程为主要约束,以设备运行状态等为离散优化变量,以设备流体流速等为连续优化变量,以系统运行总费用为目标函数,建立了非线性非光滑的混合整数规划,并论述了该规划问题最优解的存在性。依离散优化变量的有限性,把这个优化问题等价地分解成有限多个关于连续优化变量的线性规划,构造具体的优化算法。最后应用于一个实际冰蓄冷系统,表明了本文的数学模型及优化算法等的正确与有效性,达到缓解用电高峰的用电量,并降低了用户的运行费用。     

基于粒子群算法的变权累加生成的GM(1,1)模型

根据灰色系统的新信息优先原理可知新信息对认知的作用大于旧信息的作用,而传统的累加生成没有体现原始数据中新信息的重要性.针对这一问题引入了变权累加生成的方法,并对变权累加生成在单调性、灰指数规律、凸性等方面的性质进行了研究,得到变权累加生成序列具有单调递增性,具有较强的指数规律,并具有下凸性,这些性质是高精度建模的保证,然后建立了基于变权累加生成的GM(1,1)模型,并运用粒子群算法确定了变权累加生成的权重.通过具体的算例计算表明,变权累加生成的GM(1,1)模型能够提高模型的模拟和预测精度.     

各种运输方式客运质量的综合评价研究

在建立各种运输方式客运质量综合评价指标体系的基础上,提出了用于各种运输方式客运质量综合评价的方法——"专家法—信息熵—灰色关联投影法"相结合的组合评价模型,该模型将专家法、信息熵理论和灰色关联决策法有机结合起来.最后根据实际数据对各种运输方式的客运质量加以综合评价并排序比较,验证该方法的合理性和有效可行性.     

A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints

We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.     

一种具有区间数信息的多目标指派方法

针对具有区间数信息的多目标指派问题,给出了一种指派方法。首先,将不同类型目标的区间数损益矩阵规范化为区间数成本矩阵,并应用区间数运算法则构建区间数多目标指派问题的总成本矩阵。然后,通过事先定义的任意两个区间数的序关系,将区间数指派问题优化模型转化为一个双目标优化模型,并采用线性加权法将其转化为单目标优化模型来进行求解,同时还考虑了如何处理人员数量与任务数量不相等的情形的指派问题;最后,通过一个实例分析说明了本文给出方法的可行性和有效性。本文的方法丰富了已有的求解方法,具有实际应用价值。     

均值-VaR模型的一种新解法：鞍点近似、遗传算法

以均值度量收益,方差度量风险的均值.方差模型,广泛应用于资产组合优化.随着对金融风险度量方法研究的不断深入,VaR作为一种简便、易于理解的风险度量方法,在金融企业中得到日益广泛的应用.本文用VaR代替均值-方差模型中的方差,构建了均值-VaR模型应用干投资组合优化.均值-VaR模型是非线性规划,仅当VaR满足凸性和可微性的前提下,满足库恩-塔克条件的解才是全局最优解.本文在CreditRisk+框架下,提出一个在不允许卖空条件下,不需对VaR的性质做出前提假定的新解法:将鞍点近似法用于计算VaR,在资产头寸与VaR之间建立起函数关系,采用遗传算法寻找模型的近似最优解.并用一个债券组合说明该方法的有效性。     

公交枢纽内始发线路优化配置模型及其模拟退火算法

城市公交枢纽由于用地规模有限、公交线路集中,其内部始发站的设置不同于一般的公交首末站.本文提出了公交枢纽内始发站的布置方法,建立了公交线路和站台间优化配置模型,并提出运用模拟退火算法对模型进行求解.最后通过实例分析了提出的优化模型及解法的有效性.     

Modification of the Wolfe Line Search Rules to Satisfy the Descent Condition in the Polak-Ribière-Polyak Conjugate Gradient Method

This paper proposes a line search technique to satisfy a relaxed form of the strong Wolfe conditions in order to guarantee the descent condition at each iteration of the Polak-Ribière-Polyak conjugate gradient algorithm. It is proved that this line search algorithm preserves the usual convergence properties of any descent algorithm. In particular, it is shown that the Zoutendijk condition holds under mild assumptions. It is also proved that the resulting conjugate gradient algorithm is convergent under a strong convexity assumption. For the nonconvex case, a globally convergent modification is proposed. Numerical tests are presented. This paper is based on an earlier work presented at the International Symposium on Mathematical Programming in Lausanne in 1997. The author thanks J. C. Gilbert for his advice and M. Albaali for some recent discussions which motivated him to write this paper. Special thanks to G. Liu, J. Nocedal, and R. Waltz for the availability of the software CG+ and to one of the referees who indicated to him the paper of Grippo and Lucidi (Ref. 1).     

服务大规模定制模式下的供应链调度优化

为了提升服务大规模定制(SMC)模式下供应链系统的运作柔性,应对客户较强的多样化需求特征,本文在对服务定制特征分析、服务阶段界定以及服务规模效应探讨的基础上,指出SCM模式下的供应链调度问题是一个典型的随机需求与随机资源约束的多目标动态优化问题。研究了SMC模式下供应链调度的优化目标与约束条件,建立了完整的随机多目标动态调度优化数学模型。基于SMC运作的特点,运用改进的蚁群算法对调度问题进行了求解。最后,通过实例分析了模型及算法的可行性、有效性及适用性。     

基于贪婪算法的水上漂移目标救助物资协同调度方法

受复杂水文、气象等条件影响,水上遇险目标在等待外部救援的过程中可能发生漂移,其漂移的速度与方向将直接影响到水上救助物资调度方案的制订。针对水上事故及其救援的特殊性,在对水上遇险目标漂移路径进行预测的基础上,构建了满足运力、时间限制及应急救助物资需求,包括水上遇险目标周边船舶、岸基救助基地及其附近陆地应急物资储备点共同参与的水陆两阶段多层级协同调度模型,并运用贪婪算法对其进行求解,最后通过算例对模型和算法的有效性进行验证。     

Efficient computation of time-based customer service levels in a multi-item, multi-echelon supply chain: A practical approach for inventory optimization

Time-based item fill rates, or “channel” fill rates, are the building blocks needed to evaluate steady-state compliance with time-based customer service agreements. Exact computation of channel fill rates is both difficult and time-consuming, yet their accurate assessment is essential for system-wide inventory optimization. We describe and validate a practical method for computing channel fill rates in a multi-item, multi-echelon service parts distribution system. A simulation study is presented which shows that, in a three-echelon setting, our estimation errors are very small over a wide range of base stock level vectors. A more accurate, though less efficient, approximation method is also evaluated for comparison.