具有服务时长的在线TSP问题

针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.     

堵塞点可恢复型在线运输车辆的调度策略研究

针对现实物流配送中所遇到的无法预测的突发性线路堵塞问题,以在线车辆行驶的时间最短为优化目标,用竞争分析的方法研究了堵塞点可恢复型在线车辆的调度策略.充分地考虑到堵塞点的动态特征,分别介绍了在线运输车辆调度的贪婪策略、复位策略和等待策略等方案,并系统分析了这三种基本策略在竞争性能上的利弊,给出了选择策略及其算法模型.通过对选择策略的竞争比和竞争性能的分析,结果表明选择策略实现了对在线运输车辆的优化调度.     

基于物价指数上涨的最优在线租赁决策模型

考虑到现实租赁市场设备租金费用及购买价格随着时间推移总体呈现出持续性上涨特征, 建立了基于物价指数上涨的在线租赁决策模型, 首先分析了该问题的最优离线策略, 其次运用在线算法理论给出了该问题的确定性最优在线租赁策略及其竞争比. 从提高策略的竞争性能角度出发, 基于风险控制思想, 给出了该问题的随机性最优在线租赁策略及其竞争比, 并运用两人零和博弈分析技巧严格证明了此策略是该问题的唯一随机性最优竞争策略. 进一步指出了确定性和随机性最优策略的竞争性能均随着购买价格上涨而下降, 也随着物价指数上涨而降低. 最后, 结合数值分析发现当存在通货膨胀因素时, 最优决策日期相对提前, 但策略的竞争性能显著降低, 这表明物价指数变动对在线租赁决策具有显著影响.     

特殊在线优惠卡问题及其竞争分析

商家在策划优惠卡发行时需要严密论证发行价格和折扣率等因素对消费者消费行为的影响. 利用在线算法和竞争分析理论, 研究了消费者对同时发行的两种优惠卡的在线决策问题. 一方面得到了最优确定性策略及其竞争比; 另一方面构造了一个随机性策略, 得到了最优随机性策略竞争比的一个上界, 并利用Yao引理得到了随机性策略最优竞争比的一个下界. 借助于数值算例, 分析了各因素对在线策略及其竞争比的影响. 研究结果可以为优惠卡发行价格和折扣率的决策提供依据.     

离散型两斜率在线租赁问题

两斜率在线租赁问题是经典的在线租赁问题的一种自然的推广.基于在线租赁问题的研究分为离散时间和连续时间,鉴于已有文献对连续时间情况下两斜率在线租赁问题进行了讨论,本文研究离散时间情况下两斜率在线租赁问题.我们的讨论包括确定性竞争策略和随机性在线策略.关于确定性策略,一个竞争因数为2-[1+(s-1)a]/s的最优策略被给出.对于随机性策略,本文提出了风险均衡策略,并通过竞争分析的方法证明了该策略是唯一最优策略.最后,对两种策略的竞争性能做了分析和讨论·分析和讨论的结果表明:考虑两斜率能改善经典问题的竞争比,考虑离散性能比连续性提高决策效率.     

可分资产的在线租赁策略及其竞争分析

基于现实租赁活动中有许多租赁现象属于连续可分资产的在线租赁问题,应用在线问题之竞争分析的方法讨论了其在线租赁的最优决策方案.首先针对所租赁资产连续可分的特点,提出了风险控制策略.其次通过竞争比理论分析证明了风险控制策略是该问题唯一最优策略,而且得到了最佳竞争比.同时给出了具体租赁过程中每期的购买值和租用值的计算公式,为实际应用提供了方便.最后通过数值分析,进一步阐释和显示了风险控制策略的最优竞争性能.     

限制信息条件下基于时间窗的占线装-卸货问题及其竞争分析

提出并研究限制信息条件下基于时间窗的占线装一卸货问题。客户在提出服务请求时只指定需要承运的货物的装载地，而没有提供目的地信息，服务车只有在到达装载地之后才知道目的地的具体位置，如现实中的出租车调度和电梯调度等问题。就两种度量空间对限制信息条件下带时间窗的占线装一卸货问题进行了分析，分别给出了两种竞争策略及其竞争比结果，并得到了针对该问题的任何确定型算法的竞争比下界。     

基于方格路网的两车应急救援路径在线选择

针对方格路网上道路堵塞的位置和数量信息不完全的情形, 本文研究了两辆应急救援车的在线路径选择问题, 使得最多有k条边堵塞时, 至少一辆车尽快到达事故点进行救援. 根据网络的特点, 对两车分别设计了 横向优先和纵向优先的在线路径选择策略, 通过竞争分析法得出该在线策略 的在两种情形下的竞争比: 出发点和事故点在同一条直线上以及出发点和事 故点不在同一条直线上, 并证明两种情形下的竞争比均是紧的; 最后说明了 该在线策略在某些情形下的最优性.     

