多策略选择的在线租赁模型及其竞争分析北大核心CSCDCSSCI

传统的租赁问题以经典的"租雪橇"模型为基础,只考虑纯租赁和纯购买策略,为更加贴近实际,进一步考虑了投资者可选择先付部分购买费用后以某一较低的租赁费用进行租赁的策略,提出了多策略选择形式下的在线租赁模型。首先分析了该问题的最优离线策略;其次运用在线算法理论和竞争比思想给出该问题的确定性最优在线策略及其竞争比;最后,数值例子结果表明:在多策略选择的问题中,竞争比性能随着策略的不同而改变,说明了多策略选择对投资者的租赁决策具有显著的影响。     

局内配送车调度及其竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解)，其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题提出一种策略，对已知条件变化的每一个特例都能给出一个方案，使得该方案的解离最优方案的解总在一定的比例之内．针对在一个有限网络上建立了s个配送中心，并且有k辆配送车进行服务的局内配送车问题，在时间目标函数下给出了当配送中心、配送车和需求点个数变化时的3种竞争算法．     

限制图上的局内出租车调度与竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解）,其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题来研究这样的方法,它在变化因素的每一个特例中都能给出一个方案,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内．本文应用复位策略给出限制图上局内ｋ 出租车调度问题竞争比为１＋ （ｎ－ ｋ）λ的竞争算法．     

激励相容在线反向拍卖的竞争分析

运用在线算法与竞争分析方法,研究了网络环境下当供应商在不同时刻到达,并投标而要求采购商接到每个投标时立即做出决策的在线反向拍卖机制.首先,证明了基于采购商需求曲线的在线反向拍卖是激励相容在线反向拍卖的充分必要条件.其次,对无限可分商品,在采购商需求量一定的前提下,运用文中给出的基于投标价格上涨威胁的策略,找到了采购商竞争的需求曲线,并求出了该在线策略相对于Vickrey反向拍卖策略的竞争比.最后,给出了在线反向拍卖操作的算法框架,并通过实例进行了说明.     

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

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

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

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

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

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

具有美式看跌期权的单方向在线外汇兑换竞争策略设计

El-Yaniv等学者首次运用在线算法及其竞争分析方法研究了单方向在线外汇兑换问题, 提出了基于汇率突然下跌威胁的在线兑换策略. 结合期权工具改进了该兑换策略对汇率上、下界的估计, 即不估计汇率波动的下界, 仅估计上界. 利用看跌期权以第一期汇率价格为敲定价格锁定后续汇率波动的最低交易底价, 同时利用首期汇率信息对汇率上界进行估计, 从而这样预估的上界较El-Yaniv等学者模型中估计的上界更准确. 当汇率上界确定后, 分别给出了兑换期限已知和未知两种情形下的最优在线兑换策略, 并与El-Yaniv等学者给出的兑换策略进行了对比分析. 最后, 通过算例分析说明了当El-Yaniv等学者模型中的下界和上界参数相差很大时或末期汇率出现大幅下跌时, 本文所提出的结合期权工具的在线交易策略的竞争性能更具有优越性.     

带时间窗的局内开放式车调度问题的竞争分析

对于带时间窗的局内车辆调度问题，以往文献的研究都是关于k=1的单车调度，其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆丰（k≥2）调度的研究分析，设计了解决试问题的竞争算法，并证明了其竞争比为3．5。同时本文分析了该问题的一种特殊情形——单车调度问题，可证明其竞争比为3．优于已有结果。     

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

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

局内车辆选线问题和竞争策略分析

将现实物流配迭中所遇到的问题抽象为一个局内车辆选线问题，考虑堵塞点动态产生、一个个遇到的情况下的车辆调度方案，经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解)，在条件发生变化时就会失去其最优性。而论文所考虑的竞争算法能使得调度方案对于变化因素的每一个特例得到的解离最优方案给出的解总在一定范围之内。不仅设计了解决局内车辆选线问题的竞争算法：贪婪策略和复位策略，分析了不同情况下算法各自的竞争比，而且给出了此问题的竞争比下界。     

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

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

局内军车调度的时间优化及其竞争策略

提出时间目标函数下的局内k－军车调度问题，应用复位策略给出该问题的几种竞争算法：给出了对应的局内k－服务器问题的竞争比的c时的该问题的竞争比为c 1 1/θ的竞争算法；分别给出了当k=n和k=n-1时该问题的竞争比为1和1＋1／θ的竞争算法。     

占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.     

占线订单排序D-收益函数下改进的随机策略

对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题,Woeginger提出了完工收益与订单长度满足D-收益函数的模型,并给出了竞争比为4的最优确定性策略.针对该模型设计了竞争比为2的一个简单随机策略,该结论改进了Epstein和Levin(2008)的竞争比2.455 4.     

具有建设成本的占线中心选址问题及其竞争算法设计

研究待选址个数不确定的动态选址问题. 在实际选址过程中,经常会在全部需要建立的设施个数未知的前提下,决定在哪里建立初始的设施(或设施集),同时要求,当增加建立设施时,已经建立的设施不能被删除.此外,基于实际,待建立的设施间的初始建设成本是不同的. 建立了满足上述约束的占线选址动态模型,并给出一个竞争算法,最后证明该算法具有常数的竞争比.