研究方法论(5)

1、研究方法论,第五讲 占线问题与竞争策略 苏 兵,2,占线问题和竞争策略,3,占线问题和竞争策略,4,1966年，graham第一次提出用竞争分析方法解决并行机器调度问题，提出一个简单的确定性贪婪算法； 1983年，r.tarjan在 data structure and network algorithms 中所讨论的amotized的方法，就是占线问题与竞争策略的萌芽； 近年来，在计算机理论科学、管理科学等领域，占线问题与竞争策略的研究均取得了较好的理论和实践成果，如经典的k-服务器猜想，雪橇租赁问题，及目前研究热点物流与金融中的占线问题等。,占线问题和竞争策略,5,占线问题和竞争策略,6,

2、1. a. borodin and r. el-yaniv, online computation and competitive analysis m. cambridge university press, 1998. 2. a. fiat and g.j. woeginger, online algorithms: the state of the artm. spring-verlag, berlin heidelberg germany, 1998. 3. d. d. sleator and r. e. tarjan. amortized efficiency of list upd

3、ate and paging rules. comm. acm, 28(2):202-208, 1985. 4.堵丁柱, k车服务问题与竞争算法, 数学的实践与认识,.4:36-40, 1991. 5. r. m. karp, on-line algorithms versus off-line algorithms: how much is it worth to know the future?, international computer science institute technical report tr-92-044, berkeley, ca, 1992. 6. p.kes

4、kinocak, r.ravi., s.tayur. scheduling and reliable lead-time quotation for orders with availability intervals and lead-time sensitive revenues. management science, 47, 2: 264-279,2001,参考书目和文章,7,经济管理中的占线问题,经济管理中的占线问题,物流管理中的占线问题,金融管理中的占线问题,运输,选址,库存,道路交通堵塞问题,车辆调度问题,物流中心选择问题,投资,理财,金融租赁问题,证券投资问题,优惠卡购买问题,

5、库存管理问题,订单加工处理问题,8,网络g中，其个顶点均为服务对象，随时可能提出服务要求，现有个车辆(服务器)按需求的先后顺序来往服务于个顶点之间。假定个车辆的初始位置已固定。 考虑如下两个问题： （1）事先给出一个要求服务的顶点序列，问如何调动车辆使得全部车辆所走的总路程最小？ （2）如果要求是在服务过程中一个接一个收到的，这样每一时刻只能知道在这之前的要求和服务过程。问如何调动车辆使得总路程最小？,需求无法预知的车辆调度问题,9,假 定：一个需求发生的顶点序列 策 略：就近策略、公平策略 就近策略：由距离服务需求最近的车辆提供服务 公平策略：让每辆车的行驶里程差不多,c,b,a,1,2,s

6、1 s2,需求无法预知的车辆调度问题,10,就近策略： 一辆车会在a和b之间移动m-1次，当m比较大时，最优方案则是把b移至a，然后c点移至b;这样就近服务的运行里程与最优值的比值为 （m-1）/3,随着m 增大，比值增大，因此，就近策略不是竞争算法。,需求无法预知的车辆调度问题,11,公平策略（bal） 设n=k+1，对于每一个车辆 si以及该车辆运行的路程di，服务需求r，移动 si 使得 最小。 在服务需求为n=k+1的任意度量空间内，bal策略是k竞争的。 但是，在nk+1的度量空间中，bal是非竞争策略。,需求无法预知的车辆调度问题,12,例， n=4， k2，初始位置c、d。 服务

7、需求 最优的策略为：先将c处的车辆调到b处， 移动距离为m，然后两个车辆在每次响应服务需求时，都只需移动m。,需求无法预知的车辆调度问题,13,出租车调度问题 和k-车辆（服务器）调度问题不同的是，此时的需求为（ai,bi），表示需要从ai点搭出租车去bi点。 基本假设： i) 图g是连通的; ii)当新的服务要求出现时,k辆出租车均处于闲置状态;,需求无法预知的车辆调度问题,14,出租车调度问题 占线策略：复位策略 竞争比结果： 如果对于k-车辆调度问题存在竞争比2k-1的占线策略，那么对于k-出租车调度问题的复位策略具有竞争比 2k+1。,需求无法预知的车辆调度问题,15,出租车调度与个体

8、收益问题 在一个出租车市场上，由政府设定出租车的数量和收费标准，k辆出租车在一个有限交通网络上按照统一价格进行竞争性载客服务。网络上每一个乘客需求为 r(ai,bi),即在ai有一顾客要求乘出租车到 bi,ai出现的时间、出现的位置和 r(ai,bi)的行驶距离不确定。,需求无法预知的车辆调度问题,16,出租车调度与个体收益问题 出租车完成r(ai,bi)后可按计价规则收费，在空载行驶和等待服务需求到来的时间段无收益，并需支付一定费用。 问题： 假设不考虑每一辆出租车的固定费用，问题是如何度量出租车在时间段t上的收益，其个体运营方案对其收益将产生怎样的影响？,需求无法预知的车辆调度问题,17,

9、需求无法预知的车辆调度问题,18,出租车时间价格曲线,需求无法预知的车辆调度问题,19,车辆在交通网络上由出发地欲抵达目的地。在出发前，决策者综合考虑交通网络中各个路段的状况，选择了一条有效的行驶路径。但是，在车辆沿着这条路径的行驶过程中，可能遇到一系列的道路堵塞。由于信息获取手段的有限，决策者不可预知或只能有限预知即将遇到堵塞的信息，那么，当决策者获知某个堵塞发生的相关信息时，决策者应当制定怎样的行进策略？不同策略的执行效果如何？,o,d,?,道路突发性堵塞路径选择问题,20,模型构造： ：遭遇k个堵塞边时用策略a将货物从o点 运到d点的总费用 ： 相应的离线最优费用 基本假设： 1）去掉堵

