资源描述：
《多车场车辆优化调度模型及算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4卷第1期交通运输工程学报Vol.4No.12004年3月JournalofTrafficandTransportationEngineeringMar.2004文章编号:1671-1637(2004)01-0083-04多车场车辆优化调度模型及算法李臻,雷定猷(中南大学交通运输工程学院,湖南长沙410075)摘要:针对多车场满载运输问题的特征,提出了多车场车辆优化调度的数学模型,设计了求解该问题的启发式算法,应用结果表明,该算法是可行的。关键词:车辆调度;多车场;启发式算法;满载中图分类号:U491文献标识码:AMode
2、landalgorithmofmultipledepottransitvehicleschedulingLIZhen,LEIDing-you(SchoolofTrafficandTransportationEngineering,CentralSouthUniversity,Changsha410075,China)Abstract:Basedonanalyzingthecharacteristicofthemultipledepotvehiclescheduling(MDVS)problemwithfullloads,th
3、ispaperputforwardaoptimizationmodel,designedheuristicalgorithm.Applicationexampleshowsthatthisalgorithmisfeasible.4tabs,4figs,8refs.Keywords:vehicledispatch;multipledepot;heuristicalgorithm;fullloadsAuthorresume:LIZhen(1980-),male,graduatestudent,86-731-5641047,lzh
4、_csu@163.com.个广义指派问题,然后用SA算法将其分解为单车0引言场问题,最后用修正的Clarke-Wright启发式算法给车辆调度是各专业运输公司和大型企业部门的出单车场问题的所有巡回路线;文献[7]从一般运输一项日常性工作。其目的是在一系列已知的装货点问题的解出发将其连通来构造行车路线。本文针对和卸货点组成的运输网络中,选择适当的行车路线,此问题的特点构造了启发式算法。将运输任务合理分配,在满足一定的约束条件(如车1多车场车辆调度数学模型辆容量、容积限制、行驶里程限制等)下,达到一定的目标(如总路程最短、费用最
5、少、使用车辆最少等)。1.1问题描述及运输网络模型由于车辆优化调度问题属于NP难题,只有在设某运输公司一个工作日要完成的工作任务共任务数和车辆数较少的时候,才能求得精确解,因有n项,其运输量分别为g1,g2,…,gn,可将按吨此,启发式算法就成为人们研究该问题的自然选择。位计算的运输量换算为完成该项任务所需的整车次[1]数(a如Clarke和Wright提出的节约法,Gillett和1,a2,…,an)。另设公司共有M个车场用来[2]Miller提出的扫描法,Fisher和Jaikumar建立的停放空车(每天发出空车和停放空
6、车),车场和各项[35]货运业务均处于同一连通的道路网上,见图1。一般分派算法等。这些算法为求解车辆路径问题提供了有效的方法,但是多为针对单车场问题或将每一项业务用一个虚拟点———“重载点”表[6]非满载问题的,对于多车场满载情况下车辆调度的示,记为i,见图2。汽车由重载点i到重载点j[6,7]为空车行驶,空驶距离d问题却讨论甚少。文献[6]将此问题等价为一ij等于从第i个重载点的卸收稿日期:2003-05-17作者简介:李臻(1980-),男,河南荥阳人,中南大学硕士研究生,从事运输规划与管理研究.84交通运输工程学报20
7、04年nnnnmvmv-∑di(∑xij)+∑∑dijxij≤L(5)i=1j=1i=0j=0nmv∑xi0≤1(6)i=1nmv∑x0j≤1(7)j=1图1MDVS运输网络上述模型中,式(1)为目标函数,即求总空驶里Fig.1MDVStransportationnetwork程,并使其最小;式(2)保证第j个重载点到达车次数与其需求车次数相等;式(3)表明从第i个重载点发出的车次数与其需求车次数相等;式(4)表明每一重载点发、到车平衡;式(5)保证每辆车行驶路径长度不超过每天的最大容许行驶距离;式(6)保证车辆回到车场;式
8、(7)保证车辆从车场出发。图2重载点及其之间的距离Fig.2Fullloadssitesanddistancefromeachother2模型求解的图上作业法货点到第j个重载点的装货点之间的距离,一般本算法不考虑车场车辆数限制,利用贪婪算法dji≠dij的原则构造初始解,再对初始解进行优化
