公共慢行系统的动态调度建模与滚动时域调度算法研究_董红召

公路工程HighwayEngineering

Vo.l34,No.6Dec.,2009

公共慢行系统的动态调度建模与滚动时域

调度算法研究

董红召,赵敬洋,郭海锋,郭明飞

(浙江工业大学智能交通联合研究所,浙江杭州 310014)

[摘 要]针对公共慢行系统存在公共自行车在时间和空间上分布不均衡的问题,研究了公共慢行系统调度过程中租赁点需求的动态特性及其模糊时间窗的约束,以最大化租赁点的满意度为目标建立了公共慢行系统调度的模型,并用滚动时域调度算法对该模型进行求解,动态的获取调度计划,进而实现公共慢行系统的动态调度。

[关键词]公共慢行系统;动态车辆调度;滚动时域调度算法;禁忌搜索算法[中图分类号]U492.4+12 [文献标识码]A

[文章编号]1674)0610(2009)06)0068)04

ResearchontheDynamicModelandRollingHorizonSchedulingAlgorithmforPublic-useBicycleVehicleSchedulingProblem

DONGHongzhao,ZHAOJingyang,GUOHaifeng,GUOMingfei(ZJUT-ENJOYORITSJointInstitute,ZhejiangUniversityofTechnology,Hangzhou,Zhejiang310014,China)

[Abstract]Thedistributionofbikeisimbalancedinthetimeandthespaceinpublic-usebicyclesystem.thedynamicpropertiesandfuzzytimewindowsofthepublic-usebicyclesystemvehicleschedu-lingproblemareanalyzed.Thenthemodelisdevelopedintermsofthemaximizationsatisfactionofbicy-clesitesforthepublic-usebicyclesystemvehicleschedulingproblem.Finallytherollinghorizonschedu-lingalgorithmisappliedtosolvethemodel.

[Keywords]thepublic-usebicyclesystem;dynamicvehicleschedulingproblem;rollinghorizonschedulingalgorithm;tabusearchalgorithm 公共慢行系统又叫公共自行车系统,由公共自行车租赁点(以下简称租赁点)、公共自行车、调度中心、运输车辆、运输车辆停车场以及通信系统等组成,为市民提供自行车租赁服务,公共慢行系统承担着重要的交通任务,能有效解决公共汽车运输/最后一公里0难题,并且具有以下优点:¹无污染;º机动灵活;»停放方便,停车场占地面积少。杭州市从2008年5月开始试运行公共慢行系统以来,不断增加租赁点和自行车的数量,公共自行车已经成为市民和游客出行的重要交通工具。但是,由于公共自行车的流动性,杭州市公共慢行系统存在自行车在时间和空间上分布不均衡的问题,具体表现为:¹某些租赁点在某些时刻自行车数量过少,用户不能及时借到自行车;º某些租赁点在某些时刻自

[收稿日期]2009)08)04

[作者简介]董红召(1969)),男,浙江杭州人,教授,博士,主要研究方向为交通管理信息系统,智能交通机电控制装备与系统,网络化制造与智能系统。

行车数量过多,用户不能及时归还自行车。合理调度公共自行车,均衡公共自行车在空间和时间上的分布对完善公共交通体系,对提升城市交通的服务水平具有重要的意义。

根据调度前信息是否完全已知,可以将车辆调度问题分为静态车辆调度问题和动态车辆调度问[1]

题。由于公共自行车的流动性,租赁点的状态是实时变化的,因此公共慢行系统的调度问题是一种动态车辆调度问题。RussellBent和PascalVanHentenr对客户地理位置和服务时间随机变化的动态车辆调度问题进行了探讨,提出了MSALC(leas-tcommitmentrefinementofmultiplescenarioap-)

proach)方法来满足由动态模型预测的新需求

[2]

。

T.VanWoense,lL.Kerbach和H.Peremans利用排队

第6期

董红召,等:公共慢行系统的动态调度建模与滚动时域调度算法研究

[3]

69

理论解决具有动态旅行时间的车辆路径问题。

