求解带硬时间窗车辆路径问题的改进UMDA 算法

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

作者：柴获，何瑞春，马昌喜，代存杰

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

摘要：针对带硬时间窗的车辆路径问题(VRPHTW)求解，提出了一种混合单变量边 缘分布算法(hybrid UDMA，hUDMA)，改进了基本UMDA的概率模型.统计节点按路径分 布的概率，使其能够在解空间上找到节点—路径的分布关系，提高了UMDA的全局搜索 能力.采用两阶段插入法进行最佳节点搜索和路径分配完成UMDA采样操作，通过种群 进化来获取最优解.计算Solomon 100 客户的6 类问题56 个算例的实验结果表明：在最优 解的取得方面，C类算例能够全部取得最优解，R、RC类算例能以50%左右概率取得最优 解；在平均误差方面，C类算例计算结果与已知最优解一致，R、RC类算例计算误差率与 已知最优解比较接近，平均误差率为1.03%.

关键词：交通工程,分布估计算法,单变量边缘分布算法,带时间窗车辆路径问题,概率模型,插入法

基金资助：国家自然科学基金/National Natural Science Foundation of China(61364026,51408288)；兰州交通大学校青年基金/ Youth Foundation of Lanzhou Jiaotong University(2015026)；兰州市科技计划项目/Science and Technology Planing Project of Lanzhou(2014-1-172).