有限预知信息下集装箱码头泊位与岸桥联合在线调度北大核心CSCDCSSCI

针对码头船舶作业计划中通常存在较大比例的、需要临时排班的加班船需求,提出了具有有限预知信息的集装箱码头泊位与岸桥联合调度over-list在线模型。在分配每艘船舶服务请求时假设预知后续一个船舶请求的信息,并着重考虑了由3个相连泊位组成的混合型泊位类型、配置5个岸桥且只存在两种请求的联合调度模型;针对最小化最大完工时间的优化目标,设计出了具有最优竞争比5/4的联合调度在线策略;同时,证明了当缺少预知能力时不存在竞争比小于4/3的在线策略。上述结论表明,有限的预知能力可以有效地改进联合调度策略的竞争性能。数值实验结果进一步验证了所设计策略具有良好的执行性能。     

基于凸情形下在线设备更新问题的竞争分析

市场以在线的方式给出新设备,决策者必须决定是否更新现有的设备,并确定何时更新？即在已知现在和过去的设备信息和订单信息而对未来信息一无所知情况下,决策如何更新设备完成陆续达到的订单需求.优化目标是使设备更新投资成本与设备运行成本总和最小.首先讨论了离线设备更新问题, 给出了两种算法并分析了算法复杂度.其后, 讨论了凸情形下在线设备更新问题, 给出了临界值策略,得出了竞争比为6, 证明该策略要优于原有的策略.     

具有时间窗的局内开放式车辆调度的竞争分析

基于k-卡车问题和局内运输问题，提出了具有时间窗的局内开放式车辆调度问题．该问题的优化目标为：在服务需求的发布为局内方式的条件下，如何最小化完成整个服务需求序列的时间跨度．建立了该问题的数学模型并对有关的概念和参数进行了定义和说明．研究了当车辆数为1时该问题的竞争分析的有关结果：给出并证明了对于该问题的竞争策略的竞争比下限；针对该局内问题，设计了两种不同的竞争策略，得到了相应的竞争比，并进行了理论证明．     

多产品多阶段报童问题的在线订购策略

利用集成专家意见的在线序列预测算法研究多产品多阶段报童问题.将任意的一个固定订购量策略看成一个专家意见,用弱集成算法综合考虑众多专家意见构建在线订购策略,并基于弱集成算法的竞争性理论给出在线订购策略的理论保证.首先给出了两产品多阶段报童问题的在线订购策略,证明了其实现的累积收益可与最优固定订购量策略实现的累积收益相当.然后,将两产品多阶段报童问题的在线订购策略及其理论结果推广到多产品多阶段报童问题中.最后在不同的需求类型下,通过数值算例表明构建的在线订购策略相对于最优固定订购量策略具有较强的竞争性能.     

局内封闭式车辆调度问题及其竞争策略

基于k-卡车问题和局内运输问题,提出了具有时间窗的局内封闭式车辆调度问题,建立了相关的模型,研究了当车辆数为1时该问题的竞争分析的有关结果,给出了三种不同的竞争策略,得到了相应的竞争比,并进行了理论证明.     

基于概率分布的局内特殊优惠卡问题及其竞争分析

特殊优惠卡问题是租赁问题的推广.应用平均情形竞争分析研究了局内特殊优惠卡问题,理论和数值分析表明概率分布的引入使得竞争分析的性能得到了改善.并对存在市场利率的特殊优惠卡问题进行了讨论,市场利率的引入使得该金融模型更贴近于现实情况.得到两种情形下不同的竞争比,同时竞争比是市场利率的递减函数.     

价格连续型局内设备赁购问题的竞争分析

基于局内算法分析领域中的On-line Ski问题,提出了局内设备赁购决策问题.建立了价格连续型的该问题的数学模型,针对购价恒定的情形和一般情形分别设计了B价赁购策略和赁购平衡策略(Renting-Buying Balance Strategy),给出了相应的竞争比,并进行了理论证明.得到了价格连续型问题的竞争比下限,并给出理论证明.讨论了所得结果在现实经济管理活动中的应用,并指出了进一步的研究方向.     

加拿大旅行者问题

针对加拿大旅行者问题 ,分析其主要变形——确定型可恢复的加拿大旅行者问题。考虑堵塞边动态产生 ,一个遇到且堵塞边在时间 l( x,x)后可以自动恢复情况下的道路选择。通常对于在线算法可以从两个方面进行评价 :最坏情形分析和竞争比分析。本文先设计了求解最坏情形下旅行时间最短的标号算法并分析了其计算复杂性。而后在竞争比分析中 ,设计了基于贪婪原则的选路策略 ,并对其进行了竞争比分析 ,证明了该贪婪策略对于确定型可恢复加拿大旅行者问题的竞争比为 ( k+ 2 ) /2