李兵和郑四发等引入虚拟任务点与相关约束后,将客户需求随时间变化的动态车辆路径规划问题划分为一系列的静态车辆路径问题。JiaYongji采用滚动时域不断更新当前服务窗口的策略将动态车辆调度问题转化为静态问题进行求解

[5]

[4]

。贺竹磬和

孙林岩在不同的时间段内将运输时间服从不同的分

[6]

布规律,设计出动态交通下车辆路径选择模型。AllanLarsen将动态车辆调度问题的求解方法大致分为基于Apriori方法和实时再优化方法

)

[7]

,Apr-i

)

ori方法是基于预测的调度方法,因此对预测的精度的要求较高,而实时再优化方法具有一定的滞后性。

由于公共自行车的流动性和租赁点状态的动态性,因此,在租赁点间行驶时间已知和预测租赁点需求量的前提下,以最大化租赁点的满意度为目标建立公共慢行系统调度的动态模型,然后采用滚动时域的策略将动态的公共慢行系统调度问题转化为一系列静态的调度问题进行求解。

图1 关键点和时间轴Figure1 Thekeypointandtimeaxis

1 公共慢行系统调度模型的建立

1.1 关键点和时间轴

由于公共自行车是在各租赁点之间不断流动的,在执行调度计划期间会有新的请求,因此需要不断改变原有的调度计划,以适应租赁点状态的动态

[8]

变化。因此首先介绍关键点和时间轴的概念,如图1所示,时间轴表示一个工作日的整个调度周期,在时间轴上,每一个时刻对应一个场景,在图1中的t1时刻对应的场景为租赁点1、3、4、和6为尚未服务的对象,租赁点2是已经完成服务的对象,租赁点5为正在进行服务的对象;t2时刻对应的场景为租赁点1、4为尚未服务的对象,租赁点2、5、6是已经完成服务的对象,租赁点3为正在进行服务的对象,租赁点7为新增的有服务请求的租赁点。关键点是指正在接受服务或者有运输车辆正在前往该点的路上的租赁点,关键点的任务是不能更改的,如图1中时t1刻对应的关键点是租赁点3和5,t2时刻对应的关键点是租赁点1和3。

1.2 模糊时间窗及公共自行车租赁点的满意度时间窗是公共自行车租赁点允许服务的时间范围,用模糊时间窗来描述租赁点对服务时间的约束范围,如图2所示,[WAi,WBi]表示租赁点i可容忍的服务时间范围,[WCi,WDi]表示租赁点i期望的服务时间范围[9]

图2 模糊时间窗Figure2 TheFuzzytimewindow

当车辆到达租赁点i的时间tiI[WCi,WDi]时,租赁点i的满意度fi(ti)最大,fi(ti)=1;当tiWBi时,租赁点i的满意度fi(ti)最小,

fi(ti)=0;当tiI[WAi,WCi]G[WDi,WBi]时租赁点i的满意度fi(ti)介于0和1之间,综上所述,租赁点的满意度可以表示为:

0

fi(ti)=(ti-WAi)/(WCi-WAi)(WBi-ti)/(WBi-WDi)

1

1.3 公共慢行系统调度模型的建立

公共慢行系统调度问题可以描述为:停车场P0有k辆运输车,运输车辆最大载重量(最多装载自行车的数量)为Qk,从停车场P0派遣若干运输车辆向n个公共自行车租赁点提供服务。每一个租赁点的容量(最多容纳的自行车的数量)为Ei(i=1,2LLn),在t时刻,每个租赁点的自行车的数量为qi(t)(i=1,2LLn)。qi(t)与Ei之比为Hi(t),正常状态下租赁点i的Hi的范围是[Cmin,Cmax],租赁点的服务请求有2种情况:¹当Hi(t)>Cmax时,表示租赁点在t时刻需要运出自行车;º当Hi(t)tiWBi

WAi。 70

公路工程34卷

公共自行车租赁点需求量的确定:租赁点的需求量为租赁点需要运入或运出的自行车的数量,当Hi(t)>Cmax时,租赁点需运出自行车,设租赁点此时的需求量为di(t),当租赁点接受服务后,其Hi应该在区间[Cmin,Cmax]内,则必须满足Cmin[qi(t)-di(t)

[Cmax,即qi(t)-CmaxEi[di(t)[qi

Ei

(t)-CminEi,此时,di(t)取其下限qi(t)-CmaxEi即可满足要求;同理,当Hi(t)模型的假设条件:¹租赁点间的行驶时间是已知的;º运输车辆无行驶时间和行驶里程的限制;»可以预测10min内的各租赁点请求信息。

模型中参数的含义如下所示:

N(t):t时刻,所有未完成任务租赁点,新的有服务请求的租赁点和停车场的集合;

M(t):t时刻,所有关键点、未完成任务租赁点,新的有服务请求的租赁点和停车场的集合;K:运输车辆的集合;

TS:时间轴;

Qki:运输车辆K在租赁点i服务后装载的自行车的数量;

1 表示点i的任务有运输车辆k来

Yik=

完成;

0 其他。

以租赁点总的满意度最大化为目标建立公共慢行系统调度的模型,目标函数如下:

maxZ=

tITSiIN(t)

的租赁点至少有一辆运输车去服务。

2 算法设计

采用滚动时域调度算法对模型进行求解,首先将所有的公共自行车租赁点分为:¹当前服务窗口C即当前有服务请求的租赁点集合;º非当前服务窗口B即当前无服务需求的租赁点和已经服务过的租赁点集合。在一个工作日中工作时间设为从t0到tend,将时间轴划分为若干个子调度周期,其长度为$t,每一个子调度周期对应一个静态的公共慢行系统调度问题,通过更新每一个时间段内C中的租赁点和分别求解每一个静态的调度问题,并采用禁忌搜索算法求解静态公共慢行调度问题,达到对公共慢行系统进行动态调度的目的

[10]

(见图3)。

图3 滚动时域调度方法

Figure3 Therollinghorizonschedulingalgorithm

禁忌搜索算法是一种邻域搜索方法,通过禁忌表记录已经搜索到的局部最优解,在以后的搜索中尽量避开它们,禁忌搜索算法在搜索过程中允许接收劣解,具有较强的爬山能力,禁忌搜索算法的关键步骤的设计如下:

¹解的表示。

用多层整数序列表示解,如:0-1-5-3-8-10-00-2-4-7-9-0

表示有两辆运输车进行服务,第一辆运输车的行驶路径为从停车场0出发依次经过租赁点1、5、3、8和租赁点10,再回到停车场0;第二辆运输车的行驶路径为从停车场0出发依次经过租赁点2、4、7、9,最后再回到停车场0。

º邻域结构的设计。

采用插入法,即将一条路径上的一点插入到另一路径中来生成邻域解。

»禁忌对象和禁忌表的设计。

以插入操作的租赁点路径对为禁忌对象,用矩阵T记录被禁忌操作的租赁点路径对,T[i,j]>0表示租赁点i离开路径j的操作为禁忌操作,当TEE

fi(ti)

(1)(2)(3)

约束条件为:

QkiE

kIK

yik\\1 PiIN(t)

式(1)为目标函数,表示最大化租赁点总的满意度;式(2)为运输车辆的载重量约束条件,表示在任何时刻、任一租赁点运输车辆的载重量都不能超过其最大载重量;式(3)表示任意一个有服务请求第6期

董红召,等:公共慢行系统的动态调度建模与滚动时域调度算法研究

71

[i,j]=0表示租赁点i离开路径j的操作为非禁忌操作。

0.85。并且子调度周期的长度$t取值为5min。

根据表1和表2所示的实验数据,用滚动时域调度方法获取公共慢行系统的调度计划如表3所示,在每一个子调度周期中将新出现的有服务请求的租赁点加入到当前的调度计划中。

在以上的实验中,计算结果是共用两辆运输车进行调度,行车路线分别为/0-6-5-4-7-80和/0-2-1-3-9-100,车辆到每个公共自行车租

表1 各租赁点的自行车数量及时间窗

Table1 Thevehiclequantityandtimewindowsoftheserv-icesites

租赁点P1P2P3P4P5P6P7

租赁点容自行车的数量Ei/辆量qi(t)/辆

50455045454545504550

14555250165249202244

期望的服务时间窗08:11)08:1608:07)08:1008:18)08:1908:19)08:2308:12)08:1408:05)08:0808:25)08:2808:36)08:3808:30)08:3308:36)08:39

