研究方法论VIP

研究方法论 第五讲占线问题与竞争策略西安工业大学经济管理学院 占线问题和竞争策略 占线问题和竞争策略 1966年 Graham第一次提出用竞争分析方法解决并行机器调度问题 提出一个简单的确定性贪婪算法 1983年 R Tarjan在DataStructureandNetworkAlgorithms中所讨论的Amotized的方法 就是占线问题与竞争策略的萌芽 近年来 在计算机理论科学 管理科学等领域 占线问题与竞争策略的研究均取得了较好的理论和实践成果 如经典的k 服务器猜想 雪橇租赁问题 及目前研究热点物流与金融中的占线问题等 占线问题和竞争策略 占线问题和竞争策略 1 A BorodinandR El Yaniv Onlinecomputationandcompetitiveanalysis M CambridgeUniversityPress 1998 2 A FiatandG J Woeginger OnlineAlgorithms TheStateoftheArt M Spring Verlag BerlinHeidelbergGermany 1998 3 D D SleatorandR E Tarjan Amortizedefficiencyoflistupdateandpagingrules Comm ACM 28 2 202 208 1985 4 堵丁柱 k车服务问题与竞争算法 数学的实践与认识 4 36 40 1991 5 R M Karp On lineAlgorithmsVersusOff lineAlgorithms HowMuchisitWorthtoKnowtheFuture InternationalComputerScienceInstituteTechnicalReportTR 92 044 Berkeley CA 1992 6 P Keskinocak R Ravi S Tayur SchedulingandReliableLead TimeQuotationforOrderswithAvailabilityIntervalsandLead TimeSensitiveRevenues ManagementScience 47 2 264 279 2001 参考书目和文章 经济管理中的占线问题 经济管理中的占线问题 物流管理中的占线问题 金融管理中的占线问题 运输 选址 库存 道路交通堵塞问题 车辆调度问题 物流中心选择问题 投资 理财 金融租赁问题 证券投资问题 优惠卡购买问题 库存管理问题 订单加工处理问题 网络G中 其 个顶点均为服务对象 随时可能提出服务要求 现有 个车辆 服务器 按需求的先后顺序来往服务于 个顶点之间 假定 个车辆的初始位置已固定 考虑如下两个问题 1 事先给出一个要求服务的顶点序列 问如何调动车辆使得全部车辆所走的总路程最小 2 如果要求是在服务过程中一个接一个收到的 这样每一时刻只能知道在这之前的要求和服务过程 问如何调动车辆使得总路程最小 需求无法预知的车辆调度问题 假定 一个需求发生的顶点序列策略 就近策略 公平策略就近策略 由距离服务需求最近的车辆提供服务公平策略 让每辆车的行驶里程差不多 C B A 1 2 S1S2 需求无法预知的车辆调度问题 就近策略 一辆车会在A和B之间移动m 1次 当m比较大时 最优方案则是把B移至A 然后C点移至B 这样就近服务的运行里程与最优值的比值为 m 1 3 随着m增大 比值增大 因此 就近策略不是竞争算法 需求无法预知的车辆调度问题 公平策略 BAL 设n k 1 对于每一个车辆si以及该车辆运行的路程Di 服务需求r 移动si使得最小 在服务需求为n k 1的任意度量空间内 BAL策略是k竞争的 但是 在n k 1的度量空间中 BAL是非竞争策略 需求无法预知的车辆调度问题 例 n 4 k 2 初始位置c d 服务需求最优的策略为 先将c处的车辆调到b处 移动距离为M 然后两个车辆在每次响应服务需求时 都只需移动m 需求无法预知的车辆调度问题 出租车调度问题和k 车辆 服务器 调度问题不同的是 此时的需求为 ai bi 表示需要从ai点搭出租车去bi点 基本假设 i 图G是连通的 ii 当新的服务要求出现时 k辆出租车均处于闲置状态 需求无法预知的车辆调度问题 出租车调度问题占线策略 复位策略竞争比结果 如果对于k 车辆调度问题存在竞争比2k 1的占线策略 那么对于k 出租车调度问题的复位策略具有竞争比2k 1 需求无法预知的车辆调度问题 出租车调度与个体收益问题在一个出租车市场上 由政府设定出租车的数量和收费标准 k辆出租车在一个有限交通网络上按照统一价格进行竞争性载客服务 网络上每一个乘客需求为r ai bi 即在ai有一顾客要求乘出租车到bi ai出现的时间 出现的位置和r ai bi 的行驶距离不确定 需求无法预知的车辆调度问题 出租车调度与个体收益问题出租车完成r ai bi 后可按计价规则收费 在空载行驶和等待服务需求到来的时间段无收益 并需支付一定费用 问题 假设不考虑每一辆出租车的固定费用 问题是如何度量出租车在时间段T上的收益 其个体运营方案对其收益将产生怎样的影响 需求无法预知的车辆调度问题 需求无法预知的车辆调度问题 出租车时间价格曲线 需求无法预知的车辆调度问题 车辆在交通网络上由出发地欲抵达目的地 在出发前 决策者综合考虑交通网络中各个路段的状况 选择了一条有效的行驶路径 但是 在车辆沿着这条路径的行驶过程中 可能遇到一系列的道路堵塞 由于信息获取手段的有限 决策者不可预知或只能有限预知即将遇到堵塞的信息 那么 当决策者获知某个堵塞发生的相关信息时 决策者应当制定怎样的行进策略 不同策略的执行效果如何 O D 道路突发性堵塞路径选择问题 模型构造 遭遇k个堵塞边时用策略A将货物从O点运到D点的总费用 相应的离线最优费用基本假设 1 去掉堵塞边后图G仍是连通的 2 只有当运输车走到堵塞边的起点后 才能发现该边发生堵塞而不能通过 3 堵塞边一旦产生 这个边将永远被堵塞 道路突发性堵塞路径选择问题 贪婪策略 A 复位策略 B 竞争比2k 1不能改进 是一般网络上的堵塞不可恢复问题策略竞争比的下界 道路突发性堵塞路径选择问题 一般网络上不可恢复问题的应对策略 一般网络上不可恢复堵塞问题贪婪策略最坏情形 道路突发性堵塞路径选择问题 问题1 为什么贪婪策略竞争比显著高于复位策略 然而从日常经验来说 人们却往往采用贪婪策略 问题2 采用贪婪策略是否具有一定合理性呢 对一般网络上堵塞不可恢复问题贪婪策略的思考 道路突发性堵塞路径选择问题 道路突发性堵塞路径选择问题 对一般网络上堵塞不可恢复问题贪婪策略的思考 日常生活中的贪婪策略 道路突发性堵塞路径选择问题 城市交通网络结构 方格网络 西安市新城区局部地图 巴塞罗那城区局部地图 道路突发性堵塞路径选择问题 城市交通网络结构 环形放射式网络 上海市区局部地图 道路突发性堵塞路径选择问题 城市交通网络结构 混合式网络 方格与环形混合 上海市区局部地图 道路突发性堵塞路径选择问题 城市交通网络结构 自由式 山区等没有一定的几何形状 重庆市区局部地图 道路突发性堵塞路径选择问题 道路突发性堵塞路径选择问题 道路突发性堵塞路径选择问题 道路突发性堵塞路径选择问题 目的地为时多选择贪婪策略点可达示意图 多选择贪婪策略 特殊网络上不可恢复堵塞问题贪婪策略最坏情形 物流配送网络由多个配送中心组成 配送中心数量随着未来需求的变化而增加 因此网络建设需逐步分阶段完成 即在前阶段已建好的配送中心基础上 需要增加若干个配送中心 问题是在不同的建设阶段应如何对物流配送中心进行选址 使得在网络内对服务需求的运输费用尽可能地小 物流配送中心选址问题 物流配送中心选址问题 A B C D的需求量为任两点间的距离为d A B d A C d B C 30d D A d D B d D C 1目标函数 min W I d I A B C D 假设某个城市的道路网络如下图所示 可供选择的物流配送中心地址为A B C D 方案一 1 第1个中心 建设在D点2 建设3个中心时 只能建设在A B D cost D 300 opt1cost A B D 100 100opt3 物流配送中心选址问题 A B C D 1 30 1 1 30 30 方案二 1 第1个中心 建设在A点2 建设3个中心时 建设在A B C cost A 6001 20opt1cost A B C 1 opt3 从全局来看 方案二要优于方案一 物流配送中心选址问题 顾客数量不确定调和策略 HarmonicStrategy 如果知道顾客数量的上限M和下限m 则可以给出一个调和策略HS 即每天准备个顾客所需的即可 可证明该策略的竞争比为调和平均数 库存管理问题 订单加工排序问题描述 供货方对于不断到达的客户订单 根据其加工长度 完工收益 交货日期等因素决策加工次序 使得某种成本 总完工时间 延误订单总个数 尽可能地小或者收益 完工订单个数 完工总收益 尽可能地大 常用的加工策略 FCFS 先到先服务 EDF 最早交货时间优先 SPT 最短加工时间优先 WSPT 带权SPT 按wi pi递减次序 订单加工问题 雪橇租赁问题描述 滑雪爱好者去滑雪 他要么租用要么购买滑雪工具 设t为滑雪者实际的租赁次数 每次租金为p 如果购买 其价格为c 滑雪者在不清楚未来滑雪次数n的情况下 如何决策以使所花费用尽可能地少 Karp提出最优的占线策略 租赁到k 1次 k c p 然后购买 其竞争比为2 1 k 金融租赁问题 雪橇租赁策略设计Online 前k 1次一直租用 之后如果继续需要则立即购买 k 1 2 1 n k 1时 online和offline产生同样的成本 只租不买 2 n k 1时 offline则立即购买该设备 而online等到k 1天才买 金融租赁问题 外汇兑换交易描述M 汇率的上界m 汇率的下界 M m 变动比率 n 交易阶段数根据已知条件的不同 单方向外汇兑换问题可以分为四个不同的类型 类型1 M m 和n已知 类型2 M m已知n未知 类型3 和n已知 类型4 已知n未知 证券投资问题 基于风险的外汇兑换策略 Threat basedStrategy El Yaniv 规则1 只有在当前的汇率为最大值时才考虑将部分美元兑换成日元 规则2 每次将美元兑换成日元时 只兑换最少数目的美元 使得即使以后的汇率一直保持最低时仍能保证竞争比为r 证券