研究方法论(5)

研究方法论第五讲占线问题与竞争策略苏兵西安工业大学经济管理学院2020/1/262占线问题和竞争策略现代社会的特征：信息多变与不完全部分已知当前决策信息决策问题全部已知当前决策信息已知未来信息全部知或一无所知未来信息有限预2020/1/263占线优化方法通常是在一定的已知（静态）条件下寻求最优方案或在一定的假设下寻求统计意义上的最优方案。决策者对未来因素的变化有限预知甚至一无所知情形下,该方法可以给出较好的方案,使之与最优方案的差异（比值）总在一定的比例之内。静态优化方法两类问题：离线问题（offline）占线问题(online)决策方法：占线问题和竞争策略2020/1/2641966年，Graham第一次提出用竞争分析方法解决并行机器调度问题，提出一个简单的确定性贪婪算法；1983年，R.Tarjan在DataStructureandNetworkAlgorithms中所讨论的Amotized的方法，就是占线问题与竞争策略的萌芽；近年来，在计算机理论科学、管理科学等领域，占线问题与竞争策略的研究均取得了较好的理论和实践成果，如经典的k-服务器猜想，雪橇租赁问题，及目前研究热点物流与金融中的占线问题等。占线问题和竞争策略2020/1/265考虑一个最小费用问题P，为P的输入序列是对占线问题P所设计应对策略A下对应于输入R的费用.策略A只能在获知第i时期的输入后给出第i时期的输出为问题P所对应的离线问题在确定输入R下的最优解如果成立称为策略A的竞争比(competitiveratio).为与输入序列无关的常数。()ACR123{,,,,}nRrrrrLoptCRAoptCRcCRc,c占线问题和竞争策略占线问题和竞争策略2020/1/2661.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参考书目和文章2020/1/267经济管理中的占线问题经济管理中的占线问题物流管理中的占线问题金融管理中的占线问题运输选址库存道路交通堵塞问题车辆调度问题物流中心选择问题投资理财金融租赁问题证券投资问题优惠卡购买问题库存管理问题订单加工处理问题2020/1/268网络G中，其ｎ个顶点均为服务对象，随时可能提出服务要求，现有ｋ个车辆(服务器)按需求的先后顺序来往服务于ｎ个顶点之间。假定ｋ个车辆的初始位置已固定。考虑如下两个问题：（1）事先给出一个要求服务的顶点序列，问如何调动车辆使得全部车辆所走的总路程最小？（2）如果要求是在服务过程中一个接一个收到的，这样每一时刻只能知道在这之前的要求和服务过程。问如何调动车辆使得总路程最小？需求无法预知的车辆调度问题CBA12S1S22020/1/269假定：一个需求发生的顶点序列策略：就近策略、公平策略就近策略：由距离服务需求最近的车辆提供服务公平策略：让每辆车的行驶里程差不多CBA12S1S2需求无法预知的车辆调度问题......mABABAB14444424444432020/1/2610就近策略：一辆车会在A和B之间移动m-1次，当m比较大时，最优方案则是把B移至A，然后C点移至B;这样就近服务的运行里程与最优值的比值为（m-1）/3,随着m增大，比值增大，因此，就近策略不是竞争算法。需求无法预知的车辆调度问题2020/1/2611公平策略（BAL）设n=k+1，对于每一个车辆si以及该车辆运行的路程Di，服务需求r，移动si使得最小。在服务需求为n=k+1的任意度量空间内，BAL策略是k竞争的。但是，在nk+1的度量空间中，BAL是非竞争策略。(,)iiDdsr需求无法预知的车辆调度问题2020/1/2612例，n=4，k＝2，初始位置c、d。服务需求最优的策略为：先将c处的车辆调到b处，移动距离为M，然后两个车辆在每次响应服务需求时，都只需移动m。,,,,,,,,...,,,,abcdabcdabcdMabcdm(,)iiDdsr需求无法预知的车辆调度问题2020/1/2613出租车调度问题和k-车辆（服务器）调度问题不同的是，此时的需求为（ai,bi），表示需要从ai点搭出租车去bi点。基本假设：i)图G是连通的;ii)当新的服务要求出现时,k辆出租车均处于闲置状态;需求无法预知的车辆调度问题2020/1/2614出租车调度问题占线策略：复位策略竞争比结果：如果对于k-车辆调度问题存在竞争比2k-1的占线策略，那么对于k-出租车调度问题的复位策略具有竞争比2k+1。需求无法预知的车辆调度问题2020/1/2615出租车调度与个体收益问题在一个出租车市场上，由政府设定出租车的数量和收费标准，k辆出租车在一个有限交通网络上按照统一价格进行竞争性载客服务。网络上每一个乘客需求为r(ai,bi),即在ai有一顾客要求乘出租车到bi,ai出现的时间、出现的位置和r(ai,bi)的行驶距离不确定。需求无法预知的车辆调度问题2020/1/2616出租车调度与个体收益问题出租车完成r(ai,bi)后可按计价规则收费，在空载行驶和等待服务需求到来的时间段无收益，并需支付一定费用。问题：假设不考虑每一辆出租车的固定费用，问题是如何度量出租车在时间段T上的收益，其个体运营方案对其收益将产生怎样的影响？需求无法预知的车辆调度问题2020/1/2617出租车时间价格函数()()ftdtItowvtttTto,tw,tv分别表示载客、等待和空载时间时间段T分割成许多小的时间区间t,则出租车在每一个t内的时间价格是不一样的需求无法预知的车辆调度问题2020/1/2618出租车时间价格曲线图1政府定价下的出租车时间价格曲线载客等待空载起步价正常运价阶段空驶补偿阶段需求无法预知的车辆调度问题2020/1/2619车辆在交通网络上由出发地欲抵达目的地。在出发前，决策者综合考虑交通网络中各个路段的状况，选择了一条有效的行驶路径。但是，在车辆沿着这条路径的行驶过程中，可能遇到一系列的道路堵塞。由于信息获取手段的有限，决策者不可预知或只能有限预知即将遇到堵塞的信息，那么，当决策者获知某个堵塞发生的相关信息时，决策者应当制定怎样的行进策略？不同策略的执行效果如何？OD?道路突发性堵塞路径选择问题2020/1/2620模型构造：：遭遇k个堵塞边时用策略A将货物从O点运到D点的总费用：相应的离线最优费用基本假设：1）去掉堵塞边后图G仍是连通的；2）只有当运输车走到堵塞边的起点后，才能发现该边发生堵塞而不能通过；3）堵塞边一旦产生，这个边将永远被堵塞。12(,,,)AkCrrrL12(,,,)OPTkCrrrL道路突发性堵塞路径选择问题2020/1/2621贪婪策略（A）复位策略（B）竞争比2k＋1不能改进，是一般网络上的堵塞不可恢复问题策略竞争比的下界。11212(,,,)(21)(,,,)kAkOPTkCrrrCrrrLM1212(,,,)(21)(,,,)BkOPTkCrrrkCrrrLL道路突发性堵塞路径选择问题一般网络上不可恢复问题的应对策略2020/1/2622一般网络上不可恢复堵塞问题贪婪策略最坏情形道路突发性堵塞路径选择问题2020/1/2623问题1：为什么贪婪策略竞争比显著高于复位策略，然而从日常经验来说，人们却往往采用贪婪策略?问题2：采用贪婪策略是否具有一定合理性呢？对一般网络上堵塞不可恢复问题贪婪策略的思考道路突发性堵塞路径选择问题2020/1/2624令r1,r2,....,rk表示k个堵塞边，其中•li表示从堵塞边ri的起点到终点D的距离(r1,..,ri-1已经堵塞)•l’i表示从堵塞边ri的起点到终点D的可行距离•则且有'iiill1i对于贪婪策略A，应有下面不等式成立：1212(,,...,)(,,...,)kAkOPTkCrrrCrrr道路突发性堵塞路径选择问题对一般网络上堵塞不可恢复问题贪婪策略的思考2020/1/2625日常生活中的贪婪策略ODO1O2O3道路突发性堵塞路径选择问题2020/1/2626城市交通网络结构——方格网络西安市新城区局部地图巴塞罗那城区局部地图道路突发性堵塞路径选择问题2020/1/2627城市交通网络结构——环形放射式网络上海市区局部地图道路突发性堵塞路径选择问题2020/1/2628城市交通网络结构——混合式网络（方格与环形混合）上海市区局部地图道路突发性堵塞路径选择问题2020/1/2629城市交通网络结构——自由式（山区等没有一定的几何形状）重庆市区局部地图道路突发性堵塞路径选择问题2020/1/2630方格网式，环形放射式，自由式和混合式网络模型环形放射式方格网式混合式自由式交通网络的分类方式：道路突发性堵塞路径选择问题2020/1/2631道路突发性堵塞路径选择问题目的地为时方向贪婪策略路径示意图OPTPMPmnv00vmnvoptCmn2DCmn22DoptCmnCmn方向贪婪策略特殊网络上不可恢复堵塞问题贪婪策略最坏情形()!!!mnNmn2020/1/2632道路突发性堵塞路径选择问题目的地为时多选择贪婪策略点可达示意图optCmnMPOPTPmnv00v()ijminjvmnvMCmn1MoptCC多选择贪婪策略特殊网络上不可恢复堵塞问题贪婪策略最坏情形2020/1/2633物流配送网络由多个配送中心组成，配送中心数量随着未来需求的变化而增加，因此网络建设需逐步分阶段完成。即在前阶段已建好的配送中心基础上，需要增加若干个配送中心，问题是在不同的建设阶段应如何对物流配送中心进行选址，使得在网络内对服务需求的运输费用尽可能地小。物流配送中心选址问题2020/1/2634物流配送中心选址问题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()()()100()1wAwBwCwD30ABC1113030D假设某个城市的道路网络如下图所示，可供选择的物流配送中心地址为A,B,C,D2020/1/2635方案一：1.第1个中心，建设在D点2.建设3个中心时，只能建设在A，B，Dcost({D})=300=opt1cost({A,B,D})=100=100opt3()()()100()1wAwBwCwD30ABC1113030D