基于先排序后聚类原则下解决CARP问题的分割算法

弧路径规划问题(CARP)是物流科学研究的热点问题之一。CARP问题可以通过转换为路径规划问题(CVRP)问题来进行求解,将CARP的弧段等效于CVRP问题的点进行处理,具体求解过程中可以使用先排序后聚类(RFCS)方法,先对所有弧段当做节点来处理进行(TSP)排序,运用分割算法将完整的TSP回路,分割为多条满足背包限制的TSP路径,形成优化方案。本研究提出了一种全新的分割算法-多标号算法,在完整TSP回路的基础上得到较优的满足背包限制的TSP路径。并通过对标准问题库中问题与几种使用较为普遍的分割算法进行对比试验,数据验证结果显示多标号算法较之于其他分割算法有更好的分割效率,并通过结合蚁群算法验证了多标号算法在RFCS方式解决CARP问题中具有较好的性能与应用前景。