Journal of Systems & Management ›› 2019, Vol. 28 ›› Issue (5): 927-933.DOI: 10.3969/j.issn.1005-2542.2019.05.0015
Previous Articles Next Articles
ZHANG Huizhen, LIU Yun, NI Jing
Online:
Published:
张惠珍, 刘云, 倪静
作者简介:
基金资助:
Abstract: 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).
Key words: partheno-genetic algorithm, ant colony algorithm, multi-objective vehicle routing problem, customer satisfaction, fuzzy time windows
摘要: 为解决基于时间窗和食物新鲜度形成的综合客户满意度,且具有最大运输时间限制的带模糊时间窗的多目标车辆路径问题(MOVRPFTW),建立了相应的数学模型。针对蚁群算法容易陷入局部最优的缺陷,将单亲遗传算法和蚁群算法相结合,利用单亲遗传算法的3种遗传算子和区别于传统遗传算法的两种操作手法,构建了多种单亲遗传混合蚁群算法,并进行算例测试。结果表明:与基本蚁群算法相比,单亲遗传混合蚁群算法求出的解的各项目标的平均值更优;同时,单点单亲遗传混合蚁群算法较多点单亲遗传混合算法在求解此问题中的用时更少、计算效率更高,并且移位算子较其他两种算子具有较好的求解性能。
关键词: 单亲遗传算法, 蚁群算法, 多目标车辆路径问题, 客户满意度, 模糊时间窗
CLC Number:
U 491
ZHANG Huizhen, LIU Yun, NI Jing. A Partheno-Genetic Hybrid Ant Colony Algorithm for Solving the MOVRPFTW Based on Customer Satisfaction[J]. Journal of Systems & Management, 2019, 28(5): 927-933.
张惠珍, 刘云, 倪静. 基于客户满意度的MOVRPFTW的单亲遗传混合蚁群算法[J]. 系统管理学报, 2019, 28(5): 927-933.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: https://xtglxb.sjtu.edu.cn/EN/10.3969/j.issn.1005-2542.2019.05.0015
https://xtglxb.sjtu.edu.cn/EN/Y2019/V28/I5/927