可容忍的服务

时间窗08:08)08:1708:05)08:1308:16)08:2408:16)08:2508:09)08:1508:04)08:0908:24)08:3008:34)08:4008:28)08:3508:32)08:40

3 实验及结果分析

以杭州市某区域内的公共慢行系统为实验对象如图4所示,在该区域中共有一个停车场P0和10个租赁点P1、P2,,P10,停车场共有2辆车,每一

辆运输车最大载重量为30辆自行车。各租赁点的状态数据如表1所示,各租赁点之间以及各租赁点和停车场之间的行驶时间如表2所示,假设所有租赁点的服务时间均为2min,Cmin=0.45、Cmax=

图4 公共自行车租赁点和停车场分布

Figure4 Thenetworkofbikesitesandparkinglot

P8

P9P10

表2 各租赁点之间以及各租赁点与停车场之间的行驶时间

Table2 Transporttimesamongtheservicesites

P0

P0P1

P2P3P4P5P6P7P8P9P10

013c33d7c22d22c43d18c29d10c18d5c12d27c10d17c25d24c10d27c18d

P113c33d05c40d6c17d30c32d25c42d12c54d14c37d13c45d09c14d18c43d

P27c22d5c40d08c22d14c50d16c11d8c40d10c15d09c45d17c35d25c43d

P322c43d6c17d8c22d016c09d16c20d14c20d13c35d09c18d6c50d08c40d

P418c29d30c32d14c50d16c09d06c55d7c16d6c11d10c09d20c08d14c34d

P510c18d25c42d16c11d16c20d6c55d04c30d9c41d16c20d21c30d19c35d

P65c12d12c54d8c40d14c20d7c16d4c30d015c28d17c24d18c39d20c30d

P727c10d14c37d10c15d13c35d6c11d9c41d15c28d07c16d15c46d19c20d

P817c25d13c45d09c45d09c18d10c09d16c20d17c24d7c16d014c38d11c34d

P924c10d09c14d17c35d6c50d20c08d21c30d18c39d15c46d14c38d05c40d

P1027c18d18c43d25c43d08c40d14c34d19c35d20c30d19c20d11c34d5c40d0

表3 滚动时域算法结果

Table3 Theresultoftherollinghorizonschedulingalgorithm

子调度周期07:55)08:0008:08:08:08:

00)

05)10)15)

08:08:08:08:

05101520

行车路线0-6

0-6,0-20-6-5,0-2-10-6-5-4,0-2-10-6-5-4,0-2-1-30-6-5-4-7,0-2-1-30-6-5-4-7,0-2-1-3-90-6-5-4-7-8,0-2-1-3-9-10

说 明

一辆运输车08:00出发去租赁点P6新增一辆运输车

新增服务租赁点新增服务租赁点新增服务租赁点

08:03出发去租赁点P2P5、P1P4P3

08:20)08:2508:25)08:3008:30)08:35

新增服务租赁点P7

新增服务租赁点P9新增服务租赁点P8、P10

赁点的时间如表4所示,其中P1、P2、P4、P6、P8、P9、

P10共7个租赁点的服务时间在期望的时间窗内,有P3、P5、P7共3个租赁点的服务时间不在期望的时间窗内但是在可容忍的服务时间窗内,实验结果可行,说明该方案能满足公共慢行系统的动态调度

的实时性要求,解决公共慢行系统的动态调度问题。

(下转第75页)第6期

朱 洁等:基于资产价值评估的公路养护绩效评价方法的研究

表1 2007~2008资产价值Table1 assetsvaluein2007~2008

75

设施名称路面桥梁总计

2007资产价值/元4105528448180662351228619079

2008实际资产价值A/元

4929675038121418101305109313

预测2008资产价值B/元

3312668008047042001135971000

A-B/元1617007037437610169138313

4 结论

通过对公路养护的绩效、公路的服务水平、公路的性能及其经济效益之间关系的分析,提出用资产价值评估的方法来评价公路养护绩效的思路,并提出了一种用成本法来计算公路资产价值的方法,用未养护与养护后的公路设施资产价值之差来反映公路养护的绩效,将这种方法应用于实际的工程当中,解决养护需求与资金投入之间的矛盾,能更好地发挥资源的效益。

