共查询到17条相似文献,搜索用时 62 毫秒
1.
连续网络上的占线可恢复加拿大旅行者问题 总被引:6,自引:0,他引:6
针对堵塞完全在无法预知的情况下一个个出现,且堵塞恢复时间信息可以获取的占线可恢复加拿大旅行者问题,给出连续网络上的等待策略和移动策略以及相应策略下的竞争比,并对两种策略的执行效果进行分析和比较。 相似文献
2.
提出突发性片堵塞下的实时路径选择问题即片堵塞加拿大旅行者问题(regional blockages Canadian traveller problem),考虑出行者对堵塞信息有限预知的情形,从在线问题与竞争策略的角度,建立片堵塞加拿大旅行者问题在线路径选择模型,设计贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,通过比较信息预知点到片堵塞起始点的路段(预知路段)通行时间与最短路径上堵塞路段恢复时间的大小来分析策略的不同情形,证明贪婪策略竞争比,并讨论影响贪婪策略竞争比的预知路段通行时间临界值. 相似文献
3.
4.
5.
提出了有限预知信息的集装箱搬卸占线问题,即每一个服务请求到达时预先知道后续一部分请求信息的占线问题。建立并分析相应的数学模型,针对模型中预知信息的特征提出了贪婪移位策略。运用最坏情形分析方法研究了贪婪移位策略的竞争性能,证明其具有竞争比:(b w-2)/w。 相似文献
6.
针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量的情形,从在线问题与竞争策略的角度,给出了每个堵塞恢复时间都为均匀分布下的等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较. 相似文献
7.
自然灾害的频繁发生使得应急减灾倍受关注, 尤其有效的应急救援车辆调度对应急减灾非常重要. 针对受灾点被提前获知但是不能立即接受救援服务的情形, 通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题, 并分别给出了问题的下界, 直线网络结构下的ENO-dd算法, 和一般网络结构下的GTR-dd算法, 并对算法进行了竞争性能分析. 结果表明两个算法随着预知信息的增多会有明显改进. 更为一般的预知信息结构以及最优的算法设计是下一步研究的方向. 相似文献
8.
针对码头船舶作业计划中通常存在较大比例的、需要临时排班的加班船需求,提出了具有有限预知信息的集装箱码头泊位与岸桥联合调度over-list在线模型。在分配每艘船舶服务请求时假设预知后续一个船舶请求的信息,并着重考虑了由3个相连泊位组成的混合型泊位类型、配置5个岸桥且只存在两种请求的联合调度模型;针对最小化最大完工时间的优化目标,设计出了具有最优竞争比5/4的联合调度在线策略;同时,证明了当缺少预知能力时不存在竞争比小于4/3的在线策略。上述结论表明,有限的预知能力可以有效地改进联合调度策略的竞争性能。数值实验结果进一步验证了所设计策略具有良好的执行性能。 相似文献
9.
非线性指数回购合同约束的占线租赁问题 总被引:1,自引:0,他引:1
考虑到设备的使用寿命通常呈现出更一般的非线性衰减,本文以非线性指数价格函数为回购合同约束建立了占线租赁决策模型,并得到了模型的最优竞争策略。首先分别对指数非线性回购合同进行数学刻画并讨论了其相关的一些性质。其次对存在旧货市场的离线租赁问题进行最优分析,进而提出该问题的占线租赁策略,并运用竞争分析方法从理论上完美证明了该策略的最优性。与经典的占线租赁模型比较发现,其竞争比小于Karp雪橇租赁模型中最优策略的竞争比。另外,本文提出的具有回购合同约束的占线租赁模型是对已有研究仅考虑新货市场进行扩展突破,即考虑了允许旧货市场的存在,是对现有占线租赁模型库的一个有益补充。 相似文献
10.
由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善. 相似文献
11.
12.
13.
14.
在线租赁问题的随机性竞争策略 总被引:1,自引:0,他引:1
在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点.在前人研究基础上,采用博弈论中Nash均衡的混和策略思想并运用竞争分析理论中常用的敌手分析法,针对离线人具有遗忘性竞争对手的特点首先讨论了不存在市场利率情形下在线租赁决策的随机性竞争策略,指出在线人在有限维策略空间内(其维数为设备购买价格与设备租赁费用的比值)必定存在着最优的随机性Nash混和竞争策略,随后将该结果进一步扩展到了存在市场利率情形时的随机性Nash混和竞争策略.另外,通过数值对比分析,发现市场利率的引入使得策略的竞争性能得到显著改善,并且随着市场利率的增大其随机性Nash混和竞争策略的竞争比越小,即投资者若考虑到资金的收益及市场风险因素后将会采取更加谨慎稳健的投资策略. 相似文献
15.
16.
17.
对一般网络上的占线中心选址问题及其竞争算法进行了研究.文献[6]证明了该问题的竞争比下界是(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,其中△e是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法.本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为△e△w,其中△w是所给空间点间的最大相对权重.所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义. 相似文献