距离受限车辆路径问题的近似算法

针对无向完全图上以极小化行驶路线(环游)总距离为目标函数的距离受限车辆路径问题,将最小二元2-匹配问题与环游拆分和环游整合相结合,提出了一种近似算法。该算法将松弛问题最小二元2-匹配的最优解中距离超过限制的环游进行拆分,距离未超过限制的环游进行整合,以得到距离受限车辆路径问题的环游集合。针对该近似算法,首先通过分析该问题最优解下界与近似算法的上界,证明了算法参数形式的近似比上界;然后通过对近似比上界的证明,说明最大行驶距离与顾客点规模的取值对算法参数近似比的影响较小;最后通过构造实例,进一步说明该算法在此种情况下性能更优。该算法可为城市无人物流配送高效快速算法的设计提供参考。