实时优化论文（共7篇）
实时优化论文 篇1
摘要：降雪严重影响城市道路交通系统的正常运行, 除冰雪已经成为城市冬季道路养护工作的一项重要任务。城市道路网络复杂, 合理的除雪车辆调度方案仅仅依靠人工经验无法实现。考虑冬季道路养护中的服务水平、车队规模等约束条件, 建立了实习信息下除雪车辆优化调度的整数规划模型。该问题属于一个NP-完全问题, 因此设计了构造启发式算法对模型近似求解。算例结果表明, 该算法能够求解一定车队规模的除雪车辆调度问题, 能够提高冬季道路养护的水平, 为实际应用奠定了基础。
关键词：冬季道路养护,车辆调度,整数规划,构造启发式算法
我国的东北、西北、华北地区不仅冬季气候寒冷, 降雪较多, 而且降雪期长, 平均可达3～6个月除冰雪已经成为城市冬季道路养护工作的一项重要任务, 直接关系到城市经济、工作、生活的正常进行[1]。为了降低冬季道路养护的成本和提高冬季道路养护的效率, 国外主要采取了以下两个方面的措施:一是不断发展和采用新技术和新设备, 例如高精度的撒布设备、性能优越的除雪机械、道路气象信息系统、防冰技术、主动除雪技术等[2];二是提高决策优化水平, 例如作业区的合理划分[3]、场站的优化布局[4]、作业车辆路径优化[5,6]等。长期以来我国研究的重点主要在除冰雪的技术与设备上, 而在决策优化方面研究相对滞后。
路面积雪密度越大, 与路面的结合力越强, 清除越困难, 因此根据降雪强度和降雪时间选择好除雪时机非常重要。实时的车辆调度计划可以根据天气信息和路面积雪情况及时的调配车辆, 从而提高道路养护效率和节约养护成本。目前的除雪车辆调度计划主要依靠有经验的调度人员确定, 难以保证调度方案的优化[7]。鉴于此, 本课题依据除雪车辆的实际作业情况和现实的约束条件, 建立基于实时信息的除雪车辆调度整数规划模型, 制定出实时的除雪车辆调配时序计划。
1 问题描述
本文中的除雪车辆调度方案指的是在考虑资源约束条件以及保证一定服务水平的前提下, 基于天气信息和路面信息确定某一时刻向某一路径的调配车辆数, 实现总的养护工时最小和路网服务水平最优。模型的建立流程如图1所示。
在建立模型之前, 本文做出如下假设:
(1) 路网的实时天气信息是已知的, 如单位小时降雪量、路面积雪厚度等信息;
(2) 城市路网通常被划分为不相重叠的分区, 本文称之为作业区, 并假定作业区已经划分完毕;
(3) 养护站是除雪车辆的存放点, 本文假定养护站的位置已经确定;
(4) 除雪车辆的路径已经规划好, 在给定的路网中, 有一组路径集;
(5) 养护站的资源是有限的, 除雪车辆数目有限, 即车队规模限制;
(6) 养护标准越高, 养护成本越高, 本文假定路段的最低服务水平限制是确定的。
2 数学模型建立
2.1 路网构成要素
路段:路段是组成路网的基本单元, 表示道路的一个部分。路段的符号标记为i, 编号由0至n-1, 其中n是模型中总的路段数。路段被设定为单向或双向要根据路段具体的除冰雪作业而定。
路径:路径是由路段按实际地图上的次序顺序排列的, 表示除雪车辆通过路网的路径。假设所有路径的起终点都是该区域中心的道路养护站 (调度中心) 。路径用k表示, 标号0至m-1, m表示模型中考虑的路线总数。
时段:养护作业所需的时间周期被分解为若干离散的时段, 时段是除雪车辆调度的基本单位, 符号标记为t, 编号由0至T-1, T为模型中考虑的总的时段数。
2.2 模型参数与变量
li表示路段i的长度, 用养护车辆通过路段i所需的时段数表示 (取最接近的整数) 。这样便于构建模型。
dk表示养护车辆通过路径k所需的时段数, 可由组成路径k的各个路段的li之和得到。本文中dk用来表示养护路径k的养护成本, 即用养护时间来度量所消耗的成本。
φi表示路段i所允许的最大路面积雪厚度, 即整个周期内需要保证的服务水平界限。
wi表示在时间周期开始时即零时刻路段i的天气情况。
Wi, t表示路段i在t时段内的路面状况改变量, 这一变量仅是基于上一时段的改变量, 并不是绝对数据。
Pk, t是一个时序表格, 表示在t时段之初分配到路径k上的车辆数。
b表示养护站在工期内所能提供的最大车辆数, 即车队规模限制。
Rk, t表示路段i在路径k中的顺序编号, 如果路段没有出现在该路径中, 则编号为零。
Xk, t是一个二元决策变量矩阵, 当且仅当在时段t的开始有一辆车辆驶向路径k时其值为1, 否则为0。
Yi, t表示在t时段内分布在路段i上的车辆数。
Ci, t表示路段i在时段t的末尾的路面状况。这一中间变量由前一时段的Ci, t-1、相关的天气改变情况Wi, t以及养护事件Yi, t产生的改变决定。
2.3 模型约束条件
本文用路段的积雪厚度表示服务水平, 服务水平约束指的是路段积雪厚度不超过一个最大路面积雪厚度, 即要满足:
车队规模限制是为了确保在任一时段内利用的除雪车辆不超过b辆, 那么求在给定时段内所有路段上的车辆数之和, 使这个数值不大于b就是车队规模的约束条件:
约束条件并没有限制一辆除雪车辆在整个工期内只能被派出一次, 只要满足在给定的时段内所利用的车辆不大于b即可。也就是说一辆除雪车辆在满足约束的前提下可以执行多次派出任务。
假设一次作业能够移除的积雪厚度为δ, 则路面状况的改变就是-δ。而Yi, t给出了每一个路段在指定时段内的养护事件数目, 事件数与δ的乘积就是对路面状况总的改变量。定义C为:
为了将路网中给定车辆的启程信息与之后的养护时间联系起来, 本文引入一个四维二元矩阵Qk, i, t, t′, 由l和R得到:
对于确定的k和i, 可以等到一个与t′和t相关的排列Qk, i。用p表示允许的在养护作业开始之前派出车辆数, Zk.i, t表示路线k上的路段i在t时段分布的车辆数。基于以上的分析可知:
2.3 数学模型
模型如下:
目标函数是两个有着不同度量单位的代数式之和, 第一个代数式表示工期内所有路段总的服务水平, 第二个代数式表示养护作业消耗的成本。建立二者之间的联系需要找到一个权重因数β, 权重因数既可以确定二者之间的优先权, 也可以作为一个单位转换因数使二者能以一个共同的度量单位来求和。
3 模型求解
分支定界法是解决整数规划的重要方法之一, 本文在此方法的基础上, 通过构造启发式算法进行模型的近似计算。通过AMPL建模语言建立数据文件和模型文件对该问题建模, 并用GLPK (GNU LinearProgrammingKit) 进行求解。
AMPL (A Modeling Language forMathematical Programming) 语言是专门为优化问题设计的建模语言。以分支定价法为基础的构造启发式算法用AM-PL建模语言表示为:
4 算例分析
4.1 情景的制定
算例的路网结构如图2所示。该算例的总时间周期选为3h, 并取10min为单位时间, 故可将总时间周期分成0～17共18个段。算例选取了A～I九个作业区和一个调度中心点 (用PY表示) 。图中的节点表示养护作业区, 节点之间的弧表示连接两个作业区主干路的长度 (用单位时间表示) , 每个节点处的圈表示完成该作业区除雪作业需要的时间。此路网结构为双路段模式, 有26条弧 (例如A-B和B-A) 组成。
算例中选取了11条路径, 分别用R1～R11表示。机械除雪一次的深度δ=500mm。车队数量b=5, 目标函数相关系数β=0.5, 路段需要保持的服务水平均为20mm。
天气情况假设如下:在前60min内降雪量是逐渐增加的, 并且在接下来的30min内达到一个高峰, 在最后90min呈逐渐递减趋势。具体的天气情况实时矩阵W如表1所示。
路径矩阵如表2所示。0表示不经过该路段, 1, 2, …表示经过各路段的顺序。例如R6, 依次经过PY-E, E-E, E-PY。
各节点间的距离矩阵L (用时间单位10min表示) 如表3所示。
4.2 结果分析
计算出来的车辆实时调度计划如表3所示。从表中得知在11条路径中, 只有7条路径被选择, 分别是R2, R3, R4, R5, R6, R7, R10。表3中的1代表在其所对应的时间段起点有车辆被派到指定的路径上, 黄色区域表示第一次被派出的车辆, 蓝色表示车辆被第二次派出。从表中可以看出, 5辆除雪车全被派出, 4辆车被派出过两次。本文提出的除雪车辆调度模型能够从较多的路径中选择出最优的路径, 因此备选路径越多, 越有利于目标函数取得最优值。
车队数量b=5时, 目标函数值为25 323mm。图3为目标函数值与车队数量b之间关系。随着除雪车辆的数量增加, 目标函数值越来越小。理想的情况是每个作业区都能够配置足够的除雪车辆, 但这在现实中是不可取的, 因为除雪车辆的购置费和维护费都非常的高。如何在目标函数里面更好的考虑除雪车辆的费用问题, 并确定某一路网所需的除雪车辆数, 具有重要的研究意义。
通过算例分析说明, 在实际问题中可以利用此模型建立车辆调度计划表, 并可以预测到调度计划完成后路网所能达到的服务水平。
5 结论
本文针对实时天气信息下除雪车辆时序调度计划优化问题进行了研究, 构建了整数规划模型, 并通过构造启发式算法求解, 可以在资源限制和服务水平约束条件下制定出使整体路网的养护成本和路网服务水平最优的调度方案。该研究能够为冬季道路养护的管理部门提供决策支持, 具有很大的应用潜力。
冬季道路养护优化决策问题是高度复杂的, 并且各种决策行为是密切相关的, 例如路径规划与场站选址问题, 本文研究的问题仅是其中的一个子问题。综合考虑除雪车辆路径规划、车队数量优化、实时调度等问题进行建模, 将更加有利于提高养护效率和节约成本, 这也是下一步的研究方向。
参考文献
[1]蒋贤才, 裴玉龙.冰雪道路交通安全管理措施及其成效分析.公路交通科技, 2008;25 (4) :127—130
[2]Perrier N, Langevin A, Campbell J F.A survey of models and algo-rithms for winter road maintenance part II:system design for snow disposal.Computers&Operations Research, 2006; (33) :239—262
[3]Applications O R.The sector design and assignment problem for snow disposal operations.European Journal of Operational Research, 2008; (189) :508—525
[4]Perrier N, Langevin A, Campbell J F.A survey of models and algo-rithms for winter road maintenance part III:vehicle routing and depot location for spreading.Computers&Operations Research, 2007; (34) :211—257
[5]Lacomme P, Prins C, Ramdane-Cherif W.Competitive mathematics algorithms for arc routing problems.Annals of Operations Research, 2004; (131) :159—185
[6]Perrier N, Langevin A, Campbell J F.A survey of models and algo-rithms for winter road maintenance part IV:vehicle routing and fleet sizing for plowing and snow disposal.Computers&Operations Re-search, 2007; (34) :258—294
[7]Fu Liping, Trudel M, Kim V.Optimizing winter road maintenance operations under real-time information.European Journal of Opera-tional Research, 2008; (3) :1—9
优化系统架构提升消费提醒实时性 篇2
2012年度以来, 随着市场竞争的不断加剧, 电信营销套餐的数量和种类也在不断增长, 套餐中各种免费量使用范围和共享限制也越来越复杂。除了主套餐, 还出现了可选包、加装包等多重营销的免费量组合共享、甚至出现了跨套餐的免费量共享模式。为用户能够更清晰明了地掌握套餐内和套餐外的实时消费情况, 集团公司和市场部对用户短信提醒的覆盖范围和实时性要求也越来越高, 对短信提醒的服务范围和销售品、套餐的组合共享提醒提出了更高的要求。同时, 为进一步扩大提醒套餐覆盖范围, 上海电信市场部也提出了融合套餐语音免费量的提醒需求, 需要将现有融合套餐的账务级优惠迁移成清单级批价后才能实现提醒功能, 并同时支持主套餐和加装包的设备群级免费量共享提醒。
针对上述提醒要求, 需要对现有的融合计费提醒功能进行相关的优化和改造, 通过在计费模型上的一系列优化和创新, 将原有定时短信提醒能力提升为实时提醒能力, 并增强市面上各类群组类套餐及组合营销套餐提醒能力, 实现提醒阈值的统一规则管理, 套餐内外使用量用户前台可展现。
2. 短信提醒现状分析
短信提醒是现有计费系统中直接面向用户服务的一个模块, 每天的发送量巨大, 对用户的电信业务使用起着引导和主动提示的作用, 因此其准确性和及时性都至关重要。现有的融合计费系统短信提醒功能, 是依附于融合计费系统的综合信控模块短信定时提醒子模块, 该综合信控模块于2011年上线, 最初定位为传统的信控功能, 主要实现准预用户停复机以及封顶断网功能, 在短信提醒能力上对复杂场景和群组类套餐都只能通过外挂定时脚本实现, 达不到集团公司和市场部新提出的提醒要求。
目前短信提醒存在的主要问题如下:
2.1 实时性问题
目前虽然已经实现了套餐使用量提醒需求中的阈值定时提醒, 而业务需要提升为实时提醒, 目前定时提醒采用的是定时批量提数的实现方式, 该方案导致短时间内提醒程序无法将所有需要提醒的数据完成提数和短信的生成, 即便提醒程序能完成, 下游短信平台在短时间内也不能进行全量短信的发送。
2.2 系统性能问题
目前已经实现了的实时提醒业务 (停机前余额提醒、国际漫游流量提醒、国际漫游费用提醒、阶梯提醒、余额不足设定阈值提醒、封顶断网提醒) 和实时信控业务的触发源不仅合用, 而且群组对象、场景适配都是使用同一任务, 信控和提醒任务完全交织在一起, 随着提醒的种类、覆盖的产品、套餐越来越多, 将会导致程序在处理提醒任务时的开销越来越大, 在每月月初信控高峰时段会造成信控发送的不及时。
2.3 套餐覆盖问题
目前套餐阈值提醒为单产品套餐的提醒, 对于群组共享套餐和融合套餐的提醒无法实现。
2.4 可维护性问题
目前信控生成的提醒短信工单, 都是人工后台查证, 没有统一的前台配置和查证界面。日常程序运行都是依靠人工后台控制, 缺乏异常情况下的自动调度和告警机制。
通过对现有综合信控模块的优化, 重新设计新的短信提醒模块, 将短信提醒和信控业务分离。提供实时提醒能力、个性化阈值定制提醒能力、处理环节的petri网管理、短信提醒规则的前台界面配置以及投诉查证界面化;并能有效提升原有信控处理效率, 减少系统资源的占用和消耗。
3. 实时提醒架构的设计与实现
本次实时提醒新架构的设计, 主要在原有融合计费信控模型的基础上进行改进和优化。通过新增策略预判断功能和提醒规则引擎增强, 实现提醒阈值的规则统一管理, 并支持不同销售品对应设备群的共享免费量的提醒功能。
此外采用实时提醒和实时信控模型和程序统一, 部署和任务处理分离的方式, 也有助于将现有信控上定时提醒业务迁移至实时提醒模型的工作, 保证提醒迁移的平稳过渡。
3.1 自动化调度的实现
在新的短信提醒模型基础上, 通过对各类提醒的业务场景和业务流程进行重新梳理, 使得整个短信提醒的业务处理流程统一化和规格化, 便于日常运维和后续新增业务提醒的可配置化。同时在各个子模块之间通过petri网技术实现流程的统一调度, 提升业务处理的并发处理性能。在自动化作业调度的同时, 还针对原有的监控告警流程进行了优化。原有的定时提醒由于每天定时生成短信文件, 频度为一天1-2次, 本身实时性较差。可以依靠短信数量告警和人工干预检查进行处理, 但迁移至实时提醒之后, 由于短信的发送频率改为24小时实时发送, 必须依靠自动化监控的手段来保障日常运营的安全稳定。为此专门设计开发了短信提醒“踩刹车”功能。主要为实现高命中率, 连续对象命中监控而设计。该功能通过独立进程实现判断监控, 发现异常时进行告警并暂停相应的业务处理进程, 由人工确认后再进行恢复。拦截的阈值可通过历史几个月的发送数据进行自学习管理, 并可以根据预设的节假日进行多组阈值的判断, 防止特殊日期短信数量暴增而发生误“踩刹车”的问题。
3.2 群组共享免费量提醒实现
针对现有的群组类套餐, 在提醒规则引擎中增加群组共享免费量的群组适配功能:对于主副卡共享免费量套餐, 在共享群组中的主卡和副卡都要同时发送提醒短信。
其主要流程如图2所示, 具体如下:
(1) 根据场景查找群组对象并适配出信控计划流程, 匹配出销售品实例需要触发执行的信控计划;
(2) 在计划定价配置表中新增提醒用户SQL配置, 该SQL是根据累积量文件给定的销售品实例, 查询出该用户所在的群组;再通过群组ID提取该群组中所有有效的移动用户;
(3) 对通过SQL提取出来的所有用户生成阈值短信提醒。
3.3 融合套餐提醒的实现
融合套餐短信提醒的覆盖, 需要计费支持角色功能, 且需要将融合套餐从账务级迁移到计费级。上海大部分融合套餐目前使用账单级优惠模式, 每月开账后抵扣语音通话费用。要实现这些融合套餐使用提醒, 首先需要将这些套餐从账单级优惠模式向批价级优惠模式迁移。
在增融合套餐提醒中, 如果主套餐免费量供加装包使用, 那么需要提醒加装包用户, 否则不提醒加装包用户;一般主套餐内语音免费量需要和加装包用户共享, 需要同时提醒主套餐和加装包用户, 而上网和短信免费量则仅为主套餐内用户享受, 仅需提醒主套餐用户。为此在群组成员表中增加角色字段, 不同类别的设备角色取值不同, 目前分:ZC-主套餐C网, ZG-主套餐固网, JC-加装包C网。
为了解决同一个套餐内不同免费量提醒范围不同的问题, 针对融合套餐的提醒增加了角色判断的功能, 如图3所示, 具体规则如下:
(1) 短信提醒基本针对融合套餐需要提醒累积量增加累积量是否限制加装包用户使用标识, 0:表示该累积量包含加装包C网用户, 1:表示该累积量不包含加装包C网用户;
(2) 根据累积量触发文件提取需要提醒累积量类型及所有群组用户;
(3) 判断需要提醒累积量是否限制使用范围;
(4) 针对限制使用范围的累积量, 判断用户是否为加装包用户;
(5) 如果需要提醒的累积量范围没有限制用户, 则该融合套餐下所有用户均发送短信提醒;
(6) 如果需要提醒的累积量范围限制不包含加装包用户, 则剔除融合套餐群组内加装包用户 (剔除规则为群组用户表中角色字段不等于“JC”) ;
4. 总结
通过本次实时提醒新架构的设计和功能优化, 系统的能力提升总结如下:
(1) 短信提醒实时能力提升
原定时外挂脚本方式的提醒实时性差, 用户收到短信往往要延迟4-10小时, 很多用户都抱怨收到的提醒时间太晚, 实际使用已超出了免费量的使用范围。现提升为实时提醒能力后, 计费系统收到用户话单后只需20-30秒即可发送短信完毕。加上网元下话单的延迟, 平均用户挂机断网后5-15分钟即可收到短信。
(2) 系统性能提升
原短信提醒和信控停复机的业务触发源不仅合用, 而且业务处理都使用同一任务, 信控和提醒任务完全交织在一起, 在每月月初信控高峰时段会造成信控发送的停复机指令不及时。本次实时提醒新架构重新设计并实现了与信控业务数据源和处理逻辑的分离, 提升了信控停复机的能力, 并可通过优先级管理确保重要短信及时送达。
(3) 套餐覆盖范围提升
原定时提醒套餐覆盖不全;仅覆盖了部分的单C套餐;且模型对不同销售设备群的共享免费量的提醒支持程度差, 对于账务级优惠的融合套餐无法实现提醒功能。现已实现了全量C网套餐和融合套餐的提醒。
5. 结束语
通过对实时短信提醒模型的改造和优化, 使得短信提醒模块在功能、性能和套餐覆盖范围上都有较大的提升, 实现了主套餐、加装包、可选包等群组共享的营销产品在套内套外免费量的实时提醒能力。同时增加了免费量使用情况前台可查询的范围, 实现用户前台可解释的目标。让广大用户可以享受到实时提醒带来的更多便捷, 真正做到“轻轻松松使用, 明明白白消费”。实时提醒上线后对外提供的提醒服务基本涵盖了用户整个消费生命周期中的全过程。用户挂机断网后收到提醒短信的时间由原来的几个小时缩短到5-10分钟。同时提醒套餐的覆盖范围也从原来的部分试点套餐逐步扩展到了C网全业务套餐和融合套餐1000多个。已成为引导广大用户日常电信业务使用中必不可少的功能。
摘要：随着业务的发展, 现有的套餐内各种免费量抵扣范围和共享规则越来越复杂, 出现了可选包、加装包等多重营销的免费量共享组合以及跨套餐的免费量共享模式。为用户能够更清晰明了地掌握套餐内和套餐外的实时消费情况, 本文通过对现有短信提醒模型的设计优化, 使短信提醒模块在功能、性能和套餐覆盖范围上都有较大提升, 扩大了前台免费量使用查询的范围, 达到用户前台可解释的目标。使广大用户可以享受到实时提醒带来的更多便捷, 真正做到“轻轻松松使用, 明明白白消费”。
关键词：短信提醒,服务提醒,计费模型,架构优化,信控
参考文献
[1]中国电信集团公司.关于进一步优化全生命周期服务提醒短信规范的通知[Z], 2012.
实时优化论文 篇3
目前市面上的摄像头输出的格式都是其他格式, 不是FLASH格式, 如果需要转换为FLASH格式, 做法是将摄像头的视频输出接入网络视频服务器, 而网络视频服务器不是电脑, 是一个专用的机器, 由于是连接在网络结构中的物理层, 而且视频服务器不是电脑, 所以计算能力不够强, 所以能接入的摄像头数量比较少, 最多为32路。市面上一个网络视频服务器的造价比较昂贵, 并且一台机器不可以在多个不同的地点同时接入摄像头。
可以将一台计算机作为转换服务器, 在其上开发一个转换系统, 并且与硬盘录像机通过网络层连接, 不用在物理层上与摄像头连接, 就可以实现将其他视频格式的转化为FLASH视频格式。
这个技术方案步骤如下:
(1) 搭建服务器;
(2) 视频获取;
(3) 格式转换;
(4) 视频播放。
步骤1:所述的搭建服务器是将计算机配置公网IP并部署转换软件后作为服务器的搭建过程, 具体是将计算机连入因特网, 申请固定公网IP地址A, 安装ffmpeg开发包, 将需要装换格式的硬盘录像机的IP地址记录到列表B中, 然后以计算机作为服务器, 计算机要求最低配置为:处理器双核主频1.8G Hz, 内存2GBDDR2 667MHz, 硬盘120G/5200转, 1000M网卡。
步骤2:所述的视频获取是服务器根据步骤1的列表B, 根据逐条IP地址访问目标硬盘录像机, 获取存储在目标硬盘录像机中的视频流, 通过RTMP流媒体协议进行视频流数据传输, 将视频流数据存储在服务器内存中, 以IP地址作为索引, 并生成视频流清单C的过程。
步骤3:所述的格式转换是将步骤2存储在服务器内存中的视频流数据按照索引进行分类, 按照视频流总数生成同等数量的线程, 每个线程运行步骤1中服务器部署的ffmpeg开发包, 并且每个线程生成多个缓冲池, 用于保存重要的数据包帧, 进行数据格式的实时转换, 缓冲池的数量可以设定, 每个线程缓冲池不能超过20个, 转换成功后, 将原视频流数据在内存中清空, 保存新生成的FLV视频流10秒钟, 11秒后将10秒前生成的FLV视频流也在内存中清空, 清空的数据保存在硬盘中, 直至硬盘空间剩余20%时自动删除前部分的视频流, 存在内存中的视频流用于给用户查看实时录像, 存在硬盘中的视频流数据用于提供给用户查看历史录像。
步骤4:所述的视频播放是用户通过互联网访问步骤1中申请的IP地址A, 获取到步骤2中生成的视频清单C, 从视频清单C中挑选需要观看的视频, 如查看实时录像, 服务器实时将步骤3转化后存在内存中的FLV视频流以RTMP流媒体协议传输给用户使用FLASH PLAYER进行播放, 如查看历史录像, 服务从硬盘中读取步骤3转化后存在硬盘中的FLV视频流以RTMP流媒体协议传输给用户使用FLASH PLAYER进行播放。
实时优化论文 篇4
目前，具有小批量、多批次特点的实时的城市配送的不断发展大大增加了配送成本，不合理的配送方案会严重增加城市交通负担。与城际配送等长距离的配送相比，城市配送货物需求点繁多且分布不均匀、单批需求量小且时常发生变动、道路堵塞情况时有发生，初始规划路线往往不能保证最小化企业运输成本，而且顾客可以通过移动电子商务平台随时随地进行订单的添加、取消和订货量的变更，加大了对配送实时响应性和灵活性的要求，增加了配送路径安排的难度。
实时的城市配送需要借助地理信息系统（GIS）、全球定位系统（GPS）、智能交通系统（ITS）、移动电子商务平台（MC）和全球移动通讯系统（GSM）等技术工具实时地获取动态信息，而调度中心要不断的合并新信息，在每个动态事件发生时刻生成新的配送计划。信息获取过程如下：MC用于获取顾客需求量和需求点位置信息，ITS用于获取实时交通道路信息，车辆使用GPS进行定位，GIS用于获取任意两个顾客的实际距离。根据以上实时信息，每次有动态事件发生，配送中心生成新的配送路径方案，其指令通过GSM传达给车辆司机。
关于动态车辆路径问题的研究在近10年取得了一定的进展。谢秉磊和郭耀煌[1]对动态车辆路径问题的研究进行了综述，并对该问题的发展前景进行了展望。针对在配送过程中有事先未知位置的新顾客出现的情形，Branke[2]提出了以最大概率将新顾客整合到原配送方案的等待策略。Potvin[3]针对考虑顾客实时需求和动态行驶时间的动态车辆路径问题，比较了不同的调度策略。针对动态网络环境下的车辆路径问题，王江晴[4]提出了一种实时路径评估模型，用于找出实时最短路径，在此基础之上构造了一个改进的Dijkstra算法，实现对行驶线路的不断调整。Du等[5]以牛奶配送为应用背景，提出车辆实时调度中采用2-Exchange改进法则用于配送线路内部的改进十分迅速有效。刘霞[6]研究了带时间窗的动态车辆路径问题，使用插入法构造初始解，使用重定位法、节点交换法、2-opt法和Or-opt法4种局部搜索方法的不同组合完成对初始解的改进。刘士新[7]设计了在动态环境下的车辆路径问题，提出一种导向局部搜索算法，算法对初始解中各车辆配送路线的顾客服务顺序进行动态改进。针对具有模糊预约时间的动态车辆路径问题，张建勇[8]提出了在新顾客出现时的一种插入启发式算法，确保顾客综合满意度最大。针对出现新需求的情况，Attanasio等[9,10]提出了接受或拒绝新订单的策略。郎茂祥[11]考虑车辆故障和允许多次配送的情况，提出了包括制定整体计划和实时局部优化的两阶段策略，分别采用禁忌搜索算法和局部搜索算法进行求解。针对配送车辆在配送途中出现故障的情形，Li[12]提出了一种拉格朗日松弛插入算法安排其他配送车辆完成故障车辆尚未完成的配送任务。王旭坪[13]等从干扰管理的角度，提出了解决配送过程中出现动态信息的方法。陈森[14]针对路网结构变动和需求随机双重不确定因素的动态车辆路径问题，设计了加速自适应遗传算法进行求解。针对带时间窗动态车辆路径问题，王君[15]通过定义紧急顾客，提出基于紧急顾客插入的重复优化方法、分批处理的方法或上述两种方法的的混合三种应对策略。
对于动态车辆路径问题，目前相关研究多采用插入新需求点和调整部分线路的局部优化方法，尽量减少原有配送线路的变动程度。针对可能发生的动态事件，通常只选取其中的一种或两种情形作为考虑对象。
针对现行研究存在的上述问题，本文考虑配送过程中可能发生的多种动态事件，在每次动态信息更新后在原有配送方案基础上对剩余尚未配送的顾客需求点进行全局优化。提出了一种能够即时处理各种动态信息的车辆实时调度方法，考虑了顾客接收货物的时间窗限制和车辆超出最大距离的附加成本。通过实时收集顾客需求信息、监测车辆运行情况，对已经安排好的车辆路径进行即时调整或重新安排车辆所需服务的顾客需求点，实现配送路径的实时优化调整。
2 实时车辆调度问题描述与模型构建
2.1 建模假设与符号说明
本文研究的动态车辆路径问题，可定义如下：在保证每个顾客的需求被满足，且不超过配送车辆的最大配送量，考虑车辆超出最大行驶距离和违反时间窗限制的附加成本的情况下，考虑配送过程中实时变化的信息（需求点增减、需求量变化、道路交通中断、配送车辆故障），每当有动态事件发生时应该如何重新安排车辆的行驶路线，目标是使整个配送周期的车辆配送总成本最小。
本文假设配送中心有一定数量的配送车辆，车辆载重量均为Q，所有顾客的货物需求量均小于配送车辆的最大装载能力，车辆由配送中心出发，完成配送任务后要返回配送中心，方案计划安排的车辆数为m，平均车速为v.c为单位距离运输成本，c0为多派出一辆车的固定成本。车辆每日最大行驶距离为L，超出最大行驶距离后的惩罚系数（即每公里需附加支付给司机的费用）为pl，违反时间窗约束的惩罚系数为p1、p2.
每当有动态事件发生时，更新所有相关信息，包括：已经完成服务的顾客集合I1={1,2，…，n′}；尚未服务的顾客集合I2={1,2，…，n}，顾客i的货物需求量qi、服务时间si及顾客位置，i∈I2，顾客i要求货物最好在时间窗[ETi,LTi]内送达，最差不得超出[ai,bi]的送货时间范围；尚未服务和已服务的所有顾客集合I={1,2，…，n′，…，n′+n}；正在执行任务车辆集合H={1,2，…，h}，各车的位置和状态（车辆是否发生故障），各车在该时刻已完成的货物配送量Qk和已行驶的距离Lk,k∈H；当前所有节点集合（尚未服务的顾客、虚拟顾客、配送中心）N={0,1，…，n，…，n+h}，任意两节点距离dij，及现有节点间各路段交通状况（道路交通中断时dij取无限大），i,j∈N；尚未服务的顾客和虚拟顾客的集合D={1，…，n，…，n+h}。
动态事件发生时，对尚未服务的顾客重新编号1,2，…，n，虚拟顾客编号n+1,n+2，…，n+h，配送中心编号仍为0，将正在执行任务的车辆（亦即该路径）与各自虚拟顾客n+1,n+2，…，n+h对应编号为1,2，…，h，从配送中心出发的车辆顺次编号为h+1,h+2，…，m．配送车辆集合M={1,2，…，h，…，m}。
决策变量xijk表示车辆k经过路径（i,j），有
车辆k到达顾客i的时间为TAi，离开时间为TLi．显然有，，递推可得，而TLi=TAi+si.
2.2 问题分析与转化
根据配送开始之前的已知信息，按照静态车辆路径问题的方法进行求解，所得即为初始配送方案。
配送开始之后有任何一种动态事件发生时，部分车辆正在配送途中进行配送。此时，需更新所有相关信息进行重新调度。该时刻点的路径安排问题可视为多车型的混合式车辆路径问题，原因如下：
(1)在配送中心尚未出发车辆的货物配送量是Q吨，其最大行驶距离为L；在配送途中的车辆已经完成Qk吨货物配送量，车上剩余Q-Qk吨货物配送量，其最大行驶距离为L-Lk．因此，在配送中心尚未出发的车辆和在配送途中的车辆可以看作不同的车型。
(2)在配送中心即将出发的车辆最终会回到配送中心，其行驶路线是闭合回路；在配送途中的车辆此时不在配送中心，相当于从该时刻点该车辆所在途中位置出发，最终返回配送中心，其行驶路线是开放式的路径，而不是闭合回路。因此，在重新调度时，可以将该问题看作是包含封闭式和开放式车辆路径问题的混合式车辆路径问题。
进一步将多车型的混合式车辆路径问题转化为静态单车型车辆路径问题，转化方法如下：
(1)将在配送途中正在进行配送的车辆k当前所在的位置设置一个虚拟顾客，其需求量为Qk，该虚拟顾客与配送中心的距离为Lk.
(2)在配送途中正在进行配送的车辆必须首先服务其对应的虚拟顾客。
2.3 数学模型
根据上述求解思路，本文提出的动态车辆路径问题模型建立如下。
目标函数：
其中，
约束条件：
模型中，式（1）表示问题的目标函数配送总成本最小，包括车辆的运输成本、车辆启用的固定成本、超出最大行驶距离附加成本（2）和违反时间窗限制的惩罚成本（3）；约束（4）保证每辆配送车辆均不超过其最大载量能力；约束（5）、约束（6）确保每个顾客只能被分配到一条路径上，即只被服务一次；约束（7）保证每一条路径上，离开每个节点的车辆数等于进入该节点的车辆数；约束（8）确保所有车辆的起、终点都在配送中心；约束（9）表示每辆当前正在执行任务的车辆必须首先服务其对应的虚拟顾客，从而使配送的路径转化为简单圈；约束（10）限制车辆行驶路径轨为简单圈，避免子回路的产生。式（11）为到达时间的非负性约束。
3 混合遗传算法设计
3.1 实时调度的整体流程
步骤1：数据初始化。开始时间为0，全部车辆起始位置在配送中心。根据现有的相关信息，利用混合遗传算法生成初始配送方案。
步骤2：车辆司机严格按照调度中心传达的配送线路行驶。
步骤3：判断是否已经完成所有配送任务或达到最长工作时间。若是，结束任务，车辆返回配送中心；否则，转步骤4。
步骤4：发生动态事件时，更新相关信息，得到一组新的需求节点和需求量，在途车辆状态、位置的集合，以及当前各路段交通状况的相关信息。
步骤5：调度中心根据最新雅息对配送车辆的行车路线进行重新安排，并将新的行车路线即时传达给配送车辆司机，下转步骤2。
3.2 混合遗传算法步骤
根据模型的结构特点以及决策变量的可行域，本文设计了结合局部搜索思想的混合遗传算法，在每次信息更新后重新对配送路线进行求解，从而实现实时调度。混合遗传算法按以下步骤进行：
Step1：编码，生成初始种群。采用需求点直接排列的编码方法，用一个染色体表示所有尚未服务的需求点的配送顺序，即由尚未服务的顾客编号1～n构成一个实数串。随机产生未被访问过的需求点序列，按顺序逐一将每个需求点加入到当前配送路线中。检验是否满足车辆载重限制，若满足，则将该需求点加入到当前配送路线中；若不满足，则将其加入到下一条配送路线，如图1所示。
重复上述过程得到N条染色体。
Step2：计算个体适应度。P=1/（Z+Gpw）。式中Z为目标函数值，G为配送路径条数与配送中心的车辆总台数之差（若配送路径条数<车辆总台数，则取G=0，表示该个体对应一个可行解；否则，G>0，表示该个体对应一个不可行解），可将G看成该个体对应的配送路径方案的不可行路径条数，设对每条不可行路径的惩罚权重为pw．若适应度值满足优化准则，满足转step8，否则转step4。
Step3：选择再生个体。采用轮盘赌选择具有较高适应度的个体。保留当前子代的最优解，并保持子代的群体个数与种群个体数相同。
Step4：交叉方法采用类改进的OX法实施交叉操作。操作方法说明如下：选择两条父代染色体，随机选择两个基因交叉点，在两个父代个体前分别加入异方双亲的交叉区域，顺次删除与交叉区域重复的基因，得到子代染色体。交叉操作示意图如图2。
Step5：变异。对子代进行两点交换操作。交换前后进行适应度计算，如果其适应度比之前好，那么采用变异后的值，如果较差，则再进行一次随机变异。
Step6：判断是否达到预先设定终止进化代数，满足转下一步，否则返回Step2。
Step7：输出最优解，算法停止。
4 算例设计与结果分析
4.1 算例设计
某城市配送中心位置坐标为（112,88）。共有15台配送车辆，拥有若干个位置已知的潜在需求点。运输成本c=1元/公里，多派出一辆车的固定成本c0=100元，车辆最大货物配送量Q=8吨，车辆每日最大行驶距离L=250公里，超出最大行驶距离后每公里需附加支付给司机的费用pl=1元/公里，p0=20元，p1=p2=50元/小时，ai=ETi-2,bi=LTi+2,A=10000元，平均车速v=50公里/时，粗略将需求量（吨）的1/3记为该需求点的服务时间（小时）。
在配送开始前有8个货物配送任务，各个顾客的需求情况如表1所示。
4.2 对比策略
将本文所提出的实时调度方法与传统的静态调度方法进行对比实验。
传统的静态调度方法是指所有配送车辆均按照配送开始前的初始配送方案进行配送，配送顺序和配送量均不作任何变动。对于配送过程中可能出现的各种动态情形，采取如下方式进行处理：
(1)在配送过程中，对于新增需求点和需求量，从配送中心另外派出车辆进行配送，调度方法与静态车辆路径问题相同。
(2)对于取消订单的需求点，配送车辆直接将其略过，对下一顾客进行配送。
(3)对于在途中发生故障的车辆，从配送中心另外派出车辆按照顾客点顺序依次完成该车未完成的配送任务。
(4)对于两需求点间发生交通中断的情形，该配送车辆直接对原路线的下一需求点进行配送，发生交通中断而无法到达的需求点由新派出的车辆进行配送，调度方法与静态车辆路径问题相同。
4.3 结果分析
(1）初始配送线路的构建
使用混合遗传算法进行求解，得到初始配送线路。配送中心需派出3辆车，配送路线分别为：0-1-4-5-0,0-8-22-0,0-17-16-15-0。
(2）实时信息下的线路优化
(1)情形1:
T1=1时20分，发生如下动态事件：老顾客4、22分别新增需求0.5吨，老顾客5取消订单，出现新顾客6、7、10、11、19、28、29。此时，尚未服务的顾客需求见下表。
对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表3。
若使用传统的静态调度方法，可以得到如下配送方案。
对比表3和表4可以得出，如本算例在需求点和需求量发生变动的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本，在该算例中可以有效降低157.8元，高达原配送成本的10.4%.
(2)情形2:
T2=2时，发生如下动态事件：车辆2在行驶途中发生故障，短时间内无法修好；顾客15、16之间的交通中断。此时，还剩下顾客4、5、15、22未被服务。
对信息变更后的配送任务运用混合遗传算法重新构造配送路线，得到的配送方案如表5。
若使用传统的静态调度方法，可以得到如下配送方案。
对比表5和表6可以得出，如本算例在车辆发生故障和部分顾客间出现交通中断的情况下，采用本文所提出的动态车辆调度方法可以降低总配送成本130.7元，降低14.6%，显示了本文动态车辆调度方法的有效性。
5 结论
对于需要具备快速响应能力的城市配送问题，本文通过引入虚拟顾客的概念，将实时信息下的动态车辆路径问题转化为经典的静态车辆路径问题。借助GIS、GPS、ITS等技术工具获取实时信息，解决了四种动态事件情形下的配送线路实时优化调度。运用所提出的混合遗传算法求解模型，通过算例测试，与传统的非实时配送方案进行对比，得出该调度方法可以有效地找到实时最短路径、降低配送成本。
实时优化论文 篇5
火电机组锅炉实时控制与优化节能技术,即在火电机组锅炉运行过程中,实时控制与优化其节能技术,提高其节能效率的过程。它可以反映出一个火电单位的生产效率、经营成果,是一个单位综合生产能力的重要体现。
火电机组锅炉是火电单位重要的生产设备。在火电机组锅炉运行过程中,进行实时控制,能够对火电机组锅炉运行过程中发生的排放超标、非计划启停等进行及时补救,或者尽早发现问题的苗头并采取相应措施,将损失降到最低。
1 国内外的锅炉燃烧优化软件产品
Ultramax锅炉燃烧优化系统是美国Ultramax公司所开发研究出的,该锅炉燃烧优化系统是将一组锅炉燃烧情况参数输入其中,这些参数包括烟气排放物、烟气含氧量以及排烟温度等。根据输入的这些参数建立起一个模型,工作人员再利用燃烧优化系统软件进行优化燃烧的操作。
我国邹县电厂已成功引进该燃烧优化系统。当前,全世界利用这个系统的电厂已经有30多个。
NeuSIGHT系统也为美国一家公司所研制的锅炉燃烧优化系统,其主要利用的技术手段是人工智能神经网络技术。NeuSIGHT系统的主要功能是降低氮氧化物的排放量以及提高火电机组锅炉的热效率,该系统在美国的市场占有率是40%。在那些没有进行污染物排放控制的电厂中,NeuSIGHT系统可以在极大程度上降低氮氧化物的排放量,其降低程度最高可达60%。
Power Perfecter系统也是美国一家公司所研制的锅炉燃烧优化控制软件,其是运用神经网络技术而建立起的多个目标的动态控制器。此控制软件可以在一定程度上提高火电机组锅炉的热效率,其提高空间一般在0.5%～2.5%。Power Perfecter系统还可以在一定范围内降低氮氧化物的排放量,其降低程度虽然没有NeuSIGHT系统大,但也在10%～30%之间。该系统还可以使灰飞含碳量降低7%～9%。我国的华电电厂及华能电厂均使用了Power Perfecter系统,运行结果显示这个系统的效果还是比较好的。
还有清华大学热科学与动力工程教育部重点实验室研制开发的OCP3火电锅炉燃烧优化控制软件,该软件是利用神经网络建立的,采用静态优化设计而成。当前,这个软件已经应用于大容量火电机组上。实践表明,该系统可以提高火电机组锅炉运行效率0.5%左右,氮氧化物排放量可以降低10%～20%。
2 火电机组锅炉的实时控制
在2000年国家重点新产品评选中,PID自动整定软件以其优良的性能当选。在负电荷变化幅度比较大的状态下,焦作的AES电力公司的锅炉在420 t/h负荷下运行时,其回路还是可以达到标准要求。主汽压力的偏差标准要求大概在-0.2～+0.2 MPa之间;但如果运用PID系统软件,就可以缩小主汽压力的偏差波动范围,使其在-0.093～+0.088 MPa之间波动,这样的波动偏差只有标准偏差的1/2都不到。汽包水位偏差的标准要求是在-15～+15 mm之间,如果运用PID系统软件,也可以在一定程度上缩小偏差,使之在-10～+10 mm之间波动。
1998年投入运行的淮南平电公司#1锅炉,在额定工况下运行时,其主蒸汽的温度大致能控制在527～551℃范围内。在淮南平电公司#1锅炉的运行过程中,经常超温。淮南平电公司先后6次对其主蒸汽温度自动控制系统进行改造,但都效果甚微。通过使用广义预测控制,在负荷稳定的情况下,其蒸汽温度的波动范围只是在-3～+3℃之间。由此可见,在广义预测控制系统投入运行后,该锅炉的蒸汽温度波动范围在极大程度上缩小了,其波动情况如图1所示。
石横锅炉在额定工况下运行时,其主蒸汽的温度大致上能控制在-10～+10℃的范围内。石横锅炉在运行过程中,是采用二级PID自动整定软件,其经常需要人工操作来防止超温。在使用多模型广义预测控制系统后,这种情况得到了一定程度的改善,其运行变化情况如图2所示。
1—风量(%) 2—煤量(t/h) 3—主汽温(℃) 4一机组功率(MW)
负荷从190 MW到308 MW,主汽温处于(539±3)℃。此前为手动,汽温经常波动在±12℃以上。
3 火电机组锅炉的优化节能技术
位于内蒙古的某600 MW火电机组#2锅炉,其型式为亚临界一次中间再热、四角切圆燃烧、Ⅱ型布置、燃煤汽包锅炉。该电厂#2机组锅炉的设计效率大概是93%,其汽轮机是亚临界、一次中间再热汽轮机,该机组的实际供电煤耗为310 g/kW·h。
位于贵港的某600 MW火电机组#1锅炉,其型式为超临界、一次中间再热、四角切圆燃烧、Ⅱ型燃煤汽包锅炉。该电厂#1机组锅炉的设计效率大概是94%,其汽轮机型式为超临界、一次中间再热凝汽式汽轮机。所设定的机组供电煤耗大概是294 g/kW·h,但该机组的实际供电煤耗为306 g/kW·h。
有许多因素会造成机组锅炉的运行效率低下,大到排烟温度,小到锅炉保温。对机组锅炉燃烧进行优化调整,要结合飞灰可燃物及炉底灰渣可燃物等多种因素考虑。就前面所说的内蒙古某600 MW机组#2锅炉而言,其煤质比较平稳,使用效率较高。针对这种情况,可通过控制进氧量来再次提高其运行效率。如针对贵州电厂的机组锅炉特性,则要通过多种技术的结合,来提高锅炉运行效率,提高煤的使用效率。
有许多因素会造成机组锅炉汽轮机热耗增多,大到主蒸汽温度,小到汽封间隙。对机组锅炉汽轮机燃烧进行优化调整,要结合再热蒸汽及排汽参数等多种因素考虑,最大程度地将汽轮机的汽封安装间隙值降低,并将不同负荷的主汽压力调整到最佳值。同时,将汽轮机从单阀运行方式改变为顺序阀运行方式。
4 结语
在全球工业污染日益严重的今天,在运营中尽量控制排放量、减少污染,对火电单位的可持续发展具有至关重要的作用,因此研究火电机组锅炉的实时控制与优化节能技术具有重要意义。
参考文献
实时优化论文 篇6
需求响应(DR)作为智能电网的重要组成部分，为用户和供应商提供了更多选择，是解决能源价格浮动和能源消耗上涨的一种有效方法[1,2]。DR是通过用户响应电价变化或激励支付，改变其固有的消费模式，减少了用户电力支付，并且保证了系统稳定性[3,4,5]。用户使用的平均电价模式并不能反应实际的消耗价格，因此，针对平均电价的这种不足，提出了实时电价(RTP)、分时电价(TOU)和尖峰电价(CPP)[6,7]。分时电价和尖峰电价一个季度进行一次管理，电价值是提前设定，但为了真实地反映用户实际消耗和公共事业单位的电价水平，需要每小时进行电价的更新与管理，实时电价具有更高的灵活性，每小时对电价进行更新，符合智能家居[8,9]中通过电价的高低进行器具调度的要求。因此，本文中以实时电价为基础，对家庭器具进行优化调度，家庭器具调度系统如图1所示。
优化调度的前提是预测提前一天的实时电价。电价预测的方法有很多种，主要包括时间序列法，神经网络法和组合方法[10,11]。在文献[12,13]中，采用时间序列法(ARIMA)对电价进行了预测，这种方法需要的历史数据少，计算速度快，但是相比于其他方法预测误差较大;在文献[14]采用神经网络(NN)对实时电价进行电价预测，虽然神经网络方法相比于时间序列法预测精度得到了提高，但是当每个小时电价值的变化相差较小时，仍会影响预测效果。本文为了更加精确地预测实时电价，以西班牙的历史电价为基础[15]，采用小波、微粒子群和自适应神经网络模糊推理系统(Wavelet-PSO-ANFIS,WPA)组合的方法预测实时电价。通过与其他电价预测的方法(ARIMA,W-ARIMA,NN)比较，表明了本文采用的这种电价预测方法在不牺牲计算复杂度的前提下，大大提高了电价预测精度。
其次，关于家庭器具的优化调度，学者也在不断的研究。文献[16,17]中通过不同的优化调度方法，减少了用户的电力支付，把保证了系统的稳定性，但是忽略了对用户舒适度的考虑;文献[18]中通过结合可再生能源的可用性预测和市场电价预测技术，为家用电器分配动态优先权，实现智能家居能源消耗的有效管理和调度，但是缺乏节能与体验质量的均衡性考虑与分析;文献[5,19]提出的优化调度算法权衡了用户的电力支付与用户的舒适度。但是以上的研究中均没有考虑器具的特殊性，没有针对家庭中不同器具的特性，考虑用户对不同器具延迟或者提前的影响。
针对器具的工作时长不同，文中提出了一种相对量化用户舒适度的方法，采用该方法解决了用户对不同器具延迟或者提前产生不同敏感度的问题，应用数学方法衡量了用户对不同器具的满意度。本文建立了关于用户电力支付和用户舒适的线性规划模型，通过优化调度有效地权衡了用户的电力支付与用户的舒适度，降低了系统的峰均比，保证了供电方系统的稳定性。
2 实时电价预测
准确的电价预测对于供应商和用户都存在重大意义。供应商利用预测的电价来策略投标，风险评估和制作投资计划等;用户则根据预测的电价重新安排器具。
2.1 利用WPA进行实时电价的一般步骤
WPA方法是一种混合方法，在电价预测中小波、PSO和ANFIS对于提高预测精度各有不同的用途。其中，小波转换将价格序列转换为一系列基本序列，这些基本序列比原始的价格序列表现出更好的性质，因此，可以更加精确地预测。它用在电价预测的第一阶段和最后一阶段。ANFIS结合了NN的自我学习能力和模糊推理的语言表达能力，应用于非线性预测，利用过去的样本来预测未来的样本，而PSO用于提高ANFIS的性能，调整隶属函数来实现低的错误。电价预测的具体步骤如图2所示。
第一步:价格序列的分解。对价格序列按照小波分析法进行分解，得到高频序列和低频序列。
第二步:高频和低频序列的预测。对每个序列进行预测时，首先确定PSO的种群大小，用初始化的种群代替ANFI的前件参数，根据前件参数计算后件参数的值，从而计算网络误差，将该网络误差作为粒子群的适应度值。接着更新粒子的速度和位置从而得到ANFIS的各参数。最后利用ANFI对这些序列逐步训练以确定最佳模型，通过该模型预测所有序列。
第三步:将预测的序列重构为原来序列的预测值。
2.2 利用WPA预测西班牙的实时电价
本节选取西班牙2013年3月到5月的电价作为训练数据，预测出2013年6月1日07:00到6月2日06:00的24小时的电价。PSO的参数设置如表1所示。图3是利用文中提出WPA方法预测的电价与实际电价的对比图。
2.3 不同的实时电价预测方法
根据式(1)计算了ARIMA、W-ARIMA、NN和WPA的平均绝对百分比误差(MAPE)。由表2数据可知，文中提出的WPA的预测效果优于其他几种方法。
式中:Ch是实际的电价，C'h是预测的电价。
2.4 电价模式
为了防止用户在低电价时段开启大量器具，本文中采用实时电价与斜坡块率(IBR)结合的电价模型
式中:mh和nh是根据能耗划分的阶梯型电价，nh>mh;Emax,h为时隙h的能耗上限;lh表示每时隙的总能耗，
3 优化调度模型
根据器具自身特性和用户的行为习惯，将家庭器具进行分类:非实时器具和实时器具。为了满足用户需求器具运行时间不能延时，当器具到达运行时间后必须马上开启，这类器具被指定为实时器具，例如:电视、电脑、电灯等;而热水壶、洗衣机、电饭煲等家庭器具可以根据所接收到的电价信息调度操作时间，减少电力支付，这类器具被称为非实时器具。将家庭器具的优化调度范围设定为一天(2013年6月1日07:00到6月2日06:00)，利用H表示优化调度空间，则调度时隙h∈[1,2，…，H]。A表示非实时器具，对于每个器具a∈A，在时隙h的能耗是ea,h。
3.1 目标函数
目标函数的目的是最小化用户的支付成本，包括电力成本和用户舒适度成本。
3.1.1 用户电力支付
在所预测的实时电价基础上，用户的电力成本被公式化为
3.1.2 用户不满意度
由于家庭中不同器具的工作时长不同，为了权衡用户对不同器具的满意度问题，我们提出了一个量化舒适度的方法，即在用户可以容忍器具的工作时段内，利用优化调度后器具的工作时隙和用户最满意器具的工作时隙的相对距离与用户可容忍器具工作时隙总数之比来表示用户的满意度
式中:ψa是器具a优化调度后的实际开启时隙;γa是用户最满意器具a的开启时隙;la是器具a工作完成需要的总时隙数;λa是器具a在舒适度成本中所占的权重，λa=w/la;Za表示用户对器具a的不满意度;Z表示用户的不满意度。
3.2 约束条件
为了满足目标函数，达到最小的用户电力支付成本与用户的舒适度成本，需要满足以下约束条件。
3.2.1 能耗约束
在调度过程中为了保证器具a可以完成操作，所需的能源是
式中:αa和βa分别表示用户能够容忍的器具a运行的开始时隙和结束时隙;Ea表示器具a完成操作需要的总能耗。
为了保证系统的稳定，每个时隙器具的能耗有限，假设Emax,h为时隙h的最大能耗上限
3.2.2 舒适度约束
为了保证用户的舒适度，每个器具的不满意度需要小于用户对该器具的最大不满意值m
3.3 线型规划模型
结合式(3)和式(5)，本文中提出的用户支付的目标函数为
由于式(9)是不可微分的，所以将目标函数(9)进行优化。结合式(2)，每个时隙的电力支付被重新公式化:
当h时隙家庭器具的能耗0≤lh≤Emax,h时，用户的电力支付Pa为
当h时隙家庭器具的能耗lh>Emax,h时，用户的电力支付为(11)
因此
引入二进制决策变量xa,h，当xa,h=0表示器具a在时隙h开启;xa,h=1表示器具a在时隙h关闭。则式(11)被重新公式化为
通过上述变换，所提出的最小支付的调度问题被公式化为如下整数线性规划模型
式中:w1,w2分别为电力成本与舒适度在成本支付中的权值，w1+w2=1。
4 仿真验证
这一部分，利用计算机软件MATLAB和CPLEX仿真验证来评估提出的基于电价预测的家庭器具优化调度方法的性能。假设住宅在仿真过程中器具的参数设定如表3所示。时隙长度为10 min，则时隙t∈T=[1,2,3，…，144]。假设本文中所有器具的运行时间均为用户能够容忍的器具的工作范围。
4.1 电力成本与不满意度的关系
通过表4中的3种案例来说明用户不满意度与电力成本的关系。案例1:首先假设用户对器具的不满意度上限m=2，考虑用户的电力成本，即w1=1,w2=0时，对家庭器具进行优化调度。图4是经过优化调度后器具的实际操作时隙。然后将表3与图4中数据带入式(4)可以得出每个器具的不满意度值，如表5所示。此时，用户的不满意度Z=3.072，用户的电力支付Pa=50.95 cents;案例2:只考虑用户的最小电力成本，不考虑其他两个因素，即w1=1,w2=0时，m可以无限大，则用户不满意度Z=5.357，用户的电力支付Pa=41.39 cents;案例3:不考虑m与Pa，只考虑用户的不满意度，即w1=0,w2=1，此时不满意度Z=0，用户的电力支付为65.89 cents。
通过比较以上3种案例，发现用户的电力支付与用户的不满意度成反比。因此，可以通过对器具的优化调度来权衡用户的电力支付与用户的不满意度。
4.2 量化舒适度的影响
以上一节中案例1为对象说明本文中所提出的相对量化舒适度的性能。根据表3中的数据可知，电饭煲的实际开启时间比用户最满意的开始时间提前了6个时隙，而电动汽车的实际开启时间比用户最满意的开启时间延后了18个时隙。通过文献[5]中的方法，单从时隙方面来看，电动汽车对用户造成的影响较大。但是，电动汽车的工作时长相比于电饭煲要长，只采用这种方法无法准确衡量用户的满意度。所以采用本文中提出的相对量化方法，可以得出电动汽车的不满意度是3/4，而电饭煲的不满意度为2，如表5所示。因此，电饭煲开启时间的改变相比于电动汽车对用户的影响较大。
这种针对不同的器具特性，采用相对量化的方法，可以更加准确的衡量出器具延迟或者提前对用户造成的影响，提高用户的舒适度。
4.3 用户的支付成本
以上一节中案例1为例，说明优化调度对系统性能的影响。本节通过用户的电力支付评估文中提出的优化调度方案的性能。图5中显示出优化调度前与优化调度后用户的电力支付从65.89美分降低到50.95美分，降低了22.67%。图6中表明了一个月内用户每天优化调度前与优化调度后的电力支付，一个月内用户的电力支付从20.32美元降低到15.98美元。
利用式(15)计算系统的分均比可知，通过使用优化调度算法系统的平均PAR从5.65降低到4.57，降低了19.1%。
仿真结果表明利用文中所提出的优化调度算法不仅可以减少用户的电力支付，还可以降低系统的峰均比，保证系统的稳定性。
5 结束语
本文将WPA电价预测方法应用到智能家居中的实时电价预测。这种方法不仅保证了电价预测的预测精度，还保证了所预测电价的实时性。在预测的实时电价基础上，提出了一种家庭器具的优化调度算法，权衡了用户的电力支付与用户的舒适度问题，并且在文中提出了一种相对量化舒适度的方法，解决了器具由于工作时长不同，造成的用户对不同器具延迟或者提前工作产生不同影响的问题。
摘要：针对家庭器具优化调度中电价预测误差高和用户舒适度衡量偏差大的问题,提出了一种基于小波、微粒子群和自适应神经网络模糊推理系统(Wavelet-PSO-ANFIS,WPA)电价预测的家庭器具优化调度算法。并在该算法中针对器具运行时长不同的问题,提出了一种新颖的相对量化舒适度的方法。仿真结果表明,此电价预测方法在不牺牲计算复杂度的基础上提高了预测精度,不仅可以权衡用户的用户支付和不满意度,还可以降低系统的峰均比。
实时优化论文 篇7
自动化立体仓库以高层货架、 搬运设备和控制系统为三要素, 是以物联网技术为基础的现代物流系统重要组成部分[1]。在影响其作业效率的诸多因素中, 出入库调度策略是影响系统运行过程执行效能的关键。 作为 出入库作业调度的核心环节, 堆垛机任务调度建模与优化主要研究以满足约束条件为前提,对堆垛机作业任务按照运行路径最优、执行时间最佳进行排序,以便缩短立体仓库货位的运转周期和提高立体仓库设备资源的利用率。
目前国内外在堆垛机调度算法方面, 通常采用的方法有部分枚举法、启发式规则法、遗传算法、模拟退火算法和模拟仿真方法等[1,2],这些方法从不同角度解决较小规模的堆垛机任务调度问题, 但难以应对较大规模的问题求解。例如,西安理工大学的徐香玲等人将专家系统知识库思想应用于自动化立体仓库的作业调度和货位分配, 但在大问题空间的求解方面存在一定局限性[1];山东工业大学的田国会、 刘常有等采用模拟退火算法等对影响自动化立体仓库实际运行效率的若干调度问题进行模拟仿真优化研究,但在实际中不一定是最好的[3];天津大学的杨华等人将堆垛机作业调度抽象为TSP旅行商问题,采用遗传算法获取作业调度最佳路径, 提供了求解复杂调度问题的通用框架, 但在很多方面还存在进一步改进的要求[4];黄杨波等人通过改进初始种群的遗传算法提高双伸位堆垛机的运行效率, 但难以解决多堆垛机的调度优化问题[5];Donald Tepas采用知识信息系统,针对自动化立体仓库中的调度问题进行辅助决策, 但需要进一步提高搜索算法的效率[6];Kim Byung等针对自动化立体仓库中的货位拣选问题, 设计了可用于调度控制的复杂智能Agent结构,但Agent设计难以满足堆垛机的复杂任务[7]。 这些方法从不同角度解决较小规模的堆垛机任务调度的最优解问题, 但是当问题规模逐渐增大时, 这些算法在求解最优解方面就体现出自身的一些局限性。
1 堆垛机出入库调度问题
在生产物流系统中, 立体仓库中的各种资源可保证各生产工序间的有序生产, 但需通过堆垛机等搬运设备进行合理调度, 实现任务作业顺序的组合优化。 堆垛机作为立体仓库中货物出入库搬运的重要设备, 主要功能如图1所示。
图1中某生产物流系统自动化立体仓库设计为 6 巷道,每巷道 2 排货架;每排货架8 层 10 列, 每台堆垛机均为单叉双向, 负责对应巷道货架的出入库任务, 所有堆垛机初始状态均位于入库站台一侧。 出入库站台分布在立体仓库的两端, 由堆垛机负责从入库站台搬运货物到指定货位点, 或者从指定货位点搬运货物到出库站台,完成出入库任务,满足生产工序的要求。
堆垛机搬运货物出入库的流程主要包括:首先,堆垛机接到生产线上一批货物的出入库指令;然后,如果执行入库指令,则把货物从入库站台搬运到指定货位点,反之,如果执行出库指令,则把指定货位点上的货物搬运到出库站台;最终,堆垛机反复执行出入库指令直至完成所有任务。 一般堆垛机在执行指令时有两种方式: 单一工作模式和复合工作模式[2]。
单一工作模式指某巷道内某堆垛机仅执行出库指令或仅执行入库指令, 且堆垛机每次作业仅能装卸一件货物。 在单一工作模式下, 堆垛机的总运行路径和总执行时间是固定的,不受指令系列执行顺序的影响,不存在调度效率高低的问题。
复合工作模式指某巷道内某堆垛机混合执行出入库指令系列, 既包括出库指令又包括入库指令, 且堆垛机每次作业仅能装卸一件货物。 出入库指令的执行顺序将影响堆垛机的总运行路径和总执行时间, 最终影响调度效率的高低。
图2假设在复合工作模式时某巷道内某堆垛机出入库指令序列组成和指令执行顺序均为随机,堆垛机的入库站台为A、出库站台为a,横坐标表示某巷道内某货架的列号,纵坐标表示某巷道内某货架的层号,某货架内任意货位用方格表示, 可描述为二维坐标(i,j),其中i表示某货架的列号,j 表示某货架的层号,堆垛机仅允许从入库站台入库与从出库站台出库,实圈代表要出库的货物所在货位点,空圈代表要入库的货物到达货位点, 假定堆垛机的运行速度一定,采用不同的出入库指令序列调度策略,堆垛机的总运行路径不同,总执行时间也不同。
图2中堆垛机出入库指令序列包括入库指令I1和出库指令O1, I1入库货位点为M(5,6),O1出库货位点为 N(3,6),从而存在不同的调度策略 S1(先执行I1,再执行O1)和S2(先执行O1,再执行I1),其相应的运行路径分别为L1和L2,假定每个货位均为标准长宽2×2,则:
L1=LAM+LMN+LNa+LAa=
2(6+5+2+5+4+10)=64
L2=LAN+LNa+LaA+LAM+LMA =
2(8+5+5+2+10+6+5+5+6)=104
其中,LAM指调度策略S1执行I1时所走的路径长度, 水平方向上从入库站台A行进到货位5列, 垂直方向上从货位1层行进到货位6层;LMN指堆垛机完成 I1后转去执行O1所要走的路径长度,水平方向上堆垛机先从货位5列行进到货位3列, 垂直方向上没有移动;LNa指到达要出库的货位点取到货物后所走的路径长度,水平方向上从 3列行进到出库站台, 垂直方向上从6层行进到1层;LaA指堆垛机返回到原始出发点所要走的路径长度, 总路径长度为64。 调度策略S2运行路径的计算方法与S1类似, 因篇幅有限, 在此不再赘述, 相应结果 L2为104。由结果比较得知,调度策略S1优于S2。
如果某堆垛机收到包含n条出入库指令的任务, 其中, 入库指令p条,出库指令q条,p+q=n,则该堆垛机采用不同调度策略的总路径长度执行n条指令所需要的路径长度为如公式(1)所示:
在公式(1)中,LA,i表示堆垛机从入库站台 A 出发执行入库指令 i,将货物从入库站台搬运到指定货位点的路径长度;Lj,a表示堆垛机执行出库指令 j,将货物从指定货位点搬运到出库站台 a 的路径长度;r表示入库指令和出库指令交替执行的次数; Lk表示堆垛机执行完入库指令i之后,到指定货位点执行出库指令j的路径长度;La,A表示堆垛机从出库站台回到入库站台的路径长度。
堆垛机运行路径长度的第一部分
2 堆垛机任务调度混合算法
旅行商问题是尚未彻底解决的组合优化问题之一,属于 NP 完全问题范畴。计算复杂性是这一类问题的难点,NP 完全问题算法最坏情况下均为指数级时间复杂度[9]。
遗传算法和模拟退火算法是目前解决旅行商问题的主要策略[10];遗传算法较易获得全局最优解,但局部优化能力相对较弱, 且收敛性较差;模拟退火算法较易获得局部最优解,但参数难以确定, 且执行时间随问题规模的增大呈指数级增长[11]。 本文采用遗传—退火混合算法解决 TSP 问题,其算法流程[12,13]如下所示:
①参数初始化: 根据任务指令序列和任务量, 确定混合算法的初温和初始化种群数。
②评价种群中个体: 判断种群中连续几代个体的差异是否收敛于设定的阈值, 收敛则得到最优的输出结果, 如果不收敛则执行第③步。
③执行遗传算法: 遗传算法的复制、 交叉、 变异操作, 得到模拟退火算法的初始种群。
④执行模拟退火算法: 利用模拟退火算法对第③步得到的初始种群进行抽样操作, 根据模拟退火算法状态生成函数生成新个体, 用约束条件判断生成的新个体。
⑤稳定性检测: 根据模拟退火算法进行稳定性检测,不稳定继续执行第④步,否则退温执行第②步操作。
3 混合优化算法仿真
假定货位形态为固定箱体, 大小为固定值(长宽高均为 2m) ,堆垛机的水平运行速度为Vx=2.5m/s , 垂直运行速度为Vy=1.5m/s,堆垛机货叉取货送货速度为定值,在仿真计算时忽略不计。
假定某堆垛机在复合工作模式下接收到含15条指令的任务, 其中7条入库指令,8条出库指令,如图3所示,可得出入库指令中各货位点的坐标值,具体如表1所示。
在Matlab中分别采用遗传算法、模拟退火算法和混合算法,得到执行这15条指令的最优路径分别如图4所示。 根据图4计算结果, 执行这15条指令的平均路径长度,最优路径长度以及计算迭代次数如表2所示。
由图4的仿真结果可以得出结论, 在计算最优路径方面, 混合算法比任何一种单一算法更有效,同时由表2可以看出,在计算平均路径长度和迭代次数方面混合算法比单一的遗传算法和模拟退火算法更具优越性。
4 结束语
通过对生产物流系统自动化立体仓库中堆垛机任务调度问题设计系统模型, 分析并将其抽象为 TSP 问题,采用遗传—退火混合算法求解最优调度方案, 仿真实验结果表明混合算法比单一遗传算法或模拟退火算法在计算性能和最优值求解方面更具优越性,一定程度上提高了调度效率,优化了堆垛机任务指令的执行路径。 遗传算法在堆垛机任务调度方面还可与其他算法结合, 但遗传—退火混合算法表现出来的优越性,使其在堆垛机任务调度优化方面有较好的研究价值,值得进一步的研究。
摘要：堆垛机任务调度是自动化立体仓库提高作业效率、实现智能控制的核心要素之一。首先建立堆垛机实时调度系统的任务指令模型,进而将模型求解抽象为作业路径长度最短的旅行商TSP问题。利用遗传—退火混合算法解决TSP问题,根据混合算法特点设计算法流程,运用数学工具进行任务调度方案仿真,结果证明遗传—退火混合算法比单一的遗传算法或模拟退火算法在最优路径求解和时间耗费上具有优越性。