堵塞恢复时间未知的可恢复加拿大旅行者问题研究

加拿大旅行者问题是指旅行者针对行走过程中遭遇的突发性道路堵塞,如何设计一个有效路径选择策略,使得旅行者从出发地抵达目的地行走时间尽可能少的问题.从在线问题与竞争策略的角度,考虑每个堵塞恢复时间未知且相互独立的情形,给出了每个堵塞恢复时间为三角模糊数下的等待策略和贪婪策略及竞争比,并对策略执行效果进行了分析与比较.     

一类带时间窗车辆分配问题的贪婪算法

本文对一类带时间窗的车辆分配问题进行了分析,引入了车辆任务的概念,并将问题转化为车辆与车辆任务的匹配问题,同时制订了运输任务选择和车辆选择的贪婪策略,并在此基础上设计了车辆分配问题的贪婪算法,最后通过实例验证了算法的有效性。     

基于动态VaR约束与随机波动率模型的最优投资策略

研究Stein-Stein随机波动率模型下带动态VaR约束的最优投资组合选择问题. 假设投资者的目标是最大化终端财富的期望幂效用,可投资于无风险资产和一种风险资产, 风险资产的价格过程由Stein-Stein随机波动率模型刻画. 同时, 投资者期望能在投资过程中利用动态VaR约束控制所面对的风险.运用Bellman动态规划方法和Lagrange乘子法, 得到了该约束问题最优策略的解析式及特殊情形下最优值函数的解析式; 并通过理论分析和数值算例, 阐述了动态VaR约束与随机波动率对最优投资策略的影响.     

基于指数分布的可恢复加拿大旅行者问题的策略研究

针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量且服从指数分布的情形,从在线问题与竞争策略的角度,给出了等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较.     

随机环境下堵塞可恢复的旅行者问题策略研究

针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量的情形,从在线问题与竞争策略的角度,给出了每个堵塞恢复时间都为正态分布下的等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较。     

客户动态变更配送需求的配送路线优化研究

针对物流配送途中客户动态变更配送需求问题,分别研究了满足客户临时变更收货时间窗、收货地址和取消收货的三种要求时所需成本相较于预先设计配送路径所需成本的波动值,建立了客户临时变更配送需求的动态管理模型.基于嵌套分割算法,设计了邻近救援策略、最佳离库策略、增派车辆策略对模型进行求解.最后,通过算例试验,证明模型可以有效的降低物流配送成本,且具有更强的实用性、灵活性,且嵌套分割算法还在数据优化、计算时间上有显著成效.     

考虑顾客退货和固定成本的联合补货与定价策略

为了吸引更多顾客,许多电子商务零售商允许顾客在一定时间内退货,导致其利润明显减少。同时,在补货时不仅产生依赖补货量的变动成本,而且会产生与补货量无关的固定成本。基于此,以最大化电子商务零售商的利润为目标,建立考虑顾客退货和固定成本的联合补货与定价模型,其中顾客的退货量与满足的需求呈正比。在一般需求情形下,部分刻画多期问题的最优策略;在特殊需求情形下,证明(s,S,p)策略对单期问题最优,并对多期问题的最优策略进行严格刻画。根据已有刻画为多期问题构造启发式策略。数值结果表明启发式策略近似最优;当初始库存水平足够高/低时,最优补货水平和定价随退货率与固定成本单调变化。关键词:联合补货与定价模型;顾客退货;固定成本;随机动态规划;最优策略     

通胀市场下的风险补偿在线租赁策略设计

考虑到实际租赁市场中设备的租赁和购买价格随着时间推移持续上涨的特征,研究了通货膨胀市场中的租赁问题在有利率情形下的在线竞争策略,并建立了相应的概率预期的风险补偿模型。首先运用在线算法和竞争分析理论设计了该问题的最优竞争策略,并给出最优竞争比。接着,在风险补偿竞争分析框架下,进一步讨论该问题,投资者可以控制风险,根据自己不同的风险容忍度和未来预期选择补偿最大的租赁策略;也可以根据给定的补偿收益约束选择风险最小的策略。最后通过数值分析,验证了相关结论的正确性,也表明了基于概率预期的风险补偿策略大大改善了该租赁问题的竞争比性能。     

基于移动机器人的拣选系统货架动态储位分配研究

为了提高基于移动机器人的拣选系统拣货效率,更好地满足客户动态需求和订单时效要求,提出了考虑货架后续需求频次、需求紧迫程度以及拥堵因素的货架动态储位分配策略,构建了最小化货架搬运距离的动态储位分配模型,并设计了启发式算法进行模型求解.首先,基于货架需求紧迫程度,构造贪婪算法生成动态货架储位分配的初始解;然后,基于货架在后续批次订单的需求频次及通道间负载均衡,采用邻域搜索算法进行动态货架储位优化.最后,通过与其他静态和动态储位分配方法对比,验证文章提出的模型和算法的有效性.     

供应链中需求在线的库存问题研究

考虑一个生产商和两个零售商之间的数量折扣问题,针对顾客需求量不确定时,生产商采用数量折扣策略鼓励零售商提高单次订货量,从而降低库存成本的决策问题,从在线算法与竞争分析的角度出发,结合零售商的议价能力这一因素,分别考虑两个零售商之间合作与非合作时的情形,设计了相应的平衡策略,并证明该策略为最优策略.     

基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。     

混合动力公交车能量控制策略的优化模型

