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

摘要

This paper presents a univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows (VRPHTW). In the VRPHTW,a fleet of vehicles must deliver goods to a set of customers,time window constraints of the customers must be respected and the fact that the travel time between two points depends on the time of departure has to be taken into account. The latter assumption is particularly important in an urban context where the traffic plays a significant role. A shortcoming of univariate marginal distribution algorithm for vehicle routing problems is that,customers are not independent events in probabilistic model. Hence,we propose a novel probabilistic model that probability of the distribution of customers delivered by the same vehicle. Moreover,the new population is generated by two phase insertion heuristics method. Computational results with 56 Solomon benchmark problems confirm the benefits of other algorithms,the resulting algorithm turns out to be competitive,matching or improving the best known results.%针对带硬时间窗的车辆路径问题(VRPHTW)求解，提出了一种混合单变量边缘分布算法(hybrid UDMA，hUDMA)，改进了基本UMDA的概率模型.统计节点按路径分布的概率，使其能够在解空间上找到节点—路径的分布关系，提高了UMDA的全局搜索能力.采用两阶段插入法进行最佳节点搜索和路径分配完成UMDA采样操作，通过种群进化来获取最优解.计算Solomon 100客户的6类问题56个算例的实验结果表明：在最优解的取得方面，C类算例能够全部取得最优解，R、RC类算例能以50%左右概率取得最优解；在平均误差方面，C类算例计算结果与已知最优解一致，R、RC类算例计算误差率与已知最优解比较接近，平均误差率为1.03%.