改进蚁群算法优化周期性车辆路径问题

《改进蚁群算法优化周期性车辆路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第５期运筹与管理Ｖｏｌ．２３，Ｎｏ．５２０１４年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１４改进蚁群算法优化周期性车辆路径问题１１１１２蔡婉君，王晨宇，于滨，杨忠振，姚宝珍（１．大连海事大学交通运输管理学院，辽宁大连１１６０２６；２．大连理工大学机械工程学院，辽宁大连１１６０２４）摘要：周期性车辆路径问题（ＰＶＲＰ）是标准车辆路径问题（ＶＲＰ）的扩展，ＰＶＲＰ将配送期由单一配送期延伸到T（T＞１）期，因此，ＰＶＲＰ需要优化每个配送期的顾客组合和配送路径。由于ＰＶＲＰ是一

2、个内嵌ＶＲＰ的问题，其比标准ＶＲＰ问题更加复杂，难于求解。本文采用蚁群算法对ＰＶＲＰ进行求解，并提出采用两种改进措施———多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后，通过９个经典ＰＶＲＰ算例对该算法进行了数据实验，结果表明本文提出的改进蚁群算法求解ＰＶＲＰ问题是可行有效的，同时也表明两种改进措施可以显著提高算法的性能。关键词：周期性车辆路径问题；蚁群算法；多维信息素；扫描法中图分类号：ＴＰ１８文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０５-００７０-０８ImprovedAntColonyAlgor

3、ithmforPeriodVehicleRoutingProblem１１１１２ＣＡＩＷａｎ-ｊｕｎ，ＷＡＮＧＣｈｅｎ-ｙｕ，ＹＵＢｉｎ，ＹＡＮＧＺｈｏｎｇ-ｚｈｅｎ，ＹＡＯＢａｏ-ｚｈｅｎ（１．TransportationManagementCollege，DalianMaritimeUniversity，Dalian１１６０２６，P．R．China；２．SchoolofAutomotiveEngineering，DalianUniversityofTechnology，Dalian１１６０２４，P．R．China）Abstrac

4、t：ＰｅｒｉｏｄＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ（ＰＶＲＰ）ｉｓａｇｅｎｅｒａｌｉｚｅｄｃｌａｓｓｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ（ＶＲＰ），ｉｎｗｈｉｃｈｔｈｅｐｌａｎｎｉｎｇｐｅｒｉｏｄｉｓｅｘｔｅｎｄｅｄｔｏａｔ-ｄａｙｐｅｒｉｏｄ．Ｔｈｅｒｅｆｏｒｅ，ｃｕｓｔｏｍｇｒｏｕｐａｎｄｒｏｕｔｅｓｈｏｕｌｄｂｅｏｐｔｉｍｉｚｅｄｅｖｅｒｙｄａｙｉｎＰＶＲＰ．ＥｍｂｅｄｄｅｄｉｎＶＲＰ，ＰＶＲＰｉｓｔｏｏｃｏｍｐｌｉｃａｔｅｄｔｏｂｅｓｏｌｖｅｄ．Ａｓｍａｎｙｒｏｕｔｅｏｐｅｒａｔｉｏｎｓａｒｅｆｏｒｍｕｌ

5、ａｔｅｄｉｎａｃｅｒｔａｉｎｐｅｒｉｏｄ，ＰＶＲＰｉｓｖｅｒｙｐｏｐｕｌａｒｉｎｐｒａｃｔｉｃｅ．Ｉｎｒｅｃｅｎｔｙｅａｒｓ，ｄｉｓｔｒｉｂｕｔｉｏｎｃｅｎｔｅｒｓｈａｖｅｐａｉｄｍｕｃｈａｔｔｅｎｔｉｏｎｔｏｔｈｅｐｒｏｂｌｅｍｏｆｖｅｈｉｃｌｅｄｅｌｉｖｅｒｙｗｉｔｈｔｈｅｇｒｏｗｉｎｇｆｕｅｌｃｏｓｔａｎｄｆｉｅｒｃｅｓｕｐｐｌｙｃｈａｉｎｃｏｍｐｅｔｉｔｉｏｎ．Ｅｓｐｅｃｉａｌｌｙｉｎｓｏｍｅｓｉｔｕａｔｉｏｎｓ，ｖｅｈｉｃｌｅｓｈａｖｅｔｏｓｅｒｖｅｓｏｍｅｆｉｘｅｄｃｕｓｔｏｍｅｒｓｉｎａｇｉｖｅｎｐｅｒｉｏｄ，ａｎｄ

6、ｂｅｓｉｄｅｓ，ｔｈｅｓｅｒｖｉｃｅｔｉｍｅｓｏｆｅａｃｈｃｕｓｔｏｍｅｒａｒｅｓｅｔｔｌｅｄｉｎａｄｖａｎｃｅ．Ｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｈｅｒｅｐｅｔｉｔｉｖｅｏｐｅｒａｔｉｏｎｓｗｉｌｌｓｉｇｎｉｆｉｃａｎｔｌｙｓａｖｅｃｏｓｔ．Ｍａｎｙｒｅｓｅａｒｃｈｅｓｈａｖｅｓｈｏｗｎｔｈａｔｔｈｅｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｂａｓｅｄｏｎｔｈｅｓｉｍｕｌａｔｉｏｎｏｆｂｉｏｌｏｇｉｃａｌｉｓｖｅｒｙｓｕｉｔａｂｌｅｆｏｒｓｏｌｖｉｎｇｌａｒｇｅ-ｓｃａｌｅｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．Ａｎｔ

7、ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ｉｓｆｏｕｎｄｅｄｏｎｔｈｅｂｅｈａｖｉｏｒｏｆａｎｔｃｏｌｏｎｙｆｏｒａｇｉｎｇｉｎｎａｔｕｒｅ，ｗｈｉｃｈｈａｓｂｅｅｎｐｒｏｖｅｄｔｏｂｅｆｅａｓｉｂｉｌｉｔｙｆｏｒｓｏｌｖｉｎｇＶＲＰｐｒｏｂｌｅｍｓｉｎｌｏｔｓｏｆｒｅｓｅａｒｃｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｎｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＩＡＣＯ），ｉｎｗｈｉｃｈａｍｕｌｔｉ-ｄｉｍｅｎｓｉｏｎｐｈｅｒｏｍｏｎｅｍａｔｒｉｘａｎｄａｌｏｃａｌｏｐｔｉｍｉｚａｔｉｏｎ

8、ｓｔｒａｔｅｇｙｂａｓｅｄｏｎｓｃａｎｎｉｎｇｍｅｔｈｏｄａｒｅｉｎｔｒｏｄｕｃｅｄ．ＴｏｔｅｓｔｔｈｅｔｗｏｓｔｒａｔｅｇｉｅｓｆｏｒＩＡＣＯ，ｔｈｉｓｐａｐｅｒｄｅｓｉｇｎｓｆｏｕｒｇｒｏｕｐｓｏｆｃｏｎｔｒａｓｔｔｅｓｔｓ，ｉｎｗｈｉｃｈＡＣ