针对混合动力公交车在循环工况内功率需求的特点,建立了未来功率需求贝叶斯预测模型;利用2-阶段随机动态规划模型将大规模的随机动态规划问题简化为多个小规模的随机动态规划问题和一个确定型动态规划问题;对于随机动态规划模型的求解,给出了稀疏表示的降维方法,将复杂的泛函极值问题转化为常规的随机动态优化问题,并采用分布估计算法和计算资源最优配置算法的计算机仿真优化算法对随机动态优化问题进行求解;给出了基于查表的在线控制策略,为模型的实际应用进行了有益的探索。     

基于订单采购模式的销售商在线采购策略

对于按订单采购的销售商而言,采购成本和延误成本是影响总成本的主要因素,销售商需要采取适当的采购策略,权衡二者,以使总成本尽量小.文章首先给出了订单需求完全已知情况下的离线最优策略,并指出策略的计算复杂性为O(n2).其次,针对订单需求难以预测的情形,设计了相应的在线采购策略,证明了该策略的竞争比为2;同时,证明了该问题的竞争比下界为((√5)+1)/2＞1.618.     

在线住房出租问题及其竞争策略

本文研究了投资者不确定其持有房产时间的在线住房出租问题。为了增加收益,投资者在抛售房产前可以选择出租毛坯房或装修后出租策略最大化利润。本文从出租人角度运用在线算法建立住房在线出租模型,分析了投资者的竞争策略与竞争比。在线住房出租模型分析发现:最优的在线策略并不一定从毛坯房出租转换到装修后出租,出租人首先需要权衡装修成本与装修后单周期的收益,只有当装修后单周期收益高于装修成本时,在线出租策略才存在最优的转换时机。研究结论对在高度不确定环境下开展经营活动的租赁公司下一步策略选择具有启示意义。     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

基于AGV的智能仓库系统订单分批问题研究

研究了基于自动引导小车(AGV)的“货到人”智能仓库订单分批拣选问题, 在同时考虑工作人员拣选商品成本和AGV搬运货架成本的前提下, 建立了以总成本极小化为目标函数的订单分批问题整数规划模型。根据订单中包含的商品信息和商品所在的货架信息构建了描述订单之间关系的加权相似度指标, 分析了加权相似度与总拣选成本之间的正相关关系。基于订单之间的加权相似度设计了求解模型的贪婪算法。利用具体算例进行模拟计算, 分析了加权系数的变化对订单分批结果的影响, 以及加权系数λ的取值与工作人员拣取一件商品的成本c₁和AGV搬运一次货架的成本c₂之间的关系, 得到了贪婪算法中加权系数λ的确定方法。进一步分析了贪婪算法的计算时间和计算效果, 结果显示, 通过适当选取加权系数, 利用贪婪算法可以在短时间内得到订单分批问题的近似最优解;对于小规模算例, 贪婪算法在最坏情况下近似比不超过1.35。利用本文的模型和算法进行订单分批, 兼顾了工作人员拣取商品的成本和AGV搬运货架的成本, 可以有效提高订单拣选效率, 降低订单拣选总成本。     

基于两阶段混合动态规划算法的龙门吊路径优化

产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。     

考虑无缺陷退货的在线商品信息发布策略

消费者网络购物面临的不确定性往往导致非质量原因的退货。合理发布产品信息,并提供退货保障,是网络零售商促进消费者购买和提高利润的有效策略。基于消费者效用理论和博弈论,构建了产品信息影响消费者购买和退货模型,研究了零售商在垄断和竞争情形下的产品信息发布决策问题,发现垄断性零售商的最优信息发布策略和竞争性零售商在发布产品信息量和信息内容方面的均衡策略均取决于产品价值和退货成本特征,提出了不同市场结构下基于产品特征的在线商品信息发布策略。     

考虑商品数量和商品拣选成本的AGV智能仓库订单分批问题研究

AGV(Automated Guided Vehicle,自动导引车)智能仓库是一种基于“货到人”拣选模式的自动化仓库。本文考虑了订单中商品的需求量和货架上商品的存储量,以极小化货架搬运成本和商品拣选成本为目标,建立了AGV智能仓库订单分批问题的整数规划模型。本文针对订单分批问题的特点,提出了一种基于订单和货架交替选择的贪婪求解算法。对比CPLEX求解器的精确最优解,本文提出的贪婪算法的误差百分比不超过10%,平均误差百分比为5.38%;对比基于相似性的分批算法的求解结果,本文提出的贪婪算法不仅运算时间更短,解的质量也更好。进一步地,对比不考虑商品拣选成本的订单分批模型,本文提出的模型在不明显增加货架搬运成本的前提下,可以大幅度降低商品拣选成本。因此,在订单分批模型中考虑商品拣选成本是非常必要的。     

统计信息下在线反向拍卖的竞争分析

对于投标具有统计特征的在线反向拍卖问题,利用在线算法与平均情形竞争分析相结合的方法,讨论了单一定价策略的平均情形最优单一定价及其竞争性能,提出了无限可分商品在线反向拍卖的平均情形竞争分析策略,基于此策略建立了具有均匀分布特征的在线反向拍卖模型,通过对模型求解得到了采购商的竞争需要曲线。与不考虑投标的统计信息、只是利用常规的最坏情形竞争分析得到的在线反向拍卖的竞争策略进行对比分析,发现统计信息的利用提高了在线反向拍卖策略的竞争性能。