[参考文献]

[1]

[3]

ment[Z].Assetmanagementprimer.U.S.departmentofTransportation,1999.

CambridgeSystematics,Inc.CambridgeSystematicaInc[Z].Synthesisofassetmanagementpractice,2002.

[4] 上海市政工程管理处.城市道路基础设施资产的评估与管理

方法研究[Z].上海:同济大学,2006.

[5] 孙立军.道路与机场设施管理[M].北京:北京交通出版社,

2009.

[6] 姚祖康.路面管理系统[M].北京:人民交通出版社,1993.[7] 符秋生,卢 毅,张起森.公路养护成本预测和养护方案.决策

方法的研究[J].中南公路工程,2004,29(1):73~75.

[8] 贺晓良.公路养护的困境及对策[J].湖南交通科技,2003,29

(3):47~48.

[9] 姚忠阳,彭益清.浅谈FIDIC管理模式在公路养护中的运用

[J].湖南交通科技,2007,33(1):75~76.

[10] 徐 峰.浅谈叶集至信阳高速公路养护管理方法与工作[J].

湖南交通科技,2008,34(1):85~87.

CambridgeSystematics,Inc.AssetManagementFramework[Z].NCHRPWebDocument41(ProjectSP20-24[11]).ContractorsFinalReport,Feb,2002.

[2] FederalHighwayAdministrationOfficeofAssetManage-

(上接第71页)

表4 车辆到达各租赁点开始服务时间

Table4 Theservicetimeofservicesites

租赁点 P1

P2 P3 P4 P5

车辆到达时间08:15:0208:07:2208:23:1908:20:3708:11:42

租赁点 P6

P7 P8 P9 P10

车辆到达时间08:05:1208:28:4808:36:0408:32:0908:37:49

hicledispatchingproblemwithpich-upsanddeliveries[J].TransportationResearchPartC14(2006)157~174.

[2] RussellBent,PascalVanHentenryck.

DynamicVehicle

RoutingwithStochasticRequest.BrownUniversity,Box1910Providence,RI02912

[3] T.VanWoense,lL.Kerbache,H.Peremans,N.Vandaele.

Vehicleroutingwithdynamictraveltimes:Aqueueingap-proach[J].EuropeanJournalofOperationalResearch186

(2008)990~1007

[4] 李 兵,郑四发,等.求解客户需求动态变化的车辆路径规划

方法[J].交通运输工程学报,2007,7(1):106~110.

4 结论

建立基于公共自行车租赁点满意度最大化的公共慢行系统调度模型,并用采用滚动时域调度算法将动态的公共慢行系统调度问题转化为一系列的静态的调度问题进行解决,并且实验结果基本可行,该方法对公共慢行系统管理部门进行公共自行车的调度具有重要的指导意义。调度计划的质量还依赖于对租赁点需求量和租赁点间行驶时间的精确预测,以及根据实际情况确定合适的子调度周期的长度,这需要更进一步的研究和探索。

[参考文献]

[1] MichelGendreau,FrancoisGuertin,JeanYvesPotvinRene

[5]JiaYongj,iGuHanyuandXiYugeng.rollinghorizon

schedulingalgorithmfordynamicvehicleschedulingsys-tem.JoumalofSoutheastUniversity[J],2005,21(6):92~

96.

[6] 贺竹磬,孙林岩.动态交通下车辆路径选择模型及算法[J].

交通工程学报,2007,7(1):111~115.[7]

AllanLarsen.TheDynamicVehicleRoutingProblem[D].Copenhagen:TheTechnicalUniversityofDenmark.,2007.

[8] 郭凤鸣,动态环境下的车辆调度问题研究[D].上海:同济大

学,2006.

[9] 张建勇,郭耀煌,李 军.基于顾客满意度的多目标模糊车辆

优化调度问题研究[J].铁道学报2003,25(2):15~17.[10] 贾永基,车辆调度问题优化算法研究[D].上海:上海交通大

学,2004.

Seguin.Neighborhoodsearchheuristicsforadynamicve-