In order to solve the waste collection vehicle routing problem with intermediate facilities rn(WCVRP-IF) and reduce the route length and overlaps between two different vehicle routes, a rnclustering-based multiple ant colony system ( CMACS) algorithm was proposed. This CMACS algorithm rnpossesses a set of new strategies to construct solutions, including clustering-based strategy, improved rnglobal pheromone update rule and cross operator. Tests on two standard instances were conducted,rntheir deviations being 0 and 2. 13％ from the best known solution, respectively. In addition, a rncomparison between calculated results based on different ant colony algorithms was made. The research rnresults show that the length and compactness of the optimal route calculated by the proposed algorithm rnwith a clustering-based strategy is 4. 90％ shorter and 83. 33％ smaller respectively than those of the rnoptimal route calculated by the traditional ant colony system algorithm. The contribution degree of rndifferent strategies is successively the clustering-based strategy, the global pheromone update rule and rnthe cross operator.%为减少城市垃圾的收运成本和各车辆路径之间的重叠区域,设计了一种具有聚类策略、改进全局信息素更新规则和交叉算子的多重蚁群算法.用该算法求解2个标准算例,一个达到目前已知的最优解,另一个偏离度为2.13%.此外,还对含有不同规则的蚁群算法进行了比较.结果表明:与不带聚类策略的蚁群算法相比,该算法求解的路径最佳,其长度缩短4.90%,紧凑度降低83.33%;不同转移更新规则的贡献程度从大到小依次是:带块可见度的聚类策略、全局信息素更新规则和交叉算子.
展开▼
