基于客户满意度的MOVRPFTW的单亲遗传混合蚁群算法

A Partheno-Genetic Hybrid Ant Colony Algorithm for Solving the MOVRPFTW Based on Customer Satisfaction

为解决基于时间窗和食物新鲜度形成的综合客户满意度,且具有最大运输时间限制的带模糊时间窗的多目标车辆路径问题(MOVRPFTW),建立了相应的数学模型。针对蚁群算法早熟收敛的缺陷,将单亲遗传算法和蚁群算法相结合,利用单亲遗传算法的3种遗传算子和区别于传统遗传算法的两种操作手法,构建了多种单亲遗传混合蚁群算法,并进行算例测试。结果表明:与基本蚁群算法相比,单亲遗传混合蚁群算法求出的解的各项目标的平均值更优;同时,单点单亲遗传混合蚁群算法较多点单亲遗传混合算法在求解此问题中的用时更少、计算效率更高,并且移位算子较其他两种算子具有较好的求解性能。

For solving the multi-objective vehicle routing problem with fuzzy time windows (MOVRPFTW), which involves the restriction of maximum vehicle transportation time and two types of customer satisfaction resulted by time windows and food freshness respectively, a novel model is formulated.Besides,several partheno-genetic hybrid ant colony algorithms are proposed for solving the MOVRPFTW by combining the partheno-genetic algorithm and the ant colony algorithm, in which three genetic operators and two operating measures different from the classical genetic algorithm are separately adapted to overcome the premature convergence of the basic ant colony algorithm. In addition, these proposed algorithms are tested in the same numerical experiment. The results show that the average objective values obtained by using the partheno-genetic hybrid ant colony algorithm are better than those obtained by using the basic ant colony algorithm. The monogenepartheno-genetic hybrid ant colony algorithm has a better effectiveness and efficiency than the polygenic partheno-genetic hybrid ant colony algorithm, and genetic shift operator has a better computational performance than the other two genetic operators (genetic transposition operator and genetic inverse operator).