求解双目标带时间窗车辆路径问题的蚁群算法

来源：交通运输系统工程与信息杂志2018年第4期北京时间：

作者：柴获，何瑞春，苏江省，宋宇博，代存杰，马昌喜

单位：兰州交通大学 a. 机电技术研究所；b. 交通运输学院，兰州 730070

摘要：针对运输网络为多重图的双目标带时间窗车辆路径问题设计了蚁群算法.首先，建立了多重图的双目标带时间窗车辆路径问题的数学模型，提出了针对该问题解的搜索空间构建方法，定义了一种综合考虑各优化目标、时间窗和信息素等启发信息的状态转移概率公式. 为了对比说明该算法的有效性，同时设计基于NSGA-II的多目标遗传算法.针对本文算例，对蚁群算法中的各参数进行了敏感性分析，根据分析结果设定算法参数，获得了算例的Pareto最优路径集，同时与NSGA-II算法及相关文献算法针对运行时间、收敛性和群体多样性进行比较.结果显示，本文设计的蚁群算法在这3个指标上均明显优于NSGA-II算法；在相同蚂蚁数量情况下，本文的算法在收敛性和群体多样性方面优于相关文献算法.

关键词：交通工程,带时间窗的车辆路径问题,多目标优化,蚁群算法,NSGA-II,状态转移概率,多重图

基金资助：国家自然科学基金/National Natural Science Foundation of China (61364026)；兰州交通大学校青年基金/ Youth Foundation of Lanzhou Jiaotong University (2015026)；兰州交通大学优秀科研平台(团队)资助计划/Excellent Platform of Lanzhou Jiaotong University(201604).