10、塞边后图g仍是连通的； 2）只有当运输车走到堵塞边的起点后，才能发现该边 发生堵塞而不能通过； 3）堵塞边一旦产生，这个边将永远被堵塞。,道路突发性堵塞路径选择问题,21,贪婪策略（a） 复位策略（b） 竞争比2k1不能改进，是一般网络上的堵塞不可 恢复问题策略竞争比的下界。,道路突发性堵塞路径选择问题,一般网络上不可恢复问题的应对策略,22,一般网络上不可恢复堵塞问题贪婪策略最坏情形,道路突发性堵塞路径选择问题,23,问题1：为什么贪婪策略竞争比显著高于复位策略，然 而从日常经验来说，人们却往往采用贪婪策略? 问题2：采用贪婪策略是否具有一定合理性呢？,对一般网络上堵塞不可恢复问题贪婪策略的

11、思考,道路突发性堵塞路径选择问题,24,道路突发性堵塞路径选择问题,对一般网络上堵塞不可恢复问题贪婪策略的思考,25,日常生活中的贪婪策略,道路突发性堵塞路径选择问题,26,城市交通网络结构 方格网络,西安市新城区局部地图,巴塞罗那城区局部地图,道路突发性堵塞路径选择问题,27,城市交通网络结构 环形放射式网络,上海市区局部地图,道路突发性堵塞路径选择问题,28,城市交通网络结构混合式网络（方格与环形混合）,上海市区局部地图,道路突发性堵塞路径选择问题,29,城市交通网络结构自由式（山区等没有一定的几何形状）,重庆市区局部地图,道路突发性堵塞路径选择问题,30,道路突发性堵塞路径选择问题,31

12、,道路突发性堵塞路径选择问题,32,道路突发性堵塞路径选择问题,目的地为 时多选择贪婪策略点 可达示意图,多选择贪婪策略,特殊网络上不可恢复堵塞问题贪婪策略最坏情形,33,物流配送网络由多个配送中心组成，配送中心数量随着未来需求的变化而增加，因此网络建设需逐步分阶段完成。即在前阶段已建好的配送中心基础上，需要增加若干个配送中心，问题是在不同的建设阶段应如何对物流配送中心进行选址，使得在网络内对服务需求的运输费用尽可能地小。,物流配送中心选址问题,34,物流配送中心选址问题,a,b,c,d的需求量为 任两点间的距离为 d(a,b)=d(a,c)=d(b,c)=30 d(d,a)=d(d,b)=d

13、(d,c)=1 目标函数：min w（i） d ; i=a,b,c,d,假设某个城市的道路网络如下图所示，可供选择 的物流配送中心地址为a,b,c,d,35,方案一： 1.第1个中心，建设在d点 2.建设3个中心时，只能建设在 a，b，d,cost(d) =300=opt1 cost(a,b,d)=100=100opt3,物流配送中心选址问题,36,a,b,c,d,1,30,1,1,30,30,方案二： 1.第1个中心，建设在a点 2.建设3个中心时，建设在 a，b，c,cost(a)600120opt1 cost(a,b,c)=1=opt3,从全局来看，方案二要优于方案一。,物流配送中心选址

14、问题,37,顾客数量不确定 调和策略（harmonic strategy） 如果知道顾客数量的上限m和下限m,则可以 给出一个调和策略hs,即每天准备 个顾客所需的即可. 可证明该策略的竞争比为 调和平均数：,库存管理问题,38,订单加工排序问题描述： 供货方对于不断到达的客户订单，根据其加工长度、完工收益、交货日期等因素决策加工次序，使得某种成本（总完工时间、延误订单总个数）尽可能地小或者收益（完工订单个数、完工总收益）尽可能地大。 常用的加工策略： fcfs（先到先服务） edf（最早交货时间优先） spt（最短加工时间优先） wspt（带权spt：按wi/pi递减次序）,订单加工问题,3

15、9,雪橇租赁问题描述： 滑雪爱好者去滑雪，他要么租用要么购买滑雪工具。设t为滑雪者实际的租赁次数，每次租金为p， 如果购买，其价格为c。滑雪者在不清楚未来滑雪次数n的情况下，如何决策以使所花费用尽可能地少？ karp 提出最优的占线策略： 租赁到k1次(k=c/p)，然后购买。 其竞争比为2-1/k.,金融租赁问题,40,雪橇租赁策略设计 online：前k1次一直租用， 之后如果继续需要则立即购买( k=1,2,.)。 1）nk1时， online 和offline 产生同样的成本，只租不买。 2）n k1时，offline则立即购买该设备，而online等到k1天才买。,金融租赁问题,41,外汇兑换交易描述 m=汇率的上界 m=汇率的下界 m/m （变动比率） n=交易阶段数 根据已知条件的不同，单方向外汇兑换问题可以分为四个不同的类型： 类型 1：m，m，和n已知； 类型 2：m，m已知n未知； 类型 3：和n已知； 类型 4：已知n未知。,证券投资问题,42,基于风险的外汇兑换策略 （threat-based strategy）（el-yaniv） 规则1：只有在当前的汇率为最大值时才考虑将部分美元兑换成日元； 规则2：每次将美元兑换成日元时，只兑换最少数目的美元，使得即使以后的汇率一直保持最低时仍能保证竞争比为r。,证券投