基于时空聚类的带时间窗车辆路径规划算法-论文.pdf

《基于时空聚类的带时间窗车辆路径规划算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第3期计算机科学Vo1．41No．32014年3月ComputerScienceMar2014基于时空聚类的带时间窗车辆路径规划算法戚铭尧。张金金任丽(清华大学深圳研究生院物流与交通学部深圳518055)(深圳市物流工程与仿真重点实验室深圳518055)摘要针对带时间窗车辆路径问题，设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式，然后利用遗传算法对顾客点进行时空聚类，并将聚类结果应用于路径调整中，使得顾客尽可能被加入到时空距离近的顾客所在路径中，这样既能

2、有效减小搜索范围，又能更快到达更好的解。以含1000个点的标准问题集作为算例，计算结果表明，与不采用时空聚类的方法相比，该算法能在更短的时间内取得更好的解，显示了在解决大规模车辆路径问题时具有很好的潜力。关键词车辆路径问题，时间窗，时空距离，聚类分析，遗传算法，可变邻域搜索中图法分类号022，TP31文献标识码AVehicleRoutingAlgorithmBasedOnSpatiotemporalClusteringQIMing-yao’ZHANGJin-jinRENLi(DivisionofTranspo

3、rtationandLogistics，GraduateSchoolatShenzhen，TsinghuaUniversity，Shenzhen518055，China)(KeyLabofLogisticsEngineeringandSimulation，Shenzhen518055，China)AbstractArouteimprovementmethodthatconsidersspatialandtemporalfeaturessimultaneouslywasproposedtosolvevehicl

4、eroutingproblemwithtimewindows．Aspatiotemporalrepresentationofvehiclerouteswaspresentedtomeasurethespatiotemporaldistancebetweentwocustomers．Then，ageneticalgorithmwasdesignedtoclustertheCUS—tomersintoafewgroupsaccordingtospatiotemporaldistances．Theresulting

5、customergroupswerethenusedforrouteadjustment：ifacustomerwasmovedtoanotherroute，onlythenearbyroutesweresearchedandconsidered．Bythismeansthesearchspaceisdramaticallyreduced．Thecalculationon1000一customerexamplesdesignedbyGehringandHombergershowsthattheproposed

6、algorithmcangetbettersolutioninshortertime．KeywordsVehicleroutingproblem，Timewindows，Spatiotemporaldistance，Clusteringanalysis，Geneticalgorithm，Variablendghborhoodsearch启发式算法(Meta-heuristies)E。精确算法是求解VRP问题1引言的基础性算法，能得到精确最优解，但计算量大，仅适合求解车辆路径问题(VehicleRoutingP

7、roblem，VRP)的提出可几十到一百个顾客点的小规模问题。经典启发式算法运算时以追溯到1959年，该问题是典型的组合优化问题，半个世纪间短，能得到较好的结果，目前国内市场上常用的物流配送规以来受到了广泛的研究[1]。经典车辆路径问题的定义为，有划软件大多采用该算法，其缺点是结果易陷人局部最优解，精一组车辆为若干个顾客提供运输服务，车辆从场站出发，最终度不高。元启发式算法又称现代智能优化算法，它是经典启返回该场站，车辆的装载量有限，顾客的需求量已知，且一个发式算法的改进。二者的区别在于，元启发式算法包含随机

8、顾客只能被服务一次，求通过所有顾客的最短运输路_1]。近搜索的技巧，在算法运行过程中允许出现解的退化甚至不可年来，更多的研究考虑了各种新特征的VRP问题，如带时间行解。已有较多的学者验证元启发式算法能在一定时间内求窗的VRP(VRPwithTimeWindows，VRFrrW)、动态VRP、得相对优的解。关于ⅥTw的启发式及元启发式算法的随机VRP、同时考虑取货和送货的VRP等等。虽然VRP的综述，