资源描述：
《局内出租车调度与竞争算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第31卷增刊É西安交通大学学报Vol.31Sup.É1997年6月JOURNALOFXI’ANJIAOTONGUNIVERSITYJun.1997局内出租车调度与竞争算法徐寅峰王刊良(西安交通大学,710049,西安)摘要应用复位策略给出了局内k出租车调度问题的竞争算法.给出了当k=n和当k=n-1时竞争比为2的竞争算法.关键词局内问题竞争算法竞争比中国图书资料分类法分类号TB114.1现实生活中的许多经济现象通常都具有非常强的动态特征,人们对于这些现象一般是先进行数学上的抽象,然后用静态或统计的方法来加以研究和处
2、理.从优化的理论和方法上看,经典的优化理论大多是站在旁观者的立场上看问题.即首先确定已知条件,然后在假设这些已知条件不变的基础上给出最优方案(即最优解).条件一旦发生变化,这种方法所给出的最优方案就会失去其最优性.现实世界中的一切事物通常都是随着时间的推移而不断变化的.如果这种可变化的不确定因素对所考虑的问题影响很大,那么将如何给出优化呢?对于可变化的因素,数学上有两种经典的方法来进行处理:一是将可变化的因素随机化,寻求平均意义上的最优方案;二是考虑可变化因素的最坏情形,寻求使最坏情形达到最优的方案.这两种处理方法
3、对变化因素的一个特例都可能给出离实际最优解相距甚远的解,这显然是难以满足实际要求的.那么是否存在一种方法,它在变化因素的每一个特例中都能给出一个方案,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢?近年来兴起的局内问题与竞争算法的研究结果,在一定意义上给如上问题一个肯定的答案,参见文献[1～4].出租车调度问题的实际背景是一个出租汽车公司如何调度出租车来完成顾客所提出的一个接一个的具体服务要求.对于一个出租汽车公司,假设它有k辆出租车在一个有限交通网络上进行载客服务,每个服务要求均由总调度台调度出租车
4、来完成.考虑如下两个问题:(1)事先给定一个要求服务的任务序列,如何调动出租车,使得相关的费用最少?(2)如果服务要求是在服务过程中一个个地接到的,这样,每一时刻只能知道在此之前的任务序列与服务过程,那么如何调动出租车使费用较少呢?出租车调度问题的优化目标是所有出租车所行驶的总里程数最少(因为出租车行驶的总收到日期:1997202225.徐寅峰:男,1962年9月生,管理学院战略与决策研究所,副教授.3西安交通大学科研基金资助课题.增刊É徐寅峰等:局内出租车调度与竞争算法57里程数与出租车公司的费用成正比,在完成一
5、个服务要求序列之后,费用越少越好).问题(1)是个局外问题,而问题(2)是一个局内问题.两者的不同点在于可知的服务要求序列是全部还是局部.问题(1)的最优解可以用动态规划方法来求得,而问题(2)却难以处理.事实上,服务要求序列对调度方案有着致命的影响,随着服务要求出现的不同,最优调度方案也随之发生变化.局内出租车调度问题是局内k服务器问题的一个推广.局内k服务器问题是近年来优化[1～3]理论与竞争算法领域的一个热点研究项目.在国际上已有许多这方面的研究成果.国内这[5]方面的研究开展得不多,主要有堵丁柱教授的一篇介
6、绍性文章.本文首先建立局内k出租车调度问题的数学模型,给出了k服务器问题与k出租车问题之间的内在联系,同时给出了k出租车问题竞争比的几个结果.在结束语中提出了几个有待进一步深入研究的问题.1数学模型令G=(V,E)为一边加权无向图,其中V为顶点集合,E为边集合,对于u,v,w∈V,边之间的权满足三角不等式,即d(u,v)+d(v,w)≥d(w,u),其中d(x,y)表示顶点为x,y的边的权.假设有k辆出租车在顶点V的一个子集合上,一个服务要求r=(a,b),a,b∈V(其实际意义为在顶点a有一顾客要求从a乘出租车到
7、b顶点).一个服务要求序列R由一些服务要求按先后顺序组成,即R=(r1,r2,⋯,rm),其中ri=(ai,bi),ai,bi∈V.局内出租车问题是要求在每一个服务要求出现后决定派哪一辆出租车来完成这一服务,而假设对后面可能出现的服务要求都一无所知.以下的所有讨论都基于如下基本假设:i)图G是连通的;ii)当新的服务要求出现时,k辆出租车均处于闲置状态.对于R=(r1,r2,⋯,rm),令Copt(R)为已知服务要求序列R情况下最优调度方案完成R中所有服务要求后,出租车所行驶的总里程数.如果调度方案A对于每一个新到
8、来的服务要求ri可以不依赖于ri以后的服务要求序列来进行调度,那么称A为局内调度方案.对于局内调度方案A,如果存在与服务要求序列R无关的常数A和B满足CA(R)≤ACopt(R)+B对任意可能出现的服务要求序列R都成立,则称A为竞争算法,其中CA(R)为完成服务要求序列R后,调度方案A的总费用(即出租车行驶的总里程数).对于服务要求ri=(ai,bi),调度
