车辆调度问题的分派启发式算法

《车辆调度问题的分派启发式算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1999年1月系统工程理论与实践第1期　a车辆调度问题的分派启发式算法李　军(西南交通大学经济管理学院,四川成都610031)摘要　对有时间窗的车辆调度问题进行了分析,提出了以分派为基础的启发式算法.算法中讨论了如何完成任务所需要的车辆数,定义了两种分派费用,设计了在分派过程中安排线路的方法,并用实例进行了验证.最后对算法的适用性及进一步应用进行了讨论.关键词　车辆调度　时间窗　根顾客　分派GeneralizedAssignmentHeuristicsforVehicleSchedulingLiJun(SouthwestJiaotongUniversity,Ch

2、engdu610031)AbstractInthispaper,basedontheanalysisforcharacteristicsofvehicleschedulingproblemswithtimewindows,anassignmentheuristicsispresented.Inthealgorithmthenumberofvehiclesaccomplishingtasksisestimatedandtwokindsofassignmentcostaredefined.Anexampleisemployedtoshowtheeffectivene

3、ssofthealgorithm.Finally,theadaptabilityandfurtherapplicationofthismethodarediscussed.Keywordsvehiclescheduling;timewindows;rootcustomer;assignment1　问题的提出车辆从一车场出发去完成一些货运任务,当各任务量较小(小于车辆容量)时,为了提高车辆的利用率,可安排一辆车执行几项运输任务,这时,如何安排车辆的路线,使得既满足各任务的需求,能够完成任务,而又使总路程最短,这就是一个需要解决的问题.设车场为D,所有车辆容量为q,

4、现有n项货物运输任务1,⋯,n,任务i的货运量为gi

5、ki=0　否则.1　车辆k从点i行驶到点j;xijk=0　否则.a本文于1997年7月9日收到国家自然科学基金资助项目(编号79700019)©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.28系统工程理论与实践1999年1月则可得到调度数学模型P.模型中,(7)式为支路消去约束,能够避免出现与车场分离的线路;(9)式表示一条线路上两邻接任务存在的条件;(10)式为任务的时间窗约束.minz=666dijxijk(1)ijk6giyki≤qPk(2)i6yki=1i=1,⋯,n(3)k

6、yki=0或1i=D,1,⋯,n;Pk(4)6xijk=ykjj=D,1,⋯,n;Pk(5)i6xijk=ykii=D,1,⋯,n;Pk(6)j66xijkFûSû-1SA{1,⋯,n},2FûSûFn-1(7)i,j∈S×Sxijk=0或1i,j=D,1,⋯,n;Pk(8)xijk=1]ei+tijFsji,j=1,⋯,n;Pk(9)aiFsiFbii=1,⋯,n(10)3　算法311　模型分解问题P属NP难题,尚无精确解法,因此将模型分解成一个分派问题P1和一个有时间窗的旅行商问题P2.P1:minz=6f(zk)k6giykiFqPki6yki=1i=1,

7、⋯,nkyki=0或1i=D,1,⋯,n;Pk其中zk是满足yki=1的顾客的集合,即车辆k所能服务的顾客的集合,而f(zk)是在zk中顾客的最优旅行商线路的长度.f(zk)可由问题P2确定:P2minf(zk)=666dijxijkijk6xijk=ykjj=D,1,⋯,n;Pki6xijk=ykii=D,1,⋯,n;Pkj66xijkFûSû-1SA{1,⋯,n},2FûSûFn-1i,j∈S×Sxijk=0或1i,j=D,1,⋯,n;Pkxijk=1]ei+tijFsji,j=1,⋯,n;PkaiFsiFbii=1,⋯,nf(zk)相当复杂,只有对特定的问

8、题才能够写出来.在此,采