动态车辆路径问题排队模型分析

《动态车辆路径问题排队模型分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态车辆路径问题排队模型分析第9卷第1期2006年2月管理科学学报JOURNALOFMANAGEMENTSCIENCESINCHINAV01．9No．1Feb．20()6动态车辆路径问题排队模型分析①郭耀煌，钟小鹏(西南交通大学经济管理学院，成都610031)摘要：分析了一类动态车辆路径问题，其中顾客需求以泊松流形式出现，现场服务时间服从一般分布。提出解决该问题的两种策略：顺序服务策略和中点改进策略，利用排队论、几何概率论等领域的知识分别求出了这两种策略的系统时间，并通过仿真数据实验验证了这两种策略的有效性．关键词：动态车辆路径问题；旅行商问题；排队论；几何

2、概率中图分类号：U116．2；0221．2文献标识码：A文章编号：10ft／一9807(2006)01—0033—0<50引言车辆路径问题(vehicleroutingproblem，Ⅵ)将运筹学理论与交通运输中的实际问题紧密联系在一起，被认为是运筹学领域4o多年来研究最活跃、成果最精彩的方向之一_1J．Ⅵ可以大致描述为一组车辆从单个或多个车场出发，沿着一定的路径去不同地点执行运输服务，如装货、卸货、运货或其它现场服务l2,3j．传统的vRP研究多集中在静态模型，近lO年来，由于通讯技术和信息技术的发展，明显区别于传统静态模型的动态车辆路径问题引起了人们的广

3、泛重视[．与静态vRP相对应，动态VRP模型的特征表现为：1)计划者在制定车辆路线时并不完全知道所有相关的信息；2)新的信息会在路线安排过程以及执行过程中到来，原有的信息也可能发生改变；3)计划者不可能仅通过一次调度就得到确定的执行的行车路线．本文以顾客等待时间最小化作为系统目标，研究了一类动态vRP的实时优化策略，计算出其期望系统时问，通过数据仿真试验验证，表明它比传统的先来先服务策略更好．①收稿日期：2003—10—31；修订日期：200<5～04—03，基金项目：国家自然科学基金资助项目(70071~8)．作者简介：郭耀煌(1937一)，男，河南偃师人

4、，教授，博士生导师1背景知识1．1几个几何概率公式设z1()、Z2(，厶)，是边长为a的正方形区域A内服从均匀分布的两个随机点，并且相互独立．为了便于计算lz。z2l的均值和方差，先假设zl为定点Z(l，Y1)，从而E(1zZ2l)=Il((丑一X1)+j(一1))ddg毛=』号dJ-号jcc一+(一。))dgz2=(a2+{+)现用Z1替换Z：E(1Z1Z212)：』号d』号ja一2f＼6+2+)d，从而得到E(1z1z2l)：a2(1)维普资讯//.cqvip4>>管理科学学报2OO6年2月类似地，可以求得E(1zlz21)一0．<52a(2)Vat(1

5、z1z21)=E(1z1z2I‘)一(IzIz2I)0．06a(3)设z为／1内服从均匀分布的一个随机点，zn为A的中点，用上面的方法可以得到E(1z0zl)：(4)E(i()zI)一0．38a(<5)r(1oz1)=E(1zozl‘)一(IzozI‘)0．02a(6)1．2M／G／1排队模型的Pollaczek-Khinchin(P-K)公式在一个排队模型中，定义：??一单位时问内有一个顾客到达的概率，简称概率强度；s——一单个顾客的平均服务时间；lD～一服务强度，即忙碌时间比，』D：；；??一平均等待时间，即顾客到达时刻与服务机构开始对其服务时刻之间的时

6、间段的均值；——平均系统时间，：+；一系统中的平均顾客数，包括正被服务的顾客和等待服务中的顾客，根据Little公式有Ⅳ=．列‘于单服务台的M／G／1模型，若输入过程为泊松过程，服务时间s的分布为一般任意分布(但是要求s及Var(s)都存在)，则有Ⅳ=l0+(7)这就是M／G／1排队模型的P．K公式[13I。引．2动态车辆路径问题排队论模型的系统时间动态车辆路径问题可描述如下：一辆货车以恒定速度在一个边K为的正方形区域A内执行送货任务．为r简化分析，假设这辆货车拥有足够的载能，即货车无需返回货场重新装载货物．且假设需求全部为动态需求，需求点的位置在区域A内服

7、从独立均匀分布，相邻需求的时间间隔“1'服从负指数分布，并有“：1，Var(“)：．设^^。货车在送货点停留的时间s的分布是一般的，其平均值s和方差Var(s)都存在．定义为需求完成时刻与到来时刻之间的时间间隔，为需求开始被服务时刻i与到来时刻之间的时间间隔，所以有=一s；稳态系统时间：limE[Ti]，稳态等待时间=—．研究的目的l—0∞是找到一个服务策略来最小化，记为．根据上述定义，该动态车辆路径问题可以看作是一个M／G／1排队模型．需要注意的是，对于某个需求来说，服务时间si应包括货车在点的停留时间s和货车收到需求信息f后驶向点的时间di／V

8、，其中，d为行驶的距离，为货车行驶的速度．对于稳态系