运输路径优化蚁群算法问题研究

《运输路径优化蚁群算法问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：1003—1421(2010)09-0068—05中图分类号：0229；Ul16．2文献标识码：A运输路径优化蚁群算法问题研究Researchonantcolonyatg0dthmfortransportrouteoptimization陈钢铁，帅斌CHENGans"-tie，SHUAIBin(西南交通大学交通运输学院，四川成都6f0051)(SchoolofTrafficandTransportation，SouthwestJiaotongUniversity，Chengdu，Sichuan610

2、031，China)Abstract：First．therouteoptimizationmodelbasedonriskandtakingaccountofcostandtime—varyingconditions摘要：对于某一特定源点和目的地之间wasestablishedforthetraintraficdispatchingproblems的车辆运输调度问题，建立基于风险、考betweencertainoriginanddestination．Inthispaper，虑成本和时变条件下的路径优化模型，

3、采pheromoneupdatestrategyofantcolonyalgorithmisused，用蚁群算法的信息素更新策略，使边上残sothatthemarginresidualpheromonecouldaccurately留信息素能够正确反映时变网络中边上权reflectthechangeofthemarginvalueintime—varyingnetwork．Then，bycombiningwithGeneticalgorithms，值的变化，并结合遗传算法，采取最优个theantcolonyf

4、ormedaftereachtraversalsolutionasthe体交叉策略将蚁群每次遍历后形成的解作initialspeciesintermsofsingle—pointcrossover,inorder为初始群种进行单点交叉计算，以避免陷toavoidgettinginlocaloptimalsolutionandimprovethe入局部最优解，提高算法的收敛性。通过convergenceofthealgorithm．Thevalidityofthealgorithm算例分析验证算法的有效性。is

5、provedbytheexample．Keywords：Time-varyingNetwork；RouteOptimization；关键词：时变网络；路径优化；蚁群算法AntColonyAlgorithm一第32卷第9期运输路径优化蚁群算法问题研究陈钢铁等石雨时间窗的车辆路径问题(VehiceR。uing顶点集，ff—N；E一(g)为弧集，=。P()表ProblemwithHardTimeWindow．VRPHTW)示顶点v的前点集；s(i)表示顶点v的后点集；表是众多车辆路径问题(VechicleRouti

6、ngProblem，示完成运输的总时间上界；c表示完成运输的总费VRP)中的一种。该问题既考虑车辆容量约束，也用上界；表示在顶点v，的等待时间上界；表示考虑客户对货物送达的时间要求，并且每个客户在顶点v等待的单位时间风险；c表示在顶点v等都要求将货物在指定的时间窗内送达，既不能提待的单位时间费用；a表示在顶点v的到达时间；前，也不能延后。VRPHTW问题的求解方法分为『j，表示弧e0．的距离；w表示在顶点v的等待时间；精确算法和启发式方法。精确算法由于引入严格的c(表示t时刻进入弧P的单位运费；t，(表示t时

7、数学方法，无法避免指数爆炸问题，只能有效求刻进入弧P所需的时间；，(f)===1表示t时刻进入解小规模VRPHTW问题之]。而VRPHTw问题是强弧e，，()一0表示tN刻没有进入弧e。NP(NonlinearProgramming)难题，只能寻找近似2．2建立模型算法。因此，构造高质量的启发式算法显得尤其重选取顶点1为源点，Ⅳ为目的地，建立混合整要。目前，用于求解VRPHTWI'fi]题的启发式算法数规划：主要有遗传算法、禁忌搜索算法]。对基于风min∑∑r(×(+∑xw(1)⋯1∈E∈V险考虑成本和时变条

8、件下的问题建立模型，采用蚁群算法的信息素更新策略，使边上残留信息素能够s．t．F∑1∑∈I)(f)一1(2)正确反映时变网络中边上权值的变化，结合蚁群算∑∑，(，)一∑∑(===0法和遗传算法，将蚁群每次遍历后形成的解作为初始群种进行单点交叉计算，可以避免陷入局部最优i=1，2，⋯，JV一1(3)解，提高算法的收敛性。圭∑(f)一1(4)F1f∈，(Ⅳ)1问题描述∑∑，(≤1i=1，⋯，Ⅳ一1(5)