网络收益管理问题中的动态定价问题:改进行生成算法

研究了MNL需求下网络收益管理中的动态定价问题。建立了动态规划模型并使用基于线性的近似动态规划方法来处理动态规划中的“维数灾难”问题。尽管如此,因为动态规划问题的价格决策空间是连续的,得到的近似线性规划(ALP)是一个半无限的线性规划,故将使用行生成算法来求解近似线性规划。基于ALP问题最优解的特性,简化了ALP规划,改进了行生成算法。数值实验显示,改进的行生成算法的收敛时间比原来的行生成算法快了近70%。

基于改进列生成算法的高速列车开行方案优化研究

针对编制开行方案涉及因素多、建模及求解困难的特点,结合有容量限制的多商品流网络设计问题,建立确定列车开行对数、开行区段、停站方案及编组形式的多目标整数规划模型,运用权重法将多目标规划转化为单目标规划。鉴于标准的列生成算法难以协同处理网络设计与网络配流问题,设计综合使用列生成与行生成策略的启发式算法确定列车的运行路径及停站方案,采用改进分支策略的分支定界算法求解最终模型。最后,以京沪高铁为例进行验证,在有效时间内获得较高质量解,该解与最优解的误差率为2.13%,且优于京沪高铁实际采用的开行方案。

电动车辆路径问题:可调鲁棒数学模型与算法

针对行驶时间不确定的允许部分充电的带时间窗电动车辆路径问题,考虑多面体不确定集度量行驶时间的不确定性,建立了一个可调鲁棒优化模型,设计了基于行生成和集划分的求解算法,采用标号法对路径的可行性进行判定,并将不可行的路径作为新的约束加入到模型中.数值实验表明,94%的算例可求得最优解,这验证了本算法的效率;利用多面体不确定集进行度量对总行驶距离和车辆总数目具有正向的影响;相比于普通鲁棒优化,可调鲁棒优化的求解结果有显著提高,可以提升车辆调度的灵活性.

考虑维修天窗和到发线数量的复线铁路列车运行图优化

研究了维修天窗与复线铁路列车运行图一体化编制问题,考虑到发线数量、维修限速等约束条件,建立了混合整数规划模型.针对约束的特点对约束进行分类,并运用行生成方法对到发线数量等约束进行分解,运用两阶段法处理较为复杂的维修限速约束,结合商业软件GUROBI求解模型.设计算例进行验证,比较分析了模型约束的不同分解方法.结果显示分解到发线数量约束可以提高求解效率25%~45%,而列车追踪间隔间距约束是否宜采取分解与求解规模有关.

重载组合站列车组合方案随机机会规划模型及算法

重载铁路组合站在重载运输中扮演着至关重要的角色。通过分析重载组合站的组合作业特点,引入组合模式变量对重载组合站组合方案进行优化,在考虑组合规则、到发线数量、列车发车时间间隔调整以及组合作业时间的不确定性等约束的基础上,以重载列车在站停留时间和前方站分解时间最小为目标,构建非线性随机机会规划模型。将随机机会和非线性约束等价转换为线性确定约束,同时借鉴行生成算法的优化思想,分解复杂的到发线数量约束,运用商业求解器GUROBI求解。最后,以大秦线湖东站为案例进行分析,结果表明相比于实际生产中的经验方法,优化后的组合方案使总时间消耗降低7.5%,且更加均衡可靠,验证了模型与算法的可行性。

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。

PLC应用于喷泉控制系统的方案设计

采用PLC与计算机组成的喷泉控制系统,充分利用PLC的通信功能和编程特点,实现上位机与下位机之间的通信和控制,由远程计算机与PLC之间进行通信,通过PLC实现对喷泉各种水型和灯光的快速控制;另一方面,利用PLC的自诊断功能,可实现喷泉控制系统的故障诊断,不但缩短了维修时间,而且提高了控制系统的稳定性。

混合整数半无限规划问题

本文主要讨论混合整数半无限规划(mixed integer semi-infinite programming, MISIP)问题的求解方法.首先分离内层约束中的连续变量和整数变量并将原问题转化为混合整数互补约束规划(mixed integer mathematical programming with complementarity constraints, MIMPCC)问题.其次在假设内层问题满足Slater约束规范的条件下得到了转化前后问题的等价性.继而分别将MIMPCC问题转化为可用常规优化软件求解的混合整数规划问题和非线性规划问题.由于在转化过程中会生成大量的变量和约束,为求解内层问题中变量较多的MISIP问题,本文提出一种行约束生成法,并证明该算法可在最多O(|Z|)次迭代之后得到最优解.最后通过一些数值实例验证算法的有效性.

考虑旅客换乘的高铁列车停站方案-票额分配鲁棒优化

随着我国高速铁路客运量的迅速增长,旅客出行需求时空波动性大,跨线换乘旅客多等特征凸显,对列车停站和票额分配方案的制定提出了更高要求.本文通过构造基于条件概率的不确定性集,刻画旅客出行需求的不确定性,并建立考虑旅客换乘行为的列车停站方案-票额分配联合鲁棒优化模型,提升高速铁路运输组织方案的鲁棒性和灵活性.提出了行-列生成算法对模型进行有效求解,并针对子问题设计基于库恩-塔克条件的精确算法和基于问题结构性质的近似算法.利用京沪线高铁运营数据的计算实验表明考虑换乘的联合优化方案具有更高的客流满足率和更少的停站时间,行-列生成算法具有很高的收敛速度和求解精度.在运行方案制定过程中,应综合考虑旅客出行需求的不确定性和换乘行为,兼顾服务效率和服务水平进行决策.