用于求解混合车辆路径问题的混合进化算法

摘要：

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的.给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次.MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小.混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法.该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛.在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的.

关键词：元启发式、车辆路径问题、禁忌搜索、混合进化算法

所属期刊栏目：45

分类号：TP183(自动化基础理论)

资助基金：国家自然科学基金项目61602196,61472147,61772219,61270183;深圳市科技计划项目JCYJ20170307154749425

在线出版日期：2018-06-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：76-82