系统管理学报

系统管理学报 ›› 2019, Vol. 28 ›› Issue (5): 927-933.DOI: 10.3969/j.issn.1005-2542.2019.05.0015

• 运筹与工业工程 • 上一篇    下一篇

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

张惠珍, 刘云, 倪静   

  1. 上海理工大学管理学院，上海200093
  • 出版日期:2019-09-28 发布日期:2019-11-02
  • 作者简介:张惠珍(1979-)，女，博士，副教授。研究方向为运筹学、智能优化。
  • 基金资助:
    国家自然科学基金资助项目(71401106)；教育部人文社会科学基金资助项目(16YJA630037)

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

ZHANG Huizhen, LIU Yun, NI Jing   

  1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2019-09-28 Published:2019-11-02

PDF

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

关键词: 单亲遗传算法, 蚁群算法, 多目标车辆路径问题, 客户满意度, 模糊时间窗

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

中图分类号: