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

摘要：

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

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

所属期刊栏目：16

分类号：U492.3(交通工程与公路运输技术管理)

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

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

页数：共7页

页码：176-182