蚁群算法及其在有硬时间窗的车辆路径问题中的应用.pdf

维普资讯 第 12卷第4期 计算机集成制造系统 Vo1．12No．4 2006年 4月 ComputerIntegratedManufacturingSystems Apr．2006 文章编号 ：1006—5911(2006)04--0596一O7 蚁群算法及其在有硬时间窗的 车辆路径问题中的应用 刘志硕 ，柴跃廷 ，申金升 (1．清华大学 自动化系，北京 100084；2．北京交通大学 交通运输学院，北京 100044) 摘 要：为求解有硬时间窗的车辆路径问题，提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法。 在第一阶段，用蚂蚁的局部遍历代替传统的全局遍历，每个蚂蚁采用蚁群算法进行局部遍历，构造一个回路，蚂蚁 转移采用回路两阶段构路策略；在第二阶段，由前一阶段所构造的回路通过采用近似解可行化策略来组合形成可 行解 此外，为提高算法的寻优能力，在转移规则中引入了基于时间窗的紧迫性 因子和匹配度因子，并与节约算法 和爬山法有机结合。实验结果表明，自适应混和蚁群算法性能优 良，能够有效地求解有硬时间窗的车辆路径问题。 关键词：有硬时间窗的车辆路径问题 ；自适应混合蚁群算法；可行解两阶段构造策略；回路两阶段构造策略；紧 迫性因子；匹配度因子 中图分类号：TP1 文献标识码 ：A Antcolonyalgorithm forvehicleroutingproblem with hardtimewindow LIUZhi--shuo，CHAIYue—ting ．SHEN Jin sheng。 (1．Dep．ofAutomation，TsinghuaUniv．，Beijing 100084，China； 2．Sch．ofTraffic＆ Transportation，BeijingJiaotongUniv．，Beijing 100044，China) Abstract：AnAdaptiveHybridAntColonyAlgorithm (AHACA)basedonthetwo—phaseconstructionprocedureof feasiblesolutionWaSestablishedtosolvetheVehicleRoutingProblem withHardTimeW indow (VRPHTW)． ThereweretwophasesintheconstructionoffeasiblesolutionsofVRPHTW ．Inthefirstphase。antcolonyalgo— rithm wasappliedtoconstructthesesub toursandthetwo— phasesub— tourconstructionprocedurewasusedin itsstatetransitionrule．Inthesecondphase，thesub— tourswerecomposedoffeasiblesolutionsbymeansofthe feasibilityprocessofapproximatesolutionwhichcould increasethenumberofoptimalfeasiblesolutionsinlarger scale．Moreover，toincreasetheabilityofoptimizationandavoid